Article

A Study of the Impact of Index Updates on Distributed Query Processing for Web Search

Authors:

Charalampos Sarigiannis,

Vassilis Plachouras,

Ricardo Baeza-YatesAuthors Info & Claims

ECIR '09: Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval

Pages 595 - 602

https://doi.org/10.1007/978-3-642-00958-7_55

Published: 18 April 2009 Publication History

Abstract

Query processing in Web search engines today is mainly performed within a single site or data center, which is required to scale as the Web grows and users require fast answers to their queries. Constraints in the size and cost of data centers, however, may limit the scalability of search engines. Multi-site search engines that perform distributed query processing represent one way to overcome such constraints. Each site processes locally as many queries as possible, keeping latency low without contacting remote sites. Forwarding a query to remote sites depends on the document collection of remote sites. Multi-site search engines pose several new challenges. When a site updates its index, it has to inform other sites. The updates, however, are not instantaneous due to the volume of data exchanged or possible network failures. During the period of time that there are index inconsistencies across sites, queries may not be forwarded optimally. In this work, we investigate the impact of index inconsistencies on a distributed query processing algorithm, when there are index updates, and we observe that delayed index information propagation reduces the effectiveness of query processing, because queries are less likely to be routed optimally.

References

[1]

AllTheWeb search engine, http://www.alltheweb.com

Google Scholar

[2]

Baeza-Yates, R., Castillo, C., Junqueira, F., Plachouras, V., Silvestri, F.: Challenges in distributed information retrieval. In: 23rd ICDE (2007)

Google Scholar

[3]

Baeza-Yates, R., Gionis, A., Junqueira, F., Plachouras, V., Telloli, L.: On the feasiblity of multi-site Web search engines (2008) (submitted for reviewing)

Google Scholar

[4]

Barroso, L.A., Dean, J., Hölzle, U.: Web search for a planet: The google cluster architecture. IEEE Micro. 23(2), 22-28 (2003)

Crossref

Google Scholar

[5]

Callan, J.: Distributed Information Retrieval. In: Croft, W.B. (ed.) Advances in Information Retrieval, pp. 127-150. Kluwer Academic Publishers, Dordrecht (2000)

Google Scholar

[6]

Douglis, F., Feldmann, A., Krishnamurthy, B., Mogul, J.C.: Rate of change and other metrics: a live study of the world wide web. In: 1st USITS (1997)

Crossref

Google Scholar

[7]

D'Souza, D., Thom, J.A., Zobel, J.: Collection selection for managed distributed document databases. Inf. Process. Manage. 40(3), 527-546 (2004)

Crossref

Google Scholar

[8]

Fetterly, D., Manasse, M., Najork, M., Wiener, J.L.: A large-scale study of the evolution of web pages. Softw. Pract. Exper. 34(2), 213-237 (2004)

Crossref

Google Scholar

[9]

Ntoulas, A., Cho, J.: Pruning policies for two-tiered inverted index with correctness guarantee. In: 30th SIGIR Conference, pp. 191-198 (2007)

Crossref

Google Scholar

[10]

Ntoulas, A., Cho, J., Olston, C.: What's new on the web?: the evolution of the web from a search engine perspective. In: 13th WWW, pp. 1-12 (2004)

Crossref

Google Scholar

[11]

Puppin, D., Silvestri, F., Perego, R., Baeza-Yates, R.: Load-balancing and caching for collection selection architectures. In: 2nd INFOSCALE, pp. 1-10 (2007)

Crossref

Google Scholar

[12]

Risvik, K.M., Aasheim, Y., Lidal, M.: Multi-tier architecture for web search engines. In: 1st LAWEB, pp. 132-143 (2003)

Crossref

Google Scholar

[13]

Robertson, S.E.,Walker, S., Jones, S., Hancock-beaulieu, M.M., Gatford, M.: Okapi at trec-3. In: Text REtrieval Conference (TREC-3), pp. 109-126 (1995)

Google Scholar

[14]

Yalag, P., Nath, S., Yu, H., Gibbons, P.B., Seshan, S.: Beyond availability: Towards a deeper understanding of machine failure characteristics in large distributed systems. In: USENIX WORLDS (2004)

Google Scholar

Cited By

View all

Brefeld UCambazoglu BJunqueira FKing INejdl WLi H(2011)Document assignment in multi-site search enginesProceedings of the fourth ACM international conference on Web search and data mining10.1145/1935826.1935907(575-584)Online publication date: 9-Feb-2011
https://dl.acm.org/doi/10.1145/1935826.1935907
Cambazoglu BPlachouras VBaeza-Yates RAllan JAslam JSanderson MZhai CZobel J(2009)Quantifying performance and quality gains in distributed web search enginesProceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval10.1145/1571941.1572013(411-418)Online publication date: 19-Jul-2009
https://dl.acm.org/doi/10.1145/1571941.1572013

A Study of the Impact of Index Updates on Distributed Query Processing for Web Search
1. Information systems
  1. Data management systems
    1. Database management system engines
  2. Information retrieval
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Efficient query processing in geographic web search engines
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data

Geographic web search engines allow users to constrain and order search results in an intuitive manner by focusing a query on a particular geographic region. Geographic search technology, also called local search, has recently received significant ...
Index compression and efficient query processing in large web search engines
Batch query processing for web search engines
WSDM '11: Proceedings of the fourth ACM international conference on Web search and data mining

Large web search engines are now processing billions of queries per day. Most of these queries are interactive in nature, requiring a response in fractions of a second. However, there are also a number of important scenarios where large batches of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ECIR '09: Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval

April 2009

817 pages

ISBN:9783642009570

Editors:
Mohand Boughanem
Université de Toulouse - IRIT,, Toulouse Cedex 4,, France 31062,
,
Catherine Berrut
Laboratoire d'Informatique de Grenoble, BP 53,, Université Joseph Fourier,, Grenoble Cedex 9,, France 38041
,
Josiane Mothe
Université de Toulouse - IRIT,, Toulouse Cedex 4,, France 31062
,
Chantal Soule-Dupuy
Université de Toulouse - IRIT,, Toulouse Cedex 4,, France 31062

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 April 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Brefeld UCambazoglu BJunqueira FKing INejdl WLi H(2011)Document assignment in multi-site search enginesProceedings of the fourth ACM international conference on Web search and data mining10.1145/1935826.1935907(575-584)Online publication date: 9-Feb-2011
https://dl.acm.org/doi/10.1145/1935826.1935907
Cambazoglu BPlachouras VBaeza-Yates RAllan JAslam JSanderson MZhai CZobel J(2009)Quantifying performance and quality gains in distributed web search enginesProceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval10.1145/1571941.1572013(411-418)Online publication date: 19-Jul-2009
https://dl.acm.org/doi/10.1145/1571941.1572013

Abstract

References

Cited By

Recommendations

Efficient query processing in geographic web search engines

Index compression and efficient query processing in large web search engines

Batch query processing for web search engines

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations