Concise: Compressed 'n' Composable Integer Set

Alessandro Colantonio, Roberto Di Pietro

Research output: Contribution to journalArticlepeer-review

73 Scopus citations

Abstract

Bit arrays, or bitmaps, are used to significantly speed up set operations in several areas, such as data warehousing, information retrieval, and data mining, to cite a few. However, bitmaps usually use a large storage space, thus requiring compression. Consequently, there is a space-time tradeoff among compression schemes. The Word Aligned Hybrid (WAH) bitmap compression trades some space to allow for bitwise operations without first decompressing bitmaps. WAH has been recognized as the most efficient scheme in terms of computation time. In this paper we present Concise (Compressed 'n' Composable Integer Set), a new scheme that enjoys significantly better performances than WAH. In particular, when compared to WAH our algorithm is able to reduce the required memory up to 50%, while having comparable computation time. Further, we show that Concise can be efficiently used to represent sets of integral numbers in lieu of well-known data structures such as arrays, lists, hashtables, and self-balancing binary search trees. Extensive experiments over synthetic data show the effectiveness of our proposal. © 2010 Elsevier B.V. All rights reserved.
Original languageEnglish (US)
Pages (from-to)644-650
Number of pages7
JournalInformation Processing Letters
Volume110
Issue number16
DOIs
StatePublished - Jul 31 2010
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-20

ASJC Scopus subject areas

  • Signal Processing
  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Concise: Compressed 'n' Composable Integer Set'. Together they form a unique fingerprint.

Cite this