UPI: A Primary Index for Uncertain Databases

Summary: UPI is a primary index for uncertain databases, clustering by uncertain attributes and duplicating tuples per possible value. It adds a Cutoff Index to cap low-probability data and uses buffered, batched updates with cost models, delivering up to 100x faster uncertain queries than baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10302
Venue: VLDB
Year: 2010
Pagerank: 5.6004812e-05
Overall Rank: 7,553 | 48.19%
DOI: 10.14778/1920841.1920922

Incoming Non-self Citations Over Time

Authors

1. Hideaki Kimura (Brown University)
2. Samuel Madden (Massachusetts Institute of Technology)
3. Stanley B. Zdonik (Brown University)

BibTeX Citation

@article{kimura_vldb10,
        title = {{UPI: A Primary Index for Uncertain Databases}},
        author = {Kimura, Hideaki and Madden, Samuel and Zdonik, Stanley B.},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {630--641},
        doi = {10.14778/1920841.1920922},
        url = {https://doi.org/10.14778/1920841.1920922},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,585	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	5.4075213e-05
12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	5.093636e-05
12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.7808696e-05
3,417	DBLP — Some Lessons Learned	2009	VLDB	7.4294642e-05
5,764	Indexing Uncertain Data	2009	PODS	6.0955299e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
2	1,551	Updatable Learned Index with Precise Positions	2021	VLDB
3	2,806	Are Updatable Learned Indexes Ready?	2022	VLDB
4	4,988	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD
5	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
6	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
7	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
8	12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD
9	1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB
10	12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD