High-performance priority queues for parallel crawlers

ABSTRACT

Large scale data centers for crawlers are able to maintain a very large number of active http connections in order to download as fast as possible the usually huge number of web pages from given sections of the WWW. This generates a continuous stream of new URLs of documents to be downloaded and it is clear that the associated work-load can only be served efficiently with proper parallel computing techniques. The incoming new URLs have to be organized by a priority measure in order to download the most relevant documents first. Efficiently managing them along with other synchronization issues such as URLs downloaded by different processing nodes forming a cluster of computers are the matters of this paper. We propose efficient and scalable strategies which consider intra-node multi-core multi-threading on an inter-nodes distributed memory environment, including efficient use of secondary memory.

REFERENCES

• 1: Serge Abiteboul , Mihai Preda , Gregory Cobena, Adaptive on-line page importance computation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775192]
• 2: R. Baeza-Yates and C. Castillo. Balancing volume, quality and freshness in web crawling. In Soft Computing Systems - Design, Management and Applications, pages 565--572. IOS Press, 2002.
• 3: Ricardo Baeza-Yates , Carlos Castillo , Mauricio Marin , Andrea Rodriguez, Crawling a country: better strategies than breadth-first for web page ordering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062768]
• 4: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 5: 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
• 6: Duen Horng Chau , Shashank Pandit , Samuel Wang , Christos Faloutsos, Parallel crawling for online social networks, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242809]
• 7: Junghoo Cho , Hector Garcia-Molina, Parallel crawlers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511464]
• 8: S. Dong, X. Lu, L. Zhang, and K. He. An efficient parallel crawler in grid environment. In Int. Conf. on Grid and Cooperative Computing, LNCS 3032, pages 229--232. Springer, 2004.
• 9: C. A. R. Hoare, Algorithm 65: find, Communications of the ACM, v.4 n.7, p.321-322, July 1961 [doi>10.1145/366622.366647]
• 10: B. Thau Loo, S. Krishnamurthy, and O. Cooper. Distributed Web crawling over DHTs. Technical Report UCB/CSD-04-1305, EECS Department, University of California, Berkeley, Feb 2004.
• 11: M. Marin. Binary Tournaments and Priority Queues: PRAM and BSP. Technical Report PRG-TR-7-97, Oxford University, 1997.
• 12: Mauricio Marin , Carolina Bonacic, Bulk-Synchronous On-Line Crawling on Clusters of Computers, Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), p.414-421, February 13-15, 2008 [doi>10.1109/PDP.2008.84]
• 13: R. Paredes. Graphs for Metric Space Searching. PhD thesis, Universidad de Chile, 2008. Advisor: G. Navarro. Tech Report TR/DCC-2008-10. Available at www.dcc.uchile.cl/~raparede/publ/08PhDthesis.pdf.
• 14: R. Paredes and G. Navarro. Optimal incremental sorting. In Proc. 8th Workshop on Algorithm Engineering and Experiments and 3rd Workshop on Analytic Algorithmics and Combinatorics, pages 171--182. SIAM Press, 2006.
• 15: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
parallel and distributed computing, priority queues