Incremental updates of inverted lists for text document retrieval

ABSTRACT

With the proliferation of the world's “information highways” a renewed interest in efficient document indexing techniques has come about. In this paper, the problem of incremental updates of inverted lists is addressed using a new dual-structure index. The index dynamically separates long and short inverted lists and optimizes retrieval, update, and storage of each type of list. To study the behavior of the index, a space of engineering trade-offs which range from optimizing update time to optimizing query performance is described. We quantitatively explore this space by using actual data and hardware in combination with a simulation of an information retrieval system. We then describe the best algorithm for a variety of criteria.

REFERENCES

• 1: D. Cutting , J. Pedersen, Optimization for dynamic inverted index maintenance, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.405-411, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98245]
• 2: Samuel DeFazio. Full-text document retrieval benchmark. In Jim Gray, editor, The Benchmark Handbook }or Database and Transaction Processsng Systems, cha.pter 8. Morgan Kaufmann, second edition, 1993.
• 3: Christos Faloutsos , H. V. Jagadish, Hybrid Index Organizations for Text Databases, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.310-327, March 23-27, 1992
• 4: Christos Faloutsos , H. V. Jagadish, On B-Tree Indices for Skewed Distributions, Proceedings of the 18th International Conference on Very Large Data Bases, p.363-374, August 23-27, 1992
• 5: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: Donna Harman and Gerald Candela. Retrieving records from a gigabyte of text on a minicomputer using statistical ranking. Journal of the American Society }or Information Science, 41(8):581-589, 1990.
• 7: Donald E. Knuth. The Art of Computer Programmzng. Addison-Wesley, Reading, Massachusetts. 1973.
• 8: Katia Obraczka , Peter B. Danzig , Shih-Hao Li, Internet Resource Discovery Services, Computer, v.26 n.9, p.8-22, September 1993 [doi>10.1109/2.231277]
• 9: Kurt A. Shoens , Allen Luniewski , Peter M. Schwarz , James W. Stamos , Joachim Thomas, II, The Rufus System: Information Organization for Semi-Structured Data, Proceedings of the 19th International Conference on Very Large Data Bases, p.97-107, August 24-27, 1993
• 10: Kurt Shoens , Anthony Tomasic , Héctor García-Molina, Synthetic workload performance analysis of incremental updates, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.329-338, July 03-06, 1994, Dublin, Ireland
• 11: Anthony Tomasic , Hector Garcia-Molina , Kurt Shoens, Incremental Updates of Inverted Lists for Text Document Retrieval, Stanford University, Stanford, CA, 1993
• 12: George Kingsley Zipf. Human Behavior and the Prznciple of Least Effort. Addison-Wesley Press, 1949.
• 13: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

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

General Terms:
Algorithms, Design, Documentation, Experimentation, Performance