Tree structures construction using key densities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tree structures construction using key densities

Full text

Pdf (336 KB)

Source

ACM Annual Conference/Annual Meeting archive
Proceedings of the 1975 annual conference table of contents

Pages: 337 - 342

Year of Publication: 1975

Author

S. B. Yao

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

Storage structure alternatives exist for structuring symbol trees. Sequential structure is used in Trie and linked list structure is used in Doubly Chained Tree. A model of hybrid tree structures is presented which employs storage structures at levels where they are most efficient. The model parameters are determined by the densities of key components. A related hit ratio problem is solved so that these densities can be estimated. Analyses are given to determine appropriate tree structures from the model.

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	R. de la Briandais, File searching using variable length keys, Proc. 1959 Western Joint Computing Conference, 295-298.
	2	Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
	3	S. A. Hoffman, Data structures that generalize rectangular arrays, AFIPS Conference Proc. 1962 Joint Computer Conference, 325-333.
	4	Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
	5	Dennis Gordon Severance, Some generalized modeling structures for use in design of file organizations., 1972
	6	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]
	7	S. Subas, R. L. Kashyap, and S. B. Yao, The clustering concept and secondary key retrieval for on-line systems, Proc. Conference on Computer Graphics, Pattern Recognition, & Data Structure, May 1975, 181-190.
	8	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]
	9	Shi Bing Yao, Evaluation and optimization of file organizations through analytic modeling., 1974
	10	S. B. Yao and A. G. Merten, Selection of file organizations using an analytic model, Tech. Repert CSD TR 151, Purdue University, April 1975.

CITED BY 4

	Douglas Comer , Ravi Sethi, The Complexity of Trie Index Construction, Journal of the ACM (JACM), v.24 n.3, p.428-440, July 1977
	S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977
	T. J. Teorey , K. Sundar Das, Application of an analytical model to evaluate storage structures, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
	S. B. Yao , A. G. Merten, Selection of file organization using an analytic model, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts