The SBC-Tree: An index for run-length compressed sequences

Mohamed Y. Eltabakh, Wing Kai Hon, Rahul Shah, Walid G. Aref, Jeffrey S. Vitter

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Citations (Scopus)

Abstract

Run-Length-Encoding (RLE) is a data compression technique that is used in various applications, e.g., time series, biological sequences, and multimedia databases. One of the main challenges is how to operate on (e.g., index, search, and retrieve) compressed data without decompressing it. In this paper, we introduce the String B-tree for Compressed sequences, termed the SBC-tree, for indexing and searching RLE-compressed sequences of arbitrary length. The SBC-tree is a two-level index structure based on the well-known String B-tree and a 3-sided range query structure [7]. The SBC-tree supports pattern matching queries such as substring matching, Prefix matching, and range search operations over RLE-compressed sequences. The SBC-tree has an optimal external-memory space complexity of O(N/B) pages, where N is the total length of the compressed sequences, and B is the disk page size. Substring matching, Prefix matching, and range search execute in an optimal O(Formula Presented) I/O operations, where |p| is the length of the compressed query pattern and T is the query output size. The SBC-tree is also dynamic and supports insert and delete operations effciently. The insertion and deletion of all suffixes of a compressed sequence of length m take O(mlogB(N + m)) amortized I/O operations. The SBC-tree index is realized inside PostgreSQL. Performance results illustrate that using the SBC-tree to index RLE-compressed sequences achieves up to an order of magnitude reduction in storage, while retains the optimal search performance achieved by the String B-tree over the uncompressed sequences.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings
PublisherAssociation for Computing Machinery
Pages523-534
Number of pages12
ISBN (Print)9781595939265
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event11th International Conference on Extending Database Technology, EDBT 2008 - Nantes, France
Duration: 25 Mar 200829 Mar 2008

Publication series

NameAdvances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings

Conference

Conference11th International Conference on Extending Database Technology, EDBT 2008
Country/TerritoryFrance
CityNantes
Period25/03/0829/03/08

Fingerprint

Dive into the research topics of 'The SBC-Tree: An index for run-length compressed sequences'. Together they form a unique fingerprint.

Cite this