Record number :
1229496
Title of article :
On the compression of search trees
Author/Authors :
Francisco Claude، نويسنده , , Patrick K. Nicholson، نويسنده , , Diego Seco، نويسنده ,
Issue Information :
دوماهنامه با شماره پیاپی سال 2014
Pages :
12
From page :
272
To page :
283
Abstract :
Let image be a sequence of non-decreasing integer values. Storing a compressed representation of X that supports access and search is a problem that occurs in many domains. The most common solution to this problem uses a linear list and encodes the differences between consecutive values with encodings that favor small numbers. This solution includes additional information (i.e. samples) to support efficient searching on the encoded values. We introduce a completely different alternative that achieves compression by encoding the differences in a search tree. Our proposal has many applications, such as the representation of posting lists, geographic data, sparse bitmaps, and compressed suffix arrays, to name just a few. The structure is practical and we provide an experimental evaluation to show that it is competitive with the existing techniques.
Keywords :
Random access , Compression , Integers , data structure , Search
Journal title :
Information Processing and Management
Link To Document :