File structures using hashing functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

File structures using hashing functions

Full text

Pdf (667 KB)

Source

Communications of the ACM archive
Volume 13 , Issue 7 (July 1970) table of contents

Pages: 427 - 432

Year of Publication: 1970

ISSN:0001-0782

Authors

E. G. Coffman, Jr.	Univ. of Newcastle upon Tyne, England
J. Eve	Univ. of Newcastle upon Tyne, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 63, Citation Count: 13

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/362686.362693 What is a DOI?

ABSTRACT

A general method of file structuring is proposed which uses a hashing function to define tree structure. Two types of such trees are examined, and their relation to trees studied in the past is explained. Results for the probability distributions of path lengths are derived and illustrated.

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	Thomas N. Hibbard, Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting, Journal of the ACM (JACM), v.9 n.1, p.13-28, Jan. 1962 [doi>10.1145/321105.321108]
	2	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	3	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	4	Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]

CITED BY 13

	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974
	Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, ACM SIGMOD Record, v.24 n.2, p.175-186, May 1995
	R. M. Lea , E. J. Schuegraf, An associative file store using fragments for run-time indexing and compression, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.280-295, June 23-27, 1980, Cambridge, England
	Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.813-825, September 1997
	Jia Liang Han , Ashley W. Plank, Background for association rules and cost estimate of selected mining algorithms, Proceedings of the fifth international conference on Information and knowledge management, p.73-80, November 12-16, 1996, Rockville, Maryland, United States
	J. Gerry Purdy, A graduate course in database management, ACM SIGMOD Record, v.7 n.1, p.10-15, 1975
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Robin Williams, A Survey of Data Structures for Computer Graphics Systems, ACM Computing Surveys (CSUR), v.3 n.1, p.1-21, March 1971
	Wei-Pang Yang , M. W. Du, A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table, Proceedings of the 10th International Conference on Very Large Data Bases, p.245-254, August 27-31, 1984
	Luc Devroye , Gabor Lugosi , Gahyun Park , Wojciech Szpankowski, Multiple choice tries and distributed hash tables, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.891-899, January 07-09, 2007, New Orleans, Louisiana
	N. Broutin , L. Devroye, An analysis of the height of tries with random weights on the edges, Combinatorics, Probability and Computing, v.17 n.2, p.161-202, March 2008
	M. H. McKinney, Variable-length hash area entries, Proceedings of the June 13-16, 1977, national computer conference, June 13-16, 1977, Dallas, Texas
	Peter Brass, Universal hash functions for an infinite universe and hash trees, Information Processing Letters, v.109 n.10, p.461-462, April, 2009

INDEX TERMS

Keywords:
data structures, file structures, hashing functions, information retrieval, scatter tables, tree structures

Collaborative Colleagues:

E. G. Coffman, Jr.: colleagues

J. Eve: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player