Method and system for maintaining profiles of information channels

[0001] This invention relates to the field of information management. In particular, the invention relates to maintaining profiles of information channels on the Web.

[0002] Much of the content on the Web is available through syndication channels which need to be actively monitored to maintain an up-to-date profile of their published information over time. Such monitoring is essential for next generation of Web 2.0 applications that provide sophisticated search and discovery services over Web information channels. A channel's profile can change over time due to the dynamic nature of the channel. Therefore, maintaining a fresh channel profile is extremely difficult, especially under the constraint of a limited monitoring budget.

[0003] The number of diverse information channels available on the Web is rapidly increasing. It spans many different knowledge domains such as news, stock and market reports, auctions, and more recently channels containing data gathered from Blogs or Wikis. Recent advances in Web technology, such as the improved access capabilities to channels and the availability of new data delivery mechanisms for disseminating the channel content, have resulted in the emergence of more advanced client-side Web applications.

[0004] These applications require sophisticated manipulation of channels on the Web including the discovery, search, and recommendation of relevant channels. Such applications include various Web 2.0 mashups, and situational applications in general, which integrate data that is gathered from several different, possibly inter-related, channels. An imperative task for developers of such applications is to locate relevant channels that will maximize the benefit gained from their applications.

[0005] A crucial step toward the support of such advanced services over channels is the ability to capture the essence of each Web channel. This can be done using channel profiles. A channel profile is a compact representation of the channel content, which can be used to summarize and capture the main characteristics of the content published on this channel. Profiles can simplify the way relevant channels can be located and can be used to match application requirements against the available set of channels managed by the system.

[0006] Maintaining channel profiles is challenging due to several reasons. First, channel content is usually dynamic, as in the case of Web feeds where the content is continuously changing, sometimes at a daily or even hourly rate. Because the profiles of such channels may continually change over time, capturing the dynamic trends of the channel content is extremely difficult.

[0007] Second, the majority of channels on the Web are available nowadays for access via pull-only protocols, while most servers refrain from supporting push protocols due to scalability issues. Previous work on novelty detection in data streams, and data stream summarization, assume that the stream of updates to a channel is pushed into the system. By contrast, in a pull based scenario each channel is required to be actively monitored in order to maintain enough snapshots to construct a fresh and reliable profile of its content. The freshness of maintained profiles therefore directly depends on the rate at which channels are monitored. Moreover, different channels may have different rates at which novel content is being published on them; thus profiles of different channels may change at a different (possibly even non-regular) rate.

[0008] Third, in the pull-based scenario, channels may be volatile, meaning that novel content published over time has a limited lifespan during which it is available on the channel. Such data volatility is very common in Web feeds, where channels have a limited capacity for the number of feed entries that are maintained on the feed. Such limitation is further determined by the feed popularity and the feed provider update policy (e.g., an overwrite policy for which the provider maintains only the last newest entries of the feed). Therefore, monitoring the channel profiles in a pull setting is challenging, where it is hard to predict the moments when novel content, which may result in a significant profile change, is published on such volatile channels and is still available for access.

[0009] Finally, channel monitoring can be constrained, either due to limited system resources such as bandwidth, memory, or CPU (central processing unit), or due to monitoring restrictions set by the channel providers themselves (sometimes termed “politeness constraints”) due to heavy workloads imposed by multiple client access. Therefore, the number of channels that can be monitored in parallel is further limited and requires efficient utilization of the allocated resources for the maintenance of fresh profiles.

[0010] According to a first aspect of the present invention there is provided a method for maintaining profiles of information channels available on the Web, wherein the information channels are accessed via pull-only protocols, the method comprising: monitoring one or more channels by a channel pull action at a monitoring rate, wherein the monitoring rate is determined for the one or more channels based on the number of update events in a previous time period.

[0011] Preferably, the method includes filtering the update events in the time period by a novelty measure, wherein the filtering disregards events that do not include significant novel information.

[0012] The monitoring rate may be adapted based on reinforcement learning applying iterative learning rules over time.

[0013] The filtering may determine if update events include significant novel information by evaluating an update event's influence on channel cohesion, and disregarding update events with high similarity to an information channel's current profile. The method may include setting a threshold parameter to control the amount of novelty filtering. The threshold parameter may be a similarity of an update event to the information channel's current profile, below which update events are disregarded.

[0014] The method may include monitoring multiple channels, wherein the monitoring rate is refined based on inter-channel profile similarities.

[0015] The method may further include maintaining a similarity matrix with entries corresponding to the average profile similarity between two channels during a given time period.

[0016] Where the method includes monitoring multiple channels, the M most important channels may be monitored at any moment in time, wherein the importance of a channel may be determined as a channel with a higher monitoring rate. Alternatively, M randomly selected channels may be monitored at any moment in time.

[0017] The length of the previous time period in which the update events are monitored may be varied to optimize the quality of results against resource use.

[0018] According to a second aspect of the present invention there is provided a computer software product for maintaining profiles of information channels available on the Web, wherein the information channels are accessed via pull-only protocols, the product comprising a computer-readable storage medium, storing a computer in which program comprising computer-executable instructions are stored, which instructions, when read executed by a computer, perform the following steps: monitoring one or more channels by a channel pull action at a monitoring rate, wherein the monitoring rate is determined for the one or more channels based on the number of update events in a previous time period.

[0019] According to a third aspect of the present invention there is provided a method of providing a service to a client over a network for maintaining profiles of information channels available on the Web, wherein the information channels are accessed via pull-only protocols, the service comprising: monitoring one or more channels by a channel pull action at a monitoring rate, wherein the monitoring rate is determined for the one or more channels based on the number of update events in a previous time period.

[0020] According to a fourth aspect of the present invention there is provided a system for maintaining profiles of information channels available on the Web, wherein the information channels are accessed via pull-only protocols, the system comprising: means for determining a monitoring rate for one or more channels based on a number of update events in a previous time period; and means for monitoring one or more channels by a channel pull action at a monitoring rate.

[0021] The system may include a novelty filter to filter the update events in the time period, wherein the novelty filter disregards events that do not include significant novel information. The system may further include means for setting a threshold parameter to control the amount of novelty filtering.

[0022] The means for determining a monitoring rate may include a reinforcement learning mechanism to apply iterative learning rules over time.

[0023] The means for monitoring may include monitoring multiple channels, wherein the means for determining the monitoring rate includes means for refinement based on inter-channel profile similarities. The means for monitoring may include monitoring multiple channels wherein the M most important channels are monitored at any moment in time, wherein the importance of a channel is determined as a channel with a higher monitoring rate. Alternatively, M randomly selected channels may be monitored at any moment in time.

[0024] The system may include means for varying the length of the previous time period in which the update events are monitored to optimize the quality of results against resource use.

[0025] Most current Web monitoring solutions derive monitoring rates based solely on the “raw” update rates of Web channels. Thus, such solutions may consume superfluous resources and, therefore, may fail to scale.

[0026] The present described method considers also the rate of content change published on these channels to improve the monitoring policy. For this purpose, a learning scheme is suggested based on novelty detection for Web channels in pull-only settings. More specifically, some of the contributions can be stated as follows.

• • [0027] A profiling model for channel content is described that can be used for channel search and discovery.
  • [0028] The problem of maintaining dynamic profiles of channels' content is formally defined. Several evaluation measures are provided for those profiles quality.
  • [0029] Using the proposed measures, solutions are explored for channel profile maintenance and efficient and effective monitoring policies are proposed for a single channel as well as for multi-channel monitoring. The described policies continuously decide which channels to monitor over time, considering both the update rate as well as the novel content rate of the channels data. The channel monitoring rates are further refined by utilizing inter-channel profile similarities.
  • [0030] By taking the content update rate of the channels into consideration, it is possible to significantly save the monitoring resources required by the policy while maintaining a high profile quality.

[0037] It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numbers may be repeated among the figures to indicate corresponding or analogous features.

[0038] In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

[0039] Referring to FIG. 1, an example embodiment is shown of a system 100 for application of a profile management system 110 for Web channels. FIG. 1 illustrates the architecture of such a system 100 shown as monitoring multiple channels 111, 112, 113 for a client 120.

[0040] The system 100 includes: pull protocol adapters 101; a profile management system 110; and a service application programming interface (API) 105. The profile management system 110 monitors channels 111-113 and accesses the content published on the channels 111-113 using the pull protocol adapters 101 (e.g., using HTTP (Hypertext Transfer Protocol) GET calls).

[0041] The profile management system 110 includes a monitor 102, a profiler 103, and a search index 104. The profile management system 110 also includes a means for determining a monitoring rate 106 for applying the methods as described in detail. The means for determining the monitoring rate 106 may include a learning mechanism 114 and a history component 108 which is updated after every monitoring probe as described further below. The means for determining the monitoring rate 106 may also include an optional novelty filter 107 and an optional inter-channel comparison mechanism 109 if more than one channel is monitored.

[0042] In the profile management system 110, the content gathered by the monitor 102 is delivered to the profiler 103 that is responsible for updating the channel profile and generating a fresh profile for the channel's content. The profile is then updated in the search index 104. The profile management system 110 exposes a convenient service API 105 for clients 120 to search and locate relevant channels 111-113 for their application needs.

[0043] The profile management system 110 can further match the client 120 requirements (which might also be submitted as a user-profile to the system) against the current channel profiles available in the system to recommend relevant channels that can satisfy the client's needs.

[0044] A mashup application is a web application that combines data from more than one source into a single integrated tool. Clients 120 of a profile management system 110 may consist of various mashup applications that need to discover the most relevant channels to be used as inputs and outputs of the different mashup components. Other clients 120 may consist of different Web feed readers that search for relevant feeds according to their user profile, which describes the user's information interests. Moreover, the profile management system 110 can recommend new sources for clients 120, helping them discover new relevant channels that they would not be aware of otherwise.

[0045] The monitor 101 of the profile management system 110 has a limited amount of available resources for the task of maintaining fresh channel profiles; thus, it is required to monitor the channels 111-113 efficiently to maximize system capability and cope with the management of multiple channels. To do so, the monitor 101 uses the means for determining the monitoring rate 106 to set the rate at which each channel 111-113 should be monitored and how to schedule the limited allocated monitoring system resources in the most efficient way. In what follows, monitoring policies are described tailored for this specific task, i.e., maintaining good representative channel profiles that best reflect the channel content, under the constraints of limited computational resources.

[0046] Referring to FIG. 2, an exemplary system for implementing a profile management system 110 as shown in FIG. 1 includes a data processing system 200 suitable for storing and/or executing program code including at least one processor 201 coupled directly or indirectly to memory elements through a bus system 203. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

[0047] The memory elements may include system memory 202 in the form of read only memory (ROM) 204 and random access memory (RAM) 205. A basic input/output system (BIOS) 206 may be stored in ROM 204. System software 207 may be stored in RAM 205 including operating system software 208. Software applications 210 may also be stored in RAM 205.

[0048] The system 200 may also include a primary storage means 211 such as a magnetic hard disk drive and secondary storage means 212 such as a magnetic disc drive and an optical disc drive. The drives and their associated computer-readable media provide non-volatile storage of computer-executable instructions, data structures, program modules and other data for the system 200. Software applications may be stored on the primary and secondary storage means 211, 212 as well as the system memory 202.

[0049] The computing system 200 may operate in a networked environment using logical connections to one or more remote computers via a network adapter 216.

[0050] Input/output devices 213 can be coupled to the system either directly or through intervening I/O controllers. A user may enter commands and information into the system 200 through input devices such as a keyboard, pointing device, or other input devices (for example, microphone, joy stick, game pad, satellite dish, scanner, or the like). Output devices may include speakers, printers, etc. A display device 214 is also connected to system bus 203 via an interface, such as video adapter 215.

[0051] In this section definitions for the main concepts are provided.

Web Channels

[0052] Let T represent an epoch of time, and let TεT denote a time moment in T. Denote C={C₁, C₂, . . . , C_n} a set of n channels, where each channel CεC is defined as an infinite stream of update events C=(e₁, e₂, . . . ), starting from the beginning of epoch T. Assume textual streams, where each update event eεC contains a text message. Further denote life(e) the period of time during T on which update event e is available on the channel.

[0053] For a given time TεT, and a channel CεC, a channel snapshot at time T (denoted C_T) is given by the set of update events available on the channel at time T; that is:
C_T={e|eεC^(Tεlife(e))}

[0054] Let W be a time window in T². Given a channel CεC, further denote C_W the union of channel snapshots during the time window W:
C_W=∪_TεwC_T
Channel Profiles

[0055] A channel profile represents the textual content of the channel events belonging to the channel snapshot C_T. Due to the dynamic nature of channels, channel snapshots captured during different times may differ, resulting in a possible difference in the corresponding channel profiles.

[0056] In this work, the Bag Of Words (BOW) model is adopted for representing the channel content. Given a vocabulary of terms D={t₁, t₂, . . . , t_m}, the channel profile, at given time T, is then defined as a weight vector:
P(C_T)=(w_t1, w_t2, . . . , w_tm)

[0057] Each weight w_t corresponds to a unique term tεD, which may appear in the textual content of the channel events. If C_T content does not contain term t, then w_t=0. Each term can be either a word, a phrase, or a lexical affinity.

[0058] Similarly, given a window W of k last events captured on the channel (i.e., a window of size k), define P(C_W) as the profile representing the content of those events.

[0059] The channel profile is therefore a compact representation of the channel content at a given time and is used to capture the relative importance of each of the terms in the channel at time T (or during a time window W).

[0060] An increase in profile window size results in more content that is accumulated over a longer period of time, and therefore, it may require more resources such as in-memory. Furthermore, the profile window size has an important role from a user's point of view. A user that prefers generality (i.e., a wide perspective of the content published on the channel for a long time) would require a large window size to satisfy these needs. On the other hand, a user that prefers specificity (i.e., a narrow perspective of the current content published on the channel) would require a small window size.

Web Feed Profiles

[0061] Web feeds are usually used by content providers to publish content on the Web. Those feeds are dynamic channels, supported by pull-only protocols (e.g., available for access through HTTP GET calls), where the set of published items on each feed changes over time and items are volatile in most cases.

[0062] A Web feed, such as RSS (Really Simple Syndication) or Atom feed, is an XML (Extensible Markup Language) file that contains a set of feed items, where each item links to some Web resource (e.g., an HTML (HyperText Markup Language) file), and contains summarized details of the resource such as title and description. The items that are published on the feed over time comprise the dynamic feed channel. Therefore, every new item published on feed C is treated as an update event eεC. The set of terms appearing in the item text (title and description) comprise the item bag of terms, B(e).

[0063] The terms' weights in a Web feed profile are determined using the well-known tf-idf weighting scheme. Given C_W, the set of items that are available on feed C during the time window W, the term frequency of a term t, tf (t, C_W), is the number of occurrences of t in C_W. To calculate the inverse document frequency of a term t, idf(t), first count all items gathered from the feeds CεC, from the beginning of the epoch until the end of the time window W, denoted C_W(T). Then count the number of items in C_W(T) that include at least one occurrence of term t, C_W^t(T). Then the idf of term t is calculated by:

[0064] $idf\left(t\right)=\log \left(\frac{C_W\left(T\right)}{C_W^t\left(T\right)}\right)$

[0065] Finally, the weight of each term t in the profile P(C_W) is given by w_t=tf(t,C_W)·idf(t).

[0066] While the tf of a given term t in the profile represents a the temporary local importance of the term in the channel during the given time window, the idf of a term represents its global importance by considering also the occurrence of the term in items that appeared on the different channels during the history. Since channel profiles are used to represent the dynamic textual content of the channel, common terms appearing in many channel items are less important in representing the channel content in a given time frame. Therefore, common terms (with low idf value) will be weighted lower compared to the rarest terms.

Measures

[0067] Two measures are defined over channel profiles. The first is a profile similarity, which is used to evaluate the similarity between two channel profiles. The profile similarity will be used to evaluate how the channel content is changed over time, by measuring the difference between channel profiles in different time periods. The second is a channel cohesion measure that further can be used to compare different channels with regard to the average rate of change of their content over time.

Profile Similarity

[0068] Given a pair of channel profiles P₁, P₂, define the similarity between the two profiles as their vector space model cosine similarity:

[0069] $\begin{array}{cc}sim\left(P_1,P_2\right)=\frac{P_1·P_2}{P_1·P_2}& \left(1\right)\end{array}$

[0070] It is worth noting that the similarity between profiles of the same channel in two different time windows reflects the amount of changes in content of the channel over time.

Channel Cohesion

[0071] Channel cohesion measures the cohesion of the textual content in the channel over time. A channel with a low cohesion is one for which new published events dynamically change the channel content as reflected by the corresponding channel profile. Such a low cohesive channel will require a higher monitoring rate in order to keep its profile up to date.

[0072] A higher cohesive channel is one where new items cause only minor change in its profile. This is typical of channels with many duplicate (or near duplicate) items or when items are focused on the same topic for a long period of time. For such channels, a low monitoring rate will suffice.

[0073] DEFINITION 1 (CHANNEL COHESION). Given a channel CεC, the channel cohesion during the epoch T=[T₁, T₂] is calculated as:

[0074] $\begin{array}{cc}coh\left(C,T\right)=\frac{1}{T_2-T_1}{\int }_{T_1}^{T_2}sim\left(P\left(C_T\right),P\left(C_{T+dT}\right)\right)dT& \left(2\right)\end{array}$

[0075] Channel cohesion measures the average profile similarity in a given time period [T₁, T₂]. If the channel profiles significantly differ over the time period, the cohesion will be low. In practice, one can approximate the cohesion metric to measure the relative profile change per update event. Given N update events that occurred during epoch T, and assuming that the initial profile is empty (all terms weights are zero), Equation 2 is modified to:

[0076] $\begin{array}{cc}coh\left(C,T\right)=\frac{1}{N}\sum _{i=1}^{N}sim\left(P\left(C_{W_{l-1}}\right),P\left(C_{W_i}\right)\right)& \left(3\right)\end{array}$
where C_Wi-1 is the channel without event e_i and C_Wi is the channel after adding event e_i.
Channel Monitoring Policy

[0077] A monitoring policy's task is to maintain accurate channel profiles by deciding which channels to probe at any given time. A probe is a channel pull action. A channel monitoring task is considered to consist of several costs such as opening a TCP/IP connection to the Web channel provider, capturing its current snapshot by downloading its content, refreshing the channel profile, and updating the index. A constrained monitoring setting is assumed where the monitoring policy is allowed to probe up to M<n channels in parallel at each time TεT. The policy objective is therefore to maximize the quality of the channel profiles by selecting which M channels to probe at any given time, under the defined constrained setting.

Monitoring Quality

[0078] Given a channel CεC, denote the optimal profile at time TεT, P^opt(C_T) as the profile obtained by monitoring the channel after each update event in the channel. Given a channel monitoring policy pol, further denote P^pol(C_T) as the profile obtained by the monitoring policy at time T, which in general will be sub-optimal due to some missing non-monitored events caused by policy decisions. The profile monitoring quality obtained by policy pol over the set of channels C, is given by:

[0079] $\begin{array}{cc}Q\left(C,pol\right)=\frac{1}{n}\sum _{C\in C}\left[\frac{1}{T}{\int }_{T\in T}sim\left(P^{opt}\left(C_T\right),P^{pol}\left(C_T\right)\right)dT\right]& \left(4\right)\end{array}$

[0080] This quality measure provides an indication of how good the policy pol is with respect to the optimal policy. It measures the average similarity between the optimal profiles obtained by the optimal policy, to the profiles obtained by pol, over time and over the full set of channels.

Single Channel Monitoring

[0081] This section describes the proposed framework for single channel monitoring. In this simplified case, the number of channels to monitor by the policy, in Equation 4, is reduced to n=1.

[0082] Off-line and on-line channel monitoring is distinguished. In the off-line case a policy is applied that monitors the channel in a uniform monitoring rate with respect to the average update rate of the channel.

[0083] For the on-line case an adaptive learning scheme is provided to derive the channel update rate, which is used to derive a monitoring rate as in the off-line case. Experimentally, it can be shown how the effectiveness of the learning scheme converges to the same uniform monitoring rate as determined in the off-line case.

[0084] The policy is further extended to consider the content published on the channel. This extension estimates the rate of novel update events that appear on the channel. This work shows that monitoring based on the novel update rate provides a high quality channel profile with significant reduction in the system resources required for the monitoring task.

[0085] Referring to FIG. 3, a flow diagram 300 shows the general method of determining a channel monitoring rate. Monitoring of a channel is carried out at an initial monitoring rate 301, and a set of captured update events to the channel is obtained and recorded in a time interval 302. Optionally, a novelty filtering is applied 303 to the set of events to filter out the events which provide a significant novel content to the channel. Learning rules are applied 304 to the monitoring rate based on the set of captured update events and a new monitoring rate is determined 305. Monitoring of the channel is then carried out at the new monitoring rate 306. The method loops 307 and the new monitoring rate is used in the next cycle. A method of determining a channel monitoring rate may be applied to more than one channel in parallel.

Off-Line Monitoring

[0086] In the case of off-line monitoring for a given channel CεC, the set of all update events eεC and their corresponding content is known in advance for a given epoch T. This mode is, of course, only possible in retrospect. In practice, only the on-line case is a realistic one, for which the set of update events is unknown in advance.

[0087] Let θ_C(T) denote the update rate for channel C at time TεT and let λ_C(T) denote the monitoring rate of channel C at that same time. The off-line monitoring rate of channel CεC is derived as the average update rate in the epoch T. That is, given that channel C has N update events during T, then for each time TεT the off-line monitoring rate is determined as the uniform rate

[0088] ${\lambda }_C^{\mathrm{off}}\left(T\right)=\frac{N}{T}.$

[0089] It is worth noting that the off-line (uniform) monitoring rate λ_C^off (T) serves as a first order approximation to the real (non-uniform) update rate of the channel θ_C(T).

On-Line Monitoring

[0090] In the on-line case, due to the volatile nature of the channels (and especially in the case of Web feeds), the rate at which we monitor the channel determines how many update events may be captured. With limited system resources for channel monitoring, the monitoring rate should be selected wisely—maximizing the profile quality while minimizing the monitoring rate.

[0091] In on-line monitoring, the next monitoring time is derived from the current on-line monitoring rate. Denote T_prev the last time that the channel was monitored and λ_C^on (T_prev) be the current online monitoring rate. Thus, choose to monitor the channel again at time

[0092] $T=T_{\mathrm{prev}}+\frac{1}{{\lambda }_C^{\mathrm{on}}\left(T_{\mathrm{prev}}\right)}.$
Learning Online Monitoring Rate

[0093] An adaptive scheme is provided based on Reinforcement Learning for deriving the monitoring rate of a channel. For this purpose we use Boltzman Learning.

[0094] Equation 5 provides the iterative learning rules that we use, assuming that the learning process starts at the beginning of epoch T. Let λ_C^on (0)=λ₀ be the initial monitoring rate, selected arbitrarily, and let T_prev=0 denote the beginning time of epoch T. Let C_W′ denote the set of captured update events between two consecutive probes to channel C that occurred at times T_prev and T respectively, where define W′=[T_prev, T] and |W′|=(T−T_prev). Then the learning rule is given

[0095] $\begin{array}{cc}\begin{array}{c}{\lambda }_C^{\mathrm{on}}\left(T\right)={\alpha }_T·{\lambda }_C^{\mathrm{on}}\left(T_{\mathrm{prev}}\right)+\left(1-{\alpha }_T\right)·\frac{C_{W^{\prime }}}{W^{\prime }}\\ {\alpha }_T={\alpha }_0·{\exp }^{\frac{-T}{G}}\end{array}& \left(5\right)\end{array}$

[0096] α_T is a learning parameter that controls the tradeoff between the amount of exploitation and exploration of the learning process. The larger α_T is, the more the current monitoring rate λ_C^on (T_prev) is relied upon learned from history (exploitation) and the less the (local) observed rate (exploration) is relied upon. The G parameter controls the rate of learning where larger values imply a slower learning process. For experiments α₀=0.1 and G=100, chosen by trial and error using the full set of Web feeds.

[0097] Experiments demonstrate that the on-line monitoring rate, as learned by the learning scheme, converges to the off-line monitoring rate.

[0098] Note that the off-line rate expresses the average rate of updates on the channel, while the on-line rate continuously adapts to the dynamic update rate of the channel. When the update rate is changed over time, the on-line rate will adapt to those changes in a local manner.

Channel Monitoring Based on Novelty Detection

[0099] A channel monitoring scheme is now described based on novelty detection. The idea behind this scheme is based on the observation that many new events are redundant in terms of providing novel information and do not cause any significant change to the channel profile. Moreover, the rate of new novel events differs from channel to channel therefore it is beneficial to learn the update rate of novel events and then use it as the monitoring rate for the channel. Since novel update rate is usually smaller than the complete update rate, and since a policy based on the novel update rate is expected to provide high quality channel profiles, valuable system resources can be saved.

Novelty Detection Scheme

[0100] The described novelty detection scheme works as follows. Similarly to the Learning On-line Monitoring Rate, let C_W′ denote an ordered set of captured update events between two consecutive probes to channel C that occurred at times T_prev and T respectively (hence, W′=[T_prev, T]). Furthermore, let coh(C, T) be the cohesion calculated given the last N captured events on the channel up to time TεT, as determined by Equation 3. First calculate for each event e_iεC_W′ its marginal influence on the channel cohesion, given by:
Δ_eicoh(C,T)=sim(P(C_Wi-1),(C_Wi))

[0101] Further determine the standard deviation of the channel cohesion using the following unbiased estimator:

[0102] $\begin{array}{cc}{\sigma }_{coh}\left(C,T\right)=\sqrt{\frac{1}{N-1}\sum _{i=1}^N{\left({\Delta }_{e_i}coh\left(C,T\right)-coh\left(C,T\right)\right)}^2}& \left(6\right)\end{array}$

[0103] Then, disregard any event e_iεC_W′ if its similarity to the current profile is high. That is:
Δ_eicoh(C,T)≧coh(C,T)+β·σ_coh(C,T)  (7)

[0104] Otherwise, the event is considered novel following its dissimilarity to the channel profile and its potential for significant influence on the profile.

[0105] Let C_W′^now denote the set of remaining detected novel events that pass the novelty filter.

[0106] The parameter β is a threshold parameter that is used to control the amount of filtering for novelty detection. It controls the tradeoff between monitoring rate and profile quality. A high β means low filtering—most events will be considered novel. Conversely, a low β will cause only a few events to be considered as novel, but this will, in turn, cause insufficient monitoring followed by degradation in channel quality.

Applying Novelty Detection for Monitoring

[0107] Using the novelty detection filter for off-line monitoring is straightforward—apply the filter on the complete set of events and calculate the off-line monitoring rate while considering only novel events.

[0108] In the on-line case, FIG. 4 shows a flow diagram of the process of updating the on-line monitoring rate using the novelty detection filter. The different equations involved in the calculation are also given next to their relevant components.

[0109] Starting from the leftmost component, update events e_i 401 are captured and suppose that N₁ new update events are captured between two consecutive monitoring times T_prev and T, which are kept in the buffer C_W′ 402 in FIG. 4. The update events e_i are input 403 into a novelty filter 410. The novelty filter 420 also has an input 404 of the parameter β to control the amount of filtering.

[0110] Further, suppose that prior to time T a total of N₂ events were captured, thus resulting in a total of N=N₁+N₂ events at time T. Then, update Equation 3 to maintain the channel cohesion value on-line:

[0111] $\begin{array}{cc}coh\left(C,T\right)=\frac{1}{N}\left[N_2·coh\left(C,T_{\mathrm{prev}}\right)+\sum _{i=N_2+1}^{N}sim\left(P\left(C_{W_{i-1}}\right),\left(C_{W_i}\right)\right)\right]& \left(8\right)\end{array}$

[0112] A history component 420 maintains both the last calculated channel cohesion value and the novel monitoring rate, and is updated after every monitoring probe. The coh(C, T_prev) value 405 is taken from the history component 420 and a cohesion calculator 430 calculates the new cohesion value which is input 406 to the novelty filter 410 and input 407 to the history component 420.

[0113] The novelty filter 410 uses the previous and the new cohesion values to calculate the standard deviation of the channel cohesion using Equation 6. It then applies the filtering rule of Equation 7 on the new N₂ update events captured at time T. The output of the novelty filter 410 is C_W′^nov 408 which is then used to derive the observed novelty update rate λ 440 at time T, which is combined 450 with the history learned rate (λ_C^now(T_prev)) 409 according to the adaptive rules of Equation 5, where C_W′←C_W′^nov. This provides the current monitoring rate λ_C^nov(T) 460 which is also returned 411 to the history component 420.

[0114] It is worth noting that by using this on-line scheme the expensive complexity in maintaining channel cohesion is reduced, where only the current buffer of captured events is considered in [T_prev, T] for novelty detection filtering.

Performance Analysis

[0115] A performance analysis study carried out provides empirical evidence that using the proposed content-based scheme compared to the content-free scheme can maintain high quality channel profiles with a significant savings in the number of probes required for this task. For example, the proposed content-based scheme reduces the number of times it probes channels by 50% while losing no more than 5% in quality.

[0116] For this purpose a simulation using a set of Web feeds was carried out. Each feed was monitored twice, once using the content-free monitoring scheme and once using the content-based monitoring scheme. The quality obtained was measured by applying each monitoring scheme on each feed according to Equation. 4. In addition, the total number of probes was recorded by monitoring each feed according to each scheme. Using these two measures it was further calculated for each feed the ratio of quality loss and probe cutoff (gain) between the two monitoring schemes as follows. Given a feed CεC, let Q(C, free) and K(C, free) denote the quality and number of probes of the content-free scheme, and let Q(C, content) and K(C, content) denote the quality and number of probes of the content-based scheme. Then calculate the quality loss as

[0117] $Q_{\mathrm{loss}}\left(C\right)=1-\frac{Q\left(C,\mathrm{content}\right)}{Q\left(C,\mathrm{free}\right)}\mathrm{and}\mathrm{probe}\mathrm{cutoff}\mathrm{as}$ $K_{\mathrm{cutoff}}\left(C\right)=\frac{K\left(C,\mathrm{free}\right)}{K\left(C,\mathrm{content}\right)}-1.$
Novelty Filtering Threshold Analysis

[0118] The effect of the filtering threshold β on profile quality was first studied. It was observed that increasing β increases the average quality per channel (feed). Obviously, larger β values imply that more events are considered novel and thus the corresponding monitoring rate is larger and increases quality. Moreover, for β≧0.1 the average quality among the different monitored channels is at least 95% from optimal. Finally, the 98-percentile curve of the channel profiles quality shows that for β≧0.25 at least 98% of the monitored channels have at least 95% of the optimal profile quality.

[0119] Using the same off-line case, the novelty detection scheme's trade-off between monitoring quality and saving monitoring resources has further been explored. The relative cutoff was measured in the number of probes compared to the loss in quality resulting from the cutoff. It has been shown that a small loss in quality compared to significantly fewer probes for reasonable β values. For instance, for β=0.1, 5% in average profile quality was lost while cutting down a third of the probes (50% gain).

Profile Window Size Analysis

[0120] The effect of the profile window size Win terms of the number of update events is considered for profile calculation on the quality-budget trade-off in the on-line monitoring setting. In this experiment, the threshold parameter is fixed β=0.1 that was learned in the off-line analysis.

[0121] It was observed that the quality loss is directly affected by the profile window size W. As the window size increases, the profile provides a wider perspective of the channel and therefore there is less chance of missing update events and deviating from the optimal profile; hence the quality loss is reduced.

[0122] Using the evaluation results presented in this section it is concluded that the monitoring scheme based on novelty detection indeed provides better utilization of the monitoring budget while producing high quality channel profiles. This observation will be supported in the next section that further explores the multi-channel monitoring case.

Multi-Channel Monitoring

[0123] A monitoring policy is allowed to monitor at most M channels in parallel. Thus, the profile quality obtained for multi-channel monitoring depends on the policy's on-line decisions of which channels to monitor over time. In the following a simple classification scheme for multi-channel monitoring policies is introduced. Inter-channel profile similarities are also introduced as a means of further refining the monitoring rates. Finally, an empirical evaluation study is discussed on the performance of these policies

Monitoring Policies

[0124] The importance of a channel is defined during time to be relative to its monitoring rate, as derived by the learning scheme presented previously. A channel with higher monitoring rate is considered more important. Note that the relative importance of a channel is changed dynamically over time according to the change in the derived monitoring rate.

[0125] The monitoring policies can be classified according to two main properties. The first property classifies the policies as either greedy or fair. A greedy monitoring policy monitors the most M important channels at any moment in time. It is worth noting that policies assume the availability of a given update model, while the present method learns the model on-line. Furthermore, it is noted that the described monitoring rate learning methods can be easily integrated with any other monitoring solution that requires an update model as input. Therefore, the analysis for the multi-channel case also provides a proof of concept for the ease of usage of the described methods by a wide range of other possible monitoring policies. A fair policy, on the other hand, selects M channels at random, according to the distribution induced by the channel relative importance values.

[0126] The second property relates to the policy attention to the content of the update events. A policy that ignores content is termed a content-free policy while a policy that considers content is termed a content-based policy. When the content is ignored, the monitoring rates are learned as described in Equation 5. When the content is also considered, the monitoring rate of each channel is calculated using the novelty detection filter. Since the monitoring rates of the channels determine their relative importance, a certain channel might have different importance values under content-free or content-based policies, due to the difference in monitoring rates.

[0127] Based on the classification described above, experiments have been made with four policy types: content-free (greedy), content-free (fair), content-based (greedy), and content-based (fair). The four policy types represent a wide range of possible policies for multi-channel monitoring.

Using Inter-Channel Profile Similarities for Refining Channel Monitoring Rates

[0128] A regularization scheme is proposed that can be used to further refine the channel monitoring rates based on inter-channel profile similarities. Using this scheme, a channel's monitoring rate can be refined according to its profile similarity to other channels' profiles without actually having to probe that channel. For example, suppose a channel's profile has high similarity with the profile of another channel that has just been monitored (and therefore, its monitoring rate has been updated). Therefore, an increase in the last channel's monitoring rate will cause an increase in the first channel's monitoring rate as well.

[0129] For this propose we maintain an n×n similarity matrix S, where a matrix entry S_i,j corresponds to the average profile similarity between channel C_i profile and channel C_j profile during a given time period T, which is calculated as follows:

[0130] $\begin{array}{cc}{S}_{i,j}=\frac{1}{T}{\int }_{T}sim\left(P\left(C_{i,T}\right),P\left(C_{j,T}\right)\right)dT& \left(9\right)\end{array}$

[0131] Every row i of matrix S is normalized by dividing each entry S_i,j by the total sum of values on that row. A definition is provided of the relationship between each pair of Web feeds as was determined by a human assessment, either an inclusion (denoted C₁˜C₂) or a similarity (denoted C₁⊂C₂). For example, the content published on the NY-TIMES.TECHNOLOGY.Circuits Web feed is almost completely contained in the content that is published on the NY-TIMES.TECHNOLOGY Web feed (resulting in very high profile similarity).

[0132] How the similarity matrix S is used to refine the monitoring rates is now discussed. Let {right arrow over (λ)}_C(T)=(λ_C1, λ_C2, . . . , λ_Cn) denote a vector of channel monitoring rates at time T, and let S^norm(T) denote the normalized similarity matrix as calculated at time T.

[0133] Then refine the monitoring rates as follows:
{right arrow over (λ)}_C′(T)=S^norm(T)×{right arrow over (λ)}_C(T)  (10)

[0134] It is worth noting that a channel C_i whose profile is not similar to any of the other channel profiles will have S_i,j≠i^norm=0 and S_i,i^norm=1, and therefore, after applying Equation. 10 its monitoring rate will remain unchangeable and depend solely on the channel's own update events (content). Otherwise, the channel shares some profile similarity with other channels in the system and therefore its monitoring rate is determined by the relative similarity its profile has with the other channel profiles and the current channel monitoring rates. As is shown later, such refinement can further improve the quality of maintained channel profiles.

Evaluation

[0135] An empirical evaluation has been carried out of the different policies that have been proposed in the monitoring policies using varied parameter settings. In general, the two content-based policies dominated their content-free counterparts. It is show that the monitoring rates refinement scheme of inter-channel profile similarities can further help to improve the performance.

Content-Based Versus Content-Free

[0136] FIG. 5 shows a graph 500 of the results of a simulation conducted monitoring a set of 132 channels while using different monitoring budgets (i.e., different M values). The graph 500 shows the average profile quality 501 obtained by the different policies for different M values 502. The two content-free policies 510, 520 are represented by complete lines with the greedy content-free policy 510 having triangle marks and the fair content-free policy having square marks. The two content-based policies 530, 540 are represented by dashed lines with the greedy content-based policy 530 having circle marks, and the fair content-based policy 540 having diamond marks. The profile window size was fixed to be W=20 and further fixed β=0 as the novelty filtering threshold for the content based policies.

[0137] The obvious observation from FIG. 5 is that the quality obtained by the policies increases as the monitoring budget increases. Furthermore, the empirical results reveal two interesting observations. First, both content-based policies 530, 540 dominate the content-free policies 510, 520 at every budget level. These results support the empirical observations made on single channel monitoring. The results further suggest that considering the content for the derivation of channel monitoring rates and using them to determine the relative channel importance can improve the quality obtained by content-based policies.

[0138] Second, it is observed that while fairness provides better quality over greediness for the content-free policies, this is not the same for the content-based policies. The content-based (greedy) policy 530 dominates the other three policies. This observation implies that when content is not considered, it is preferable to fairly share the budget between the different channels and avoid making local greedy decisions. On the other hand, these results further imply that content-based policies may benefit from some greedy decisions when the budget is spread more efficiently among the different channels. Nevertheless, fairness might still be the preferred choice, for example when the policy monitors channels where most of them have high novel content rates.

[0139] To explore the effect of profile window size on the four different policies the monitoring budget was fixed to be M=6 and the simulation run using different profile window size (W) values. It was observed that as the profile window size is increased, the quality obtained by all four policies is improved; yet again, with less remarkable improvement for the content-free (greedy) policy. It is also observed that the two content-based policies still dominate the two other content-free policies, and manage to better utilize the monitoring budget for every profile window size. Overall the two content-based policies show almost similar performance, suggesting that any type of content-based policy, whether fair, greedy, or in between, may achieve better performance than any possible content-free policy.

[0140] The effect of the novelty filtering threshold β on the performance of the two content-based policies was also evaluated. Again the monitoring budget was fixed to M=6 and fixed the profile window size to W=20. As β values increase, less update events get filtered and the two content-based policies behave differently. For β≦0 (more novelty filtering) it is observed that overall the two policies keep their same performance level, where the greedy policy further dominates the fair policy. On the other hand, for β>0 (less novelty filtering) it is observed that the two policies show opposite trends. While the fair policy remains quite robust and even improves slightly with the increase in the filtering threshold, the greedy policy performance completely deteriorates, almost to the level of quality obtained by its content-free counterpart greedy policy.

[0141] This can be explained as follows: as less update events are filtered, the monitoring rates are less affected by the novelty filter and the two policies behave similarly to their content-free counterpart policies. Therefore, the content-based (fair) policy dominates the content-based (greedy) policy in a similar way the content-free (fair) dominates the content-free (greedy) policy in FIG. 5.

[0142] To conclude, overall, the simulation results clearly show that taking content into consideration, by the multi-channel monitoring policies, improves the overall obtained quality of the channel profiles.

Utilizing Inter-Channel Profile Similarities

[0143] Finally, the inter-channel profile similarities refinement scheme was evaluated. For this purpose the content-based (fair) policy was experimented with using different levels of novelty filtering thresholds (β). For β>0, the content-based (fair) policy dominates the content-based (greedy) policy, and therefore, an aim is to improve its performance furthermore by utilizing inter-channel profile similarities.

[0144] It is observed, that in general, the refinement scheme manages to improve the baseline performance of the policy for all budget levels, where the highest improvement is by 15%. Furthermore, it is observed that the improvement is much better when mild novelty filtering is used (β=0.2). To explain, a more aggressive novelty filtering may result in lower inter-channel profile similarities, and therefore, a channel's monitoring rate is less effected by the other channels' monitoring rates.

[0145] It is concluded, that indeed, inter-channel profile similarities can be efficiently utilized to further refine the channel monitoring rates and improve the overall performance.

Summary

[0146] Some measures of profile monitoring quality have been described. Using these measures, it is demonstrated the necessity for methods for maintaining channel profiles. Both off-line and on-line monitoring cases are discussed and the challenges in monitoring profiles on-line. For the on-line case, a monitoring scheme is proposed based on reinforcement learning for the derivation of channel monitoring rates. An extension of this monitoring scheme is further presented by considering the content that is published on the channel. A novelty detection filter is proposed that refines the monitoring rate according to the rate at which novelty content is expected to be produced on the channel. It is also demonstrated how inter-channel profile similarities can be utilized to refine more the monitoring rates.

[0147] Using real-world data of Web feeds, the performance of the on-line monitoring scheme has been studied for single and multi-channel monitoring. The empirical study showed that the monitoring rates learning, combined with the on-line novelty detection, can guarantee high quality channel profiles, while significantly cutting down the monitoring budget which in turn improve the overall performance. Finally, it was showed that inter-channel profile similarities can be utilized to improve more the performance.

[0148] A profile management system may be provided as a service to a client over a network.

[0149] The invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

[0150] The invention can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer usable or computer readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus or device.

[0151] The medium can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk read only memory (CD-ROM), compact disk read/write (CD-R/W), and DVD.

[0152] Improvements and modifications can be made to the foregoing without departing from the scope of the present invention.