Optimization for dynamic inverted index maintenance

ABSTRACT

For free-text search over rapidly evolving corpora, dynamic update of inverted indices is a basic requirement. B-trees are an effective tool in implementing such indices. The Zipfian distribution of postings suggests space and time optimizations unique to this task. In particular, we present two novel optimizations, merge update, which performs better than straight forward block update, and pulsing which significantly reduces space requirements without sacrificing performance.

REFERENCES

• 1: R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. A cta lnforrnatiea, 1:173-189, 1972.
• 2: D. Harmon , G. Candela, A very fast prototype retrieval system using statistical ranking, ACM SIGIR Forum, v.23 n.3-4, p.100-110, Spring 1989 [doi>10.1145/74697.74703]
• 3: H.S. Heaps. Storage analysis of a compression coding for a document database. 1NFOR, I0(i):47-61, February 1972.
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: 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
• 6: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 7: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 8: G. K. Zipf. Human BetLavior and the Principle of Least EJ3ort. Addison-Wesley, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Composite structures**

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

General Terms:
Algorithms, Design, Experimentation, Performance