Article

Improving Web search efficiency via a locality based static pruning method

Authors:

Edleno S. de Moura,

Célia F. dos Santos,

Daniel R. Fernandes,

Altigran S. Silva,

Mario A. NascimentoAuthors Info & Claims

WWW '05: Proceedings of the 14th international conference on World Wide Web

Pages 235 - 244

https://doi.org/10.1145/1060745.1060783

Published: 10 May 2005 Publication History

Abstract

The unarguably fast, and continuous, growth of the volume of indexed (and indexable) documents on the Web poses a great challenge for search engines. This is true regarding not only search effectiveness but also time and space efficiency. In this paper we present an index pruning technique targeted for search engines that addresses the latter issue without disconsidering the former. To this effect, we adopt a new pruning strategy capable of greatly reducing the size of search engine indices. Experiments using a real search engine show that our technique can reduce the indices' storage costs by up to 60% over traditional lossless compression methods, while keeping the loss in retrieval precision to a minimum. When compared to the indices size with no compression at all, the compression rate is higher than 88%, i.e., less than one eighth of the original size. More importantly, our results indicate that, due to the reduction in storage overhead, query processing time can be reduced to nearly 65% of the original time, with no loss in average precision. The new method yields significative improvements when compared against the best known static pruning method for search engine indices. In addition, since our technique is orthogonal to the underlying search algorithms, it can be adopted by virtually any search engine.

References

[1]

R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999.

Digital Library

[2]

D. Bahle, H. E. Williams, and J. Zobel. Efficient phrase querying with and auxiliary index. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 215--221, 2002.

Digital Library

[3]

T. C. Bell, J. G. Cleary, and I. H. Witten. Text compression. Prentice Hall, 1990.

Digital Library

[4]

P. P. Calado, E. S. de~Moura, B. Ribeiro-Neto, I. Silva, and N. Ziviani. Local versus global link information in the web. ACM Transactions on Information Systems (TOIS), 2003.

Digital Library

[5]

D. Carmel, D. Cohen, R. Fagin, E. Farchi, M. Herscovici, Y. S. Maarek, and A. Soffer. Static index pruning for information retrieval systems. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43--50, New Orleans, Louisiana, USA, September 2001.

Digital Library

[6]

W. B. Croft, H. R. Turtle, and D. D. Lewis. The use of phrases and structured queries in information retrieval. In Proceedings of the 14th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 32--45, 1991.

Digital Library

[7]

E. S. de~Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Fast and flexible word searching on compressed text. ACM Transactions on Information Systems(ACM TOIS), 18(2):113--139, April 2000.

Digital Library

[8]

S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of American Society for Information Science, 41(6), 1990.

[9]

R. Fagin, R. Kumar, and D. Sivakumar. Comparing top k lists. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 28--36, 2003.

Digital Library

[10]

D. Fetterly, M. Manasse, M. Najork, and J. Wiener. A large-scale study of the evolution of web page. In Proceedings of the 12th International World Wide Web Conference, pages 669--678, May 2003.

Digital Library

[11]

D. Hawking, N. Craswell, and P. B. Thistlewaite. Overview of TREC-7 very large collection track. In The Seventh Text REtrieval Conference (TREC-7), pages 91--104, Gaithersburg, Maryland, USA, November 1998.

[12]

D. Hawking, N. Craswell, P. B. Thistlewaite, and D. Harman. Results and challenges in web search evaluation. Computer Networks, 31(11--16):1321--1330, May 1999. Also in Proceedings of the 8th International World Wide Web Conference.

Digital Library

[13]

D. Hawking, E. Voorhees, P. Bailey, and N. Craswell. Overview of trec-8 web track. In Proc. of TREC-8, pages 131--150, Gaithersburg MD, November 1999.

[14]

J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 668--677, San Francisco, California, USA, January 1998.

Digital Library

[15]

L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Agarwal. Dynamic maintenance of web indexes using landmarks. In Proceedings of the 12th International World Wide Web Conference, pages 102--111, May 2003.

Digital Library

[16]

G. Navarro, E. S. de~Moura, M. Neubert, N. Ziviani, and R. Baeza-Yates. Fast and flexible word searching on compressed text. Information Retrieval Journal, 3(1):49--77, 2000.

Digital Library

[17]

M. Persin, J. Zobel, and R. Sacks-Davis. Filtered document retrieval with frequency-sorted indexes. Journal of the American Society of Information Science, 47(10):749--764, Oct. 1996.

Digital Library

[18]

G. Salton and M. J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1st edition, 1983.

Digital Library

[19]

P. C. Saraiva, E. S. Moura, N. Ziviani, B. Ribeiro-Neto, W. Meira, and R. L. C. Fonseca. Rank-preserving two-level caching for scalable search engines. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 51--58, New Orleans, September 2001.

Digital Library

[20]

I. Witten, A. Moffat, and T. Bell. Managing Gigabytes. Morgan Kaufmann Publishers, New York, second edition, 1999.

Cited By

Chang XMishra DMacdonald CMacAvaney SHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Neural Passage Quality Estimation for Static PruningProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657765(174-185)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657765
Altin SBaeza-Yates RCambazoglu B(2020)Pre-indexing Pruning StrategiesString Processing and Information Retrieval10.1007/978-3-030-59212-7_13(177-193)Online publication date: 17-Sep-2020
https://doi.org/10.1007/978-3-030-59212-7_13
Rodriguez JSuel T(2018)Exploring Size-Speed Trade-Offs in Static Index Pruning2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8622177(1093-1100)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8622177
Show More Cited By

Index Terms

Improving Web search efficiency via a locality based static pruning method
1. Information systems
  1. Information retrieval

Recommendations

Locality-Based pruning methods for web search

This article discusses a novel approach developed for static index pruning that takes into account the locality of occurrences of words in the text. We use this new approach to propose and experiment on simple and effective pruning methods that allow a ...
Identifying popular search goals behind search queries to improve web search ranking
AIRS'11: Proceedings of the 7th Asia conference on Information Retrieval Technology

Web users usually have a certain search goal before they submit a search query. However, many laypersons can't transform their search goals into suitable queries. Thus, understanding original search goals behind a query is very important for search ...
Improving Ranking Consistency for Web Search by Leveraging a Knowledge Base and Search Logs
CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

In this paper, we propose a new idea called ranking consistency in web search. Relevance ranking is one of the biggest problems in creating an effective web search system. Given some queries with similar search intents, conventional approaches typically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '05: Proceedings of the 14th international conference on World Wide Web

May 2005

781 pages

ISBN:1595930469

DOI:10.1145/1060745

Conference Chairs:
Allan Ellis
Southern Cross University
,
Tatsuya Hagino
Keio University

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
691
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chang XMishra DMacdonald CMacAvaney SHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Neural Passage Quality Estimation for Static PruningProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657765(174-185)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657765
Altin SBaeza-Yates RCambazoglu B(2020)Pre-indexing Pruning StrategiesString Processing and Information Retrieval10.1007/978-3-030-59212-7_13(177-193)Online publication date: 17-Sep-2020
https://doi.org/10.1007/978-3-030-59212-7_13
Rodriguez JSuel T(2018)Exploring Size-Speed Trade-Offs in Static Index Pruning2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8622177(1093-1100)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8622177
De Moura ECristo M(2018)Inverted FilesEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_1136(2037-2041)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_1136
De Moura ECristo M(2017)Inverted FilesEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_1136-2(1-5)Online publication date: 16-Oct-2017
https://doi.org/10.1007/978-1-4899-7993-3_1136-2
Jiang WRodriguez JSuel T(2016)Improved methods for static index pruning2016 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2016.7840661(686-695)Online publication date: Dec-2016
https://doi.org/10.1109/BigData.2016.7840661
Cambazoglu BBaeza-Yates R(2015)Scalability Challenges in Web Search EnginesSynthesis Lectures on Information Concepts, Retrieval, and Services10.2200/S00662ED1V01Y201508ICR0457:6(1-138)Online publication date: 29-Dec-2015
https://doi.org/10.2200/S00662ED1V01Y201508ICR045
Chen RLee CCroft WAllan JCroft Bde Vries AZhai C(2015)On Divergence Measures and Static Index PruningProceedings of the 2015 International Conference on The Theory of Information Retrieval10.1145/2808194.2809472(151-160)Online publication date: 27-Sep-2015
https://dl.acm.org/doi/10.1145/2808194.2809472
Kulkarni ACallan J(2015)Selective SearchACM Transactions on Information Systems10.1145/273803533:4(1-33)Online publication date: 23-Apr-2015
https://dl.acm.org/doi/10.1145/2738035
Dimond JSanders P(2015)Faster Exact Search Using Document ClusteringProceedings of the 22nd International Symposium on String Processing and Information Retrieval - Volume 930910.1007/978-3-319-23826-5_1(1-12)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-23826-5_1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents