Self-indexing inverted files for fast text retrieval

ABSTRACT

Query-processing costs on large text databases are dominated by the need to retrieve and scan the inverted list of each query term. Retrieval time for inverted lists can be greatly reduced by the use of compression, but this adds to the CPU time required. Here we show that the CPU component of query response time for conjunctive Boolean queries and for informal ranked queries can be similarly reduced, at little cost in terms of storage, by the inclusion of an internal index in each compressed inverted list. This method has been applied in a retrieval system for a collection of nearly two million short documents. Our experimental results show that the self-indexing strategy adds less than 20% to the size of the compressed inverted file, which itself occupies less than 10% of the indexed text, yet can reduce processing time for Boolean queries of 5-10 terms to under one fifth of the previous cost. Similarly, ranked queries of 40-50 terms can be evaluated in as little as 25% of the previous time, with little or no loss of retrieval effectiveness.

REFERENCES

• 1: Timothy C. Bell , Alistair Moffat , Craig G. Nevill-Manning , Ian H. Witten , Justin Zobel, Data compression in full-text retrieval systems, Journal of the American Society for Information Science, v.44 n.9, p.508-531, Oct. 1993 [doi>10.1002/(SICI)1097-4571(199310)44:9<508::AID-ASI2>3.0.CO;2-A]
• 2: BOOKSTEIN, A., KLEIN,S.T.,AND RAITA, T. 1992. Model based concordance compression. In Proceedings of the IEEE Data Compression Conference, J. A. Storer and M. Cohn, Eds. IEEE Computer Society Press, Los Alamitos, Calif., 82-91.
• 3: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 4: Y. Choueka , A. Fraenkel , S. Klein , E. Segal, Improved techniques for processing queries in full-text systems, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.306-315, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42039]
• 5: Y. Choueka , A. S. Fraenkel , S. T. Klein, Compression of concordances in full-text retrieval systems, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.597-612, May 1988, Grenoble, France [doi>10.1145/62437.62500]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: W. Bruce Croft , Pasquale Savino, Implementing ranking strategies using text signatures, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.42-62, Jan. 1988 [doi>10.1145/42279.45947]
• 8: ELIAS, P. 1975. Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory IT-21, 2 (Mar.), 194-203.
• 9: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
• 10: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 11: Chris Faloutsos, Signature files: design and performance comparison of some signature extraction methods, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.63-82, May 1985, Austin, Texas, United States
• 12: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 13: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 14: FRAENKEL,A.S.AND KLEIN, S. T. 1985. Novel compression of sparse bit-strings:Prelimi-nary report. In Combinatorial Algorithms on Words, A. Apostolico and Z. Galil, Eds. NATO ASI Series F, vol. 12. Springer-Verlag, Berlin, 169-183.
• 15: GALLAGER,R.G.AND VAN VOORHIS, D. C. 1975. Optimal source codes for geometrically distributed integer alphabets. IEEE Trans. Inf. Theory IT-21, 2 (Mar.), 228-230.
• 16: GOLOMB, S. W. 1966. Run-length encodings. IEEE Trans. Inf. Theory IT-12, 3 (July), 399-401.
• 17: HARMAN, D. K., Ed. 1992a. Proceedings of TREC Text Retrieval Conference (Washington, D.C., Nov.). National Institute of Standards Special Publication 500-207. NIST, Washing-ton, D.C.
• 18: Donna Harman, Ranking algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 19: HARMAN,D.K.AND CANDELA, G. 1990. Retrieving records from a gigabyte of text on a mini-computer using statistical ranking. J. Am. Soc. Inf. Sci. 41, 8, 581-589.
• 20: HWANG,F.K.AND LIN, S. 1972. A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput. 1, 1, 31-39.
• 21: KENT,A.J.,SACKS-DAVIS, R., AND RAMAMOHANARAO, K. 1990. A signature file scheme based on multiple organizations for indexing very large text databases. J. Am. Soc. Inf. Sci. 41, 7, 508-534.
• 22: Shmuel T. Klein , Abraham Bookstein , Scott Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.230-245, July 1989 [doi>10.1145/65943.65946]
• 23: Gordon Linoff , Craig Stanfill, Compression of indexes with full positional information in very large text databases, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.88-95, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160699]
• 24: LOVINS, J. B. 1968. Development of a stemming algorithm. Mech. Transl. Comput. 11, 1-2, 22-31.
• 25: Dario Lucarella, A document retrieval system based on nearest neighbour searching, Journal of Information Science, v.14 n.1, p.25-33, January 1988 [doi>10.1177/016555158801400104]
• 26: MCDONELL, K. J. 1977. An inverted index implementation. Comput. J. 20, 1, 116-123.
• 27: Alistair Moffat , Justin Zobel, Parameterised compression for sparse bitmaps, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.274-285, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133210]
• 28: MOFFAT, A., ZOBEL, J., AND KLEIN, S. T. 1995. Improved inverted file processing for large text databases. In Proceedings of the 6th Australasian Database Conference, R. Sacks-Davis and J. Zobel, Eds. 162-171.
• 29: Alistair Moffat , Justin Zobel , Ron Sacks-Davis, Memory efficient ranking, Information Processing and Management: an International Journal, v.30 n.6, p.733-744, 1994 [doi>10.1016/0306-4573(94)90002-7]
• 30: R. Sacks-Davis , A. Kent , K. Ramamohanarao, Multikey access methods based on superimposed coding techniques, ACM Transactions on Database Systems (TODS), v.12 n.4, p.655-696, Dec. 1987 [doi>10.1145/32204.32222]
• 31: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 32: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 33: 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
• 34: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992
• 35: Justin Zobel , Alistair Moffat , Ross Wilkinson , Ron Sacks-Davis, Efficient retrieval of partial documents, Information Processing and Management: an International Journal, v.31 n.3, p.361-377, May-June 1995

INDEX TERMS

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

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.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design, Performance