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: 5010
Venue: SIGMOD
Year: 2015
Pagerank: 5.093636e-05
Overall Rank: 12,103 | 16.97%
DOI: 10.1145/2723372.2723728

Incoming Non-self Citations Over Time

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

Authors

1. Lu Chen (Zhejiang University)
2. Yunjun Gao (Zhejiang University)
3. Xinhan Li (Zhejiang University)
4. Christian S. Jensen (Aalborg University)
5. Gang Chen (Zhejiang University)
6. Baihua Zheng (Singapore Management University)

BibTeX Citation

@inproceedings{chen_sigmod15,
        title = {{Indexing Metric Uncertain Data for Range Queries}},
        author = {Chen, Lu and Gao, Yunjun and Li, Xinhan and Jensen, Christian S. and Chen, Gang and Zheng, Baihua},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723728},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723728},
        year = {2015}
}

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
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00016029789
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,254	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.0001147266
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	7.1780127e-05
4,743	Probabilistic String Similarity Joins	2010	SIGMOD	6.5268783e-05
5,244	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	6.3018164e-05
5,764	Indexing Uncertain Data	2009	PODS	6.0955299e-05
6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8389373e-05
7,553	UPI: A Primary Index for Uncertain Databases	2010	VLDB	5.6004812e-05
7,839	Set Similarity Join on Probabilistic Data	2010	VLDB	5.5340666e-05
8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB	5.484341e-05
9,581	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
2	7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB
3	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
4	4,627	Pivot-based Metric Indexing	2017	VLDB
5	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
6	592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
7	7,553	UPI: A Primary Index for Uncertain Databases	2010	VLDB
8	12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
9	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
10	1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB