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: 8300
Venue: VLDB
Year: 1995
Pagerank: 0.00031093647
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.00051785122
392	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024546229
415	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00023774838
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
956	Serializable Snapshot Isolation in PostgreSQL	2012	VLDB	0.00015068342
986	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00014825631
1,028	Accelerating XPath Location Steps	2002	SIGMOD	0.00014578947
1,060	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014359912
1,089	Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices	2009	VLDB	0.00014140761
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,808	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010476269
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
2,153	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	9.418541e-05
2,220	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	9.2614686e-05
2,492	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.649434e-05
2,519	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6048934e-05
2,606	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	8.4621503e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
3,415	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB	7.1162894e-05
3,575	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9509846e-05
3,902	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6454492e-05
3,979	Making Updates Disk-I/O Friendly Using SSDs	2013	VLDB	6.5641036e-05
4,174	Ganos: A Multidimensional, Dynamic, and Scene-Oriented Cloud-Native Spatial Database Engine	2022	VLDB	6.3775863e-05
4,492	TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data	2022	SIGMOD	6.1374891e-05
4,817	Extensible Optimization in Overlay Dissemination Trees	2006	SIGMOD	5.8961372e-05
5,010	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7545425e-05
5,395	High-Performance Extensible Indexing	1999	VLDB	5.530641e-05
5,582	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.4211286e-05
6,055	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.2297716e-05
6,172	javax.XXL: A Prototype for a Library of Query Processing Algorithms	2000	SIGMOD	5.1692113e-05
6,241	Helios: Hyperscale Indexing for the Cloud & Edge	2020	VLDB	5.1357476e-05
6,440	From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems	2019	SIGMOD	5.0546781e-05
7,083	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	4.8331444e-05
7,230	Anarchy in the Database: A Survey and Evaluation of Database Management System Extensibility	2025	VLDB	4.789692e-05
7,521	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7135369e-05
7,648	amdb: An Access Method Debugging Tool	1998	SIGMOD	4.6842082e-05
7,653	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	4.6831774e-05
8,086	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	4.5858883e-05
8,217	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	4.5519066e-05
8,408	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	4.5159669e-05
8,470	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.4993203e-05
9,114	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	4.3887024e-05
9,902	Towards Systematic Index Dynamization	2024	VLDB	4.2539423e-05
11,558	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1905499e-05
12,014	YZStack: Provisioning Customizable Solution for Big Data	2014	VLDB	4.1905499e-05
12,099	QuEval: Beyond high-dimensional indexing a la carte	2013	VLDB	4.1905499e-05
12,233	Load-Balanced Query Dissemination in Privacy-Aware Online Communities	2010	SIGMOD	4.1905499e-05
12,420	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1905499e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
292	Shoring Up Persistent Applications	1994	SIGMOD	0.00028735468
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
1,476	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00011752931
3,042	High-Concurrency Locking in R-Trees	1995	VLDB	7.6669657e-05
3,111	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.5445257e-05
5,464	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.4920667e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,653	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	4.6831774e-05
6,467	Indexing Multiple Sets	1994	VLDB	5.0452906e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
8,471	Adaptive Index Structures	2002	VLDB	4.4986491e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
8,086	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	4.5858883e-05
2,174	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3762595e-05
5,395	High-Performance Extensible Indexing	1999	VLDB	5.530641e-05
2,519	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6048934e-05