VigiL to highlight role of change detection graph (CDG) which forms the core of the WebVigiL The burgeoning data on the Web makes it dif- system. cult for one to keep track of the changes that constantly occur to speci c information of interest. Currently, the most widespread way of de- 1 Introduction tecting changes occurring to Web content is to manually retrieve the pages of interest and check The world wide web has outdone traditional methem for changes. This mode of action not only dia such as television, to become an indispenswastes useful resources, but also presents infor- able source of information. There is data for mation that may not be relevant to the given everyone and everything on the Web, and this context. data is increasing at a rapid pace. This plethora In this paper, we present a change-monitoring of information often leads to situations wherein system { WebVigiL { which e ciently monitors users looking for speci c pieces of information user-speci ed web pages for customized changes are ooded with irrelevant data. For example, an and noti es the user in a timely manner. We information technology professional who is only present the data ow approach used for detect- interested in news related to his areas of intering multiple types of changes to a page. This est, is ooded with news on many topics when approach has been optimized to group simi- he goes to any popular news website. There are lar/same speci cations to reduce the computa- other situations in which users are interested in tion of changes. Multiple changes to the same knowing about the updates happening to a parpage can also be handled in our approach. We ticular web page of their interest. For example, also provide the overall architecture of Web- students might want to know about the updates that are made to their course websites regardThis work was supported, in part, by the O ce of ing any new projects. In other scenarios there Naval Research & the SPAWAR System Center-San Diego & by the Rome Laboratory (grant F30602-01-2-05430), are large software development projects where and by NSF (grant IIS-0123730). there are number of documents, such as require-
ments analysis, design speci cation, detailed de- or XML pages. Changes to pages and changes sign document and implementation documents. to images, links, keywords and etc. correspond Typically, a large number of people are work- to primitive events when mapped to the ECA ing on the project and managers need to be paradigm and their combinations form composaware of the changes to any one of the docu- ite events. Thus, some of the techniques develments to make sure the changes are propagated oped for active databases, when extended approproperly to other relevant documents. In gen- priately, will provide a solution to detect changes eral, the ability to specify changes to arbitrary to web pages. This paper focuses on developing documents and get noti ed in di erent ways will a framework and to provide a selective propabe useful for reducing the wasteful navigation. gation approach to detect changes that are of The proposed architecture also provides a pow- interest to the users in the context of web and erful way to disseminate information e ciently other large-scale network-centric environments without sending unnecessary or irrelevant infor- by adapting and extending the existing active mation. technology.
Today, information retrieval is mostly done us- The remainder of the paper is organized as foling the pull paradigm where the information of lows. In section 2 we present the related work interest is pulled from its source by the user giv- that has been done in the eld of change detecing a query (or queries). The user takes the tion of web content. In section 3 we present the burden of analyzing the pulled information for architecture of the WebVigiL system. In section any changes of interest. Although there are ap- 4 we show how the ECA paradigm is incorpoproaches, such as mailing lists, to notify users of rated into the system. In section 5 we present the the changes that happen to information of inter- core component of the WebVigiL system which est, there is little or no scope for the user to cus- is the Change Detection Graph (CDG). Finally, tomize those noti cations. The user has to be we discuss future work in section 6. satis ed with whatever information the source wishes to send rather than what speci c information the user wants. 2 Related Work
A great deal of research has been done in the
eld of active technology to provide the capa- Many tools have been developed and are
curbility of timely responses for many applications. rently available for tracking changes to web
Event-Condition-Action (or ECA) rules are used pages. AIDE (AT&T Internet Di erence
Ento provide active capability to a system. In gine) [
WebCQ [8] is a prototype system for large- can explicitly specify the pages that can parscale web information monitoring and deliv- ticipate in change detection. ery, which makes use of the structure present in hypertext and the concept of continuous 3. Composite change detection: WebVigiL proqueries. WebCQ is designed to discover and de- vides an elegant way to specify multiple tect changes to the web pages and to provide a change types, such as 'changes occurring to personalized noti cation of the changes to the either images or links', which none of the users. User's monitoring requests are modelled above systems provide. as continuous queries on the web. The authors specify that composite changes can be detected 3 WebVigiL Architecture but , currently the system does not seem to support them. WebCQ lacks a ne grouping WebVigiL is a change-detection and noti cation strategy which results in the change being com- system, which can monitor and detect changes to puted more than once for two users having the unstructured documents in general. WebVigiL same type of request. The system only supports aims at investigating the speci cation, manageHTML documents and the frequency of fetching ment and propagation of changes as requested by is at the level of day which does not prove good the user in a timely manner while meeting the for situations which require a short frequency of quality of service requirements. Figure 1 summafetching. Also there is no provision to specify rizes the complete architecture of WebVigiL. The new requests based on old requests. functionality of each module is described brie y
WYSIGOT [
For example, the Sentinel created for a request to monitor http://www.cnn.com for any updates Every valid user request arriving at WebVigiL related to Iraq, for a period of 2 years starting initiates a series of operations that occur at diffrom now, would be mapped as follows: ferent points in time. Some of these opera
Create Sentinel s1 on the URL tions are: creation of a sentinel (based on start http://www.cnn.com time), monitoring the requested page, detecting
Monitor for keywords \Iraq", Fetch using changes of interest, notifying the user(s) of the
`Best e ort' change, and deactivation of sentinels. This
modFrom NOW to NOW + 2 Years ule generates ECA [1] rules to perform the
acNotify by e-mail to user@uta.edu every 4th day tions of: activating and deactivating sentinels,
Compare alternate versions of fetched pages. constructing and maintaining Change Detection
A detailed explanation is given in [7]. Graph and generating fetch rules. Change
detection algorithms that give the di erence between
3.2 Veri cation Module [t1w0o].HTML/XML pages have been developed [7]
This module processes user requests for
syntactic and semantic correctness. Valid sentinels are
populated in the Knowledge base (currently, Or- 3.5 Fetch Module
acle) and a noti cation of the valid sentinels is
sent to the change detection module. Brie y, the The fetch module [
WebVigiL uses the Java Local Event Detec3.7 Presentation Module tor(LED) to incorporate active capability in the system. LED is a library designed to provide The primary functionality of this module is to support for primitive and composite events, and clearly present the detected changes in a legible rules in Java applications in a seamless manner. triggered at the speci ed time point, rule T1 is executed, which in turn raises the event Start S1.
Triggering of the event Start S1 activates the sentinel S1 and also initiates the periodic event used for fetching the pages of URL speci ed in S1. Now, if another sentinel S2 which is de ned over the interval [start(S1), end(S1)] arrives, the
Figure 2: Event Generation events and rules are generated in order to enable Primitive and composite event detection in vari- S2 are shown in Figure 2. Here, we are associatous parameter contexts and coupling modes has ing the rule R start S2 with the event Start s1, been implemented. which was created at the arrival of sentinel S1.
This rule actually raises the Start S2 event to
During its lifespan, a sentinel is active and par- activate the periodic event associated with S2. ticipates in change detection. A sentinel can be In this manner, ECA rules are used to asyndisabled (does not detect changes during that pe- chronously activate and deactivate sentinels at riod) or enabled (detects changes). By default, run time. Once the appropriate events and rules a sentinel is enabled during its lifespan. The are created, the local event detector handles the user can also explicitly change the state of the execution at run time. By enabling/disabling of sentinel during its lifespan. The start/end of a sentinel, we mean addition/deletion of that sensentinel can be time points or events. When a tinel to the change detection graph. sentinel's start time is now, it is enabled immediately. But in cases where the start is at a later time point or depends on another event that has 5 Change Detection Graph not occurred, we need to enable the sentinel only when the start time is reached or the event of interest has occurred. In WebVigiL, the ECA rule generation module creates the appropriate events and rules to enable/disable sentinels. We achieve this as follows. Consider the scenario where S1 is de ned in the interval [06/02/04, 01/02/05]. At time 06/02/04 sentinel S1 has to be enabled. Figure 2 shows the events and rules that are generated to enable sentinel S1.
The assumption while developing the WebVigiL system has been that even though there will be requests for di erent change types on di erent URLs, there will be overlaps among URLs, types of changes, frequency of access, etc. One of the goals of WebVigiL is to process sentinels e ciently and be able to scale to a very large number of sentinels. A very nave approach for change detection is to maintain a hash table with the pages of interest as the keys and the values being the list of sentinels monitoring that page.
When a page is fetched, the sentinel(s) on that page are extracted and change type is detected for each sentinel. This approach is not e cient as it results in redundant change calculations if more than one sentinel is interested on the same
Fetch S1 is a periodic event created with Start S1 as the start event, the frequency of page fetch, and End S1 as the end event. The rule associated with it handles the fetching of page for S1. A rule associated with an event is red when the event is triggered. More than one rule can be associated with an event. When event Temp1 is
Primitive change detection involves detecting changes to links, images, keywords etc., in a page. In order to facilitate primitive change detection, grouping of sentinels, and data flow we construct a graph. This graph is referred to as the change detection graph (CDG). The graph is constructed bottom up as shown in Figure 5.3. The different types of nodes in the graph are as follows: page for the same change-type. To remove the redundant calculations, a di erent approach can be employed wherein the sentinels in the hashtable are grouped based on the change-type.
This means that the values present in the hashtable will contain a list of sentinel lists which are grouped on the same change-type. This results in some e ciency, but it becomes di cult to implement composite change types (like im- Figure 5.3: Change Detection Graph ages AND links) using this approach. Figure 3: Change Detection Graph We need a data structure that will allow· uUsRL node i(nUtne):reAst (e.g., \www.uta.edu"). The number URL node is a leaf node at level-0 (L0) that denotes the to asynchronously feed fetched pages for change
page of inotefreUstR(eL.g.n,owdwesw.iunta.tehdue)g.rTahpehnuimsbeeqruofalUtRoL tnhoedes in the
detection, allow parallelism where possible, opti- number of distinct pages the system is
monmize the computation by grouping sentinels ovegrraph is eqiutaolrtiongtheatnutmhbaetr pofardtiisctiunclatrpaignesstathnetsyosftetmimisem.oAnitoring at
URL's and change types, and facilitate
composite change detection using the same paradigm athsat particulparaginestaisntfoeftctihmeed. Aatt tthhisislevleelvewlhaennedverprthoepvaegrsaiotnedof a page
to respective nodes at level-1.
primitive change detection. Deletion and propis- fetched (treated as fetch event), it is propagated to respective nodes at
agation of delete semantics must be straightfor- Change type node (Cn): All level-1 (L1)
ward in the representation chosen. Althoughleavel-1. nodes in the graph are change type nodes.
number of data structures have been proposed These nodes represent the the type of change
in the literature for event detection, such as on a page (links, images, keywords, phrases
Petri nets [
Primitive change detection involves detecting of changes, the relationship between nodes at changes to links, images, keywords, etc., in a di erent levels is captured using the subscrippage. In order to facilitate primitive change de- tion/noti cation mechanism. The higher-level tection, grouping of sentinels, and data ow we nodes subscribe to the lower level nodes in the construct a graph. This graph is referred to as graph. This subscription information is mainthe Change Detection Graph (CDG). The tained in the subscriber list at each node. This graph is constructed bottom-up as shown in Fig- subscriber list at each node contains the followure 3. ing:
The di erent types of nodes in the graph are as follow: Level-0: Contains references of level-1 URL node (Un): A URL node is a leaf nodes. node at level-0 (L0) that denotes the page of Level-1: Contains references of sentinels 7 wn in Figure 5.4. The node references are maintained at the URL nTaobdlee5-2. Compare-options supported (pagei). time at which the sentinel arrives is taken into consideration. NOT, AND, OR. As shown in FNiOguTr,eA7N,cDo,mapndosO-R.6TheyCcoannecxlteundsitoonanyannudmbFeruoft ulevreels. WTheosreknodes are created ite event nodes are at levels L2 and above.
The change is computed forfoarllevtherey sseennttiinneellsmoTnhitoeringrsat cvoemrpsoiosnite oefventth.eLeWvele-b2VaingdiLabsoyvsetecmontains references present in the subscriber list at the change type has been implemented and can be accessed node. Hence, for sentinels moonfitothreinngodceosmbpeolos-nginfrgo mto thhtetpi:m//mbeedrilaitne.uhtiag.heedru:le8v0e8l1/(cwoembpvoigsitle. eveAntll containing more ite changes, a representation at its constituent the modules shown in Figure 1 has been implechange type node is needed. Thtihsains tiwmopcloemnsetintuteendts) omr esnentteidne.lsT. he system is being extended in a numby creating proxy sentinels with the same prop- ber of ways. The current architecture of Weerties of the original sentinel at each oTfhtehechcaonng-e isbVcoigmiLputfeadcilfiotrataelsl tthhee smenotinnietlosripnregseonft oinnl ythepasguebsscriber list at the stituent change type node. Consider the scenario without embedded frames. To monitor a page where sentinel S5 is interestedchinanlginektsypaendnoidme.- Hewnicteh, fforra mseensti,netlhsemeoxnaitcotrinUgRcLomopfostihtee cfhraanmgees,haasrepresentation at ages change on pagei (Figure i8ts). cWonhsteitnuenat ncehwangeto tbypeeginvoedne. Wisonrekedisedi.n Tphriosgriesssimtopleemxteenntedd thbye creating proxy version of the pagei is fetched, it is propagated to system to internally handle pages with frames. the links and images nodes. If tsehnetrineeilss awcihthantghee, saTmheispwroipllerbtiees acohfietvheedobriygineaxltesnedntiinngel thate esaycshte mof the constituent sentinels subscribed to it are noti ed. Sentinel to take sentinels which monitor more than one Sand acts as a proxy for S5. WchheangSeantydpeis nodtei-. CUoRnsLid.eWrothrek issceanlasroioinwphreoregressesnttinoelprSo5vi dise iannteriens-ted in links and ed, the change computed is propagated to the dependent fetch module that can be installed on fetched it is propagated to the links and images node. If there is a change, sentinels subscribed to it are notified. Sentinel Sand acts as a proxy for S5. When Sand is notified the change computed is in turn propagated to the AND node. At the AND node, S5 is informed only when it receives notifications from both its constituent Sand sentinels.
[7] J. Jacob. Webvigil: Sentinel speci catin
Figure 8: Composite Example and user-intent based change detection for Following atrhe ethesystesptsetmakehnowshteinnagneaw wseenbtinseilties.regTishteirsedmwiothdtuhelesywsteimll: xml. Master's thesis, The University of locally detect changes and push that information Texas at Arilngton, 2003. 1). The URL WebVigiL server thereby reducing [8] L. Ling, P. Calton, and T. Wei. Weto tnhoederceomrreostpeonding to the target page of sentinel is created if there is none. the network tra c. bcq: Detecting and delivering information