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