Title | ||
---|---|---|
Indexing multi-dimensional uncertain data with arbitrary probability density functions |
Abstract | ||
---|---|---|
In an "uncertain database", an object o is associated with a multi-dimensional probability density function(pdf), which describes the likelihood that o appears at each position in the data space. A fundamental operation is the "probabilistic range search" which, given a value pq and a rectangular area rq, retrieves the objects that appear in rq with probabilities at least pq. In this paper, we propose the U-tree, an access method designed to optimize both the I/O and CPU time of range retrieval on multi-dimensional imprecise data. The new structure is fully dynamic (i.e., objects can be incrementally inserted/deleted in any order), and does not place any constraints on the data pdfs. We verify the query and update efficiency of U-trees with extensive experiments. |
Year | Venue | Keywords |
---|---|---|
2005 | VLDB | multi-dimensional probability density function,value pq,indexing multi-dimensional uncertain data,range retrieval,object o,multi-dimensional imprecise data,rectangular area rq,cpu time,data space,arbitrary probability density function,data pdfs,probabilistic range search,probability,probability density function,indexation,access method,optimization |
Field | DocType | ISBN |
Data mining,Data space,Multi dimensional,Access method,Computer science,CPU time,Search engine indexing,Uncertain data,Theoretical computer science,Probabilistic logic,Probability density function,Database | Conference | 1-59593-154-6 |
Citations | PageRank | References |
132 | 4.23 | 15 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yufei Tao | 1 | 7231 | 316.71 |
Reynold Cheng | 2 | 3069 | 154.13 |
Xiaokui Xiao | 3 | 3266 | 142.32 |
Wang Kay Ngai | 4 | 213 | 7.43 |
Ben Kao | 5 | 2358 | 194.98 |
Sunil Prabhakar | 6 | 2664 | 152.75 |