On the use of bit maps for multiple key retrieval
Published 1 January 1976
Oscar Vallarino
Citations10
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this paper, the use of bit maps for executing multiple key searches is studied and the goal is to reduce the total number of I/O accesses required to execute a retrieval based on a Boolean qualification.
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.34
Keywords
Computer Science
Communications of the ACMA relational model of data for large shared data banks
4,834 Citations1983E. F. Codd
Communications of the ACMAnalysis and performance of inverted data base structures
307 Citations1975Alfonso F. Cárdenas
The need to envision and architecture data base systems in a hierarchical level by level framework is stressed, and formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.
Communications of the ACMA formal system for information retrieval from files
176 Citations1970David K. Hsiao, Frank Harary
A generalized file structure is provided by which the concepts of keyword, index, record, file, directory, file structure, directory decoding, and record retrieval are defined and from which some of the frequently used file structures are derived.
Communications of the ACMAttribute based file organization in a paged memory environment
143 Citations1974James B. Rothnie, Tomás Lozano‐Pérez
A method called multiple key hashing is proposed which attempts to minimize the high cost of page accessing and can often improve on a simple inversion technique by a factor of 2 or 3.
Communications of the ACMSpecifying queries as relational expressions
100 Citations1975Raymond F. Boyce, Donald D. Chamberlin +2 more
A data sublanguage called SQUARE, intended for use in ad hoc, interactive problem solving by non-computer specialists, and is shown to be relationally complete; however, it avoids the quantifiers and bound variables required by languages based on the relational calculus.
ACM Computing SurveysA Survey of Indexing Techniques for Sparse Matrices
82 Citations1973Udo W. Pooch, Al Nieder
The concluding section of the paper compares the types of methods, discusses their suitabihty for different types of processing, and makes suggestions about the adaptability and flexibility of the maj or exmting methods of indexing algorithms for application to user problems.
Communications of the ACMCanonical structure in attribute based file organization
82 Citations1971Eugene Wong, T.‐C. Chiang
A new file structure for attribute based retrieval is proposed that allows queries involving arbitrary Boolean functions of the attribute-value pairs to be processed without taking intersections of lists.
Information Storage and RetrievalProgram design for retrospective searches on large data bases
48 Citations1972L.H. Thiel, H. S. Heaps
The vocabulary of the data base is automatically expressed in terms of 8, 16 and 24 bit codes chosen to point to the natural spelling in a dictionary, and file size is reduced without the necessity for extensive processing for decoding.
Communications of the ACMDesign of tree structures for efficient querying
28 Citations1973R. G. Casey
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.
Communications of the ACMSecondary key retrieval using an IBM 7090-1301 system
19 Citations1965Dixon Davis, A. D. Lin
The secondary key retrieval method involves the preparation of secondary storage lists from primary data records, producing a complete set of addresses of primary records relevant to the request.
Query execution and index selection for relational data bases
18 Citations1975Gilles Farley, S. A. Schuster
An algorithm to evaluate primitive Boolean selections over single relations is presented and it will be argued that the algorithm is efficient with respect to the number of relational accesses and withrespect to the merging of inverted lists.
Information Storage and RetrievalOptimum procedures for economic information retrieval
15 Citations1970H. S. Heaps, L.H. Thiel
It is suggested that the search procedure should be designed to minimize computation time at the expense of convenience in the form of output, but that facilities should be included so that the user who is willing to pay the additional cost may receive output in a more convenient form.
Information Storage and RetrievalAn adaptive information retrieval system using partial file inversion
4 Citations1974B. Reardon
A system design utilizing this concept and incorporating features to generate file keys of wide generality, to minimise sequential searching, and to regulate the size of the inverted file is described.
International Journal of Parallel ProgrammingBitmaps and filters for attribute-oriented searches
3 Citations1973John M. Burke, Jon Rickman
This paper presents inverted file structures for attribute searches in the form of bitmaps and techniques to reduce search lengths through the use of blocking and block-filter records.