Oscar Vallarino
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
- 1 Davis, D.R., and Lin, A.D. "Secondary key retrieval using an IBM 7090-1301 system". CACM 8, 4 (April 1965), 243-246. Google Scholar
Digital Library
- 2 Fraser, W.D. "A proposed system for multiple descriptor data retrieval", inSome Problems in Information Systems, M. Kocken (Ed.). Scarecrow Press, New York, 1965, pp. 187-205.Google Scholar
- 3 Lefkovitz, D. File structures for on-line systems. Spartan Press, New York, 1969.Google ScholarCross Ref
- 4 Casey, R.G. "Design of tree structures for efficient querying". CACM 16, 9 (September 1973), 549-556. Google ScholarDigital Library
- 5 Knuth, D.E. The art of computer programming V3: sorting and searching. Addison-Wesley, Reading, Mass., 1973, pp. 550-567. Google ScholarDigital Library
- 6 Rothnie, J.B., and Lozano, T. "Attribute based file organization in a paged environment". CACM 17, 2 (February 1974), 63-69. Google ScholarDigital Library
- 7 Farley, G.H.J., and Schuster, S.A. "Query execution and index selection for relational data bases." Technical report CSRG-53, Computer Systems Research Group, University of Toronto, 1975.Google Scholar
- 8 Codd, E.F. "A relational model for large shared data banks". CACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 9 Codd, E.F. "Relational completeness of data base sublanguages". Courant Computer Science Symposia 6, inData Base Systems, Randall Rustin (Ed.), Prentice Hall, New Jersey, 1972, pp. 65-98.Google Scholar
- 10 Boyce, R.F., Chamberlin, D.D., King III, W.F., and Hammer, M.M. "Specifying queries as relational expressions: SQUARE". IBM Technical Report RJ1291, IBM Res. Labs., San Jose, California, October 1973.Google Scholar
- 11 Pooch, U.W., and Nieder, A. "A survey of indexing techniques for sparse matrices". ACM Computing Surveys 5, 2 (June 1973), 109-133 Google ScholarDigital Library
- 12 Hardgrave, W.T. "The prospects of large capacity set support systems imbedded within generalized data base management systems".Proc. International Computing Symposium 1973, Davos, Switzerland. North-Holland Publishing Co., Amsterdam, 1974, pp. 549-556.Google Scholar
- 13 Burke, J.M., and Rickman, J.T. "Bit maps and filters for attribute-oriented searches". International Journal of Computer and Information Sciences2,3 (1973), 187-200.Google ScholarCross Ref
- 14 Martin, J.Computer Data-Base Organization. Prentice-Hall, New Jersey, 1975, pp. 379-200. Google ScholarDigital Library
- 15 Hsiao, D., and Harary, F. "A formal system for information retrieval from files". CACM 13, 2 (February 1970), 67-73. Google ScholarDigital Library
- 16 Vose, M.R., and Richardson, J.S. "An approach to inverted index maintenance". The Computer Bulletin 16, 5 (May 1972) 256-262.Google Scholar
- 17 Inglis, J. "Inverted indexes and multilist structures". The Computer Journal 17 (February 1974), 59-63.Google ScholarCross Ref
- 18 Wong, E., and Chaing, T.C. "Canonical structure in attribute based file organization". CACM 14, 9 (September 1971), 593-597. Google ScholarDigital Library
- 19 Reardon, B.C. "An adaptive information retrieval system using partial file inversion". Information Storage and Retrieval 2, 10 (February 1974), 49-56.Google Scholar
- 20 Cardenas, A.F. "Analysis and performance of inverted data base structures". CACM 5, 18 (May 1975), 253-263. Google ScholarDigital Library
- 21 King, D.R. "The binary vector as a basis of an inverted index file". Journal of Library Automation 7, 4 (December 1974), 307-314.Google Scholar
- 22 Thiel, L.H. and Heaps, H.S. "Program design for restrospective searches on large data bases". Information Storage and Retrieval 8 (1972), 1-20.Google ScholarCross Ref
- 23 Heaps, H.S. and Thiel, L.H. "Optimum procedures for economic information retrieval". Information Storage and Retrieval 6 (1970), 137-153.Google ScholarCross Ref
Index Terms
- On the use of bit maps for multiple key retrieval
Recommendations
On the use of bit maps for multiple key retrieval
Proceedings of the 1976 conference on Data : Abstraction, definition and structureThe 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 ...
On the use of bit maps for multiple key retrieval
Proceedings of the 1976 conference on Data : Abstraction, definition and structureThe 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 ...
Indexes for highly repetitive document collections
CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge managementWe introduce new compressed inverted indexes for highly repetitive document collections. They are based on run-length, Lempel-Ziv, or grammar-based compression of the differential inverted lists, instead of gap-encoding them as is the usual practice. We ...
Comments