III: Small: Efficient Query Processing in Large Search Engines

目前，最大的网络搜索引擎每天要接收数以亿计的查询，这些查询需要在几分之一秒内从数百亿的网络文档集合中得到回答。为了处理所有这些查询，搜索引擎消耗越来越多的硬件和能源资源。这个项目的重点是开发新的算法、索引结构和其他软件技术，用于扩展搜索引擎中的查询处理，也就是说，这些技术允许使用更少的硬件和能源在更大的数据集上更快地执行查询。本项目的研究活动主要集中在三个方面。首先，该项目研究了如何通过改进的索引压缩技术减少索引大小和访问时间。其次，新的早期终止技术的工作考虑了如何在不彻底遍历查询词的索引结构的情况下计算查询的顶部结果，对于简单的排序函数，如BM25或cos，以及当前web搜索引擎使用的具有许多特性的更复杂的函数。最后，该项目探讨了信息检索（IR）系统中查询优化的一般技术，受到数据库系统中查询优化器的大量工作的启发。网络搜索引擎是一个价值数十亿美元的产业，也是互联网的重要组成部分。该项目产生的技术有望通过降低大规模搜索服务的硬件成本和能源消耗而使该行业受益。结果将通过主要会议和期刊上的出版物、会议上的教程、软件库的分发、对现有软件工具（如Lucene）的贡献来传播。该项目为研究生和本科生提供了研究和教育机会，并为他们以后在公司、研究实验室或大学的工作做好准备。网站（http://cis.poly.edu/westlab/queryproc/）提供了关于这个项目的更多信息。

The largest web search engines now receive hundreds of millions of queries per day that need to be answered in fractions of a second on collections of tens of billions of web documents. In order to process all these queries, search engines consume increasing amounts of hardware and energy resources. This project focuses on developing new algorithms, index structures, and other software techniques for scaling query processing in search engines, that is, techniques that allow queries to be executed faster and on larger data sets using fewer hardware and energy resources. Research activities in this project focus on three main approaches. First, the project studies how index size and access time can be reduced through improved index compression techniques. Second, work on new early termination techniques considers how the top results for a query can be computed without exhaustive traversal of the index structures for the query terms, for simple ranking functions such as BM25 or Cosine, and for the more complex functions with many features used by current web search engines. Finally, the project explores general techniques for query optimization in information retrieval (IR) systems, inspired by the significant body of work on query optimizers in database systems. Web search engines are a multi-billion dollar industry and a crucial component of the internet. Techniques resulting from this project are expected to benefit this industry by reducing the hardware cost and energy consumption of large-scale search services. Results will be disseminated through publications in major conferences and journals, tutorials at conferences, distribution of software libraries, contributions to existing software tools such as Lucene. This project provides research and educational opportunities for graduate and undergraduate students and prepare them for later work at companies, research labs, or universities. Web site (http://cis.poly.edu/westlab/queryproc/) provides more information about this project.