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: h545c90046b1e136d
Venue: VLDB
Year: 2010
Pagerank: 5.4748399e-05
Overall Rank: 7,702 | 48.22%
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,747	Probabilistic Management of OCR Data using an RDBMS	2012	VLDB	5.2865969e-05
12,396	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.9793485e-05
12,397	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.9793485e-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
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010396565
2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0366183e-05
2,329	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.6292256e-05
3,488	DBLP — Some Lessons Learned	2009	VLDB	7.2629454e-05
5,882	Indexing Uncertain Data	2009	PODS	5.9588542e-05

Semantically Similar Papers

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