Incremental Updates of Inverted Lists for Text Document Retrieval.

Anthony Tomasic, Hector Garcia-Molina, Kurt A. Shoens: Incremental Updates of Inverted Lists for Text Document Retrieval. SIGMOD Conference 1994: 289-300

@inproceedings{DBLP:conf/sigmod/TomasicGS94,
  author    = {Anthony Tomasic and
               Hector Garcia-Molina and
               Kurt A. Shoens},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Incremental Updates of Inverted Lists for Text Document Retrieval},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {289-300},
  ee        = {http://doi.acm.org/10.1145/191839.191896, db/conf/sigmod/TomasicGS94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 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.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994

, SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1362 KB]

References

[1]: Douglas R. Cutting, Jan O. Pedersen: Optimizations for Dynamic Inverted Index Maintenance. SIGIR 1990: 405-411
[2]: ...
[3]: Christos Faloutsos, H. V. Jagadish: Hybrid Index Organizations for Text Databases. EDBT 1992: 310-327
[4]: Christos Faloutsos, H. V. Jagadish: On B-Tree Indices for Skewed Distributions. VLDB 1992: 363-374
[5]: William B. Frakes, Ricardo A. Baeza-Yates (Eds.): Information Retrieval: Data Structures & Algorithms. Prentice-Hall 1992, ISBN 0-13-463837-9
Contents
[6]: ...
[7]: ...
[8]: Katia Obraczka, Peter B. Danzig, Shih-Hao Li: Internet Resource Discovery Services. IEEE Computer 26(9): 8-22(1993)
[9]: Kurt A. Shoens, Allen Luniewski, Peter M. Schwarz, James W. Stamos, Joachim Thomas II: The Rufus System: Information Organization for Semi-Structured Data. VLDB 1993: 97-107
[10]: Kurt A. Shoens, Anthony Tomasic, Hector Garcia-Molina: Synthetic Workload Performance Analysis of Incremental Updates. SIGIR 1994: 329-338
[11]: ...
[12]: George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
[13]: Justin Zobel, Alistair Moffat, Ron Sacks-Davis: An Efficient Indexing Technique for Full Text Databases. VLDB 1992: 352-362