Change Detection and Notification of Webpages: A Survey <s> Detecting <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> Detecting <s> The exponential increase of information on the web has affected the manner in which the information is accessed, disseminated and delivered. The emphasis has shifted from mere viewing of information to efficient retrieval and monitoring of selective changes to information content. Hence, an effective monitoring system for change detection and notification based on user-profile is needed. WebVigiL is a general-purpose, active capability-based information monitoring and notification system, which handles specification, management, and propagation of customized changes as requested by a user. The emphasis of change detection in WebVigiL is to detect customized changes on the content of the document, based on user intent. As XML is an ordered semi-structured language, detecting customized changes to part of the value of the text nodes and even portion of the content spanning multiple text nodes of an ordered XML tree is difficult. In this paper, we propose an algorithm to handle customized change detection to content of XML documents based on user-intent. An optimization to the algorithm is presented that has a better performance for XML pages with certain characteristics. We also discuss various change presentation schemes to display the changes computed. We highlight the change detection in the context of WebVigiL and briefly describe the rest of the system. <s> BIB002
Changes in XML Documents BIB001 CX-DIFF BIB002 Identifies user specific changes on XML documents. Objects of interest are extracted, filtered for unique insertions and deletions, and the common order subsequence is computed.