The Most Likely Object to be Seen Through a Window
作者： Paz Carmi , Farah Chanchary , Anil Maheshwari , Michiel Smid
DOI: 10.1142/S0218195919500092
关键词:
摘要: We study data structures to answer window queries using stochastic input sequences. The first problem is the most likely maximal point in a query window: Let α1,αc be constants, with 0 < α1 α2 αc 1. P = P1 P2 Pc set of n points d, for some fixed d. For i 1, 2,c, each Pi associated probability αi existence. A p (x1,xd) on layer if there no other q (x1′,x d′) such that x1′ x 1,x2′ 2, and xd′ Consider random subset obtained by including, independently αi. interval [i,j], ≤ j, we report Pi,j (pi,pj) has highest O(1) time O(nlog n) space. solve special as follows. sequence d given (d ≥ 2), where (0, 1] existence it. Given [i,j] an integer t pt O(logdn) O(nlogdn) second consider common element problem. {1, 2,n} universe. S1,S1,Sm subsets 1,m 1,n, added Sp αpi (independently choices). τ real number indices p, q, 1 m j n, decide whether exists k Pr(k nr=pqS r) O(mn) space these elements O(log + w) time, w size output.
sci-hub.st 参考文章(31)
Charu C Aggarwal, Managing and Mining Sensor Data Springer US. ,(2013) , 10.1007/978-1-4614-6309-2
Rita de Caluwe, Fuzzy And Uncertain Object-Oriented Databases: Concepts And Models ,(1997)
Subhash Suri, Kevin Verbeek, Hakan Yıldız, On the Most Likely Convex Hull of Uncertain Points european symposium on algorithms. pp. 791- 802 ,(2013) , 10.1007/978-3-642-40450-4_67
Michalis Vazirgiannis, Maria Halkidi, Dimitrious Gunopulos, None, Uncertainty handling and quality assessment in data mining ,(2003)
Allan Jørgensen, Maarten Löffler, Jeff M. Phillips, Geometric Computations on Indecisive and Uncertain Points arXiv: Computational Geometry. ,(2012)
William E. Devanny, Lowell Trott, Joseph A. Simons, Michael J. Bannister, Michael T. Goodrich, Windows into Geometric Events: Data Structures for Time-Windowed Querying of Temporal Point Sets arXiv: Data Structures and Algorithms. ,(2014)
Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips, Approximate) Uncertain Skylines Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 52, pp. 342- 366 ,(2013) , 10.1007/S00224-012-9382-7
Amirali Abdullah, Samira Daruki, Jeff M. Phillips, Range counting coresets for uncertain data symposium on computational geometry. pp. 223- 232 ,(2013) , 10.1145/2462356.2462388
Pegah Kamousi, Timothy M. Chan, Subhash Suri, Stochastic minimum spanning trees in euclidean spaces symposium on computational geometry. pp. 65- 74 ,(2011) , 10.1145/1998196.1998206
Maarten Löffler, Jack Snoeyink, Delaunay triangulation of imprecise points in linear time after preprocessing Computational Geometry. ,vol. 43, pp. 234- 242 ,(2010) , 10.1016/J.COMGEO.2008.12.007