Design of Tree Structures for Efficient Querying A standard information retrieval operation is to determine which records in a data collection satisfy a given query expressed in terms of data values. The process of locating the desired responses can be represented by a tree search model. This paper poses an optimization problem in the design of such trees to serve a well-specified application. The problem is academic in the sense that ordinarily the optimal tree cannot be implemented by means of practical techniques. On the other hand, it is potentially useful for the comparison it affords between observed performance and that of an intuitively attractive ideal search procedure. As a practical application of such a model this paper considers the design of a novel tree search scheme based on a bit vector representation of data and shows that essentially the same algorithm can be used to design either an ideal search tree or a bit-vector tree. An experimental study of a small formatted file illustrates the concepts. CACM September, 1973 Casey, R. G. tree file, information storage and retrieval, clustering, search, data structure, data management, query answering 3.62 3.74 CA730904 JB January 23, 1978 9:38 AM 1050 4 2451 1234 4 2451 1935 4 2451 1936 4 2451 2017 4 2451 2032 4 2451 2257 4 2451 2257 4 2451 2360 4 2451 2360 4 2451 2451 4 2451 2451 4 2451 2451 4 2451 2451 4 2451 2452 4 2451 2452 4 2451 2556 4 2451 2556 4 2451 2765 4 2451 2978 4 2451 944 5 2451 1935 5 2451 1936 5 2451 2451 5 2451 2451 5 2451 2451 5 2451 2765 5 2451 2965 5 2451 849 5 2451 1936 6 2451 1976 6 2451 2046 6 2451 2046 6 2451 2451 6 2451 2451 6 2451 2452 6 2451 616 6 2451