Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A General Approach to Compress...

A General Approach to Compression of Hierarchical Indexes

Jukka Teuhola, A General Approach to Compression of Hierarchical Indexes. In: Database and Expert Systems Applications, 12th International Conf., DEXA 2001, Lecture Notes in Computer Science 2113, 775–784, Springer-Verlag, 2001.

Abstract:

Tree-structured indexes typically restrict the search domain level by
level, which means that the search information can be encoded more and
more compactly on the way down. This simple observation is here
formulated as a general principle of index compression. Saving storage
space is one advantage, but more important is reduction of disk
accesses, because more entries can be packed into a page. The index
fan-out can be increased, reducing the average height of the tree.
The applicability of compression is studied for several popular
one- and multi-dimensional indexes. Experiments with the well-known
spatial index, R*-tree, show that with modest assumptions and simple
coding, 30-40% reduction of disk accesses is obtainable for intersection
queries. Compression of index entries can be used together with other
index compaction techniques, such as quantization and pointer list
compression.

BibTeX entry:

@INPROCEEDINGS{pTeuhola01a,
  title = {A General Approach to Compression of Hierarchical Indexes},
  booktitle = {Database and Expert Systems Applications, 12th International Conf., DEXA 2001},
  author = {Teuhola, Jukka},
  volume = {2113},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {775–784},
  year = {2001},
}

Publication Forum rating of this publication: level 1

Edit publication