Concurrency and Recovery in Generalized Search Trees

Summary: Generalized concurrency control and recovery algorithms for GiST, applicable to diverse tree indexes. Link-based protocol avoids node locks during I/Os; repeatable read via predicate locks and 2PL; shows why B-tree techniques fail for general trees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2997
Venue: SIGMOD
Year: 1997
Pagerank: 8.9111106e-05
Overall Rank: 2,227 | 84.73%
DOI: 10.1145/253260.253272

Incoming Non-self Citations Over Time

Authors

1. Marcel Kornacker (University of California Berkeley)
2. C. Mohan (IBM)
3. Joseph M. Hellerstein (University of California Berkeley)

BibTeX Citation

@inproceedings{kornacker_sigmod97,
        title = {{Concurrency and Recovery in Generalized Search Trees}},
        author = {Kornacker, Marcel and Mohan, C. and Hellerstein, Joseph M.},
        series = {{SIGMOD} '97},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/253260.253272},
        url = {https://dl.acm.org/doi/10.1145/253260.253272},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
807	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.00013884448
1,616	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010213691
1,874	Storage Management in AsterixDB	2014	VLDB	9.5750002e-05
1,942	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	9.4451535e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
5,173	High-Performance Extensible Indexing	1999	VLDB	6.3341007e-05
5,978	From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems	2019	SIGMOD	6.0212877e-05
6,045	Helios: Hyperscale Indexing for the Cloud & Edge	2020	VLDB	5.9957544e-05
6,488	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.865078e-05
7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.6111155e-05
7,681	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	5.5683442e-05
7,768	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	5.5475685e-05
7,970	Locking Protocols for Materialized Aggregate Join Views	2003	VLDB	5.516316e-05
8,988	Towards Systematic Index Dynamization	2024	VLDB	5.3384135e-05
9,357	Repeating History Beyond ARIES	1999	VLDB	5.2827941e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
214	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024680756
464	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00018055592
958	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012956148
1,501	Key Range Locking Strategies for Improved Concurrency	1993	VLDB	0.00010559899
1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00010073735
3,057	High-Concurrency Locking in R-Trees	1995	VLDB	7.807389e-05
3,114	Access Method Concurrency with Recovery	1992	SIGMOD	7.7405805e-05
5,119	Commit LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems	1990	VLDB	6.3577506e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,292	Concurrency Control In A Dynamic Search Structure	1982	PODS
2	3,057	High-Concurrency Locking in R-Trees	1995	VLDB
3	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
4	7,026	Operation Specific Locking In B-Trees	1987	PODS
5	4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
6	1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
7	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
8	3,114	Access Method Concurrency with Recovery	1992	SIGMOD
9	202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB
10	7,681	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD