Extended Rice Code and Its application to R-Tree Compression

ABSTRACT

Compression techniques are essential for those applications which require more disk accesses. Since the uncompressed data need more disk accesses than the compressed data, compression is used for reducing the costs of disk access to enable the retrieval of data to be faster. Various variable length codes, such as Elias codes, Rice code, and fast extended Golomb code have been used in many applications to compress the data. Particularly, these codes have been used in information retrieval-based applications to compress integers. In these applications, integers are the basis of indexes that are used to resolve queries. This paper has proposed a new method to represent non-negative integers based on the idea used in Rice code and fast extended Golomb code. The variable length codes produced by the proposed method can be suitable for representing small, middle, and large range of integers, where Rice code suits well for representing small or middle or large range of integers. This method also gives better representation for most of the integers from small-to-large range than fast extended Golomb code. In this paper, the proposed method has been applied to compress the coordinates (integers) used in the R-tree structure, which is used for indexing the spatial data. In the experiments, TIGER data collections and synthetic data collections have been used to evaluate the compression performance. The experimental results show that our code achieves better bit-rate than other existing codes for those spatial data files, which contain significant distribution of small, middle, and large integers.

Keywords:

• Data compression
• Extended Rice code
• Information retrieval
• Rice code
• R-tree compression

Additional information

Notes on contributors

Sandanam Domnic

Sandanam Domnic received the BSc degree in physics and the MCA degree from Bharathidasan University, India, in 1998 and 2001, respectively, and the PhD degree from Gandhigram Rural University, Gandhigram, India, in 2008. He is presently working as an assistant professor in the Department of Computer Applications, National Institute of Technology, Tiruchirappalli, India. His current research interests are in data compression, image compression, and information retrieval.

E-mail: [email protected]

Veluchamy Glory

Veluchamy Glory received the BSc degree in computer science from Madurai Kamaraj University and the MCA degree from Kalasalingam University, India, in 2007 and 2010, respectively. Currently, she is pursuing the PhD degree in the Department of Computer Applications, National Institute of Technology, Tiruchirappalli, India. Her research interest is in information retrieval.

E-mail: [email protected]