CAMP: A New Bitmap Index for Data Retrieval in Traffic Archival
Authors:
- 7 April 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 20 (6) , 1128-1131
Abstract
Traffic archival, an indispensable task for network analysis, has suffered from a huge amount of data. These rapid growing data can exceed storage capacity and thwart real-time analysis. In order to take insight from Internet traffic, bitmap indexing is applied in this field. However, raw bitmap indexes can consume more space and longer delay for loading larger indexes into memory. This leads to the invention of various bitmap index compression algorithms to save storage and ensure query efficiency. This paper proposes a new algorithm called common affix merging with partition. By merging common affixes in a bit sequence, it saves more storage and conducts at least one order of magnitude faster bitwise operations when compared with ROARING, WAH, CONCISE, and COMPAX. In practice, besides bitwise operations, a query should also contain the operations of loading index files into memory. The experimental results demonstrate that the speedup is still considerable even taking loading time into consideration.Keywords
Funding Information
- National Natural Science Foundation of China (61472200, 61233016)
- Ministry of Science and Technology of China under National 973 Basic Research Program (2013CB228206)
- State Grid R&D project “Research on the Architecture of Information Communication System for Internet of Energy” (SGRIXTKJ[2015]253)
- National Training Program of Innovation and Entrepreneurship for Undergraduates (201510003049, 201510003B066)
This publication has 12 references indexed in Scilit:
- SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic2015
- Better bitmap performance with Roaring bitmapsSoftware: Practice and Experience, 2015
- A survey of bitmap index compression algorithms for Big DataTsinghua Science and Technology, 2015
- BreadZip: a combination of network traffic data and bitmap index encoding algorithm2014
- SECOMPAX: A bitmap index compression algorithm2014
- A memory efficient reachability data structure through bit vector compression2011
- NET-FLiProceedings of the VLDB Endowment, 2010
- Concise: Compressed ‘n’ Composable Integer SetInformation Processing Letters, 2010
- Position list word aligned hybrid2010
- Sorting improves word-aligned bitmap indexesData & Knowledge Engineering, 2010