NDLI: A General Analytical Model for Spatial and Temporal Performance of Bitmap Index Compression Algorithms in Big Data

Content Provider	IEEE Xplore Digital Library
Author	Yinjun Wu Zhen Chen Yuhao Wen Junwei Cao Wenxun Zheng Ge Ma
Copyright Year	2015
Description	Author affiliation: Res. Inst. of Inf. Technol., Tsinghua Univ., Beijing, China (Yinjun Wu; Zhen Chen; Yuhao Wen; Junwei Cao; Wenxun Zheng; Ge Ma)
Abstract	Bitmap indexing is flexible to conduct boolean operations in data retrieval. Besides, the query processing based on bitmap indexing is also very fast. Therefore it has been widely used in various big data analytics platforms, such as Druid and Spark etc. However, bitmap index can consume a large amount of memory, which leads to the invention of different kinds of bitmap index compression algorithms without sacrificing temporal performance. In practice, we are often discommoded by choosing a proper algorithm when handling specific problems. Besides, after devising a new algorithm that may outperform existing ones, it is essential to evaluate its performance in theory. Without appropriate theoretical analysis, the deficit of a new algorithm can only be spotted until final experimental results are drawn, thus wasting much time and effort. In this paper, we propose a general analytical model to analyze both the spatial and temporal performance for bitmap index compression algorithms, which can be applied to analyze all kinds of algorithms derived from WAH (word-aligned hybrid). In this model, two types of distributed bitmaps, uniformly distributed bitmaps and clustered bitmaps, are used separately. In order to illustrate this model, several bitmap index compression algorithms are analyzed and compared with each other. Algorithms herein are COMBAT (COMbining Binary And Ternary encoding), SECOMPAX (Scope Extended COMPAX) and CONCISE (Compressed 'n' Composable Integer Set), which are all derived from WAH. Evaluation results by MATLAB simulation about these algorithms are also presented. This paper paves the way for further researches on the performance evaluation of various bitmap index compression algorithms in the future.
Starting Page	1
Ending Page	10
File Size	3390173
Page Count	10
File Format	PDF
e-ISBN	9781479999644
DOI	10.1109/ICCCN.2015.7288362
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-08-03
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Indexes Probability Mathematical model Compression algorithms Encoding Analytical models Algorithm design and analysis
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

SECOMPAX: A bitmap index compression algorithm

BreadZip: a combination of network traffic data and bitmap index encoding algorithm

SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic

A tunable compression framework for bitmap indices

COMBAT : A new bitmap index coding algorithm for Big Data

A survey of bitmap index compression algorithms for Big Data

CODIS: A New Compression Scheme for Bitmap Indexes

A Nearby Vehicle Search Algorithm Based on HBase Spatial Index

Compression of low entropy strings with Lempel-Ziv algorithms

A General Analytical Model for Spatial and Temporal Performance of Bitmap Index Compression Algorithms in Big Data

Similar Documents

SECOMPAX: A bitmap index compression algorithm

BreadZip: a combination of network traffic data and bitmap index encoding algorithm

SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic

A tunable compression framework for bitmap indices

COMBAT : A new bitmap index coding algorithm for Big Data

A survey of bitmap index compression algorithms for Big Data

CODIS: A New Compression Scheme for Bitmap Indexes

A Nearby Vehicle Search Algorithm Based on HBase Spatial Index

Compression of low entropy strings with Lempel-Ziv algorithms

A General Analytical Model for Spatial and Temporal Performance of Bitmap Index Compression Algorithms in Big Data