Improved Hierarchical Bit-Vector Compression in Document Retrieval Systems.

Yaacov Choueka, Aviezri S. Fraenkel, Shmuel T. Klein, E. Segal: Improved Hierarchical Bit-Vector Compression in Document Retrieval Systems. SIGIR 1986: 88-96

@inproceedings{DBLP:conf/sigir/ChouekaFKS86,
  author    = {Yaacov Choueka and
               Aviezri S. Fraenkel and
               Shmuel T. Klein and
               E. Segal},
  title     = {Improved Hierarchical Bit-Vector Compression in Document Retrieval
               Systems},
  booktitle = {SIGIR'86, Proceedings of the 9th Annual International ACM SIGIR
               Conference on Research and Development in Information Retrieval,
                Pisa, Italy, September 8-10, 1986},
  publisher = {ACM},
  year      = {1986},
  pages     = {88-96},
  ee        = {db/conf/sigir/ChouekaFKS86.html},
  crossref  = {DBLP:conf/sigir/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The "concordance" of an information retrieval system can often be stored in form of bit-maps, which are usually very sparse and should be compressed. Hierarchical bit-vector compression consists of partitioning a vector v_i into equi-sized blocks, constructing a new bit-vector v_i+1 which points to the non-eero blocks in v_i, dropping the zero-blocks of v_i, and repeating the process for v_i+1. We refine the method by pruning some of the tree branches if they ultimately point to very few documents; these document numbers are then added to an appended list which is compressed by the prefix-omission technique. The new method was thoroughly tested on the bit-maps of the Responsa Retrieval Project, and gave a relative improvement of about 40% over the conventional hierarchical compression method.

Copyright © 1986 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

SIGIR'86, Proceedings of the 9th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Pisa, Italy, September 8-10, 1986. ACM 1986
Contents BibTeX

Online Edition: ACM Digital Library

Citation Page

Referenced by

Alistair Moffat, Justin Zobel: Fast Ranking in Limited Space. ICDE 1994: 428-437

BibTeX

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