Indexing Metric Uncertain Data for Range Queries

Summary: Introduces object-level and bi-level models for metric uncertain data and two indexes—UPB-tree and UPB-forest—for probabilistic range queries over diverse uncertainty types. Uses pivot-based pruning with probability bounds on a B+-tree backbone, achieving lower construction cost, smaller storage, and faster queries with easy DBMS integration. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4948
Venue: SIGMOD
Year: 2015
Pagerank: 4.1945683e-05
Overall Rank: 11,904 | 17.19%
DOI: 10.1145/2723372.2723728

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,450	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011925844
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
4,901	Probabilistic String Similarity Joins	2010	SIGMOD	5.8411648e-05
5,758	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.339397e-05
5,935	Indexing Uncertain Data	2009	PODS	5.2657009e-05
6,946	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.8909775e-05
7,659	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.686672e-05
7,847	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6365272e-05
8,143	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5768015e-05
9,427	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	4.3441378e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
7,365	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7517889e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
4,985	Pivot-based Metric Indexing	2017	VLDB	5.7856648e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
7,659	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.686672e-05
12,378	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1945683e-05
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856