Digital Symposium Collection 2000

Efficient Concurrency Control in Multidimensional Access Methods Kaushik Chakrabarti and Sharad Mehrotra   View Paper (PDF)   Return to Spatial Databases Abstract The importance of multidimensional index structures to numerous emerging database applications is well established. However, before these index structures can be supported as access methods (AMs) in a “commercial-strength” database management system (DBMS), efficient techniques to provide transactional access to data via the index structure must be developed. Concurrent accesses to data via index structures introduce the problem of protecting ranges specified in the retrieval from phantom insertions and deletions (the phantom problem). This paper presents a dynamic granular locking approach to phantom protection in Generalized Search Trees (GiSTs), an index structure supporting an extensible set of queries and data types. The granular locking technique offers a high degree of concurrency and has a low lock overhead. Our experiments show that the granular locking technique (1) scales well under various system loads and (2) similar to the B-tree case, provides a significantly more efficient implementation compared to predicate locking for multidimensional AMs as well. Since a wide variety of multidimensional index structures can be implemented using GiST, the developed algorithms provide a general solution to concurrency control in multidimensional AMs. To the best of our knowledge, this paper provides the first such solution based on granular locking. References Note: References link to DBLP on the Web. [1] Rakesh Agrawal , Michael J. Carey , Miron Livny : Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985 : 108-121 [2] ... [3] Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel : A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997 : 78-86 [4] Kaushik Chakrabarti , Sharad Mehrotra : Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998 : 446-454 [5] ... [6] Kaushik Chakrabarti , Sharad Mehrotra : The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. ICDE 1999 : 440-447 [7] Christos Faloutsos , Ron Barber , Myron Flickner , Jim Hafner , Wayne Niblack , Dragutin Petkovic , William Equitz : Efficient and Effective Querying by Image Content. JIIS 3(3/4) : 231-262(1994) [8] Jim Gray , Andreas Reuter : Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2 Contents [9] Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer : Generalized Search Trees for Database Systems. VLDB 1995 : 562-573 [10] Marcel Kornacker , C. Mohan , Joseph M. Hellerstein : Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997 : 62-72 [11] David B. Lomet : Key Range Locking Strategies for Improved Concurrency. VLDB 1993 : 655-664 [12] Jim Melton , Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3 Contents [13] C. Mohan : ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990 : 392-405 [14] C. Mohan , Donald J. Haderle , Bruce G. Lindsay , Hamid Pirahesh , Peter Schwarz : ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. TODS 17(1) : 94-162(1992) [15] ... [16] Jack A. Orenstein , T. H. Merrett : A Class of Data Structures for Associative Searching. PODS 1984 : 181-190 [17] Philip A. Bernstein , Vassos Hadzilacos , Nathan Goodman : Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5 Contents [18] Christos H. Papadimitriou : The Theory of Database Concurrency Control. Computer Science Press 1986, ISBN 0-88175-027-1 [19] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 [20] Michael Stonebraker , James Frew , Kenn Gardels , Jeff Meredith : The Sequoia 2000 Benchmark. SIGMOD Conference 1993 : 2-11 [21] Michael Stonebraker , Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2 BIBTEX @inproceedings{DBLP:conf/sigmod/ChakrabartiM99,   author    = {Kaushik Chakrabarti and                 Sharad Mehrotra},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Efficient Concurrency Control in Multidimensional Access Methods},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {25-36},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM