The SBC-tree: an index for run-length compressed sequences

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 <u>S</u>tring <u>B</u>-tree for <u>C</u>ompressed 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(log_B N + |p|+T/B) 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 efficiently. The insertion and deletion of all suffixes of a compressed sequence of length m take O(m log_B(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.

REFERENCES

• 1: Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.705-714, January 23-25, 1994, Arlington, Virginia, United States
• 2: Amihood Amir , Gary Benson , Martin Farach, Optimal Two-Dimensional Compressed Matching, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, p.215-226, July 11-14, 1994
• 3: Amihood Amir , Gad M. Landau , Dina Sokol, Inplace run-length 2d compressed search, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.817-818, January 09-11, 2000, San Francisco, California, United States
• 4: Amihood Amir , Gad M. Landau , Uzi Vishkin, Efficient pattern matching with scaling, Journal of Algorithms, v.13 n.1, p.2-32, March 1992 [doi>10.1016/0196-6774(92)90003-U]
• 5: Alberto Apostolico , Gad M. Landau , Steven Skiena, Matching for run-length encoded strings, Journal of Complexity, v.15 n.1, p.4-16, March 1999 [doi>10.1006/jcom.1998.0493]
• 6: Ora Arbell , Gad M. Landau , Joseph S. B. Mitchell, Edit distance of run-length encoded strings, Information Processing Letters, v.83 n.6, p.307-314, 30 September 2002 [doi>10.1016/S0020-0190(02)00215-6]
• 7: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 8: R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, 1:173--189, 1972.
• 9: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 10: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 11: Srikanta J. Bedathur , Jayant R. Haritsa, Engineering a Fast Online Persistent Suffix Tree Construction, Proceedings of the 20th International Conference on Data Engineering, p.720, March 30-April 02, 2004
• 12: Tim Bell , Matt Powell , Amar Mukherjee , Don Adjeroh, Searching BWT Compressed Text with the Boyer-Moore Algorithm and Binary Search, Proceedings of the Data Compression Conference (DCC '02), p.112, April 02-04, 2002
• 13: H. Bunke , J. Csirik, Edit distance of run-length coded strings, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.137-143, April 1992, Kansas City, Missouri, United States [doi>10.1145/143559.143625]
• 14: M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, 1994.
• 15: Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter. Compressed text indexing and range searching. Technical Report Purdue University tech. report, CSD TR06-021, DEC 2006.
• 16: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 17: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 18: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 19: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 20: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 21: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 22: Valerio Freschi , Alessandro Bogliolo, Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism, Information Processing Letters, v.90 n.4, p.167-173, 31 May 2004 [doi>10.1016/j.ipl.2004.02.011]
• 23: S. W. Golomb. Run-length encodings. Trans. on Information Theory, 12:399--401, 1966.
• 24: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 25: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: experiments with compressing suffix arrays and applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 26: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 27: Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, A Database Index to Large Biological Sequences, Proceedings of the 27th International Conference on Very Large Data Bases, p.139-148, September 11-14, 2001
• 28: Robert W. Irving , Lorna Love, The suffix binary search tree and suffix AVL tree, Journal of Discrete Algorithms, v.1 n.5-6, p.387-408, October 2003 [doi>10.1016/S1570-8667(03)00034-0]
• 29: V. Makinen and G. Navarro. Dynamic entropy-compressed sequences and full-text indexes. In CMP, pages 306--317, 2006.
• 30: Veli Mäkinen , Gonzalo Navarro , Esko Ukkonen, Approximate Matching of Run-Length Compressed Strings, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.31-49, July 01-04, 2001
• 31: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 32: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 33: E. M. McCreight. Priority search trees. SIAM Journal, 14(2):257--276, 1985.
• 34: A. Moffat. Implementing the ppm data compression scheme. Trans. on Communications, 38(11):1917--1921, 1990.
• 35: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 36: Gonzalo Navarro, Regular expression searching on compressed text, Journal of Discrete Algorithms, v.1 n.5-6, p.423-443, October 2003 [doi>10.1016/S1570-8667(03)00036-4]
• 37: Mihai Păatraşcu , Erik D. Demaine, Tight bounds for the partial-sums problem, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 38: N. S. Prywes and H. J. Gray. The organization of a multilist-type associative memory. In Transactions on Communication and Electronics, pages 488--492, 1963.
• 39: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, SEQ: A Model for Sequence Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.232-239, March 06-10, 1995
• 40: Yusuke Shibata , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, Pattern Matching in Text Compressed by Using Antidictionaries, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.37-49, July 22-24, 1999
• 41: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 42: H. Tanaka and A. L. Garcia. Efficient run-length encodings. Trans. on Information Theory, 28(6):880--889, 1982.
• 43: Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical suffix tree construction, Proceedings of the Thirtieth international conference on Very large data bases, p.36-47, August 31-September 03, 2004, Toronto, Canada
• 44: T. Eilam-Tzoreff, Matching patterns in strings subject to multi-linear transformations, Theoretical Computer Science, v.60 n.3, p.231-254, September 1988 [doi>10.1016/0304-3975(88)90112-0]
• 45: Peter J. Varman , Rakesh M. Verma, An Efficient Multiversion Access Structure, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.391-409, May 1997 [doi>10.1109/69.599929]
• 46: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 47: P. Weiner. Linear pattern matching algorithms. In Symposium on Switching and Automata Theory, pages 1--11, 1973.
• 48: J. Ziv and A. Lempel. A universal algorithm for sequential data compression. Trans. on Information Theory, 23(3):337--343, 1977.
• 49: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. Trans. on Information Theory, 24(5):530--536, 1978.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process