Interaction of query evaluation and buffer management for information retrieval

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.

REFERENCES

• ABGM90: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• Bro95: Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215329]
• Bro97: K.P. Brown. DBGuide industrial presentation. ACM SIG- MOD Conf., Tucson, AZ, 1997.
• CD85: H.-T. Chou and D.J. DeWitt. An evaluation of buffer management strategies for relational database systems. Proc. of the VLDB Conf., Stockholm, Sweden, 1985.
• CK97: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• CR93: Chung-Min Chen , Nick Roussopoulos, Adaptive Database Buffer Allocation Using Query Feedback, Proceedings of the 19th International Conference on Very Large Data Bases, p.342-353, August 24-27, 1993
• DFJ+96: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• EH84: Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
• Fal85: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• Fid91: R. Fidel. Searchers' selection of search keys: III. Searching styles. Journal of the American Society of lnformation Science, 42(7), 1991.
• FJK96: Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.149-160, June 04-06, 1996, Montreal, Quebec, Canada
• Fox92: Christopher Fox, Lexical analysis and stoplists, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Fra92: W. B. Frakes, Stemming algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Har96: D. Harman. Overview of the fourth Text REtrieval Conference (TREC-4). The fourth Text REtrieval Conference (TREC- 4), NIST, Gaithersburg, MD, 1996.
• HHW97: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• Ink: Inktomi. The lnktomi Technology Behind Hotbot. See http ://www.inktomi.com/Tech/CoupClustWhitePap. html.
• JS94: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• KK94: Alfons Kemper , Donald Kossmann, Dual-Buffering Strategies in Object Bases, Proceedings of the 20th International Conference on Very Large Data Bases, p.427-438, September 12-15, 1994
• KQCB94: J. Koenemann, R. Quatrain, C. Cool, and N.J. Belkin~ New tools and old habits: The interactive searching behavior of expert online searchers using INQUERY. The Third Text REtrieval Conference (TREC-3), NIST, Gaithersburg, MD, 1994.
• MZ94: Alistair Moffat , Justin Zobel, Fast Ranking in Limited Space, Proceedings of the Tenth International Conference on Data Engineering, p.428-437, February 14-18, 1994
• NFS91: Raymond Ng , Christos Faloutsos , Timos Sellis, Flexible buffer allocation based on marginal gains, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.387-396, May 29-31, 1991, Denver, Colorado, United States
• OOW93: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• Per94: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• PZSD96: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• SA87: R Simpson and R. Alonso. Data caching in information retrieval systems. Proc. ACM SIGIR Conf., New Orleans, LA, 1987.
• SB88: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• SB90: G. Salton and C. Buckley. Improving retrieval performance by relevance feedback. Journal of the American Society of Information Science, 41 (4), 1990.
• SS96: Sunita Sarawagi , Michael Stonebraker, Reordering Query Execution in Tertiary Memory Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.156-167, September 03-06, 1996
• Sto81: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• TF95: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]
• TGM93a: Anthony Tomasic , Hector Garcia-Molina, Caching and database scaling in distributed shared-nothing information retrieval systems, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.129-138, May 25-28, 1993, Washington, D.C., United States
• TGM93b: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• Tra95: Transaction Processing Performance Council (TPC), 777 N. First Street, Suite 600, San Jose, CA 95112, USA. TPC Benchmark D (Decision Support), May 1995.
• Tur94: Howard Turtle, Natural language vs. Boolean query evaluation: a comparison of retrieval performance, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.212-220, July 03-06, 1994, Dublin, Ireland
• VH97: E.M. Voorhees and D. Harman. Overview of the fifth Text REtrieval Conference (TREC-5). The fifth Text REtrieval Conference (TREC-5), NIST, Gaithersburg, MD, 1997.
• WL93: Wai Yee Peter Wong , Dik Lun Lee, Implementations of partial document ranking using inverted files, Information Processing and Management: an International Journal, v.29 n.5, p.647-669, Sept.-Oct. 1993 [doi>10.1016/0306-4573(93)90085-R]
• ZMSD92: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Documentation, Experimentation, Measurement