Indexing uncertain data

ABSTRACT

Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this paper we study answering range queries over uncertain data. Specifically, we are given a collection P of n points in R, each represented by its one-dimensional probability density function (pdf). The goal is to build an index on P such that given a query interval I and a probability threshold τ, we can quickly report all points of P that lie in I with probability at least τ. We present various indexing schemes with linear or near-linear space and logarithmic query time. Our schemes support pdf's that are either histograms or more complex ones such as Gaussian or piecewise algebraic. They also extend to the external memory model in which the goal is to minimize the number of disk accesses when querying the index.

REFERENCES

• 1: Peyman Afshani , Timothy M. Chan, Optimal halfspace range reporting in three dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.180-186, January 04-06, 2009, New York, New York
• 2: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paulo G. Franciosa , Jeffrey Scott Vitter, Efficient searching with linear constraints, Journal of Computer and System Sciences, v.61 n.2, p.194-216, Oct. 2000 [doi>10.1006/jcss.2000.1709]
• 3: P.K. Agarwal and J. Erickson, Geometric range searching and its relatives, in: Advances in Discrete and Computational Geometry (B. Chazelle, J.E. Goodman, and R. Pollack, eds.), American Mathematical Society, Providence, RI, 1999, pp. 1--56.
• 4: P.K. Agarwal and J. Matoušek, Dynamic half-space range reporting and its applications, Algorithmica, 13 (1995), 325--345.
• 5: P.K. Agarwal and M. Sharir, Davenport-Schinzel sequences and their geometric applications, in: Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), Elsevier Science Publishers, Amsterdam, 2000, pp. 1--47.
• 6: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 7: Parag Agrawal , Omar Benjelloun , Anish Das Sarma , Chris Hayworth , Shubha Nabar , Tomoe Sugihara , Jennifer Widom, Trio: a system for data, uncertainty, and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: Boris Aronov , Sariel Har-Peled , Micha Sharir, On approximate halfspace range counting and relative epsilon-approximations, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247128]
• 9: J.L. Bentley and J.B. Saxe, Decomposable searching problems I: Static-to-dynamic transformation, Journal of Algorithms, 1 (1980), 301--358.
• 10: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions, SIAM Journal on Computing, v.30 n.2, p.561-575, 2000 [doi>10.1137/S0097539798349188]
• 11: B. Chazelle and L.J. Guibas, Fractional cascading: I. A data structuring technique, Algorithmica, 1 (1986), 133--162.
• 12: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 13: Bernard Chazelle , Burton Rosenberg, Simplex range reporting on a pointer machine, Computational Geometry: Theory and Applications, v.5 n.5, p.237-247, Jan. 1996 [doi>10.1016/0925-7721(95)00002-X]
• 14: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 15: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 16: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 17: H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, American Journal of Mathematics, 87 (1965), 684--689.
• 18: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 19: V. Ljosa and A.K. Singh, APLA: Indexing arbitrary probability distributions, Proc. IEEE International Conference on Data Engineering, 2007, pp. 946--955.
• 20: Gabriel Nivasch, Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1-10, January 04-06, 2009, New York, New York
• 21: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 22: S. Singh, C. Mayfield, S. Prabhakar, R. Shah, and S. Hambrusch, Indexing uncertain categorical data, Proc. IEEE International Conference on Data Engineering, 2007, pp. 616--625.
• 23: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: Yufei Tao , Xiaokui Xiao , Reynold Cheng, Range search on multidimensional uncertain data, ACM Transactions on Database Systems (TODS), v.32 n.3, p.15-es, August 2007 [doi>10.1145/1272743.1272745]
• 25: Man Lung Yiu , Nikos Mamoulis , Xiangyuan Dai , Yufei Tao , Michail Vaitis, Efficient Evaluation of Probabilistic Advanced Spatial Queries on Existentially Uncertain Data, IEEE Transactions on Knowledge and Data Engineering, v.21 n.1, p.108-122, January 2009 [doi>10.1109/TKDE.2008.135]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Theory

Keywords:
indexing, range query, uncertain data