ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Interaction of Query Evaluation and Buffer Management for Information Retrieval.

Björn Þór Jónsson, Michael J. Franklin, Divesh Srivastava: Interaction of Query Evaluation and Buffer Management for Information Retrieval. SIGMOD Conference 1998: 118-129
@inproceedings{DBLP:conf/sigmod/JonssonFS98,
  author    = {Bj{\"o}rn TH{\'o}r J{\'o}nsson and
               Michael J. Franklin and
               Divesh Srivastava},
  editor    = {Laura M. Haas and
               Ashutosh Tiwary},
  title     = {Interaction of Query Evaluation and Buffer Management for Information
               Retrieval},
  booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
               on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-995-5},
  pages     = {118-129},
  ee        = {http://doi.acm.org/10.1145/276304.276316, db/conf/sigmod/JonssonFS98.html},
  crossref  = {DBLP:conf/sigmod/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The proliferation of the World Wide Web has brought information retrieval (IR) techniques to the forefront of search technology. To the average computer user, ``searching'' now means using IR-based systems for finding information on the WWW or in other document collections. IR query evaluation methods and workloads differ significantly from those found in database systems. In this paper, we focus on three such differences. First, due to the inherent fuzziness of the natural language used in IR queries and documents, an additional degree of flexibility is permitted in evaluating queries. Second, IR query evaluation algorithms tend to have access patterns that cause problems for traditional buffer replacement policies. Third, IR search is often an iterative process, in which a query is repeatedly refined and resubmitted by the user. Based on these differences, we develop two complementary techniques to improve the efficiency of IR queries: 1) Buffer-aware query evaluation, which alters the query evaluation process based on the current contents of buffers; and 2) Ranking-aware buffer replacement, which incorporates knowledge of the query processing strategy into replacement decisions. In a detailed performance study we show that using either of these techniques yields significant performance benefits and that in many cases, combining them produces even further improvements.

Copyright © 1998 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 DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ... Online Version (ACM WWW Account required): Full Text in PDF Format

ACM SIGMOD Anthology

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

Printed Edition

Laura M. Haas, Ashutosh Tiwary (Eds.): SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. ACM Press 1998, ISBN 0-89791-995-5 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 27(2), June 1998
Contents

Online Edition: ACM SIGMOD

[Abstract]
[Full Text (Postscript)]

References

[ABGM90]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bro95]
Eric W. Brown: Fast Evaluation of Structured Queries for Information Retrieval. SIGIR 1995: 30-38 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bro97]
...
[CD85]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CK97]
Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CR93]
Chung-Min Chen, Nick Roussopoulos: Adaptive Database Buffer Allocation Using Query Feedback. VLDB 1993: 342-353 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DFJ+96]
Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, Michael Tan: Semantic Data Caching and Replacement. VLDB 1996: 330-341 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EH84]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fal85]
Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fid91]
...
[FJK96]
Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fox92]
...
[Fra92]
...
[Har96]
...
[HHW97]
Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ink]
...
[JS94]
Theodore Johnson, Dennis Shasha: 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994: 439-450 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KK94]
Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KQCB94]
Jürgen Koenemann, Richard Quatrain, Colleen Cool, Nicholas J. Belkin: New Tools and Old Habits: The Interactive Searching Behavior of Expert Online Searches using INQUERY. TREC 1994: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MZ94]
Alistair Moffat, Justin Zobel: Fast Ranking in Limited Space. ICDE 1994: 428-437 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NFS91]
Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OOW93]
Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum: The LRU-K Page Replacement Algorithm For Database Disk Buffering. SIGMOD Conference 1993: 297-306 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Per94]
Michael Persin: Document Filtering for Fast Ranking. SIGIR 1994: 339-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PZSD96]
Michael Persin, Justin Zobel, Ron Sacks-Davis: Filtered Document Retrieval with Frequency-Sorted Indexes. JASIS 47(10): 749-764(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SA87]
Patricia Simpson, Rafael Alonso: Data Caching in Information Retrieval Systems. SIGIR 1987: 296-305 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SB88]
Gerard Salton, Chris Buckley: Term-Weighting Approaches in Automatic Text Retrieval. Inf. Process. Manage. 24(5): 513-523(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SB90]
...
[SS96]
Sunita Sarawagi, Michael Stonebraker: Reordering Query Execution in Tertiary Memory Databases. VLDB 1996: 156-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sto81]
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TF95]
Howard R. Turtle, James Flood: Query Evaluation: Strategies and Optimizations. Inf. Process. Manage. 31(6): 831-850(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TGM93a]
Anthony Tomasic, Hector Garcia-Molina: Caching and Database Scaling in Distributed Shard-Nothing Information Retrieval Systems. SIGMOD Conference 1993: 129-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TGM93b]
Anthony Tomasic, Hector Garcia-Molina: Performance of Inverted Indices in Distributed Text Document Retrieval Systems. PDIS 1993: 8-17 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tra95]
...
[Tur94]
Howard R. Turtle: Natural Language vs. Boolean Query Evaluation: A Comparison of Retrieval Performance. SIGIR 1994: 212-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VH97]
...
[WL93]
Wai Yee Peter Wong, Dik Lun Lee: Implementations of Partial Document Ranking Using Inverted Files. Inf. Process. Manage. 29(5): 647-669(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZMSD92]
Justin Zobel, Alistair Moffat, Ron Sacks-Davis: An Efficient Indexing Technique for Full Text Databases. VLDB 1992: 352-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:21:34 2010 by Michael Ley (ley@uni-trier.de)