A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays

Summary: Proposes A*-tree, a unified storage-and-inference structure for uncertain multidimensional arrays that exploits local correlations to improve modeling and queries. Treats data as a Bayesian network, encodes the joint distribution in the A*-tree, and evaluates query efficiency against alternative graphical models. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10332
Venue: VLDB
Year: 2010
Pagerank: 5.1955087e-05
Overall Rank: 9,936 | 31.84%
DOI: 10.14778/1920841.1920963

Incoming Non-self Citations Over Time

Authors

1. Tingjian Ge (University of Kentucky)
2. Stan Zdonik (Brown University)

BibTeX Citation

@article{ge_vldb10,
        title = {{A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays}},
        author = {Ge, Tingjian and Zdonik, Stan},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {964--975},
        doi = {10.14778/1920841.1920963},
        url = {https://doi.org/10.14778/1920841.1920963},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
408	MauveDB: Supporting Model-based User Views in Database Systems	2006	SIGMOD	0.00019008806
724	The Multidimensional Database System RasDaMan	1998	SIGMOD	0.00014620119
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
2,451	One Size Fits All? – Part 2: Benchmarking Results	2007	CIDR	8.560157e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
2	9,580	Storing Matrices on Disk: Theory and Practice Revisited	2011	VLDB
3	680	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB
4	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
5	820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB
6	1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB
7	8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD
8	5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD
9	12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD
10	1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB