Analysis of directory searching

Thomas C. Lowe and David C. Roberts

Journal of the American Society for Information Science, 1972, vol. 23, issue 3, 143-149

Abstract: Files are frequently organized into records, and keys are associated with those records. A directory is a list of key‐address pairs, where each pair consists of a key and an address associated with that key. The addresses may be those of records in the file, or of intermediate data, such as inverted lists. A fundamental problem is searching a directory efficiently for known keys, in order to find all addresses associated with those keys. Several problems of finding keys in directories are considered. Methods of searching both ordered and unordered directories are analyzed; directories are classified as they organize unused space: compacted, distributed, or chained. Searching on ranges of key values, rather than exact key matching, is also considered. Finally, design tradeoffs among the classes of directory and searching strategies are developed.

Date: 1972
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/asi.4630230302

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jamest:v:23:y:1972:i:3:p:143-149

Ordering information: This journal article can be ordered from
https://doi.org/10.1002/(ISSN)1097-4571

Access Statistics for this article

More articles in Journal of the American Society for Information Science from Association for Information Science & Technology
Bibliographic data for series maintained by Wiley Content Delivery ().