Indexing time vs. query time: trade-offs in dynamic information retrieval systems

ABSTRACT

We examine issues in the design of fully dynamic information retrieval systems supporting both document insertions and deletions. The two main components of such a system, index maintenance and query processing, affect each other, as high query performance is usually paid for by additional work during update operations. Two aspects of the system -- incremental updates and garbage collection for delayed document deletions -- are discussed, with a focus on the respective indexing vs. query performance trade-offs. Depending on the relative number of queries and update operations, different strategies lead to optimal overall performance.

REFERENCES

• 1: T. Chiueh and L. Huang. Efficient Real-Time Index Updates in Text Retrieval Systems. Technical report, Stony Brook, New York, USA, August 1998.
• 2: T. J. Gibson and E. L. Miller. Long-Term File Activity Patterns in a UNIX Workstation Environment. In Proceedings of the 15th IEEE Symposium on Mass Storage Systems, pages 355--371, March 1998.
• 3: Nicholas Lester , Justin Zobel , Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th Australasian conference on Computer science, p.15-23, January 01, 2004, Dunedin, New Zealand
• 4: Anthony Tomasic , Héctor García-Molina , Kurt Shoens, Incremental updates of inverted lists for text document retrieval, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Experimentation, Performance