Key-to-address transform techniques

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Key-to-address transform techniques: a fundamental performance study on large existing formatted files

Full text

Pdf (1.32 MB)

Source

Communications of the ACM archive
Volume 14 , Issue 4 (April 1971) table of contents

Pages: 228 - 239

Year of Publication: 1971

ISSN:0001-0782

Authors

V. Y. Lum	IBM Research Lab., San Jose, CA
P. S. T. Yuen	IBM Research Lab., San Jose, CA
M. Dodd	IBM Research Lab., San Jose, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 24, Citation Count: 39

Additional Information:

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

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	Buchholz, W. File organization and addressing. IBM Syst. J. 2, (June 1963), 86-111.
	2	Lin, A. D. Key addressing of random access memories by radix transformation. Proc. AFIPS 1963 SJCC, Vol. 24, Spartan Books, New York, pp. 355-366.
	3	Schay, G., and Raver, N. A method for key-to-address transformation. IBM J. R&D 7, 2 (Apr. 1963), 121-129.
	4	Hanan, M., and Palermo, F. P. An application of coding theory to a file addressing problem. IBM d. R&D 7, 2 (Apr. 1963), 127-129.
	5	Peterson, W. W. Addressing for random-access storage. IBM& R&D 1, 2 (Apr. 1957), 130--146.
	6	G. Schay, Jr. , W. G. Spruth, Analysis of a file addressing method, Communications of the ACM, v.5 n.8, p.459-462, Aug. 1962 [doi>10.1145/368637.368827]
	7	M. D. Mc Ilroy, A variant method of file searching, Communications of the ACM, v.6 n.3, p.101, March 1963 [doi>10.1145/366274.366304]
	8	Introduction to IBM System/360, direct access storage devices and organization methods. IBM Student Text, C20-1649.
	9	W. D. Maurer, Programming Technique: An improved hash code for scatter storage, Communications of the ACM, v.11 n.1, p.35-38, Jan. 1968 [doi>10.1145/362851.362880]
	10	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	11	Charles A. Olson, Random access file organization for indirectly addressed records, Proceedings of the 1969 24th national conference, p.539-549, August 26-28, 1969 [doi>10.1145/800195.805959]
	12	Peterson, W. W. Error Correcting Codes. M.I.Tr Press, Cambridge, Mass. 1961.
	13	Van der Waeden, B. L. Modern Algebra. Frederick Ungar Pub. Co., New York, 1953.
	14	M. Tainiter, Addressing for Random-Access Storage with Multiple Bucket Capacities, Journal of the ACM (JACM), v.10 n.3, p.307-315, July 1963 [doi>10.1145/321172.321178]
	15	Charles E. Radke, The use of quadratic residue research, Communications of the ACM, v.13 n.2, p.103-105, Feb 1970 [doi>10.1145/362007.362036]
	16	James R. Bell, The quadratic quotient method: a hash code eliminating secondary clustering, Communications of the ACM, v.13 n.2, p.107-109, Feb 1970 [doi>10.1145/362007.362040]
	17	Ghosh, S. Private communication.
	18	Van der Pool, J. A. Private communication.

CITED BY 39

	R. F. Deutscher , P. G. Sorenson , J. P. Tremblay, Distribution-dependent hashing functions and their characteristics, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California
	C. E. Price, Table Lookup Techniques, ACM Computing Surveys (CSUR), v.3 n.2, p.49-64, June 1971
	Haim Mendelson , Uri Yechiali, A New Approach to the Analysis of Linear Probing Schemes, Journal of the ACM (JACM), v.27 n.3, p.474-483, July 1980
	C. C. Chang, The study of an ordered minimal perfect hashing scheme, Communications of the ACM, v.27 n.4, p.384-387, April 1984
	Dennis Severance , Ricardo Duhne, A practitioner's guide to addressing algorithms, Communications of the ACM, v.19 n.6, p.314-326, June 1976
	V. Y. Lum , P. S. T. Yuen, Additional results on key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.15 n.11, p.996-997, Nov. 1972
	R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988
	P. Quittner , S. Csóka , S. Halász , D. Kotsis , K. Várnai, Comparison of synonym handling and bucket organization methods, Communications of the ACM, v.24 n.9, p.579-583, Sept. 1981
	V. Y. Lum, General performance analysis of key-to-address transformation methods using an abstract file concept, Communications of the ACM, v.16 n.10, p.603-612, Oct. 1973
	James K. Mullin, An improved index sequential access method using hashed overflow, Communications of the ACM, v.15 n.5, p.301-307, May 1972
	W. D. Maurer , T. G. Lewis, Hash Table Methods, ACM Computing Surveys (CSUR), v.7 n.1, p.5-19, March 1975
	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974
	Ushio Inoue , Tetsuji Satoh , Haruo Hayami , Hideaki Takeda , Toshio Nakamura , Hideki Fukuoka, Rinda: A Relational Database Processor with Hardware Specialized for Searching and Sorting, IEEE Micro, v.11 n.6, p.61-70, November 1991
	W. C. Lynch, Operating system performance, Communications of the ACM, v.15 n.7, p.579-585, July 1972
	Jonathan D. Cohen, Recursive hashing functions for n-grams, ACM Transactions on Information Systems (TOIS), v.15 n.3, p.291-320, July 1997
	Carter Bays, A note on when to chain overflow items within a direct-access table, Communications of the ACM, v.16 n.1, p.46-47, Jan. 1973
	Charles W. Bachman, The evolution of storage structures, Communications of the ACM, v.15 n.7, p.628-634, July 1972
	James K. Mullin, A second look at bloom filters, Communications of the ACM, v.26 n.8, p.570-571, Aug. 1983
	J. C. Browne, A critical overview of computer performance evaluation, Proceedings of the 2nd international conference on Software engineering, p.138-145, October 13-15, 1976, San Francisco, California, United States
	Jukka Teuhola , Lutz Wegner, Minimal space, average linear time duplicate deletion, Communications of the ACM, v.34 n.3, p.62-73, March 1991
	Toby J. Teorey , James P. Fry, The Logical Record Access Approach to Database Design, ACM Computing Surveys (CSUR), v.12 n.2, p.179-211, June 1980
	D. G. Severance , J. V. Carlis, A Practical Approach to Selecting Record Access Paths, ACM Computing Surveys (CSUR), v.9 n.4, p.259-272, Dec. 1977
	Ian F. Blake , Alan G. Konheim, Big Buckets Are (Are Not) Better!, Journal of the ACM (JACM), v.24 n.4, p.591-606, Oct. 1977
	M. V. Ramakrishna, Hashing practice: analysis of hashing and universal hashing, ACM SIGMOD Record, v.17 n.3, p.191-199, June 1988
	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
	Haim Mendelson , Uri Yechiali, Performance Measures for Ordered Lists in Random-Access Files, Journal of the ACM (JACM), v.26 n.4, p.654-667, Oct. 1979
	C. T. Yu , M. K. Siu , K. Lam , M. Ozsoyoglu, Performance analysis of three related assignment problems, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts
	R. T. Chien , E. A. Mark, A Document Storage Method Based on Polarized Distance, Journal of the ACM (JACM), v.21 n.2, p.233-245, April 1974
	Philip Clapson, Improving the access time for random access files, Communications of the ACM, v.20 n.3, p.127-135, March 1977
	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
	Ted G. Lewis , Curtis R. Cook, Hashing for Dynamic and Static Internal Tables, Computer, v.21 n.10, p.45-56, October 1988
	Jack Minker, Information storage and retrieval: a survey and functional description, ACM SIGIR Forum, v.12 n.2, p.12-108, Fall 1977
	A system structure and data structure for an interactive on-line thesaurus, ACM SIGIR Forum, v.7 n.4, p.65-70, Winter 1972
	David Lipton, Logical authentication method, ACM SIGSAC Review, v.4 n.2, p.9-20, Spring 1986
	Jacques Savoy, Statistical behavior of fast hashing of variable length test strings, ACM SIGIR Forum, v.24 n.3, p.62-71, Fall 1990
	T. H. Merrett, Database cost analysis: a top-down approach, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada
	Kuo-Chung Tai , Alan L. Tharp, An introduction to computed chaining, Proceedings of the May 19-22, 1980, national computer conference, May 19-22, 1980, Anaheim, California
	Jerry D. Whitt , A. Gale Sullenberger, The algorithm sequential access method: an alternative to index sequential, Communications of the ACM, v.18 n.3, p.174-176, March 1975

INDEX TERMS

Keywords:
cluster, collisions, direct access method, direct addressing, file addressing, file organizations, file structures, hash coding, hashing, hashing methods, hashing techniques, information retrieval, key transformation, key-to-address transformation, keys, random access, randomizing, scatter storage, search

Collaborative Colleagues:

V. Y. Lum: colleagues

P. S. T. Yuen: colleagues

M. Dodd: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player