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: 4949
Venue: SIGMOD
Year: 2015
Pagerank: 4.1905499e-05
Overall Rank: 11,912 | 17.22%
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.00051785122
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
1,448	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011928845
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
4,907	Probabilistic String Similarity Joins	2010	SIGMOD	5.8365853e-05
5,763	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.3358283e-05
5,937	Indexing Uncertain Data	2009	PODS	5.2606762e-05
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
7,657	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.6821809e-05
7,844	Set Similarity Join on Probabilistic Data	2010	VLDB	4.6330652e-05
8,146	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5724134e-05
9,433	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	4.3399748e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,766	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010611043
7,300	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7640746e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
5,086	Pivot-based Metric Indexing	2017	VLDB	5.7036022e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
7,657	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.6821809e-05
12,386	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1905499e-05
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667