Query Scheduling in the Presence of Complex User Profiles
Haggai Roitman Avigdor Gal Louiqa Raschid







Query Scheduling in the Presence of Complex User Profiles
    Haggai RoitmanWork was done while the author was still a PhD student in the Technion - Israel Institute of Technology.  


IBM Research

Haifa University Campus, Mount Carmel

Haifa 31905, Israel

haggai@il.ibm.com Avigdor Gal  


Technion - Israel Institute of Technology

Haifa 32000, Israel

avigal@ie.technion.ac.il Louiqa Raschid 


University of Maryland

College Park, MD 20742

louiqa@umiacs.umd.edu


    December 30, 2023
=============================================================================================================================================================================================================================================================================================================================================================================================================================




Advances in Web technology enable personalization proxies that assist users
in satisfying their complex information monitoring and aggregation needs
through the repeated querying of multiple volatile data sources.
Such proxies face a scalability challenge when trying to maximize the number of
clients served while at the same time fully satisfying clients' complex
user profiles. In this work we use
an abstraction of complex execution intervals (CEIs) constructed over simple
execution intervals (EIs) represents user profiles and use existing offline approximation as a baseline for maximizing completeness of
capturing CEIs.
We present three heuristic solutions for the online problem of
query scheduling to satisfy complex user profiles. The first only considers
properties of individual EIs while the other two exploit properties of
all EIs in the CEI.
We use an extensive set of experiments on real traces and synthetic data to show that
heuristics that exploit knowledge of the CEIs dominate across multiple parameter settings.






§ INTRODUCTION


Advances in Web technology now
enable the creation of personalization proxies that assist users in satisfying
their complex information monitoring and aggregation needs. A proxy
actively decides when it needs to query information streams using pull-based
technology to satisfy clients' complex user profiles. Example platforms
include personalization portals and news aggregation applications (e.g.,
MyYahoo![<https://my.yahoo.com/>], Feedly[<https://feedly.com>]), which provide a single point of
access, services for continuously refreshing profiles, and tools for
integration via a mashup[See http://www.programmableweb.com/
for mashup examples.] of data extracted from multiple heterogeneous data
sources. Proxies are required to query multiple streams of events in a timely
manner to satisfy both the characteristics of servers, e.g., intensity
of updates, and the complex user profiles of clients.
This results in a scalability challenge when the proxy tries to satisfy
millions of clients.

Push-based solutions to satisfy complex user needs exist, e.g., WebSocket, WebRTC, HTTP/2 Push, etc.
Yet, data collection with
push-based solutions requires a high cost <cit.>, especially
if such push-based technology is not natural to the Web environment.
Pull-based solutions have considered only simple monitoring solutions
(e.g., <cit.>) that cannot satisfy complex user needs.
Lately, such complex requirements have been also introduced in the context of
Web and Social streams search, discovery, and analysis (e.g.,
<cit.>) which require the collection of data from
multiple (possibly interrelated) pull-only sources (e.g., RSS feeds).

Following <cit.>
, complex user profiles are represented in this work as a set of complex execution
intervals (CEIs). A CEI is an extension of a simple
execution interval (EI) <cit.>
which defines periods of time
during which the proxy has to probe the corresponding resources to satisfy the
profile. Querying multiple data sources is represented by combining individual
EIs to construct CEIs, possibly over a set of resources. Each EI in a CEI
should be monitored once for the CEI to be satisfied (or “captured"). A proxy schedules queries to corresponding resources in these
intervals to satisfy the profile.





We illustrate a personalized portal in Figure <ref>. A business analyst
identifies data sources that fit her needs, e.g., the CNN
Breaking News[<http://edition.cnn.com/>] website, CNN
Money.com,[<http://money.cnn.com/>] and Mish's Global Economic
Trend Analysis[http://globaleconomicanalysis.blogspot.com/] blog.
The data sources can be specified as URLs of online Web feeds (e.g.,
RSS, Atom) as shown by the RSS symbols in Figure <ref>. Alternatively,
Web Scraping[<http://en.wikipedia.org/wiki/Web_scraping>.]
technology allows her to delineate content that is to be extracted. Most Web
feeds are available via pull-only access protocols, e.g., via
 requests. However, some feeds may be pushed to the user,
with the appropriate registration, using proprietary technology (e.g.,
Google Alerts service[<www.google.com/alerts>]).

The analyst constructs a wide perspective by integrating data from multiple
business and market data sources. She is interested in querying CNN
Breaking News and CNN Money.com when a periodic querying of
Mish's Global Economic Trend Analysis blog detects that a new post in
the blog contains the word %oil%. This will be translated into the
three queries in Figure <ref>. The analyst is willing to accept a delay
of up to two minutes in probing  and a delay of 10 minutes
for the other two feeds.

According to <cit.>, 55% of Web feeds are updated hourly. Further,
about 80% of the feeds have an average size smaller than 10 KB, suggesting
that items are promptly removed from the feeds. These statistics on refresh
frequency and volatility illustrate the challenges faced in satisfying
millions of complex profiles.

Our research goal is
to support a new generation of solutions to address complex user profiles in (primarily)
pull-only settings.

Previously, <cit.>
 has introduced the problem of
capturing CEIs and showed that an offline solution is of high polynomial
complexity.
An approximate offline solution was presented in <cit.>
as a baseline
for maximizing completeness. In this paper, we present three online heuristics that
can scale to capture millions of CEIs. S-EDF is a simple extension of the
well-known Early Deadline First policy and only considers individual EIs while
making a schedule. MRSF considers the number of EIs in a CEI that have not
been scheduled and M-EDF considers the deadlines of all the EIs in the CEI
that have not been scheduled; thus, both exploit the properties of CEIs. Using
an extensive empirical analysis of real and synthetic data, we demonstrate the
dominance of the heuristics that exploit the properties of CEIs.

The paper is organized as follows:
In Section <ref> we summarize the model of
<cit.>
and define the problem. Section
<ref> presents the heuristic solution. We present experiments in
Section <ref> and in Section <ref> we describe
related work. Section <ref> concludes with future work.




§ MODEL AND PROBLEM DEFINITION




We summarize the model of complex user profiles presented in <cit.>,
for completeness sake. Clients query
Servers through proxies. A server manages resources and can be
queried (pull-based) by the proxy on behalf of its clients.
We discuss the three building blocks of our model, namely client
profiles, execution intervals, and schedules, and then define
the problem.



 §.§ Profiles and complex execution intervals



The complex information needs of a client are specified as a profile stored
at the proxy. A client profile is a set of queries, extended with
declarative monitoring guidelines. As an example, consider Figure <ref>, in which a user profile is defined as a set of three queries. The
 clause determines the triggering event (e.g.,  or oil, with the
obvious interpretation). The  clause determines the slack the
proxy is given in reporting an event (e.g., ).


A client's complex user profile is translated into a set of resources and
complex execution intervals (CEI). An execution interval (EI) <cit.>
defines periods of time during which the resource must be
probed. A profile combines individual EIs, possibly over a set of resources,
to construct a CEI. Each EI in a CEI should be monitored once for the CEI to
be satisfied (or “captured"). Details of a query language
to express complex user profiles is presented in <cit.>.
We use
pseudo continuous queries in our examples. We expect that a proxy will
provide tools, e.g., Web scraping, to provide intuitive interfaces to
clients.

Formally, let ℛ={r_1,r_2,...,r_n} be a set of n
resources and let 𝒯=( T_1,T_2,...,T_K) be an
epoch with K chronons.[
A chronon is an indivisible unit of time.] We assume the proxy manages a set
of client profiles 𝒫={p_1,p_2,… ,p_m}. A client
profile p={η |η =⟨ I_1,I_2,… ,I_t⟩} is a collection of CEIs. A CEI η contains several EIs,
where each EI I is associated with a resource r∈ℛ and I
contains a start and finish chronon I=[T_s,T_f];T_s,T_f∈
𝒯;T_s≤T_f. An interesting class of profiles, we denote by 𝒫^[1], are profiles for which any EI I of any CEI has a width
of exactly one chronon. This class serves later in our analysis.


Profiles, CEIs, and EIs construct a hierarchy as seen in Figure <ref>.
Two CEIs within the same profile, or two EIs within the same CEI, are 
siblings. To model profile complexity, we denote by rank(p) the
maximal number of execution intervals in any CEI η∈p

=max_η∈p{|η|}, where |η| is the number of execution intervals in η
. The definition is easily extended to a set of profiles 𝒫 as
follows: rank(𝒫)=max_p∈𝒫{ rank(p)}.

The beginning of an interval is determined by an update event at a resource
or a temporal event (e.g., every three minutes). In the case that the
server will push the update event, or for a temporal event, the
beginning of the interval is deterministic. A proxy may also need to predict
an update event using an update model and stochastic modeling <cit.>.
The window (length) of the interval is determined with respect to the
stream of update events, (e.g., update = overwrite), or as a temporal
event (e.g., within five minutes of the beginning of the interval).
For example, a profile for Web scraping over Web feeds requires that
published items be collected before the server overwrites them; this is a
stochastic event.



The CEIs of our motivating example (see Figure <ref>) are illustrated
in Figure <ref>. Probing the  feed every 3
minutes, with a possible slack of 2 minutes, is represented by the first set
of EIs, labeled . We note that by registering to a Pub/Sub
system, the proxy may be informed of updates to Mish's blog. However, the
proxy still has to query to get the updated blog. For posts on Mish's blog
that contain the keyword , EIs will be scheduled to probe the
other two resources, labeled  and , respectively. In
this example, some CEIs will only have a rank of 1 (when updates on Mish's
blog do not include ) while others will have a rank of 3.

EIs of the same or different profiles may overlap in time; two cases of
overlap are interesting. When EIs of different resources overlap (inter-resource overlap), then they are all candidates for being
simultaneously queried by the proxy. This can lead to congestion when
the available budget is low. When EIs associated with an identical
resource overlap (intra-resource overlap), there is the potential to
exploit this overlap to build an efficient query schedule. While delaying a
query on a resource could lead to more efficient schedules, a delay may also
result in failing to capture an EI, e.g., there is congestion-based
competition in a future chronon.
The special case of no intra-resource overlap is of theoretical
interest since it allows us to present some bounds <cit.>.



 §.§ Schedules


 A data delivery schedule S={s_i,j}_i=1,...,n;j=1,...,K (n resources and K chronons) assigns s_i,j=1 if resource r_i∈ℛ should be queried by the
proxy at chronon T_j∈𝒯, else s_i,j=0. We denote by 𝕊 the set of all possible schedules.

The expression 𝕀(I,S) indicates whether a schedule S
successfully captures (i.e., some resource r_i is queried during)
the EI I. Given a profile p, a CEI η∈p, and an EI I∈η
that refers to resource r_i∈ℛ, we have the following:

    𝕀(I,S)={[              1, ∃ T_j∈I:s_i,j=1;              0,       otherwise ].


We extend 𝕀(I,S) to describe capturing a CEI as follows: Given a
profile p and a CEI η∈p, we say that η is captured
by schedule S∈𝕊 if 𝕀(η ,S)=∏_I∈η𝕀(I,S)=1.



 §.§ Problem statement


 We assume that the proxy has a limited amount of
resources that can be consumed for querying. In this paper we consider a
constraint similar to the one used in prior works of Web Monitoring <cit.> and Web Crawlers <cit.>, where at each chronon T_j∈𝒯 the proxy can query up to C_j resources. This
constraint is represented by a budget vector C⃗=(
C_1,C_2,… ,C_K).

Given a set of client profiles 𝒫={p_1,p_2,...,p_m}, the
proxy objective is to maximize gained completeness, i.e., the
number of CEIs from 𝒫 that are captured given the budget C⃗. A CEI is successfully captured once all of its execution intervals
are captured. Every CEI η∈p that is successfully captured by the
proxy schedule (indicated by 𝕀(η ,S)=1) increases the gained
completeness.

Given a schedule S∈𝕊, the gained completeness (denoted
 in short) from monitoring 𝒫 during 𝒯
according to S is calculated as follows (where | p|
denotes the number of CEIs in profile p):

    𝙶𝙲(𝒫,𝒯,S)=∑_p∈𝒫∑_η∈p𝕀(η ,S)/∑_p∈𝒫|
    p|


Formally, the problem of query scheduling in the presence of complex user
profiles is defined by the following constrained optimization problem.

Given a set of profiles 𝒫 and an epoch 𝒯:

    [                   maximize (𝒫,𝒯,S); s.t. ∑_i=1^ns_i,j≤C_j, ∀j=1,2,… ,K ]



Previously, <cit.>
presented two offline solutions to Problem <ref>. In an offline setting, the proxy is provided with all CEIs in 𝒫 for K chronons in advance and
has to determine the schedule S of probing resources in ℛ. The
offline solutions are of high polynomial complexity <cit.>. Yet, they provide a
baseline of optimal performance.



§ QUERY SCHEDULING POLICIES


 We now present three heuristic solutions to the problem
of query scheduling in the presence of complex user profiles. CEIs are not
known a priori and proxy decision making is done online. In our example, the
EIs for querying the  feed can be determined in advance,
but query scheduling for the other two streams, (CNN Breaking News
and CNN Money.com) depends on the contents of the first feed. At
every chronon T_j, the proxy may receive a set of new CEIs. The proxy
then has to decide which resources in ℛ to probe, while
considering the set of all candidate CEIs, including those submitted prior
to T_j, which have not been completely captured yet, and the new set of
CEIs. We denote the set of all candidate CEIs at chronon T_j as cands(η ) and the union bag of all their EIs (termed candidate EIs
) as cands(I)=_η _q∈cands(η )η _q
. The bag notation () is used due to intra-resource overlaps.



 §.§ Policies




To determine which candidate EIs in cands(I) to choose the proxy
uses policies. At chronon T_j, a policy Φ considers cands(I) and the budget C_j, and returns up to C_j EIs to probe.
Such policies can be efficiently implemented.

Each of the policies we propose can be executed in either a 
non-preemptive or preemptive manner. Non-preemptive policies do not
allow new candidate CEIs to be scheduled for monitoring at chronon T_j
if previously probed CEIs need to be probed at T_j. Therefore, a
non-preemptive policy Φ first selects I∈cands(I) that
belongs to previously probed CEIs. Then, if there is any budget left, Φ
selects EIs from the newly introduced CEIs. It is worth noting that even the
non-preemptive policies do not guarantee a successful capture of a CEI that
has been probed at least once. If the number of previously probed CEIs
exceeds the bandwidth budget, some of these CEIs may be dropped.

Policies can be classified according to
the amount of information about candidate CEIs they use. We propose a three
level classification, as follows.

Individual EI level: An individual EI level policy
utilizes only the local properties of a single EI without considering
the parent CEI or sibling EIs.As a representative of this level we suggest the Single
Interval Early Deadline First (or  in short) policy, Φ _𝚂𝙴𝙳𝙵. This policy is modeled on the
well known EDF policy <cit.>, prefering EIs that have the earliest
deadline. Given an execution interval I and a chronon T, the deadline is
calculated (in terms of number of remaining chronons) as follows:

    𝚂𝙴𝙳𝙵(I,T)=I.T_f-T+1

Proposition <ref>
holds
for this policy.


Given 𝒫 without intra-resource overlap, and
rank(𝒫)=1, the policy Φ_𝚂𝙴𝙳𝙵 is
optimal.


WIC <cit.>, a well-known monitoring solution for the Web, can
also be classified as an individual EI level policy. We note that WIC was
designed to address a different optimization goal compared to our Problem 
<ref>). WIC's solution balances completeness with
timeliness, providing a bound of 2-competitiveness for its optimization
goal. WIC defines a utility for each EI and picks those EIs with the maximum
accumulated utility for probing in each chronon. For our experiments in
Section <ref> we implemented WIC (details provided later)
and compared the performance of WIC with the online policies from this
section.

Rank level: A rank level policy bases its decision on
profile complexity by considering the rank of the parent CEI. As a
representative of this level we suggest the Minimal Residual Stub First
 () policy, Φ _𝙼𝚁𝚂𝙵. This policy prefers EIs
that belong to parent CEIs with a minimal number of EIs left to be captured.
The intuition behind this policy is that a CEI with less EIs remaining to
probe has a higher probability of success. Formally, given an EI I, I∈η and η∈p, then the  value is calculated as
follows:

    𝙼𝚁𝚂𝙵(I)=rank(p)-∑_I^'∈η𝕀(I^',S)

where I^' iterates over all EIs in η. The following
proposition provides a bound for the performance of this policy.

Given 𝒫 without intra-resource overlap and
rank(𝒫)=k, the Φ_ policy is
l-competitive, where:

    l=max_η∈𝒫(∑_I∈η|I|).



Multi-EI level: A multi-EI level policy utilizes the
properties of all EIs of a parent CEI (including sibling EIs). As a
representative, we suggest the Multi Interval EDF ()
policy, Φ _𝙼𝙴𝙳𝙵, which prefers
execution intervals that have the minimal  value, calculated
as follows (for I∈η):

    𝙼𝙴𝙳𝙵(I,T)=∑_I^'∈η( 𝚂𝙴𝙳𝙵( I^',T)
    ·[ 1-𝕀( I^',S) ] )


The  value combines the EDF values of execution interval I
and its siblings that were not captured by chronon T. For each I^' (iterating over all EIs in the CEI) if the EI is not yet active (chronon T<I^'.T_s), then the EDF value is calculated with T=0, taking
into account the full length of the EI.
The intuition is to favor CEIs with less total remaining chronons so as to
increase their probability of capture, leading to a gain in completeness.

The following proposition discusses the class 𝒫^[1] of
profiles. Recall that we denote by 𝒫^[1] a set of profiles for
which any EI I of any CEI has a width of exactly one chronon.



For problem instances with 𝒫^[1] profiles the
 policy is equivalent to the  policy.






Figure <ref> illustrates the value each policy assigns to a candidate
CEI with four execution intervals. At
chronon T,  counts the number of remaining chronons until the end
of the execution interval (5).  counts the number of
remaining EIs in the CEI (4). Finally, 
accumulates the number of chronons of all remaining EIs (22). The values each policy assigns are given at
the bottom of the figure.





Figure <ref> illustrates the decision making
of each of the policies, when faced with multiple complex execution
intervals and a bandwidth constraint. Here, we have two candidates,
the first (CEI_1) with four required EIs (marked in black) and
the second (CEI_2) with three EIs (marked in gray).
Dashed lines connect a parent complex execution interval to its
children. Assume the current time is T and only one EI can be
selected (C_T=1). At T the first two EIs of CEI_1 were
successfuly captured (see the √ signs near the top of the
figure) yet we allow preemption. A decision needs to be taken
whether to probe EI_1 or EI_2.

 counts the number of remaining chronons until the end
of the current EI, yielding 5 for EI_1 and 6 for EI_2.
Therefore, the  policy will stick with CEI_1.

 counts the number of remaining EIs. With 2 remaining
EIs for CEI_1 and 3 remaining EIs for CEI_2,  will stick
with CEI_1, choosing EI_1.

Finally,  accumulates the number of chronons in all
the remaining EIs. We have 19 chronons for CEI_1 and 16 for
CEI_2. Therefore, CEI_1 will be preempted, since 
favors EI_2.




§ EXPERIMENTS






 §.§ Datasets and Experiment Setup







  §.§.§ Datasets


We used two data streams of update events in our experiments. The first is a
real-world trace of
732 auctions for Intel, IBM, and Dell laptop computers[<http://git.annonymous.com>.].
To obtain the traces, we used an RSS feed retrieved for a search query on
a popular e-commerce website
to obtain timestamps of
updates and we reconstructed the real stream. Each auction lasted 3 days with a total of 11,150 bids in the datasets. We also used a synthetic data
stream that was generated using a Poisson based update model; the parameter
λ controls the update intensity of each resource.



  §.§.§ Profiles and CEIs




We used a profile template to specify complex user needs and to generate
multiple profile instances. “𝙰𝚞𝚌𝚝𝚒𝚘𝚗𝚆𝚊𝚝𝚌𝚑(
k)" is a sample template that monitors the prices of k auctions
and notifies the user after a new bid is posted in all k auctions.
The start of an EI to monitor an auction will be prediced from an update model
constructed from the traces. The length of each EI can be specified as
 or . The  requests
every new bid to be delivered before the next update occurs and
overwrites the last published bid.

The  requests  every new bid to be delivered within a
window of  chronons from the time the bid was posted.


We generated up to m profile instances from a template using a 2-stage
process and 2 Zipf distributions. Recall that rank(𝒫)=k
corresponds to k EIs in a CEI. We determine the rank of each profile
instance according to a Zipf(β,k) distribution, where k is specified
in the template. β=0 implies a random selection or a uniform
distribution U[1,k], while a positive β value produces more profiles
whose CEIs include less (< k) EIs. This stage models
a variance of the complexity of a profile (termed intra-user
preferences).


In a second step, given some profile of rank k, we use a Zipf(α,n)
distribution to select a set of resources. α=0 implies a random
selection or a uniform distribution U[1,n], while positive α value
implies a preference towards “popular" resources. This stage
models inter-user preferences and imitates the way popular resources
are chosen by users. For Web Feeds the value of α was estimated to be
1.37 <cit.>.





  §.§.§ Experimental Setup


We implemented a simulation-based environment to test the different solutions.
Given a profile template and an update event stream, we generate m profile
instances and their CEIs.
The proxy receives as input at each chronon the set of CEIs that overlap in
that chronon.
We repeated each execution
10 times and recorded the average performances. Table
<ref> summarizes the control parameters. We report on
two metrics, namely completeness (as given in Eq.
<ref>) and runtime costs, the execution time
normalized over the total number of EIs that must be captured.

For comparison
we implemented WIC <cit.>.
We used a straightforward implementation of the algorithm presented in
<cit.>, setting  to be uniform (that is, for each
resource r_i and chronon T 𝚞𝚛𝚐𝚎𝚗𝚌𝚢_i(T)=1), 
to be either  or 
 
<cit.> (which corresponds to our ), and p_ij
set to 1 if resource r_i has an update at chronon T_j, otherwise we
set p_ij=0.
While we note that WIC does not handle complex CEIs, for certain parameter
settings, i.e., with rank(𝒫)=1, 𝚆=0, and with no
intra-resource overlap, both WIC and  provide an optimal
schedule <cit.>. Therefore both  and WIC are used as
a baseline of simple EI policies for comparison. In addition, we implemented
an offline approximation for the problem, as introduced in <cit.>
, which serves as another baseline for evaluating the performance of the
proposed policies.

The various policies and the experimental setup were implemented in Java, using JDK version 7. The JVM was initiated with a
heap-memory size of 1.00GB.





 §.§ Comparative policy performance


 



We have two versions of each of the online policies, namely with and without
preemption. To compare them, we used the real-world trace and the profile
template 𝙰𝚞𝚌𝚝𝚒𝚘𝚗𝚆𝚊𝚝𝚌𝚑(3) (each profile will monitor up to 3
auctions). We also used a window of =20, i.e., the new bid
must be reported within 20 chronons. Finally, we used a budget of C=2 probes
per chronon. We compared the gained completeness of each online policy using
various parameter settings, with and without preemption. Figure <ref>
reports on the results with 400 auction resources, 1590 CEIs and 3599
simple EIs.

Typically  and  perform better then 
over a range of experiment settings. This improved performance can be
attributed to the use of more knowledge about the rank of the profile and the
number of EIs to be captured. Our complete set of experiments with
 indicates that it performs better without preemption for C=1,
while for C>1, the preemptive version is better. The other two policies,
 and , perform better with preemption in all but a
few cases. These results were consistent for most of the parameter settings
that were tested, with a difference of up to 20% in completeness between
the preemptive and non-preemptive versions of each online policy. We label the
policies “" to denote the preemptive version and
“" for non-preemptive.



 §.§ Policies vs. the Baseline


We compared the performance of the proposed policies and WIC, with the offline
approximation solution, for different parameter settings. We used the real
trace and the 𝙰𝚞𝚌𝚝𝚒𝚘𝚗𝚆𝚊𝚝𝚌𝚑(k) profile template with
𝚆=0, i.e., the client requires an immediate probing
of each EI as soon as a bid is posted.

We first examine 𝒫^[1] profiles. To generate these profiles and
CEIs, we use C=1 and avoid intra-resource overlap by ensuring that each EI
of a CEI refers to a distinct resource. For this parameter setting, the
offline approximation guarantees a 2k-approximation <cit.> (for rank(𝒫
^[1])=k). 
<ref>, both  and 
policies perform the same and we only report on .



Figure <ref> reports on the results, where the
rank(𝒫) varies from 1 to 5. For this experiment, if
rank(𝒫)=k, then all CEIs that were generated for that problem
instance have exactly k EIs. Figure <ref> and experiments
with other settings show that both  and 
policies typically dominate the offline approximation, the 
policy (preemptive or not), and WIC. The  outperforms the
offline approximation by up to 10%. The  policy does not
dominate the offline approximation yet it dominates WIC, as is the offline
approximation. We observe that complex profiles with higher rank force the
proxy to devote more probes to each CEI and completeness decreases for all policies.

We can compute an upper bound on the optimal completeness for
rank(𝒫)=1 by using  optimal completeness for the
same problem instance. We can also determine a worst case upper bound on the
optimal completeness for rank(𝒫)>1. To do that, for every
rank(𝒫) level, we measure the completeness in terms of single EIs
that are captured (i.e., assuming that rank(𝒫)=1); This
measure provides a worst case upper bound on the optimal performance. This
bound is illustrated by the dashed line in Figure <ref>.
Therefore, we observe that the completeness achieved by the complex policies
is actually very high for every profile complexity level (from optimal
completeness for rank(𝒫)=1 to at least 77% of the optimal
completeness for rank(𝒫)=5). To conclude, the complex policies
dominate both the offline approximation and the best possible simple policies
available in the literature, and provide good performance guarantees.



 §.§ Runtime scalability


 



We next performed scalability analysis and measured the runtime of the offline
approximation and the online policies aggregated over a run with K=1000
chronons. The results are given in Figure <ref>. The
runtime is given per a single EI processing unit. We ran the experiments with
increasing number of profiles, generating as a result an increasing number of
execution intervals. The number of profiles and the update intensity that were
used are given on top of the curves, and on the lower right side of the graphs
respectively. First we compared the offline approximation and online policies
with small workloads (λ=20 and 100-500 profiles; see Figure
<ref>(1)). We can see that the offline approximation
performs much worse then the online policies. We further continued to
investigate the scalability of the online policies and increased the workload
using 2.5 times higher updates intensity and increased the number of profiles
up to 2500 (see Figure <ref>(2)). We can see that
there is still a linear trend in the policies runtime behavior, suggesting
that for real problem instances the online policies are scalable and more
robust compared to the offline approximation.



 §.§ Workload analysis


 


We next studied the effect of different workload settings on the gained
completeness of policies. For this purpose we controlled two parameter
settings, namely the average updates intensity per resource (given by
λ), and number of profiles (m) (where the other parameters are those
described in Table <ref>). It is worth noting that for
this analysis we used a strict budget allocation of C=1. In Section
<ref> we show how a more lenient budget improves performance.

Figure <ref>
contains the results of this analysis for increasing update intensity.
In general, we observe that both the  and 
policies are much better then  policy for all workload
parameter settings that were used. We also observe that the 
performs slightly better then .
Finally, as the average update intensity increases, there are more updates to
each resource, and thus, each profile requires to capture more CEIs, resulting
in decreased gained completeness.
The effect of number of profiles the proxy has to consider, on the policies
performance (not presented here due to space considerations) is similar.




 §.§ The impact of user preferences


 We now report on the impact of user preferences on performance.
For this analysis, we have used various settings of α (inter-user
preferences), and β (intra-user preference), where the other parameters
were set for the baseline values of Table <ref>. See
Section <ref> for the definition of these two parameters.

Figure <ref>(1) shows the impact of inter-user preferences. As
α increases, there is less random selection of resources in each
profile, with more execution intervals coming from popular resources. The
online policies gain more completeness due to more opportunities to capture
intra-resource overlapping execution intervals of popular resources.
Furthermore, we observe that the  policy is dominated by the
two other policies.


Figure <ref>(2) shows the impact of intra-user preferences. As
β increases, users prefer less complex profiles. The impact, as observed
in Figure <ref> as well, is an increase in performance. We
further observe that both  and  policies
still outperform the  policy, with a slight variation
between the first two. This may be attributed to the fact that there are still
CEIs that require to probe more then one execution interval, where
 was shown in Figure <ref> to be dominated.



 §.§ Effect of budgetary limitations


 We studied the effect of budgetary limitations on the different
policies. So far we have used a strict budgetary allocation of C=1.
We now show the impact of additional budget on performance. The results are
given in Figure <ref>. We observe that as the proxy budget
increases, allowing it to probe more resources per chronon, a remarkable
increase in performance is achieved. In particular,  policy
utilizes the budget much better then the  policy. We conclude
that the aggregated view of  and  policies
utilizes the budget better.



§ RELATED WORK





Many contemporary applications, such as Web crawlers and monitors <cit.>, news feeds aggregators <cit.> and social streams monitors <cit.>,
may require nowadays complex access patterns to multiple Web sources.
We can classify these applications based on their information gathering
strategy.

With push based systems, data is pushed to the system and the research focus
is mainly on aspects of efficient data processing, where load shedding
techniques <cit.> can be applied to determine the portions of the data
that must be processed. Examples are publish-subscribe (pub-sub) (e.g.,
 <cit.>), stream processing (e.g., <cit.>), and complex event
processing (CEP) (e.g., <cit.>). Pub-sub systems
such as the ONYX system <cit.> allow the registration of complex
requirements at servers and focus mainly on the trade-off between data
processing efficiency and the expressiveness of the queries that can be
processed by the system. Stream processing systems are also push-based in
nature and focus mainly on smart filtering and load shedding techniques.
Complex event processing (CEP) systems (e.g., <cit.>)
assume the pushing of a stream of raw events and focus
mainly on efficient complex event identification.

In our work, we assume a pull based solution; there is a need to collect the
data, e.g., via periodic queries. In the presence of stream data that
is available via pull-only access (e.g., Web feeds), complex queries
must cross multiple streams. Example systems include query processing in
sensor networks (e.g., <cit.>), continuous
queries (CQ) and Web monitoring (e.g., <cit.>), Grid and Web
services query processing (e.g., <cit.>), and
mashups of Web sources (e.g., <cit.>). Current
pull based monitoring is unable to handle complex data needs over multiple
data sources. For example, current works in CQ and Web monitoring such as
WIC <cit.> handle only simple single resource monitoring tasks
that are assumed to be independent of each other.



§ CONCLUSIONS AND FUTURE WORK


 In this work we presented efficient query scheduling
online policies for the satisfaction of complex data needs in pull based
environments that involve volatile data. Using intensive experiments we
analyzed the performance of these policies under different settings and
showed that even under restrictive budget constraints they can perform well.
We further showed that utilizing additional profile structures can assist to
improve performance significantly.

The problem presented in this work can be extended in several
interesting directions. First, we do not consider the varying costs of
probing resources. These variations may be due to computational costs, 
e.g., extracting a stock price may be cheaper than searching for a keyword
in a blog, the bandwidth needed to download results of varying size,
monetary charges at the servers, etc. In this case, queries will not
consume the same budget. A second extension is to consider more general
profile satisfaction constraints given as client profile utilities. Such
utilities can help to construct better prioritized policies.


plain
10

agarwal2014time
Nitin Agarwal, Debanjan Mahata, and Huan Liu.
Time-and event-driven modeling of blogger influence.
In Encyclopedia of Social Network Analysis and Mining, pages
  2154–2165. Springer, 2014.

AltinelBCKLMMNSS07
Mehmet Altinel, Paul Brown, Susan Cline, Rajesh Kartha, Eric Louie, Volker
  Markl, Louis Mau, Yip-Hing Ng, David E. Simmen, and Ashutosh Singh.
Damia - a data mashup fabric for intranet applications.
In VLDB, pages 1370–1373, 2007.

ArasuBBDIRW03
Arvind Arasu, Brian Babcock, Shivnath Babu, Mayur Datar, Keith Ito, Itaru
  Nishizawa, Justin Rosenstein, and Jennifer Widom.
Stream: The stanford stream data manager.
In SIGMOD Conference, page 665, 2003.

BansalK07
Nilesh Bansal and Nick Koudas.
Blogscope: A system for online analysis of high volume text streams.
In VLDB, pages 1410–1413, 2007.

CherniackBBCCXZ03
Mitch Cherniack, Hari Balakrishnan, Magdalena Balazinska, Donald Carney, Ugur
  Çetintemel, Ying Xing, and Stanley B. Zdonik.
Scalable distributed stream processing.
In CIDR, 2003.

Chi05
Yun Chi, Haixun Wang, and Philip S. Yu.
Loadstar: load shedding in data stream mining.
In VLDB '05: Proceedings of the 31st international conference on
  Very large data bases, pages 1302–1305. VLDB Endowment, 2005.

DemersGHRW06
Alan J. Demers, Johannes Gehrke, Mingsheng Hong, Mirek Riedewald, and Walker M.
  White.
Towards expressive publish/subscribe systems.
In EDBT, pages 627–644, 2006.

DemersGPRSW07
Alan J. Demers, Johannes Gehrke, Biswanath Panda, Mirek Riedewald, Varun
  Sharma, and Walker M. White.
Cayuga: A general purpose event monitoring system.
In CIDR, pages 412–422, 2007.

DeshpandeGMHH04
Amol Deshpande, Carlos Guestrin, Samuel Madden, Joseph M. Hellerstein, and Wei
  Hong.
Model-driven data acquisition in sensor networks.
In VLDB, pages 588–599, 2004.

Diao07
Yanlei Diao, Deepak Ganesan, Gaurav Mathur, and Prashant Shenoy.
Rethinking data management for storage-centric sensor networks.
In CIDR 2007: Proceedings of the third beinnial conference on
  inovation data systems research, 2007.

DiaoRF04
Yanlei Diao, Shariq Rizvi, and Michael J. Franklin.
Towards an internet-scale xml dissemination service.
In VLDB, pages 612–623, 2004.

ECKSTEIN2007
J. Eckstein, A. Gal, and S. Reiner.
Monitoring an information source under a politeness constraint.
INFORMS Journal on Computing, 20(1):3–20, December 2007.

GAL2000b
A. Gal and J. Eckstein.
Managing periodically updated data in relational databases: A
  stochastic modeling approach.
Journal of the ACM, 48(6):1141–1183, 2001.

Garg04
Shaveen Garg, Krithi Ramamritham, and Soumen Chakrabarti.
Web-cam: monitoring the dynamic web to respond to continual queries.
In SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international
  conference on Management of data, pages 927–928, New York, NY, USA, 2004.
  ACM.

Gruhl06
Daniel Gruhl, Daniel N. Meredith, Jan H. Pieper, Alex Cozzi, and Stephen Dill.
The web beyond popularity: a really simple system for web scale rss.
In WWW '06: Proceedings of the 15th international conference on
  World Wide Web, pages 183–192, New York, NY, USA, 2006. ACM.

HONG2005
Venugopalan Ramasubramanian Hongzhou Liu and Emin Gun Sirer.
Client and feed characteristics of rss, a publish-subscribe system
  for web micronews.

LaFleur:2015
Alexandra La Fleur, Kia Teymourian, and Adrian Paschke.
Complex event extraction from real-time news streams.
In Proceedings of the 11th International Conference on Semantic
  Systems, SEMANTICS '15, pages 9–16, New York, NY, USA, 2015. ACM.

Liu73
C.L. Liu and J.W. Layland.
Scheduling algorithms for multiprogramming in a hard real-time
  environment.
Journal of the ACM, 20(1):46–61, January 1973.

LiuPT00WebCQ
Ling Liu, Calton Pu, and Wei Tang.
Webcq: Detecting and delivering information changes on the web.
In CIKM, pages 512–519, 2000.

Mathioudakis:2010
Michael Mathioudakis and Nick Koudas.
Twittermonitor: Trend detection over the twitter stream.
In Proceedings of the 2010 ACM SIGMOD International Conference
  on Management of Data, SIGMOD '10, pages 1155–1158, New York, NY, USA,
  2010. ACM.

osborne2014real
Miles Osborne, Sean Moran, Richard McCreadie, Alexander Von Lunen, Martin D
  Sykora, Elizabeth Cano, Neil Ireson, Craig Macdonald, Iadh Ounis, Yulan He,
  et al.
Real-time detection, tracking, and monitoring of automatically
  discovered events in social media.
2014.

PANDEY2004
S. Pandey, K. Dhamdhere, and C. Olston.
WIC: A general-purpose algorithm for monitoring web information
  sources.
In Proceedings of the International conference on Very Large
  Data Bases (VLDB), pages 360–371, Toronto, ON, Canada, September 2004.

paul2016social
Michael J Paul, Abeed Sarker, John S Brownstein, Azadeh Nikfarjam, Matthew
  Scotch, Karen L Smith, and Graciela Gonzalez.
Social media mining for public health monitoring and surveillance.
In Biocomputing 2016: Proceedings of the Pacific Symposium,
  pages 468–479, 2016.

ROITMAN2008b
H. Roitman.
Profile Based Online Data Delivery - Model and Algorithms.
PhD thesis, Technion – Israel Institute of Technology, 2008.

ROITMAN2008
H. Roitman, A. Gal, , and L. Raschid.
Capturing approximated data delivery tradeoffs.
In Proceedings of the IEEE CS International Conference on Data
  Engineering, Cancun, Mexico, 2008.

ROITMAN2008a
H. Roitman, A. Gal, , and L. Raschid.
Satisfying complex data needs using pull-based online monitoring of
  volatile data sources.
In Proceedings of the IEEE CS International Conference on Data
  Engineering, Cancun, Mexico, 2008.

ROITMAN2009
H. Roitman, A. Gal, , and L. Raschid.
Web monitoring 2.0: Crossing streams to satisfy complex data needs.
In Proceedings of the IEEE CS International Conference on Data
  Engineering, Shanghai, China, 2009.

Roitman2008MDC
Haggai Roitman, David Carmel, and Elad Yom-Tov.
Maintaining dynamic channel profiles on the web.
Proc. VLDB Endow., 1(1):151–162, August 2008.

Sakaki:2010
Takeshi Sakaki, Makoto Okazaki, and Yutaka Matsuo.
Earthquake shakes twitter users: Real-time event detection by social
  sensors.
In Proceedings of the 19th International Conference on World
  Wide Web, WWW '10, pages 851–860, New York, NY, USA, 2010. ACM.

Srivastava06
Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom, and Rajeev Motwani.
Query optimization over web services.
In VLDB '06: Proceedings of the 32nd international conference on
  Very large data bases, pages 355–366. VLDB Endowment, 2006.

WOLF2002
J. L. Wolf, M. S. Squillante, P. S. Yu, J. Sethuraman, and L. Ozsen.
Optimal crawling strategies for web search engines.
In Proceedings International WWW Conference, pages 136–147,
  Honolulu, Hawaii, USA, 2002. ACM Press.

woodall2017
William H Woodall, Meng J Zhao, Kamran Paynabar, Ross Sparks, and James D
  Wilson.
An overview and perspective on social network monitoring.
IISE Transactions, 49(3):354–365, 2017.

WuDR06
Eugene Wu, Yanlei Diao, and Shariq Rizvi.
High-performance complex event processing over streams.
In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international
  conference on Management of data, pages 407–418, New York, NY, USA, 2006.
  ACM.

ZhangARS05
K. Zhang, Henrique Andrade, Louiqa Raschid, and Alan Sussman.
Query planning for the grid: adapting to dynamic resource
  availability.
In CCGRID, pages 751–758, 2005.





