Bitmap lattice index in road networks

A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server's workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve(HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.

A Survey of Bitmap Index Compression Algorithms for Big Data

With the growing popularity of Internet applications and the widespread use of mobile Internet, Internet traffic has maintained rapid growth over the past two decades. Internet Traffic Archival Systems（ITAS） for packets or flow records have become more and more widely used in network monitoring, network troubleshooting, and user behavior and experience analysis. Among the three key technologies in ITAS, we focus on bitmap index compression algorithm and give a detailed survey in this paper. The current state-of-the-art bitmap index encoding schemes include： BBC, WAH, PLWAH, EWAH, PWAH, CONCISE, COMPAX, VLC, DF-WAH, and VAL-WAH. Based on differences in segmentation, chunking, merge compress, and Near Identical（NI） features, we provide a thorough categorization of the state-of-the-art bitmap index compression algorithms. We also propose some new bitmap index encoding algorithms, such as SECOMPAX, ICX, MASC, and PLWAH＋, and present the state diagrams for their encoding algorithms. We then evaluate their CPU and GPU implementations with a real Internet trace from CAIDA. Finally, we summarize and discuss the future direction of bitmap index compression algorithms. Beyond the application in network security and network forensic, bitmap index compression with faster bitwise-logical operations and reduced search space is widely used in analysis in genome data, geographical information system, graph databases, image retrieval, Internet of things, etc. It is expected that bitmap index compression will thrive and be prosperous again in Big Data era since 1980s.

COMBAT:A New Bitmap Index Coding Algorithm for Big Data

Bitmap indexing has been widely used in various applications due to its speed in bitwise operations. However, it can consume large amounts of memory. To solve this problem, various bitmap coding algorithms have been proposed. In this paper, we present COMbining Binary And Ternary encoding （COMBAT）, a new bitmap index coding algorithm. Typical algorithms derived from Word Aligned Hybrid （WAH） are COMPressed Adaptive indeX （COMPAX） and Compressed ＂n＂ Composable Integer Set （CONCISE）, which can combine either two or three continuous words after WAH encoding. COMBAT combines both mechanisms and results in more compact bitmap indexes. Moreover, querying time of COMBAT can be faster than that of COMPAX and CONCISE, since bitmap indexes are smaller and it would take less time to load them into memory. To prove the advantages of COMBAT, we extend a theoretical analysis model proposed by our group, which is composed of the analysis of various possible bitmap indexes. Some experimental results based on real data are also provided, which show COMBAT＇s storage and speed superiority. Our results demonstrate the advantages of COMBAT and codeword statistics are provided to solidify the proof.

PLQ:An Efficient Approach to Processing Pattern-Based Log Queries

As software systems grow more and more complex,extensive techniques have been proposed to analyze the log data to obtain the insight of the system status.However,during log data analysis,tedious manual efforts are paid to search interesting or informative log patterns from a huge volume of log data,named pattern-based queries.Although existing log management tools and DMBS systems can also support pattern-based queries,they suffer from a low efficiency.To deal with this problem,we propose a novel approach,named PLQ(Pattern-based Log Query).First,PLQ organizes logs into disjoint chunks and builds chunk-wise bitmap indexes for log types and attribute values.Then,based on bitmap indexes,PLQ finds candidate logs with a set of efficient bit-wise operations.Finally,PLQ fetches candidate logs and validates them according to the queried pattern.Extensive experiments are conducted on real-life datasets.According to experimental results,compared with existing log management systems,PLQ is more efficient in querying log patterns and has a higher pruning rate for filtering irrelevant logs.Moreover,in PLQ,since the ratio of the index size to the data size does not exceed 2.5%for log datasets of different sizes,PLQ has a high scalability.