Paper Info
Title
Development and Performance Evaluation of Fast Combinatorial Unranking Implementations.
Abstract
Compressed bitmaps have been long used in computer science and today it seems they conquer more and more fields of networking. The goal of this paper is to provide fast combinatorial unranking implementations for use in bitmap data compression. Within this context, unranking refers to the operation of obtaining a bit vector given its rank in a particular enumeration of all bit vectors of the same size with respect to a given order. Easily, the simplest way to accomplish this task is to use a lookup table. However, for large block sizes such a table may not fit into the memory. Efficient combinatorial unranking algorithms, which eliminate large lookup tables, are therefore essential in practice. Taking the textbook combinatorial unranking schemes, in this paper we develop very fast combinatorial unranking implementations and we introduce a comprehensive performance evaluation and profiling toolkit to measure their efficiency. Our benchmarks show that our optimized implementations improve the performance of the naive combinatorial unranking implementations by 39%, almost attaining the performance of simple lookup tables.
Year
DOI
Venue
2014
10.1007/978-3-319-13488-8_10
ADVANCES IN COMMUNICATION NETWORKING
Field
DocType
Volume
Block size,Position (vector),Lookup table,Profiling (computer programming),Computer science,Theoretical computer science,Bitmap,Lexicographical order,Data compression,Bit array
Conference
8846
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
3
3
Name
Order
Citations
PageRank
András Majdán1311.86
Gábor Rétvári219424.87
János Tapolcai336441.42