BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-93-1
       ENTRY:: December 08, 1993
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Incremental Updates of Inverted Lists for Text Document
               Retrieval
        TYPE:: Technical Note
      AUTHOR:: Tomasic, Anthony
      AUTHOR:: Garcia-Molina, Hector
      AUTHOR:: Shoens, Kurt
       PAGES:: 44
    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 data structure. The index
               dynamically separates long and short inverted lists and
               optimizes the 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.
       NOTES:: [Adminitrivia V1/Prg/19931208]
         END:: STAN//CS-TN-93-1