Searchable Compressed Representations of Very Sparse Bitmaps

Very sparse bitmaps are used in a wide variety of applications, ranging from adjacency matrices in representation of large sparse graphs, representation of sparse space occupancy to book-keeping in databases. In this paper, we propose a method based on pruning of binary space partition (BSP) tree in minimal description length (MDL) principle for coding very sparse bitmaps. This new method for coding of sparse bitmaps meets seemingly competing objectives of good compression, the ability of conducting queries directly in compression domain, and simple and fast decoding.