article

Free access

Concurrency in linear hashing

Editor: Robert W. Taylor Author:

Carla Schlatter EllisAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 12, Issue 2

Pages 195 - 217

https://doi.org/10.1145/22952.22954

Published: 01 June 1987 Publication History

PDF eReader

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 hash files. The solution is based on locking protocols and minor modifications in the data structures.

References

[1]

BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9 (1977), 1-21.

Digital Library

Google Scholar

[2]

ELLIS, C. Concurrent search and insertion in 2-3 trees. Acta Inf. 14 (1980), 63-86.

Digital Library

Google Scholar

[3]

ELLIS, C. Concurrent search and insertion in AVL trees. IEEE Trans. Comput. C-29, 9 (Sept. 1980), 811-817.

Digital Library

Google Scholar

[4]

ELLIS, C. Extendible hashing for concurrent operations and distributed data. In Proceedings of the 2nd ACM SIGACT-SIGMOD Symposium on Principles o{ Database Systems (Atlanta, Ga., Mar. 21-23). ACM, New York, 1983, pp. 106-116.

Digital Library

Google Scholar

[5]

ELLIS, C. Concurrency and linear hashing, in Proceedings of the 4th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Portland, Ore., Mar. 25-27). ACM, New York, 1985, 1-7.

Digital Library

Google Scholar

[6]

ELLIS, C. Distributed data structures: A case study. IEEE Trans. Comput. C-34, 12 (Dec. 1985), pp. 1178-1185.

Crossref

Google Scholar

[7]

FAGIN, R., NIEVERGELT, J., PIPPENGER, N., AND STRONG, H.R. Extendible hashing-a fast access method for dynamic files. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 315-355.

Digital Library

Google Scholar

[8]

KUNG, H. T., AND LEHMAN, P.L. Concurrent manipulation of binary search trees. ACM Trans. Database Syst. 5, 3 (Sept. 1980) 354-382.

Digital Library

Google Scholar

[9]

KWONG, Y. S., AND WOOD, D. New method for concurrency in B-trees. IEEE Trans. Softw. Eng. SE-8, 3 (May 1982) 211-222.

Digital Library

Google Scholar

[10]

LARSON, P. Dynamic hashing. BIT 17 (1978), 184-201.

Crossref

Google Scholar

[11]

LEHMAN, P., AND YAO, S. B. Efficient locking for concurrent operations on B-trees. ACM Trans. Database Syst. 6,4 (Dec. 1981), 650-670.

Digital Library

Google Scholar

[12]

LITWIN, W. Linear hashing: A new tool for file and table addressing. In Proceedings o~ the 6th Conference on Very Large Data Bases (Montreal, 1980), 212-223.

Google Scholar

[13]

LOMET, D. Bounded index exponential hashing. ACM Trans. Database Syst. 8, 1 (Mar. 1983), 136-165.

Digital Library

Google Scholar

[14]

MANBER, U., AND LADNER, R.E. Concurrency control in a dynamic search structure.) ACM Trans. Database Syst. 9, 3 (Sept. 1984), 439-455.

Digital Library

Google Scholar

[15]

MILLER, R., AND SNYDER, L. Multiple access to B-trees. In Proceedings o~ Con/erence on Information Sciences & Systems (Baltimore, Md., Mar. 1978), (preliminary report).

Google Scholar

[16]

SAOIV, Y. Concurrent operations on B-trees with overtaking. In Proceedings of the 4th ACM SIGACT-SIGMOD Symposium on Principles o/ Database Systems (Portland, Ore., Mar. 25-27). ACM, New York, 1985, 28--37.

Digital Library

Google Scholar

[17]

SHASHA, D., AND GOODMAN, N. Concurrent search structure algorithms. To appear in ACM Trans. Database S yst.

Digital Library

Google Scholar

[18]

Wu, C. T., AND BURKHARD, W.A. Concurrency in linear and interpolation hashing. Unpublished manuscript. Northwestern University, Evanston, Ill., (1983).

Google Scholar

Cited By

View all

Narayanan VDetweiler DHuang TBurtsev AFedorova ANarayanan DDi Luna GQuerzoni L(2023)DRAMHiT: A Hash Table Architected for the Speed of DRAMProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587457(817-834)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3587457
(2021)BibliographyThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00033-1(533-540)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00033-1
Herlihy MShavit NLuchangco VSpear M(2021)Concurrent hashing and natural parallelismThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00023-9(305-334)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00023-9
Show More Cited By

Index Terms

Concurrency in linear hashing

Recommendations

Performance comparison of extendible hashing and linear hashing techniques

Based on seven assumptions, the following comparison factors are used to compare the performance of linear hashing with extendible hashing: 1. storage utilization; 2. average unsuccessful search cost; 3. average successful search cost; 4. split cost; 5. ...
Performance comparison of extendible hashing and linear hashing techniques
SIGSMALL '90: Proceedings of the 1990 ACM SIGSMALL/PC symposium on Small systems

Based on seven assumptions, the following comparison factors are used to compare the performance of linear hashing with extendible hashing: 1. storage utilization; 2. average unsuccessful search cost; 3. average successful search cost; 4. split cost; 5. ...
Concurrency control in multidatabase systems

Reviews

Reviewer: Sally L. Harris

This research paper discusses a solution to the problem of managing a database that will experience a significant change in the amount of data being stored. This solution is based on locking protocols, thereby allowing maximum concurrent access. This is a continuation of the author's preliminary work in linear hashing, which is vaguely explained as “one of the techniques recently proposed to allow adjustment in the range of the hashing function” with changing amounts of data. Other than the author's own works, there is only one published reference on linear hashing in the bibliography. The paper is well organized, but the bulk of it is of interest mainly to other researchers, especially the elite few already familiar with linear hashing. The author spends a good deal of time on correctness but none on the traditional database algorithm issues of insertion, deletion, read access times, or space consumed. The paper would have been more effective if the author had begun with some brief explanation of the many forms of hashing and why her proposed solution surpasses them. Several pages of algorithms and examples improve the paper's understandability.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 12, Issue 2

June 1987

185 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/22952

Editor:
Robert W. Taylor

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1987

Published in TODS Volume 12, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
959
Total Downloads

Downloads (Last 12 months)162
Downloads (Last 6 weeks)13

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Narayanan VDetweiler DHuang TBurtsev AFedorova ANarayanan DDi Luna GQuerzoni L(2023)DRAMHiT: A Hash Table Architected for the Speed of DRAMProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587457(817-834)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3587457
(2021)BibliographyThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00033-1(533-540)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00033-1
Herlihy MShavit NLuchangco VSpear M(2021)Concurrent hashing and natural parallelismThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00023-9(305-334)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00023-9
Shun J(2017)ReferencesShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018804Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018804
Shun J(2017)Conclusion and Future WorkShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018803Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018803
Shun J(2017)Parallel Wavelet Tree ConstructionShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018802Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018802
Shun J(2017)Parallel Lempel-Ziv FactorizationShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018801Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018801
Shun J(2017)Parallel Computation of Longest Common PrefixesShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018800Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018800
Shun J(2017)Parallel Cartesian Tree and Suffix Tree ConstructionShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018799Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018799
Shun J(2017)Parallel and Cache-Oblivious Triangle ComputationsShared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787.3018798Online publication date: 9-Jun-2017
https://dl.acm.org/doi/10.1145/3018787.3018798
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Performance comparison of extendible hashing and linear hashing techniques

Performance comparison of extendible hashing and linear hashing techniques

Concurrency control in multidatabase systems

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations