Fast High-Dimensional Data Search in Incomplete Databases

Summary: Introduces BR-tree and MOSAIC indexes for high-dimensional retrieval when query/data attributes are missing, avoiding exhaustive search. BR-trees reduce update/storage costs and usually speed range queries, while MOSAIC wins point queries and some incomplete, dimension-unrestricted ranges. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8693
Venue: VLDB
Year: 1998
Pagerank: 5.093636e-05
Overall Rank: 12,940 | 11.22%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Beng Chin Ooi (National University of Singapore)
2. Cheng Hian Goh (National University of Singapore)
3. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{ooi_vldb98,
        title = {{Fast High-Dimensional Data Search in Incomplete Databases}},
        author = {Ooi, Beng Chin and Goh, Cheng Hian and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '98},
        pages = {357},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,911	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB	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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00016029789
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,590	Extensible Buffer Management of Indexes	1992	VLDB	8.3696843e-05
7,979	Information Retrieval from an Incomplete Data Cube	1996	VLDB	5.5148266e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,612	Index Intersection for High-Dimensional Range Queries	2026	VLDB
2	9,365	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR
3	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
4	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
5	14,483	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD
6	6,491	Two-dimensional Substring Indexing	2001	PODS
7	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
8	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
9	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
10	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB