Dynamic hashing schemes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic hashing schemes

Full text

Pdf (2.52 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 20 , Issue 2 (June 1988) table of contents

Pages: 850 - 113

Year of Publication: 1988

ISSN:0360-0300

Authors

R. J. Enbody	Michigan State Univ., East Lansing
H. C. Du	Michigan State Univ., East Lansing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 151, Citation Count: 33

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/46157.330532 What is a DOI?

ABSTRACT

A new type of dynamic file access called dynamic hashing has recently emerged. It promises the flexibility of handling dynamic files while preserving the fast access times expected from hashing. Such a fast, dynamic file access scheme is needed to support modern database systems. This paper surveys dynamic file access scheme is needed to support modern database systems. This paper surveys dynamic hashing schemes and examines their critical design issues.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	CARTER, J. L., AND WEGMAN, M. N. 1979. Universal classes of hash functions. J. Comput. Syst. Sci. 28, 2 (Apr.), 143-154.
	2	Douglas Comer , Ravi Sethi, The Complexity of Trie Index Construction, Journal of the ACM (JACM), v.24 n.3, p.428-440, July 1977 [doi>10.1145/322017.322023]
	3	Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
	4	FLAJOLET, P. 1983. On the performance evaluation of extendable hashing and trie searching. Acta hf. 20,345-369.
	5	LARSON, P.-A. 1978. Dynamic hashing. BIT 18, 184-201.
	6	LARSON, P.-A. 1980. Linear hashing with partial expansions. In Proceedings of the 6th Conference on Very Large Databases (Montreal). Very Large Database Foundation, Saratoga, Calif.
	7	Per-Åke Larson, Performance analysis of linear hashing with partial expansions, ACM Transactions on Database Systems (TODS), v.7 n.4, p.566-587, Dec. 1982 [doi>10.1145/319758.319763]
	8	Per-Åke Larson, Linear hashing with overflow-handling by linear probing, ACM Transactions on Database Systems (TODS), v.10 n.1, p.75-89, March 1985 [doi>10.1145/3148.3324]
	9	LITWIN, W. 1980. Linear hashing: A new tool for file and table addressing. In Proceedings of the 6th Conference on Very Large Databases (Montreal). Very Large Database Foundation, Saratoga, Calif., pp. 212-223.
	10	David B. Lomet, Bounded index exponential hashing, ACM Transactions on Database Systems (TODS), v.8 n.1, p.136-165, March 1983 [doi>10.1145/319830.319837]
	11	V. Y. Lum , P. S. T. Yuen , M. Dodd, Key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.14 n.4, p.228-239, April 1971 [doi>10.1145/362575.362578]
	12	G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
	13	MENDELSON, H. 1982. Analysis of extendible hashing. IEEE Trans. Softw. Eng. SE-B, 6 (Nov.), 611-619.
	14	MULLIN, J. K. 1981. Tightly controlled linear hashing without separate overflow storage. BIT 21, 390-400.
	15	James K. Mullin, Unified Dynamic Hashing, Proceedings of the 10th International Conference on Very Large Data Bases, p.473-480, August 27-31, 1984
	16	MULLIN, J. K. 1985. Spiral storage: Efficient dynamic hashing with constant performance. Comput. J. 28,3,330-334.
	17	Ekow J. Otoo, Linearizing the Directory Growth in Order Preserving Extendible Hashing, Proceedings of the Fourth International Conference on Data Engineering, p.580-588, February 01-05, 1988
	18	M. V. Ramakrishna , P.-:1V Larson, File organization using composite perfect hashing, ACM Transactions on Database Systems (TODS), v.14 n.2, p.231-263, June 1989 [doi>10.1145/63500.63521]
	19	RAMAMOHANARAO, K., AND LLOYD, J. W. 1982. Dynamic hashing schemes. Comput. J. 25, 4, 478-485.
	20	K Ramamohanarao , R Sacks-Davis, Recursive linear hashing, ACM Transactions on Database Systems (TODS), v.9 n.3, p.369-391, Sept. 1984 [doi>10.1145/1270.1285]
	21	Michel Scholl, New file organization based on dynamic hashing, ACM Transactions on Database Systems (TODS), v.6 n.1, p.194-211, March 1981 [doi>10.1145/319540.319564]
	22	Dennis Severance , Ricardo Duhne, A practitioner's guide to addressing algorithms, Communications of the ACM, v.19 n.6, p.314-326, June 1976 [doi>10.1145/360238.360242]
	23	Eugene Veklerov, Analysis of dynamic hashing with deferred splitting, ACM Transactions on Database Systems (TODS), v.10 n.1, p.90-96, March 1985 [doi>10.1145/3148.318987]
	24	Jeffrey Scott Vitter, Implementations for coalesced hashing, Communications of the ACM, v.25 n.12, p.911-926, Dec 1982 [doi>10.1145/358728.358745]

CITED BY 33

	Edward A. Fox , Lenwood S. Heath , Qi Fan Chen , Amjad M. Daoud, Practical minimal perfect hash functions for large databases, Communications of the ACM, v.35 n.1, p.105-121, Jan. 1992
	Ye-In Chang , Chien-I. Lee , Wann-Bay ChangLiaw, Linear Spiral Hashing for Expansible Files, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.969-984, November 1999
	Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Using space-time grid for efficient management of moving objects, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.59-65, May 2001, Santa Barbara, California, United States
	Jukka Teuhola, Effective clustering of objects stored by linear hashing, Proceedings of the fourth international conference on Information and knowledge management, p.274-280, November 29-December 02, 1995, Baltimore, Maryland, United States
	E. A. Fox , Q. F. Chen , A. M. Daoud , L. S. Heath, Order preserving minimal perfect hash functions and information retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-311, September 05-07, 1990, Brussels, Belgium
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	Witold Litwin , Marie-Anne Neimat , Donovan A. Schneider, LH: Linear Hashing for distributed files, ACM SIGMOD Record, v.22 n.2, p.327-336, June 1, 1993
	Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Distributed file organization with scalable cost/performance, ACM SIGMOD Record, v.23 n.2, p.253-264, June 1994
	Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991
	K. -C. Guh , C. Yu, Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments, IEEE Transactions on Knowledge and Data Engineering, v.4 n.4, p.371-381, August 1992
	Ye-In Chang , Chien-I Lee, Alternating Hashing for Expansible Files, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.179-185, January 1997
	Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996
	Ricardo A. Baeza-Yates , Héctor Soza-Pollman, Analysis of linear hashing revisited, Nordic Journal of Computing, v.5 n.1, p.70-85, Spring 1998
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	George Kollios , Vassilis J. Tsotras, Hashing Methods for Temporal Data, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.902-919, July 2002
	E. A. Fox , Q.-F. Chen , L. Heath , S. Datta, A more cost effective algorithm for finding perfect hash functions, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.114-122, February 21-23, 1989, Louisville, Kentucky
	Ravi Prakash , Zygmunt Haas , Mukesh Singhal, Load-balanced location management for cellular mobile systems using quorums and dynamic hashing, Wireless Networks, v.7 n.5, p.497-512, September 2001
	Witold A. Litwin , Nick Roussopoulos , Gerald Levy , Wang Hong, Trie Hashing with Controlled Load, IEEE Transactions on Software Engineering, v.17 n.7, p.678-691, July 1991
	R. W. P. Luk, Time-Space Trade-Off Analysis of Morphic Trie Images, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1028-1032, November 2001
	Jun-ichi Aoe , Katsushi Morimoto , Masami Shishibori , Ki-Hong Park, A Trie Compaction Algorithm for a Large Set of Keys, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.476-491, June 1996
	D. H. C. Du , S. -R. Tong, Multilevel Extendible Hashing: A File Structure for Very Large Databases, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.357-370, September 1991
	Qingbo Zhu , Windsor W. Hsu, Fossilized index: the linchpin of trustworthy non-alterable electronic records, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Y. Kadoya , M. Fuketa , El-Sayed Atlam , K. Morita , T. Sumitomo , J. Aoe, A compression algorithm using integrated record information for translation dictionaries, Information Sciences—Informatics and Computer Science: An International Journal, v.165 n.3-4, p.171-186, 19 October 2004
	Malik Ayed Tubaishat , Sanjay Kumar Madria , Bharat Bhargava, Performance evaluation of linear hash structure model in a nested transaction environment, Journal of Systems and Software, v.63 n.3, p.219-239, 15 September 2002
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Arindam Banerji , John Michael Tracey , David L. Cohn, Protected shared libraries: a new approach to modularity and sharing, Proceedings of the Annual Technical Conference on Proceedings of the USENIX 1997 Annual Technical Conference, p.5-5, January 06-10, 1997, Anaheim, California
	K. Patel , E. Macii , L. Benini , M. Poncino, Reducing cache misses by application-specific re-configurable indexing, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.125-130, November 07-11, 2004
	R. Braumandl , J. Claussen , A. Kemper , D. Kossmann, Functional-join processing, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.156-177, February 2000
	Alexandra Poulovassilis , Carol Small, A Functional Programming Approach to Deductive Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.491-500, September 03-06, 1991
	André Eickler , Carsten Andreas Gerlhof , Donald Kossmann, A Performance Evaluation of OID Mapping Techniques, Proceedings of the 21th International Conference on Very Large Data Bases, p.18-29, September 11-15, 1995
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Mario Mense , Christian Scheideler, SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1135-1144, January 20-22, 2008, San Francisco, California
	Peter Brass, Universal hash functions for an infinite universe and hash trees, Information Processing Letters, v.109 n.10, p.461-462, April, 2009