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: h42f85bf0e4e90abb
Venue: VLDB
Year: 1998
Pagerank: 4.9793485e-05
Overall Rank: 13,230 | 11.05%
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
13,201	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
279	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022308048
597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00015766567
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,560	Extensible Buffer Management of Indexes	1992	VLDB	8.2993451e-05
8,142	Information Retrieval from an Incomplete Data Cube	1996	VLDB	5.3913918e-05

Semantically Similar Papers

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