Searchable compressed representation 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. A method based on pruning of the binary space partition (BSP) tree in the minimal description length (MDL) principle for coding very sparse bitmaps was proposed. This new method for coding of sparse bitmaps meets seemingly competing objectives of good compression, the ability of conducting queries directly in the compression domain, and simple and fast decoding.