Change Detection and Notification of Webpages: A Survey <s> Walden's Paths Path <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> Walden's Paths Path <s> Distributed collections of Web materials are common. Bookmark lists, paths, and catalogs such as Yahoo! Directories require human maintenance to keep up to date with changes to the underlying documents. The Walden's paths path manager is a tool to support the maintenance of distributed collections. Earlier efforts focused on recognizing the type and degree of change within Web pages and identifying pages no longer accessible. We now extend this work with algorithms for evaluating drastic changes to page content based on context. Additionally, we expand on previous work to locate moved pages and apply the modified approach to suggesting page replacements when the original page cannot be found. Based on these results we are redesigning the path manager to better support the range of assessments necessary to manage distributed collections. <s> BIB002 </s> Change Detection and Notification of Webpages: A Survey <s> Walden's Paths Path <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> BIB003
Manager [Francisco-Revill et al. 2001] Cosine algorithm BIB002 Compute a cosine value between two vectors of the page considered and all the pages for the similar topic except the page considered. Then measure the change in cosine value. Provides a more meaningful cutoff to identify the level of change. The context-based algorithm gives a mid-level outcome as it tends to generate false positives and false negatives. Managing distributed collections BIB002 Fuzzy Tree Difference Algorithm BIB003 A "tree difference algorithm" which is generalized into a fuzzynotion. Can eliminate trivial changes momentarily. Have to define a suitable (fuzzy) hash function. Delta framework BIB003 BULD Diff Algorithm BIB001 Match subtrees of two XML documents till no more matches can be made. Unmatched subtrees are considered to be insertions or deletions.