Partitioned Posting Files: A Parallel Inverted File Structure for Information Retrieval.

Craig Stanfill: Partitioned Posting Files: A Parallel Inverted File Structure for Information Retrieval. SIGIR 1990: 413-428

@inproceedings{DBLP:conf/sigir/Stanfill90,
  author    = {Craig Stanfill},
  editor    = {Jean-Luc Vidick},
  title     = {Partitioned Posting Files: A Parallel Inverted File Structure
               for Information Retrieval},
  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     = {413-428},
  ee        = {db/conf/sigir/Stanfill90.html},
  crossref  = {DBLP:conf/sigir/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

This paper describes algorithms and data structures for applying a parallel computer to information retrieval. Previous work has described an implementation based on overlap encoded signatures. That system was limited by 1) the necessity of keeping the signatures in primary memory, and 2) the difficulties involved in implementing document-term weighting. Overcoming these limitations requires adapting the inverted index techniques used on serial machines. The most obvious adaptation, also previously described, suffers from the fact that data must be sent between processors at query-time. Since interprocessor communication is generally slower than local computation, this suggests that an algorithm which does not perform such communication might be faster. This paper presents a data structure, called a partitioned posting file, in which the interprocessor communication takes place at database-construction time, so that no data movement is needed at query-time. Algorithms for constructing the data structure are also described. Performance characteristics and storage overhead are established by benchmarking against a synthetic database.

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

Ophir Frieder, Hava T. Siegelmann: Multiprocessor Document Allocation: A Genetic Algorithm Approach. IEEE Trans. Knowl. Data Eng. 9(4): 640-642(1997)
Anthony Tomasic, Hector Garcia-Molina: Issues in Parallel Information Retrieval. IEEE Data Eng. Bull. 17(3): 41-49(1994)
Anthony Tomasic, Hector Garcia-Molina: Query Processing and Inverted Indices in Shared-Nothing Document Information Retrieval Systems. VLDB J. 2(3): 243-275(1993)
Anthony Tomasic, Hector Garcia-Molina: Caching and Database Scaling in Distributed Shard-Nothing Information Retrieval Systems. SIGMOD Conference 1993: 129-138

BibTeX

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