On the use of bit maps for multiple key retrieval
- 15 March 1976
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 11 (SI), 108-114
- https://doi.org/10.1145/942574.807128
Abstract
The traditional file structures used to support fast response to complex user queries have been based on the inverted list organization, using either the pointer or bit string representation. In this paper, the use of bit maps for executing multiple key searches is studied. Bit maps turn out to be less precise inverted lists Where the inversion is kept for a quantization of attribute domains and the objects referenced are blocks of data records. The goal is to reduce the total number of I/O accesses required to execute a retrieval based on a Boolean qualification. An evaluation of the method is given for both storage space and expected retrieval time under simplified assumptions. Key Words and Phrases: Multiple key retrieval, inverted lists, bit strings, bit maps, Boolean queries, data base management. CR Categories: 3.70, 3.71, 3.73, 3.74, 4.33, 4.34Keywords
This publication has 13 references indexed in Scilit:
- Analysis and performance of inverted data base structuresCommunications of the ACM, 1975
- Attribute based file organization in a paged memory environmentCommunications of the ACM, 1974
- Inverted indexes and multi-list structuresThe Computer Journal, 1974
- Design of tree structures for efficient queryingCommunications of the ACM, 1973
- A Survey of Indexing Techniques for Sparse MatricesACM Computing Surveys, 1973
- Program design for retrospective searches on large data basesInformation Storage and Retrieval, 1972
- Canonical structure in attribute based file organizationCommunications of the ACM, 1971
- Optimum procedures for economic information retrievalInformation Storage and Retrieval, 1970
- A formal system for information retrieval from filesCommunications of the ACM, 1970
- Secondary key retrieval using an IBM 7090-1301 systemCommunications of the ACM, 1965