Optimized Query Execution in Large Search Engines with Global Page Ordering Xiaohui Long and Torsten Suel   View Paper (PDF)   Return to Query Processing in the Web (Session A3) Abstract Large web search engines have to answer thou- sands of queries per second with interactive re- sponse times. A major factor in the cost of exe- cuting a query is given by the lengths of the in- verted lists for the query terms, which increase with the size of the document collection and are often in the range of many megabytes. To address this issue, IR and database researchers have pro- posed pruning techniques that compute or approx- imate term-based ranking functions without scan- ning over the full inverted lists. Over the last few years, search engines have in- corporated new types of ranking techniques that exploit aspects such as the hyperlink structure of the web or the popularity of a page to obtain im- proved results. We focus on the question of how such techniques can be efficiently integrated into query processing. In particular, we study pruning techniques for query execution in large engines in the case where we have a global ranking of pages, as provided by Pagerank or any other method, in addition to the standard term-based approach. We describe pruning schemes for this case and eval- uate their efficiency on an experimental cluster- based search engine with 120 million web pages. Our results show that there is significant potential benefit in such techniques. ©2004 Association for Computing Machinery