Efficient Search of Multidimensional B-Trees

Summary: Extends concatenated B-Trees for efficient multidimensional retrieval under partial, range, list, and general disjunctive predicates. Selectively accesses small table subsets, reducing scans and the need for secondary indexes, storage, maintenance, and random I/O. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8513
Venue: VLDB
Year: 1995
Pagerank: 5.8751993e-05
Overall Rank: 6,451 | 55.75%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Harry Leslie (Tandem Computers)
2. Rohit Jain (Tandem Computers)
3. Dave Birdsall (Tandem Computers)
4. Hedieh Yaghmai (Tandem Computers)

BibTeX Citation

@article{leslie_vldb95,
        title = {{Efficient Search of Multidimensional B-Trees}},
        author = {Leslie, Harry and Jain, Rohit and Birdsall, Dave and Yaghmai, Hedieh},
        journal = {PVLDB},
        series = {{VLDB} '95},
        pages = {710--721},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,861	Factorizing Complex Predicates in Queries to Exploit Indexes	2003	SIGMOD	6.0636778e-05
9,426	Efficient Bulk Deletes for Multi Dimensional Clustered Tables in DB2	2007	VLDB	5.2710946e-05
12,486	Visualizing the robustness of query execution	2009	CIDR	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
2,082	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD	9.201869e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,940	Fast High-Dimensional Data Search in Incomplete Databases	1998	VLDB
2	1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR
3	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
4	14,479	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD
5	253	A Class of Data Structures for Associative Searching	1984	PODS
6	7,342	Efficient Search in Very Large Databases	1988	VLDB
7	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
8	9,518	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
9	8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD
10	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD