An experimental study of an opportunistic index

ABSTRACT

The size of electronic data is currently growing at a faster rate than computer memory and disk storage capacities. For this reason compression appears always as an attractive choice, if not mandatory. However space overhead is not the only resource to be optimized when managing large data collections; in fact data turn out to be useful only when properly indexed to support search operations that efficiently extract the user-requested information.

Approaches to combine compression and indexing techniques are nowadays receiving more and more attention. A first step towards the design of a compressed full-text index achieving guaranteed performance in the worst case has been recently done in [10]. This index combines the compression algorithm proposed by Burrows and Wheeler [5] with the suffix array data structure [16]. The index is opportunistic in that it takes advantage of the compressibility of the input data by decreasing the space occupancy at no significant asymptotic slowdown in the query performance.

In this paper we present an implementation of this index and perform an extensive set of experiments on various text collections. The experiments show that our index is compact (its space occupancy is close to the one achieved by the best known compressors), it is fast in counting the number of pattern occurrences, and the cost of their retrieval is reasonable when they are few (i.e., in case of a selective query). In addition, our experiments show that the FM-index is flexible in that it is possible to trade space occupancy for search time by choosing the amount of auxiliary information stored into it.

REFERENCES

• 1: Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Journal of Computer and System Sciences, v.52 n.2, p.299-307, April 1996 [doi>10.1006/jcss.1996.0023]
• 2: R. Arnold and T. Bell. The Canterbury corpus home page. http://corpus.canterbury.ac.nz.
• 3: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 4: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
• 6: Maxime Crochemore , Filippo Mignosi , Antonio Restivo , Sergio Salemi, Text Compression Using Antidictionaries, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.261-270, July 11-15, 1999
• 7: John J. Darragh , John G. Cleary , Ian H. Witten, Bonsai: a compact representation of trees, Software—Practice & Experience, v.23 n.3, p.277-291, March 1993 [doi>10.1002/spe.4380230305]
• 8: M. Farach and M. Thorup. String matching in Lempel- Ziv compressed strings. Algorithmica, 20(4):388-404, 1998.
• 9: P. Fenwick. The Burrows-Wheeler transform for block sorting text compression: principles and improvements. The Computer Journal, 39(9):731-740, 1996.
• 10: 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
• 11: G. H. Gonnet, R. A. Baeza-Yates, and T. Snider. Information Retrieval: Data Structures and Algorithms, chapter 5, pages 66-82. Prentice-Hall, 1992.
• 12: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 13: D. K. Harman, editor. Proc. TREC Text Retrieval Conference. National Institute of Standards, 1992. Special Pubblication 500-207.
• 14: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 15: Veli Mäkinen, Compact Suffix Array, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.305-319, June 21-23, 2000
• 16: 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]
• 17: U. Manber and S. Wu. GLIMPSE: A tool to search through entire file systems. In Proceedings of the USENIX Winter 1994 Technical Conference, pages 23- 32, 1994.
• 18: E. Moura, G. Navarro, and N. Ziviani. Indexing compressed text. In N. Ziviani, R. Baeza-Yates, and K. Guimaraes, editors, Proceedings of the 4th South American Workshop on String Processing. Carleton University Press, 1997.
• 19: Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast searching on compressed text allowing errors, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291013]
• 20: J. I. Munro. Succinct data structures. In Proceeding of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science. Springer- Verlag LNCS n. 1738, 1999.
• 21: Kunihiko Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array, Proceedings of the 11th International Conference on Algorithms and Computation, p.410-421, December 18-20, 2000
• 22: J. Seward. The nzlP2 home page, 1997. http ://sourceware. cygnus, com/bzip2/index, html.
• 23: 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
• 24: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 25: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Experimentation, Management, Measurement, Performance, Theory