Change Detection and Notification of Webpages: A Survey <s> Distributed <s> We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus, the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [Chandra et al. 1992]. <s> BIB001 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> We report our experience in implementing UbiCrawler, a scalable distributed Web crawler, using the Java programming language. The main features of UbiCrawler are platform independence, linear scalability, graceful degradation in the presence of faults, a very effective assignment function (based on consistent hashing) for partitioning the domain to crawl, and more in general the complete decentralization of every task. The necessity of handling very large sets of data has highlighted some limitations of the Java APIs, which prompted the authors to partially reimplement them. <s> BIB002 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> This paper presents a multi-objective approach to Web space partitioning, aimed to improve distributed crawling efficiency. The investigation is supported by the construction of two different weighted graphs. The first is used to model the topological communication infrastructure between crawlers and Web servers and the second is used to represent the amount of link connections between servers' pages. The values of the graph edges represent, respectively, computed RTTs and pages links between nodes. ::: ::: The two graphs are further combined, using a multi-objective partitioning algorithm, to support Web space partitioning and load allocation for an adaptable number of geographical distributed crawlers. ::: ::: Partitioning strategies were evaluated by varying the number of partitions (crawlers) to obtain merit figures for: i) download time, ii) exchange time and iii) relocation time. Evaluation has showed that our partitioning schemes outperform traditional hostname hash based counterparts in all evaluated metric, achieving on average 18% reduction for download time, 78% reduction for exchange time and 46% reduction for relocation time. <s> BIB003 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Web page crawlers are an essential component in a number of web applications. The sheer size of the Internet can pose problems in the design of web crawlers. All currently known crawlers implement approximations or have limitations so as to maximize the throughput of the crawl, and hence, maximize the number of pages that can be retrieved within a given time frame. This paper proposes a distributed crawling concept which is designed to avoid approximations, to limit the network overhead, and to run on relatively inexpensive hardware. A set of experiments, and comparisons highlight the effectiveness of the proposed approach. <s> BIB004 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Web is a context in which traditional Information Retrieval methods are challenged. Given the volume of the Web and its speed of change, the coverage of modern web search engines is relatively small. Search engines attempt to crawl the web exhaustively with crawler for new pages, and to keep track of changes made to pages visited earlier. The centralized design of crawlers introduces limitations in the design of search engines. It has been recognized that as the size of the web grows, it is imperative to parallelize the crawling process. Contents other then standard documents (Multimedia content and Databases etc) also makes searching harder since these contents are not visible to the traditional crawlers. Most of the sites stores and retrieves data from backend databases which are not accessible to the crawlers. This results in the problem of hidden web. This paper proposes and implements DCrawler, a scalable, fully distributed web crawler. The main features of this crawler are platform independence, decentralization of tasks, a very effective assignment function for partitioning the domain to crawl, and the ability to cooperate with web servers. By improving the cooperation between web server and crawler, the most recent and updates results can be obtained from the search engine. A new model and architecture for a Web crawler that tightly integrates the crawler with the rest of the search engine is designed first. The development and implementation are discussed in detail. Simple tests with distributed web crawlers successfully show that the Dcrawler performs better then traditional centralized crawlers. The mutual performance gain increases as more crawlers are added. <s> BIB005 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Due to colossal amount of data on the Web, Web archivists typically make use of Web crawlers for automated collection. The Internet Archive is the largest organization based on a crawling approach in order to maintain an archive of the entire Web. The most important requirement of a Web crawler, specially when they are used for Web archiving, is to be aware of the date (and time) of last modification of a Web page. This strategy has various advantages, most important of them include i) presentation of an up-to-date version of a Web page to the end user ii) ease of adjusting the crawl rate that allows future retrieval of a Web page's version at a given date, or to compute its refresh rate. The typical way for this modification information of a Web page, that is, to use the Last-Modified: HTTP header, unfortunately does not provide correct information every time. In this work, we discuss various techniques that can be used to determine the date of last modification of a Web page with the help of experiments. This will help in adjusting the crawl rate for a specific page and also helps in presenting users with up to date information and thus allowing future versioning of a Web page more meticulous. <s> BIB006 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Modern web technologies, like AJAX result in more responsive and usable web applications, sometimes called Rich Internet Applications (RIAs). Traditional crawling techniques are not sufficient for crawling RIAs. We present a new strategy for crawling RIAs. This new strategy is designed based on the concept of "Model-Based Crawling" introduced in [3] and uses statistics accumulated during the crawl to select what to explore next with a high probability of uncovering some new information. The performance of our strategy is compared with our previous strategy, as well as the classical Breadth-First and Depth-First on two real RIAs and two test RIAs. The results show this new strategy is significantly better than the Breadth-First and the Depth-First strategies (which are widely used to crawl RIAs), and outperforms our previous strategy while being much simpler to implement. <s> BIB007 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Crawling web applications is important for indexing, accessibility and security assessment. Crawling traditional web applications is an old problem, as old as the web itself. Crawling Rich Internet Applications (RIA) quickly and efficiently, however, is an open problem. Technologies such as AJAX and partial Document Object Model (DOM) updates only makes the problem of crawling RIA more time consuming to the web crawler. To reduce the time to crawl a RIA, this paper presents a new distributed algorithm to crawl a RIA in parallel with multiple computers, called Dist-RIA Crawler. Dist-RIA Crawler uses the JavaScript events in the DOM structure to partition the search space. This paper illustrates a prototype implementation of Dist-RIA Crawler and inspect empirical performance measurements. <s> BIB008 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> Although web crawlers have been around for twenty years by now, there is virtually no freely available, open-source crawling software that guarantees high throughput, overcomes the limits of single-machine systems, and, at the same time, scales linearly with the amount of resources available. This article aims at filling this gap, through the description of BUbiNG, our next-generation web crawler built upon the authors’ experience with UbiCrawler [9] and on the last ten years of research on the topic. BUbiNG is an open-source Java fully distributed crawler; a single BUbiNG agent, using sizeable hardware, can crawl several thousand pages per second respecting strict politeness constraints, both host- and IP-based. Unlike existing open-source distributed crawlers that rely on batch techniques (like MapReduce), BUbiNG job distribution is based on modern high-speed protocols to achieve very high throughput. <s> BIB009 </s> Change Detection and Notification of Webpages: A Survey <s> Distributed <s> World Wide Web is getting dense as many new web pages and resources are created on a daily basis. Keeping track of the changes in the web content has become an immense challenge and is a research problem with a great significance. Even the search engines require to detect changes in the web to keep search indexes up to date. Numerous researches have been carried out on optimizing the change detection algorithms. This paper presents a methodology named Multi-Threaded Crawler for Change Detection of Web (MTCCDW), which is inspired from the producer-consumer problem. The suggested change detection process mainly analyses the performances and suggests a tread-based implementation process for the optimisation of the changed detection process. The experimental results show that the proposed methodology is capable of reducing the effective time to detect changes in a web page by 93.51%. <s> BIB010
Crawling. This method uses multiple processes to crawl webpages and download their content. Web crawlers are distributed over different systems, allowing them to operate independently. Distributed crawling techniques were introduced due to the inherent problems faced by centralized crawling solutions, such as reduced throughput of the crawl and link congestion BIB004 . Figure 9 denotes the general arrangement of components in a distributed crawling system. The crawlers are distributed across different systems and they crawl webpages in different parts of the Web. The Web can be partitioned using different graph partitioning algorithms and each crawler is provided with a seed URL to start the crawling process [Ahmadi-Abkenari and Selamat 2012]. All the crawled content is then aggregated and sent to the main server. This content can be processed within the main server or they can be sent to other services for different purposes such as indexing and version comparison within CDN systems. BIB002 . In order to address this concern, crawlers can be designed as reliable failure detectors BIB001 , in which timeouts can be used to detect crashed agents. "UbiCrawler" BIB002 ] is an example of a web crawler with a reliable failure detector. It is a scalable distributed web crawler, which consists of several agents that are responsible to crawl their own share of the Web. Based on the experience with "UbiCrawler", the authors have built "BUbiNG" BIB009 , which is an open source fully distributed web crawler which is fast, scalable and can run on commodity hardware. It consists of a number of fetching threads which download webpages and parsing threads that parse content. Another aspect which has drawn the attention of researchers is the efficient partitioning mechanisms of the Web space. Work done in BIB003 ] has presented a multi-objective approach for partitioning the Web space by modeling the Web hosts and IP hosts as graphs. These graphs are partitioned, and a new graph is created with the weights calculated using the original weights and the edge-cuts. Results show that efficient partitioning techniques have improved download times, exchange times and relocation times. [ BIB004 has introduced "LiDi Crawl (Lightweight Distributed Crawler)", which is a centralized distributed crawling application with limited resources. It consists of a central node and several individual crawling components. The distributed crawling nature results in the reduced dependence on expensive resources. BIB005 ] has proposed a scalable, fully-distributed web crawler, without a central node. It consists of multiple agents, where each agent is coordinated so that they crawl their own region in the Web. An agent runs several threads, where each thread is made responsible to visit a single host. The main objective of having multiple agents is to break down the task of crawling into separate parts and allow specialized modules to carry them out efficiently. BIB006 states that web crawlers should be aware of webpage modifications and has discussed techniques to retrieve information on such modifications. However, the authors have found that presence of multiple JavaScript and CSS files can reduce the efficiency of certain techniques. Efficiently crawling of "Rich Internet Applications (RIA)" is an open problem as RIAs consist of many characteristics such as, the use of JavaScript and browser plugins, which makes the crawling process complex. "Model-Based Crawling"  ] was introduced to determine an optimal crawling strategy for RIA. An extension of this model is presented in BIB007 , which uses a statistical approach in determining a crawling strategy. The recent work carried out in BIB008 ], intends to lower the time taken to crawl RIAs by introducing "Dist-RIA crawler" BIB008 , which is a distributed crawler to crawl RIAs in parallel. One of the most popular high-performance distributed crawlers found at present is the "Googlebot" [Googlebot 2013]. Googlebot is the web crawler used by Google to fetch webpages for indexing. It is designed to be distributed on several machines so that the crawler can scale as the Web grows. Furthermore, crawlers run on servers that are located close to the websites, where they are getting indexed in the network, in order to reduce the bandwidth usage. "Multi-Threaded Crawler for Change Detection of Web (MTCCDW)" has been introduced in BIB010 ] to optimize the change detection process of webpages. Many threads were used to carry out the tasks of (1) "retrieving current versions of webpages", (2) "retrieving old versions from a version repository" and (3) "comparison of the two versions to detect the changes" BIB010 ]. Two thread-safe queues were used in between these three tasks in order to optimize them. The authors have determined the optimum number of threads to be used in each of these tasks, to ensure that the CDN system works optimally without idling. This multithreading-based algorithm differs from standard process optimization tasks because of the I/O operations which are involved in fetching a webpage from the Web. Hence this algorithm provides a more significant improvement in processing times over doing I/O operations and processing in a central processing unit.