Access Restriction

Author Casey, R. G.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Information storage and retrieval ♦ Query answering ♦ Tree file ♦ Data management ♦ Search ♦ Clustering ♦ Data structure
Abstract 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.
Description Affiliation: IBM Research Lab, San Jose, CA (Casey, R. G.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 16
Issue Number 9
Page Count 8
Starting Page 549
Ending Page 556

Open content in new tab

   Open content in new tab
Source: ACM Digital Library