Topical web crawlers: Evaluating adaptive algorithms

ABSTRACT

Topical crawlers are increasingly seen as a way to address the scalability limitations of universal search engines, by distributing the crawling process across users, queries, or even client computers. The context available to such crawlers can guide the navigation of links with the goal of efficiently locating highly relevant target pages. We developed a framework to fairly evaluate topical crawling algorithms under a number of performance metrics. Such a framework is employed here to evaluate different algorithms that have proven highly competitive among those proposed in the literature and in our own previous research. In particular we focus on the tradeoff between exploration and exploitation of the cues available to a crawler, and on adaptive crawlers that use machine learning techniques to guide their search. We find that the best performance is achieved by a novel combination of explorative and exploitative bias, and introduce an evolutionary crawler that surpasses the performance of the best nonadaptive crawler after sufficiently long crawls. We also analyze the computational complexity of the various crawlers and discuss how performance and complexity scale with available resources. Evolutionary crawlers achieve high efficiency and scalability by distributing the work across concurrent agents, resulting in the best performance/cost ratio.

REFERENCES

• 1: Charu C. Aggarwal , Fatima Al-Garawi , Philip S. Yu, Intelligent crawling on the World Wide Web with arbitrary predicates, Proceedings of the 10th international conference on World Wide Web, p.96-105, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371955]
• 2: Israel Ben-Shaul , Michael Herscovici , Michal Jacovi , Yoelle S. Maarek , Dan Pelleg , Menachem Shtalhaim , Vladimir Soroka , Sigalit Ur, Adding support for dynamic and focused search with Fetuccino, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1653-1665, May 17, 1999
• 3: Brian E. Brewington , George Cybenko, How dynamic is the Web?, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.257-276, June 2000, Amsterdam, The Netherlands
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1623-1640, May 17, 1999
• 6: Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
• 7: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Computer Networks and ISDN Systems, v.30 n.1-7, p.161-172, April 1, 1998
• 8: Cyveillance. 2000. Sizing the internet. White paper. http://www.cyveillance.com/.
• 9: P. M. E. De Bra , R. D. J. Post, Information retrieval in the World-Wide Web: making client-based searching feasible, Selected papers of the first conference on World-Wide Web, p.183-192, November 1994, Geneva, Switzerland
• 10: Michelangelo Diligenti , Frans Coetzee , Steve Lawrence , C. Lee Giles , Marco Gori, Focused Crawling Using Context Graphs, Proceedings of the 26th International Conference on Very Large Data Bases, p.527-534, September 10-14, 2000
• 11: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 12: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 13: Haveliwala, T. 1999. Efficient computation of pagerank. Tech. rep., Stanford Database Group.
• 14: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, Measuring index quality using random walks on the Web, Proceeding of the eighth international conference on World Wide Web, p.1291-1303, May 1999, Toronto, Canada
• 15: Michael Hersovici , Michal Jacovi , Yoelle S. Maarek , Dan Pelleg , Menanchem Shtalhaim , Sigalit Ur, The shark-search algorithm. An application: tailored Web site mapping, Proceedings of the seventh international conference on World Wide Web 7, p.317-326, April 1998, Brisbane, Australia
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 17: Kleinberg, J. and Lawrence, S. 2001. The structure of the Web. Science 294, 5548, 1849--1850.
• 18: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 19: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 20: Lawrence, S. and Giles, C. 1998. Searching the World Wide Web. Science 280, 98--100.
• 21: Lawrence, S. and Giles, C. 1999. Accessibility of information on the Web. Nature 400, 107--109.
• 22: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 23: Filippo Menczer, ARCCHNID: Adaptive Retrieval Agents Choosing Heuristic Neighborhoods, Proceedings of the Fourteenth International Conference on Machine Learning, p.227-235, July 08-12, 1997
• 24: Filippo Menczer, Complementing search engines with online web mining agents, Decision Support Systems, v.35 n.2, p.195-212, May 2003 [doi>10.1016/S0167-9236(02)00106-9]
• 25: Filippo Menczer, Lexical and semantic clustering by web links, Journal of the American Society for Information Science and Technology, v.55 n.14, p.1261-1269, December 2004 [doi>10.1002/asi.20081]
• 26: Filippo Menczer , Richard K. Belew, Adaptive information agents in distributed textual environments, Proceedings of the second international conference on Autonomous agents, p.157-164, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280794]
• 27: Filippo Menczer , Richard K. Belew, Adaptive Retrieval Agents: Internalizing Local Contextand Scaling up to the Web, Machine Learning, v.39 n.2-3, p.203-242, May-June 2000 [doi>10.1023/A:1007653114902]
• 28: Menczer, F. and Monge, A. 1999. Scalable Web search by adaptive online agents: An InfoSpiders case study. In Intelligent Information Agents: Agent-Based Information Discovery and Management on the Internet, M. Klusch, Ed. Springer, Berlin, 323--347.
• 29: Filippo Menczer , Gautam Pant , Padmini Srinivasan , Miguel E. Ruiz, Evaluating topic-driven web crawlers, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.241-249, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383995]
• 30: Alexandros Moukas , Giorgos Zacharia, Evolving a multi-agent information filtering solution in Amalthaea, Proceedings of the first international conference on Autonomous agents, p.394-403, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267747]
• 31: Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
• 32: Zacharis Z. Nick , Panayiotopoulos Themis, Web Search Using a Genetic Algorithm, IEEE Internet Computing, v.5 n.2, p.18-26, March 2001 [doi>10.1109/4236.914644]
• 33: Tadhg O'Meara , Ahmed Patel, A Topic-Specific Web Robot Model Based on Restless Bandits, IEEE Internet Computing, v.5 n.2, p.27-35, March 2001 [doi>10.1109/4236.914645]
• 34: Pant, G., Bradshaw, S., and Menczer, F. 2003. Search engine - crawler symbiosis. In Proceedings of the 7th European Conference on Research and Advanced Technology for Digital Libraries (ECDL), T. Koch and I. Solvberg, Eds. Lecture Notes in Computer Science, Vol. 2769. Springer Verlag, Berlin.
• 35: Gautam Pant , Filippo Menczer, MySpiders: Evolve Your Own Intelligent Web Crawlers, Autonomous Agents and Multi-Agent Systems, v.5 n.2, p.221-229, June 2002 [doi>10.1023/A:1014853428272]
• 36: Pant, G. and Menczer, F. 2003. Topical crawling for business intelligence. In Proceedings of the 7th European Conference on Research and Advanced Technology for Digital Libraries (ECDL), T. Koch and I. Solvberg, Eds. Lecture Notes in Computer Science, Vol. 2769. Berlin.
• 37: Pant, G., Srinivasan, P., and Menczer, F. 2002. Exploration versus exploitation in topic driven crawlers. In Proceedings of the WWW-02 Workshop on Web Dynamics.
• 38: Pinkerton, B. 1994. Finding what people want: Experiences with the WebCrawler. In Proceedings of the 2nd International World Wide Web Conference (Chicago).
• 39: Porter, M. 1980. An algorithm for suffix stripping. Program 14, 3, 130--137.
• 40: Jason Rennie , Andrew McCallum, Using Reinforcement Learning to Spider the Web Efficiently, Proceedings of the Sixteenth International Conference on Machine Learning, p.335-343, June 27-30, 1999
• 41: D. E. Rumelhart , G. E. Hinton , R. J. Williams, Learning internal representations by error propagation, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
• 42: P. Srinivasan , F. Menczer , G. Pant, A General Evaluation Framework for Topical Crawlers, Information Retrieval, v.8 n.3, p.417-447, May 2005 [doi>10.1007/s10791-005-6993-5]
• 43: Craig E. Wills , Mikhail Mikhailov, Towards a better understanding of Web resources and server responses for improved caching, Proceeding of the eighth international conference on World Wide Web, p.1231-1243, May 1999, Toronto, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks; Performance evaluation (efficiency and effectiveness); Distributed systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems; Intelligent agents
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies; Heuristic methods

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
Efficiency, evaluation, evolution, exploitation, exploration, reinforcement learning, topical crawlers