ACM SIGMOD Anthology TODS dblp.uni-trier.de

Concurrency in Linear Hashing.

Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
@article{DBLP:journals/tods/Ellis87,
  author    = {Carla Schlatter Ellis},
  title     = {Concurrency in Linear Hashing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {2},
  year      = {1987},
  pages     = {195-217},
  ee        = {http://doi.acm.org/10.1145/22952.22954, db/journals/tods/Ellis87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Concurrent access to complex shared data structures, particularly structures useful as database indices, has long been of interest in the database community. In dynamic databases, tree structures such as B-trees have been used as indices because of their ability to handle growth; whereas hashing has been used for fast access in relatively static databases. Recently, a number of techniques for dynamic hashing have appeared. They address the major deficiency of traditional hashing when applied to databases that experience significant change in the amount of data being stored. This paper presents a solution that allows concurrency in one of these dynamic hashing data structures, namely linear hashfiles. The solution is based on locking protocols and minor modifications in the data structures.

Copyright © 1987 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

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Version

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

References

[1]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[2]
Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX
[3]
Carla Schlatter Ellis: Concurrent Search and Insertion in AVL Trees. IEEE Trans. Computers 29(9): 811-817(1980) BibTeX
[4]
Carla Schlatter Ellis: Extendible Hashing for Concurrent Operations and Distributed Data. PODS 1983: 106-116 BibTeX
[5]
Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7 BibTeX
[6]
Carla Schlatter Ellis: Distributed Data Structures: A Case Study. ICDCS 1985: 201-208 BibTeX
[7]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
[8]
H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
[9]
Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX
[10]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[11]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[12]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[13]
David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX
[14]
Udi Manber, Richard E. Ladner: Concurrency Control In a Dynamic Search Structure. ACM Trans. Database Syst. 9(3): 439-455(1984) BibTeX
[15]
...
[16]
Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX
[17]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
[18]
...

Referenced by

  1. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336
  2. C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
  3. Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682
  4. Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285
  5. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  6. Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:01 2008