Indexing uncertain data
Authors:
Open Access
- 29 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 137-146
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 ℝ, 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 t , we can quickly report all points of P that lie in I with probability at least t . 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. Copyright 2009 ACMKeywords
This publication has 15 references indexed in Scilit:
- Range search on multidimensional uncertain dataACM Transactions on Database Systems, 2007
- Efficient Searching with Linear ConstraintsJournal of Computer and System Sciences, 2000
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three DimensionsSIAM Journal on Computing, 2000
- Geometric range searching and its relatives1999
- Simplex range reporting on a pointer machineComputational Geometry, 1996
- The input/output complexity of sorting and related problemsCommunications of the ACM, 1988
- Fractional cascading: I. A data structuring techniqueAlgorithmica, 1986
- Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemesCombinatorica, 1986
- The power of geometric dualityBIT Numerical Mathematics, 1985
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980