The Complexity of Trie Index Construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Complexity of Trie Index Construction

Full text

Pdf (763 KB)

Source

Journal of the ACM (JACM) archive
Volume 24 , Issue 3 (July 1977) table of contents

Pages: 428 - 440

Year of Publication: 1977

ISSN:0004-5411

Authors

Douglas Comer	Computer Sciences Department, Purdue University, West Lafayette, IN
Ravi Sethi	Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 50, Citation Count: 15

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/322017.322023 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BAYER, R, AND MCCREIGHT, E Organization and maintenance of large ordered radices Acta Informatica 1 (1972), 173-189
	3	COMER, D E, AND SETHI, R Complexity of tr~e index construction Extended abstract, Proc 17th Annual Syrnp on Foundations of Complr So , Oct 1976, pp 197-207
	4	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	5	DE LA BRIANDAIS, R File searching using variable length keys Proc Western Joint Comptr Conf, IRE, New York, 1959, pp 295-298
	6	DE MAINE, P A D , AND ROTWlTT, T JR Storage optimization of tree structured flies representing descriptor sets Proc ACM SIGFIDET Workshop on Data Description, Access and Control, Nov 1971, pp 207-217
	7	Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
	8	HYAFIL, L., AND RIVEST, R Constructing optimal binary decision trees Js NP-complete Information Processmg Letters 5, 1 (May 1976), 15-17
	9	KNUTFI, D E The Art of Computer Programmmg, Vol 1 Fundamental Algorithms Addison-Wesley, Reading, Mass , 1968
	10	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	11	J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974 [doi>10.1145/356631.356634]
	12	Mario Schkolnick, Secondary index optimization, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500106]
	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 [doi>10.1145/356631.356633]
	14	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]
	15	S. B. Yao, Tree structures construction using key densities, Proceedings of the 1975 annual conference, p.337-342, January 1975 [doi>10.1145/800181.810359]

CITED BY 15

	S. Dawson , C. R. Ramakrishnan , I. V. Ramakrishnan , K. Sagonas , S. Skiena , T. Swift , D. S. Warren, Unification factoring for efficient execution of logic programs, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-258, January 23-25, 1995, San Francisco, California, United States
	M. Al-Suwaiyel , E Horowitz, Algorithms for trie compaction, ACM Transactions on Database Systems (TODS), v.9 n.2, p.243-263, June 1984
	Steven Dawson , C. R. Ramakrishnan , Steven Skiena , Terrance Swift, Principles and practice of unification factoring, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.528-563, Sept. 1996
	Douglas Comer, Heuristics for trie index minimization, ACM Transactions on Database Systems (TODS), v.4 n.3, p.383-395, Sept. 1979
	R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988
	R. Ramesh , A. J. G. Babu , J. Peter Kincaid, Variable-depth trie index optimization: theory and experimental results, ACM Transactions on Database Systems (TODS), v.14 n.1, p.41-74, March 1989
	A. T. Berztiss, Data processing and computer science theory, ACM SIGCSE Bulletin, v.15 n.1, p.72-76, February 1983
	Douglas Comer, Analysis of a heuristic for full trie minimization, ACM Transactions on Database Systems (TODS), v.6 n.3, p.513-537, Sept. 1981
	O. J. Murphy , R. L. McCraw, Designing Storage Efficient Decision Trees, IEEE Transactions on Computers, v.40 n.3, p.315-320, March 1991
	Steffen Heinz , Justin Zobel , Hugh E. Williams, Burst tries: a fast, efficient data structure for string keys, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.192-223, April 2002
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	K. Selçuk Candan , Mehmet E. Dönderler , J. Ramamoorthy , Jong W. Kim, Clustering and indexing of experience sequences for popularity-driven recommendations, Proceedings of the 3rd ACM workshop on Continuous archival and retrival of personal experences, October 28-28, 2006, Santa Barbara, California, USA
	John Yiannis , Justin Zobel, Compression techniques for fast external sorting, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.2, p.269-291, April 2007
	Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998
	Christos Tryfonopoulos , Manolis Koubarakis , Yannis Drougas, Information filtering and query indexing for an information retrieval model, ACM Transactions on Information Systems (TOIS), v.27 n.2, p.1-47, February 2009