Optimizations for Dynamic Inverted Index Maintenance.

Douglas R. Cutting, Jan O. Pedersen: Optimizations for Dynamic Inverted Index Maintenance. SIGIR 1990: 405-411

@inproceedings{DBLP:conf/sigir/CuttingP90,
  author    = {Douglas R. Cutting and
               Jan O. Pedersen},
  editor    = {Jean-Luc Vidick},
  title     = {Optimizations for Dynamic Inverted Index Maintenance},
  booktitle = {SIGIR'90, 13th International Conference on Research and Development
               in Information Retrieval, Brussels, Belgium, 5-7 September 1990,
               Proceedings},
  publisher = {ACM},
  year      = {1990},
  isbn      = {0-89791-408-2},
  pages     = {405-411},
  ee        = {db/conf/sigir/CuttingP90.html},
  crossref  = {DBLP:conf/sigir/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

Copyright © 1990 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

CDROM Version: Load the CDROM "Volume 2 Issue 3, SIGIR, DASFAA'97, OODBS'86" 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/An2-3 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

BibTeX

Printed Edition

Jean-Luc Vidick (Ed.): SIGIR'90, 13th International Conference on Research and Development in Information Retrieval, Brussels, Belgium, 5-7 September 1990, Proceedings. ACM 1990, ISBN 0-89791-408-2
Contents BibTeX

Online Edition: ACM Digital Library

Citation page

Referenced by

Narayanan Shivakumar, Hector Garcia-Molina: Wave-Indices: Indexing Evolving Databases. SIGMOD Conference 1997: 381-392
Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen: Concurrency Control in B-Trees with Batch Updates. IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
Charles L. Viles, James C. French: On the Update of Term Weights in Dynamic Information Retrieval Systems. CIKM 1995: 167-174
Eric W. Brown, James P. Callan, W. Bruce Croft: Fast Incremental Indexing for Full-Text Information Retrieval. VLDB 1994: 192-202
Anthony Tomasic, Hector Garcia-Molina, Kurt A. Shoens: Incremental Updates of Inverted Lists for Text Document Retrieval. SIGMOD Conference 1994: 289-300

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]