Parameterised Compression for Sparse Bitmaps.

Alistair Moffat, Justin Zobel: Parameterised Compression for Sparse Bitmaps. SIGIR 1992: 274-285

@inproceedings{DBLP:conf/sigir/MoffatZ92,
  author    = {Alistair Moffat and
               Justin Zobel},
  editor    = {Nicholas J. Belkin and
               Peter Ingwersen and
               Annelise Mark Pejtersen},
  title     = {Parameterised Compression for Sparse Bitmaps},
  booktitle = {Proceedings of the 15th Annual International ACM SIGIR Conference
               on Research and Development in Information Retrieval. Copenhagen,
               Denmark, June 21-24, 1992},
  publisher = {ACM},
  year      = {1992},
  isbn      = {0-89791-523-2},
  pages     = {274-285},
  ee        = {db/conf/sigir/MoffatZ92.html},
  crossref  = {DBLP:conf/sigir/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Full-text retrieval systems often use either a bitmap or an inverted file to identify which documents contain which terms, so that the documents containing any combination of query terms can be quickly located. Bitmaps of term occurrences are large, but are usually sparse, and thus are amenable to a variety of compression techniques. Here we consider techniques in which the encoding of each bitvector within the bitmap is parameterised, so that a different code can be used for each bitvector. Our experimental results show that the new methods yield better compression than previous techniques.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 3, SIGIR, DASFAA'97, OODBS'86" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-3 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Nicholas J. Belkin, Peter Ingwersen, Annelise Mark Pejtersen (Eds.): Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Copenhagen, Denmark, June 21-24, 1992. ACM 1992, ISBN 0-89791-523-2
Contents BibTeX

Online Edition: ACM Digital Library

Citation page

Referenced by

Till Westmann, Donald Kossmann, Sven Helmer, Guido Moerkotte: The Implementation and Performance of Compressed Databases. SIGMOD Record 29(3): 55-67(2000)
Theodore Johnson: Performance Measurements of Compressed Bitmap Indices. VLDB 1999: 278-289
Hugh E. Williams, Justin Zobel: Indexing Nucleotide Databases for Fast Query Evaluation. EDBT 1996: 275-288
Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao, James A. Thom, Justin Zobel: Atlas: A Nested Relational Database System for Text Applications. IEEE Trans. Knowl. Data Eng. 7(3): 454-470(1995)
Brian Lowe, Justin Zobel, Ron Sacks-Davis: A Formal Model for Databases of Structured Text. DASFAA 1995: 449-456
Justin Zobel, Alistair Moffat, Ron Sacks-Davis: Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files. VLDB 1993: 290-301
Justin Zobel, Alistair Moffat, Ron Sacks-Davis: An Efficient Indexing Technique for Full Text Databases. VLDB 1992: 352-362

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]