Concurrent Search Structure Algorithms.

@article{DBLP:journals/tods/ShashaG88,
  author    = {Dennis Shasha and
               Nathan Goodman},
  title     = {Concurrent Search Structure Algorithms},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {1},
  year      = {1988},
  pages     = {53-90},
  ee        = {http://doi.acm.org/10.1145/42201.42204, db/journals/tods/ShashaG88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[2]

James E. Allchin, Martin S. McKendry: Synchronization and Recovery of Actions. PODC 1983: 31-44 BibTeX

[3]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Concurrency Control Theory for Nested Transactions. PODC 1983: 45-62 BibTeX

[4]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX

[5]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX

[6]

Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 BibTeX

[7]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX

[8]

...

[9]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[10]

Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX

[11]

Carla Schlatter Ellis: Extendible Hashing for Concurrent Operations and Distributed Data. PODS 1983: 106-116 BibTeX

[12]

Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7 BibTeX

[13]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[14]

Ray Ford, Jim Calhoun: Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms. PODS 1984: 51-60 BibTeX

[15]

Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX

[16]

James R. Goodman, Carlo H. Séquin: Hypertree: A Multiprocessor Interconnection Topology. IEEE Trans. Computers 30(12): 923-933(1981) BibTeX

[17]

Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19 BibTeX

[18]

Allan Gottlieb, Ralph Grishman, Clyde P. Kruskal, Kevin P. McAuliffe, Larry Rudolph, Marc Snir: The NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer. IEEE Trans. Computers 32(2): 175-189(1983) BibTeX

[19]

Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 BibTeX

[20]

...

[21]

H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX

[22]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19: 1-11(1983) BibTeX

[23]

Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) BibTeX

[24]

Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX

[25]

Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 BibTeX

[26]

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX

[27]

Barbara Liskov, Robert Scheifler: Guardians and Actions: Linguistic Support for Robust, Distributed Programs. POPL 1982: 7-19 BibTeX

[28]

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX

[29]

Udi Manber, Richard E. Ladner: Concurrency Control in a Dynamic Search Structure. PODS 1982: 268-282 BibTeX

[30]

...

[31]

Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 BibTeX

[32]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[33]

...

[34]

Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX

[35]

Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX

[36]

Gunter Schlageter: Process Synchronization in Database Systems. ACM Trans. Database Syst. 3(3): 248-271(1978) BibTeX

[37]

...

[38]

...

[39]

Dennis Shasha: What Good are Concurrent Search Structure Algorithms for databases Anyway? IEEE Database Eng. Bull. 8(2): 84-90(1985) BibTeX

[40]

Alexander Tuzhilin, Paul G. Spirakis: A Semantic Approach to Correctness of Concurrent Transaction Executions. PODS 1985: 85-95 BibTeX

[41]

William E. Weihl: Data-dependent Concurrency Control and Recovery (Extended Abstract). PODC 1983: 63-75 BibTeX

[42]

...

[43]

Gerhard Weikum: A Theoretical Foundation of Multi-Level Concurrency Control. PODS 1986: 31-43 BibTeX

Referenced by

1. Seppo Sippu, Eljas Soisalon-Soininen: A Theory of Transactions on Recoverable Search Trees. ICDT 2001: 83-98
2. Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim: A Restructuring Method for the Concurrent B⁺-Tree Based on Semantic Consistency. DASFAA 1999: 229-236
3. David B. Lomet, Betty Salzberg: Concurrency and Recovery for Index Trees. VLDB J. 6(3): 224-240(1997)
4. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997)
5. Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis W. Leinbaugh, Abraham Silberschatz, S. Sudarshan: Logical and Physical Versioning in Main Memory Databases. VLDB 1997: 86-95
6. Markos Zaharioudakis, Michael J. Carey: Highly Concurrent Cache Consistency for Indices in Client-Server Database Systems. SIGMOD Conference 1997: 50-61
7. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
8. Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen: Concurrency Control in B-Trees with Batch Updates. IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
9. Daniel Barbará, Sharad Mehrotra, Padmavathi Vallabhaneni: The Gold Text Indexing Engine. ICDE 1996: 172-179
10. Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan: Index Concurrency Control in Firm Real-Time Database Systems. VLDB 1995: 146-157
11. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561
12. Gerhard Weikum, Christof Hasse: Multi-Level Transaction Management for Complex Objects: Implementation, Performance, Parallelism. VLDB J. 2(4): 407-453(1993)
13. Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
14. David B. Lomet, Betty Salzberg: Exploiting A History Database for Backup. VLDB 1993: 380-390
15. Theodore Johnson, Padmashree Krishna: Lazy Updates for Distributed Search Structure. SIGMOD Conference 1993: 337-346
16. Peter Muth, Thomas C. Rakow, Gerhard Weikum, Peter Brössler, Christof Hasse: Semantic Concurrency Control in Object-Oriented Database Systems. ICDE 1993: 233-242
17. C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
18. John K. Lee: B-Tree Concurrency Control Algorithm for Nested Transaction Systems. DASFAA 1993: 205-215
19. C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992)
20. C. Mohan, Frank Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
21. David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
22. John Turek, Dennis Shasha, Sundeep Prakash: Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking. PODS 1992: 212-222
23. Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. ICDE 1992: 184-191
24. Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991)
25. Christof Hasse, Gerhard Weikum: A Performance Evaluation of Multi-Level Transaction Management. VLDB 1991: 55-66
26. Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990)
27. C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
28. Gerhard Weikum, Christof Hasse, Peter Brössler, Peter Muth: Multi-Level Recovery. PODS 1990: 109-123
29. Thomas C. Rakow, Junzhong Gu, Erich J. Neuhold: Serializability in Object-Oriented Database Systems. ICDE 1990: 112-120
30. George P. Copeland, Michael J. Franklin, Gerhard Weikum: Uniform Object Management. EDBT 1990: 253-268
31. Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285
32. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)