Generalized Search Trees for Database Systems (Extended Abstract)

Summary: Presents GiST, a generalized index framework for new data types, unifying B+-trees, R-trees, and RD-tree (for set-valued attributes) in a single code base. Demonstrates adapters to emulate B+-tree, R-tree, and RD-tree for set-valued attributes, with preliminary performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8299
Venue: VLDB
Year: 1995
Pagerank: 0.00031110894
Overall Rank: 242 | 98.32%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
417	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00023794574
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
957	Serializable Snapshot Isolation in PostgreSQL	2012	VLDB	0.00015048214
986	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00014838568
1,027	Accelerating XPath Location Steps	2002	SIGMOD	0.0001458865
1,061	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014368716
1,091	Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices	2009	VLDB	0.00014142229
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,157	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	9.416022e-05
2,216	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	9.2699038e-05
2,502	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.6438339e-05
2,516	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6106981e-05
2,606	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	8.4645832e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,415	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB	7.1219721e-05
3,571	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9580858e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
3,980	Making Updates Disk-I/O Friendly Using SSDs	2013	VLDB	6.5664429e-05
4,176	Ganos: A Multidimensional, Dynamic, and Scene-Oriented Cloud-Native Spatial Database Engine	2022	VLDB	6.3837225e-05
4,501	TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data	2022	SIGMOD	6.137686e-05
4,815	Extensible Optimization in Overlay Dissemination Trees	2006	SIGMOD	5.9018361e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05
5,390	High-Performance Extensible Indexing	1999	VLDB	5.5346145e-05
5,576	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.426344e-05
6,051	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.2347385e-05
6,163	javax.XXL: A Prototype for a Library of Query Processing Algorithms	2000	SIGMOD	5.1741845e-05
6,242	Helios: Hyperscale Indexing for the Cloud & Edge	2020	VLDB	5.1408379e-05
6,456	From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems	2019	SIGMOD	5.0564619e-05
7,101	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	4.8322751e-05
7,232	Anarchy in the Database: A Survey and Evaluation of Database Management System Extensibility	2025	VLDB	4.7942933e-05
7,522	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7180617e-05
7,650	amdb: An Access Method Debugging Tool	1998	SIGMOD	4.6882482e-05
7,651	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	4.6876337e-05
8,084	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	4.5902866e-05
8,223	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	4.5553657e-05
8,414	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	4.5203005e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
9,116	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	4.3928853e-05
9,903	Towards Systematic Index Dynamization	2024	VLDB	4.258022e-05
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
12,006	YZStack: Provisioning Customizable Solution for Big Data	2014	VLDB	4.1945683e-05
12,091	QuEval: Beyond high-dimensional indexing a la carte	2013	VLDB	4.1945683e-05
12,225	Load-Balanced Query Dissemination in Privacy-Aware Online Communities	2010	SIGMOD	4.1945683e-05
12,411	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
139	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042299329
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028919734
292	Shoring Up Persistent Applications	1994	SIGMOD	0.00028741386
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
1,479	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00011749057
3,039	High-Concurrency Locking in R-Trees	1995	VLDB	7.6708607e-05
3,107	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.550885e-05
5,458	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.496829e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,651	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	4.6876337e-05
6,474	Indexing Multiple Sets	1994	VLDB	5.0500524e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
5,328	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5665496e-05
8,084	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	4.5902866e-05
2,168	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3848723e-05
5,390	High-Performance Extensible Indexing	1999	VLDB	5.5346145e-05
2,516	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6106981e-05