Change Detection and Notification of Webpages: A Survey <s> Change Detection Techniques/Algorithms <s> We present a diff algorithm for XML data. This work is motivated by the support for change control in the context of the Xyleme project that is investigating dynamic warehouses capable of storing massive volumes of XML data. Because of the context, our algorithm has to be very efficient in terms of speed and memory space even at the cost of some loss of quality. Also, it considers, besides insertions, deletions and updates (standard in diffs), a move operation on subtrees that is essential in the context of XML. Intuitively, our diff algorithm uses signatures to match (large) subtrees that were left unchanged between the old and new versions. Such exact matchings are then possibly propagated to ancestors and descendants to obtain more matchings. It also uses XML specific information such as ID attributes. We provide a performance analysis of the algorithm. We show that it runs in average in linear time vs. quadratic time for previous algorithms. We present experiments on synthetic data that confirm the analysis. Since this problem is NP-hard, the linear time is obtained by trading some quality. We present experiments (again on synthetic data) that show that the output of our algorithm is reasonably close to the optimal in terms of quality. Finally we present experiments on a small sample of XML pages found on the Web. <s> BIB001 </s> Change Detection and Notification of Webpages: A Survey <s> Change Detection Techniques/Algorithms <s> Tracking the evolution of websites has become fundamental to the understanding of today's Internet. The automatic reasoning of how and why websites change has become essential to developers and businesses alike, in particular because the manual reasoning has become impractical due to the sheer number of modifications that websites undergo during their operational lifetime, including but not limited to rotating advertisements, personalized content, insertion of new content, or removal of old content. Prior work in the area of change detection, such as XyDiff, X-Diff or AT&T's internet difference engine, focused mainly on ``diffing'' XML-encoded literary documents or XML-encoded databases. Only some previous work investigated the differences that must be taken into account to accurately extract the difference between HTML documents for which the markup language does not necessarily describe the content but is used to describe how the content is displayed instead. Additionally, prior work identifies all changes to a website, even those that might not be relevant to the overall analysis goal, in turn, they unnecessarily burden the analysis engine with additional workload. In this paper, we introduce a novel analysis framework, the Delta framework, that works by (i) extracting the modifications between two versions of the same website using a fuzzy tree difference algorithm, and (ii) using a machine-learning algorithm to derive a model of relevant website changes that can be used to cluster similar modifications to reduce the overall workload imposed on an analysis engine. Based on this model for example, the tracked content changes can be used to identify ongoing or even inactive web-based malware campaigns, or to automatically learn semantic translations of sentences or paragraphs by analyzing websites that are available in multiple languages. In prior work, we showed the effectiveness of the Delta framework by applying it to the detection and automatic identification of web-based malware campaigns on a data set of over 26 million pairs of websites that were crawled over a time span of four months. During this time, the system based on our framework successfully identified previously unknown web-based malware campaigns, such as a targeted campaign infecting installations of the Discuz!X Internet forum software. <s> BIB002 </s> Change Detection and Notification of Webpages: A Survey <s> Change Detection Techniques/Algorithms <s> People develop personal information collections consisting of distributed web resources as both reminders that resources exist and to provide rapid access to these resources. Managing such collections is necessary to preserve their value. Unexpected changes within distributed collections can cause them to become outdated, requiring revisions to or removal of no-longer-appropriate resources and replacements for lost resources. In an effort to alleviate this problem, this paper presents a categorization and classification framework including a tool that supports the management and active curation of distributed collections of Web-based resources. We assess the need for such a system and analyze how current tools affect the management of personal collections with survey of 106 participants from online and offline communities. Results of the survey show that personal collections are common and collection management is an issue for ∼20% of respondents. Additionally we examine and categorize the various degrees of change that digital documents endure within the boundaries of a distributed collection. Consequently, this paper will focus on two research questions. First, what facets of the change detection process can be automated? And second, looking at this problem from a user standpoint where each document contributes towards the overall meaning of the collection, what strategies can be used to effectively detect the consequences of the various types of change found in document collections? <s> BIB003
Changes occurring in webpages can be divided into five categories as given in  . They are (1) A major concern of change detection in webpages is the ability in identifying relevant and irrelevant changes. The research carried out in BIB002 ] has focused to ignore irrelevant changes such as change of advertisements and try to detect important changes to webpages using different methods. The "Delta framework" introduced in this research, consists of 4 precise steps. In the initial step, it retrieves the currently available version of a website and normalizes the "DOM-tree" BIB002 . Then in the next step, similarities are measured in comparison to the "base version" of the website. Similar changes are clustered to lower the analysis engine submissions. The final step is the "analysis of identified and novel modifications with a potential computationally costly analysis engine" BIB002 ]. Compared to many other researches which focus on detecting changes that has been done to a website, the Delta framework focuses more on detecting significant changes occurring in a website. Changes occurring within information collections can be difficult to track due to the vast amount of data being available. Unexpected changes within the collection can make the content unorganized and outdated, which can cause burdens such as removal of outdated resources and replacement for lost resources. BIB003 has presented a study which focuses on a categorization and classification framework to manage and curate distributed collections of web-based resources. The selected pages were categorized with their relationships between the anchor text to identify the relevant information of the target page. They have proposed a digital collection manager that addresses webpages with textual content only. It has been shown that due to unexpected changes, documents in these collections can get problematic. Further research is necessary to detect changes occurring to other resources in digital collections, such as audio files, video files and documents. Various change detection approaches have been proposed across the available literature to detect the different changes occurring in webpages. Elaborated below are a few popular algorithms that were considered in this survey. More algorithms can be found in Section 7 where they have been compared. One of the common approaches that have been used for change detection in hierarchically structured documents such as webpages is the use of tree-structured data with diff algorithms BIB001 . Many variations of these diff algorithms have been presented in the available literature [Wang et al. 2003 ] BIB002 ]. The basic idea on top of which all of these algorithms are built on is the process of modeling the hierarchically structured documents in the form of a tree with nodes and compare the two trees to identify changes that have occurred. Similarly, two trees can be developed; one with nodes from the parsed content of a previous version and the other from the with nodes from the parsed content of the currently available version. The two trees could be compared to identify which nodes have changed so that the changes can be determined.