Monitoring MaxRS in Spatial Data Streams
Daichi Amagata

Takahiro Hara

Department of Multimedia Engineering Graduate
School of Information Science and Technology
Osaka University

Department of Multimedia Engineering Graduate
School of Information Science and Technology
Osaka University

amagata.daichi@ist.osaka-u.ac.jp

hara@ist.osaka-u.ac.jp

ABSTRACTDue to the increase of GPS enabled devices and a lot of locationbased services, spatial objects are continuously generated. This paper addresses a problem of monitoring MaxRS (Maximizing Range
Sum) in spatial data streams. Given a set of weighted spatial (2dimensional) objects, this problem is to monitor a location of agiven user-specified sized rectangle where the sum of the weightsof the objects covered by the rectangle is maximized. Many real life
applications obtain a benefit from monitoring MaxRS, e.g., traffic
analysis and event detection in urban sensing, but this problem has
not yet been addressed so far. Although some algorithms for static
objects have been proposed, executing such an algorithm whenever
new objects are generated is computationally expensive. These motivate us to develop an efficient algorithm that can monitor MaxRS
efficiently. In this paper, we first design a basic algorithm that isbased on an index framework and incrementally updates the result.
We then enhance the algorithm and show that the enhanced algorithm can deal with error-guaranteed approximation and monitoring top-k MaxRS. Our experimental results confirm the efficiencyof our approach.

Figure 1: An example of a MaxRS query

Motivation. Given a set of weighted spatial (2-dimensional) objects and a user-specified sized rectangle, a MaxRS query finds alocation of the rectangle where the sum of the weights of the objects covered by the rectangle is maximized.

1. INTRODUCTION
Due to the increase of GPS enabled devices such as smartphones
and tablet machines, a lot of location-based services are used inmany real life applications. From this fact, spatio-temporal databases
have been receiving significant attention recently. Supporting spatial queries is therefore becoming more important, and many studies developed techniques for efficient spatial query processing [13,15]. These studies can be classified into spatial objects retrieval
problems [3, 24] and location finding problems [10, 32, 33]. For example, kNN query processing, which retrieves the k nearest neighbor objects w.r.t. a given query point, is the representative of thespatial objects retrieval problems. In the location finding problems,on the other hand, some queries have been proposed, for example, optimal location queries [10, 33], bichromatic reverse nearest
neighbor queries [14, 35], and MaxRS (Maximizing Range Sum)
queries [6, 8, 9, 25]. This paper focuses on a kind of MaxRS problem.

E XAMPLE 1.1. Figure 1 shows an example of a MaxRS query.
In Figure 1, the rectangle with dashed line, the black points, andthe rectangles with solid line show a general monitoring space,spatial objects with weight 1, and user-specified sized rectangles,
respectively. The MaxRS query identifies the location of the shaded
rectangle as one of the optimal results because it covers the largest
number of objects, i.e., the sum of the weights of objects covered by
the rectangle is the maximum.
This query is useful because it can automatically find an important place without specifying any query points [8, 9]. In this paper, we address a novel problem of monitoring MaxRS in spatial
data streams. In other words, we address a problem of continuous MaxRS query processing over sliding-window. Since a large
amount of spatio-temporal objects are continuously generated [2,5], e.g., in the context of location-based service usages, one-time
finding an important location does not make sense but continuously
monitoring an important location is required. A continuous MaxRS
query can achieve this and has the following real life applications.

c 2016, Copyright is with the authors. Published in Proc. 19th Inter⃝

E XAMPLE 1.2. Consider urban sensing. A system, e.g., basestation, continuously collects spatio-temporal objects, e.g., generated by devices with GPS, in an urban city. Such objects can be
represented as < x, y, w > where x, y, and w are latitude, longitude, and weight, respectively. If w is communication traffic, acontinuous MaxRS query can monitor an area where traffic is concentrated. In this case, the system can notify the users holding
mobile devices in the area of warning about communication delay.

national Conference on Extending Database Technology (EDBT), March
15-18, 2016 - Bordeaux, France: ISBN 978-3-89318-070-7, on OpenProceedings.org. Distribution of this paper is permitted under the terms of theCreative Commons license CC-by-nc-nd 4.0

Example 1.2 shows that continuous MaxRS queries can help to analyze communication errors and also support decision making, e.g.,where to place Wi-Fi access points. We next consider location-

Series ISSN: 2367-2005

317

10.5441/002/edbt.2016.30

• We conduct extensive experiments using both synthetic andreal datasets that confirm the efficiency of our approach (Section 7).

based games in which continuous MaxRS queries are useful for
decision making.
E XAMPLE 1.3. In BotFighters, players try not to be attacked byother players [4], and in Ingress, players try to occupy places.
Let w in Example 1.2 represent the strength or level of a given
player, and players keep checking the area monitored by a continuous MaxRS query. This can detect an event, e.g., a competition by
many and/or high-level players, and support to plan a strategy.

In addition to the above contents, we review some related literaturesin Section 3, and Section 8 concludes this paper.

2.

PRELIMINARY

We are given a set of spatial stream objects in a general monitoring space, as shown in Figure 1. A spatial object oi is represented by oi =< x, y, w > where i is its identifier, < x, y >shows the location that oi is generated, and w is a non-negativevalue (weight), i.e., oi .w ∈ R+ . We assume a spatial stream environment, thus consider a sliding-window model [1] because it
is usual that many applications are interested only in recent objects. Count- and time-based sliding-window models are widely
accepted. The count-based sliding-window considers the most recent n objects, and in this model, m new objects generations leadto the expirations of the m oldest objects. The time-based slidingwindow, on the other hand, considers the objects generated within
the last T time-units. Selection of a suitable sliding-window model
depends on applications, and our algorithms can deal with both themodels. So, without loss of generality, we assume the count-based
sliding-window in this paper. Let O be the set of the most recent n
objects, and O residents in-memory because real-time continuous
query processing generally requires main memory computation [4,17].
Let P be an infinite set of points in the general monitoring space.
Given a user-specified sized rectangle r, the weight of a point p ∈P , p.w, is defined by∑p.w =oi .w,

Other examples include mobile sensor networks [27] that a basestation continuously collects sensor readings. By employing continuous MaxRS queries, the base-station may be able to detect sensor failures and over-concentration of mobile sensor nodes.
Technical challenge and overview. Some techniques for exact
MaxRS query processing on static objects have been developed in
the past. [12, 18] proposed in-memory algorithms while [8, 9] proposed an external-memory algorithm. The computation (I/O) complexity of the in-memory (external-memory) algorithm is shown tobe optimal. These algorithms however focus on one-time computation, so they are not efficient for continuous MaxRS queries. Thisis because computing the result from scratch whenever new objects are generated is obviously computationally expensive, meaning that an approach which can incrementally update the result is
required.
In this paper, we first propose a basic algorithm that exploits agraph in grid index, namely G2. G2 integrates graph and grid structures, thus its storage cost is O(|V |+|E|), where V corresponds toa set of objects on a given sliding-window and E is a set of edges.
(The details are described in Section 4). One of the properties of
G2 is that no overhead incurs when objects expire. We then enhance both the basic algorithm and G2, and propose aggregate G2,
aG2, and a branch-and-bound algorithm that exploits aG2. Thisalgorithm eliminates unnecessary update computation as much as
possible and accelerates the query processing efficiency.
Interestingly, the branch-and-bound algorithm can deal with errorguaranteed approximation. Let w∗ and ϵ respectively be the maximum range sum and a user-tolerance error rate. Also, let w be theweight of the area monitored by the algorithm, and we can guarantee that w ≥ (1 − ϵ)w∗ . We show that the relationship between
query processing efficiency and ϵ is trade-off but the practical error rate is much less than ϵ. In addition to the approximation, we
consider a problem of monitoring top-k MaxRS. For example, Examples 1.2 and 1.3 may require not only a single area but k (e.g., 5)
areas with the largest range sum. This requirement is satisfied by asimple modification of the branch-and-bound algorithm.

where oi ∈ O is covered by r centered at p. We are now ready toformally define the monitoring MaxRS problem.
D EFINITION 1 ( MONITORING M AX RS PROBLEM ). Given a set ofobjects on a sliding-window O, an infinite set of points in the general monitoring space, and a user-specified sized rectangle r, thegoal of the monitoring MaxRS problem is to continuously monitor
a location p∗ ∈ P that satisfies.
p∗ = argmax p.w.
p ∈P

It is infeasible to find and monitor p∗ from such infinite points,
but as the literatures [8, 9, 25] introduce, MaxRS problems canbe solved by transformation to an alternative problem. Given auser-specified sized rectangle r, let ri be the weighted rectangleof the same size of r centered at < oi .x, oi .y > (oi ∈ O andri .w = oi .w). Consider oi , oj ∈ O, and if ri overlaps with rj , itis not difficult to see that the weight of the overlapped space s is
s.w = ri .w + rj .w. We formally define this space weight.

Contributions and organization. We summarize our contributions as follows.
• We address a novel problem of continuous MaxRS query
processing in spatial data streams (Section 2). To the best of
our knowledge, we are the first to investigate this problem.
• We design a basic algorithm for a continuous MaxRS query(Section 4). This algorithm incrementally updates the result
by exploiting an efficient index framework.

D EFINITION 2 (S PACE WEIGHT [8]). Given O, we have a set ofrectangles each of which is centered at the location of the corresponding object. The weight of a space s is the sum of the weightsof the rectangles covering s.

• We enhance the basic algorithm and propose a more efficientindex and branch-and-bound algorithm (Section 5). This algorithm prunes unnecessary computation and accelerates thecomputation efficiency.

Then the alternative problem is to find s with the maximum weight
denoted by s∗ . Interestingly but not surprisingly, p∗ exists in s∗ ,that is, any points in s∗ can be p∗ .
E XAMPLE 2.1. Figure 2 shows the alternative problem of Figure
1. The center of each rectangle is at the corresponding object. Notethat the size of each rectangle is the user-specified size. Recall thatthe weight of each object is 1, and the shaded overlapped space has• We show that the branch-and-bound algorithm can deal witherror-guaranteed approximation and efficient continuous topk MaxRS query processing (Section 6).

318

Table 1: Overview of symbols
Symbol
oi
m
s∗
ri
ri .E
N (ri )
si
ci,j
Gi,j
Vi,j
ci,j .w

Figure 2: An example of the alternative problem of Figure 1
the maximum weight. We know that the weights of other overlapped
spaces are less than 4. The center of the shaded rectangle in Figure
1 exists in the shaded space.

to find a location from an infinite set of points. In the same sense,
continuous spatial queries [15, 16, 17] that monitor not locations
but objects are different from our problem.

Therefore, monitoring s∗ is equivalent to monitoring p∗ . We here
define continuous MaxRS queries that solve the monitoring MaxRS
problem.

Spatial preference queries. Spatial preference query processing
problem is one of location selection problems. Given a 2-dimensional
point p and a distance constraint d, a top-k spatial preference query[22, 29] determines the score of p by the sum of the weights of thefeature objects existing within d from p. [28] studies a problem offinding top-t most influential sites. The influential score of a givensite is defined as the sum of weights of its reverse nearest neighborobjects. In the above queries, the scores of the target points aredefined by a kind of range sum function. However, the locationsof the target points are already known, which is different from ourproblem.

D EFINITION 3 ( CONTINUOUS M AX RS QUERY ). Given a set ofobjects on a sliding-window O and a user-specified sized rectangle r, each weighted object is converted to a weighted rectangle
centered at the location of the object. A continuous MaxRS query
monitors s∗ that satisfiess∗ = argmax s.w,
s ∈S

Description
The weighted spatial object with identifier i
The number of objects generated at the same time
The space with the maximum weight
The weighted rectangle centered at the location of oi
The set of edges held by ri
The set of neighboring vertices (rectangles) of ri
The space with the maximum weight covered by ri
The cell with identifier (i, j)
The graph maintained by ci,jThe set of vertices (rectangles) of Gi,j
The upper-bound weight of ci,j(1)where S is the set of overlapped spaces.
We also consider a problem of monitoring top-k MaxRS to support the applications that require not only a single space but also
k spaces with the maximum weight. The definition of monitoring
top-k MaxRS problem is given by extending Definition 1, thus weformally define continuous top-k MaxRS queries below.

Facility location queries. The objective of this problem is to findan optimal location w.r.t. a given condition. It is often the case thata set of customers (or clients) with weights and a set of facilities
are given [11]. Then a facility location query retrieves a facility
that maximizes the total weight of its reverse (k) nearest neighborcustomers [35]. [10] proposed optimal location queries, and theextension version of the optimal location queries, min-dist optimal
location queries, has been studied in [20, 32]. Such optimal location queries have also been studied in road networks [7].
The monitoring MaxRS problem is also one of the facility location problems. We are interested in continuously monitoring alocation that maximizes the total weight of objects covered by auser-specified sized rectangle. As introduced in Section 1, thisis useful in monitoring applications in spatial data streams. The
main deference between MaxRS and the above queries is their categories: monotonic (e.g., MaxRS queries) and bichromatic (e.g.,
optimal location queries).

D EFINITION 4 ( CONTINUOUS TOP - K M AX RS QUERY ). Given a
set of objects on a sliding-window O and a user-specified sizedrectangle r, each weighted object is converted to a weighted rectangle centered at the location of the object. A continuous top-k
MaxRS query monitors the set S ∗ that satisfies |S ∗ | = k and∀s ∈ S ∗ and ∃s′ ∈ S\S ∗ , s.w ≥ s′ .w where S is the set ofoverlapped spaces, and ties are arbitrarily broken.
Since applications that execute continuous queries basically require real-time monitoring [3, 4, 17], algorithms that process suchqueries have to update query results efficiently. Our objective of
this paper is therefore to minimize computation time to update s∗ ,which is incurred by generations and expirations of objects. Table
1 summarizes the symbols frequently used in this paper.

MaxRS queries. To the best of our knowledge, the existing worksof MaxRS problems and the variants are [6, 8, 9, 12, 18, 25]. An
external-memory algorithm for exact MaxRS queries has been proposed in [8, 9], while [25] proposed a randomized sampling algorithm that bounds the error with high probability. That is, given atolerance error ϵ, the approximate algorithm returns a space withthe weight w that satisfies w ≥ (1 − ϵ)w∗ with probability 1 − n1 .
(w∗ is the weight of the optimal result and n is the number of objects.) Rotating MaxRS queries have been proposed in [6]. This
literature assumes that a given rectangle is rotatable, but we do notassume this case and assume the usual case, as well as [8, 9, 12, 18,25].
We now focus on the in-memory algorithms [12, 18] because
we also consider an in-memory algorithm for continuous MaxRS
queries. It is notable that the algorithm in [18] solves a max-

3. RELATED WORKAs introduced in Section 1, many spatial queries have been developed. This section reviews related works of the monitoring
MaxRS problem. In particular, we introduce spatial preference
queries and facility location queries in which MaxRS queries are
categorized. We then review the existing studies of MaxRS query
processing.
Before introducing the above queries, we should make it clearthat MaxRS queries are different from range aggregation queries.
The goal of range aggregation queries is to return the aggregate
result (e.g., values and points) from (i) the set of points in a given
rectangle with fixed location [19, 21, 23] or (ii) the set of values in agiven interval [26]. On the other hand, the goal of MaxRS queries is

319

𝑟2

H
A

B

C
𝑟1

𝑟6

𝑟5
D E

𝑟3

F

G

I

J

K

𝑟6

𝑟2
𝑟5

L

𝑟4

𝑟4

𝑟3

𝑟1

Figure 4: The graph constructed from the rectangles in Figure
3

Figure 3: An example of processing a plane-sweep algorithm

Table 2: Edge and neighbor sets of the vertices of the graph in
Figure 4

enclosing rectangle problem, to which the MaxRS problem can beconverted, based on well-known plane-sweep strategy, and actually
the external-memory and the approximate algorithms [8, 25] also
employ this strategy. (The algorithm proposed in [12] also employs the same strategy and the computation cost is the same as[18].) The plane-sweep algorithm [18] employs a horizontal line,
and given a set of rectangles, this line is swept from bottom to top of
the rectangles while counting the weights of intersecting intervals
on the sweeping line. Figure 3 shows an instance when sweeping
the dashed line. Let the weight of each rectangle in Figure 3 be 1,
and we can see that the weights of intervals AB, BC, and CD are 1,
2, and 3, respectively. In the plane-sweep algorithm, when a sweeping line reaches the bottom edge of a rectangle, a newly generated
interval is inserted into a binary-tree, while when reaching the topof the rectangle, the expired interval is deleted from the binary-tree.
During these procedures, the counts of intervals are also updated.
This algorithm returns the interval with the maximum weight, andthe complexity of this algorithm is O(n log n) [18], where n is thenumber of objects (rectangles). This is because the algorithm executes 2n binary-tree updates (n insertions and n deletions) thattake O(log n) time. (This algorithm also can return a set of k intervals with the maximum weight without sacrificing its computation
efficiency.)
The above algorithm is shown to be an optimal solution for the
MaxRS problem on static objects. However, it is inefficient to compute s∗ from scratch by this algorithm even in the case where thenumber of newly generated objects is not large, which is shown by
our experimental results. From the next section, we describe oursolutions that efficiently update and monitor the result over stream
data.

Vertex ri
r1
r2
r3
r4
r5
r6

Edge ri .E(r1 , r2 ), (r1 , r3 )(r2 , r3 )(r3 , r4 )(r4 , r5 )(r5 , r6 )∅Neighbor set N (ri ){r2 , r3 }
{r3 }
{r4 }
{r5 }
{r6 }
∅

We define our graph and provide a concrete example below.
D EFINITION 5 (G RAPH G). G = (V, E) is a dynamic graph. V
is a set of rectangles of a given size on a sliding-window, and E isa set of direct edges. Given two vertices ri , rj ∈ V overlapping
each other, where ri was generated earlier than rj , there is a directedge between them, (ri , rj ), and this edge is held by the vertex(rectangle) that was generated earlier than the other, i.e., ri . (Tiesare broken by identifiers.)
E XAMPLE 4.1. We construct a graph G from the set of rectangles
in Figure 3, and Figure 4 shows G. Assume that the rectangles are
generated in order of identifiers. Since r2 overlaps with r1 , thereis (r1 , r2 ) that represents a direct edge from r1 to r2 . r1 maintains
the edges (r1 , r2 ) and (r1 , r3 ).
When context is clear, we use vertices and rectangles interchangeably since they are the same, as Definition 5 describes. We denote ri .E the set of edges held by the vertex ri ∈ V . The setof neighbors of a vertex ri ∈ V is also denoted by N (ri ) ={∀rj | ∃(ri , rj ) ∈ ri .E}. Table 2 shows an example that uses Figure 4 in terms of r.E and N (r). Then we obtain the spaces on ricovered by the rectangles in N (ri ). ri maintains si , the space withthe maximum weight among the spaces. That is, si is definitely thesubspace on ri , which provides the following property.

4. BASIC SOLUTION
The generations and the expirations of objects lead to additions
and eliminations of overlapped spaces. This suggests that S in
Equation (1) is dynamic, in other words, the ranking of range sum
is dynamic, thereby efficient s∗ monitoring is not trivial. In spiteof this nature, our index framework enables to design a simple but
efficient algorithm.

P ROPERTY 1. Given ri , rj ∈ V , we have that si ̸= sj .
The proof is straightforward since ∄ri ∈ N (rj ) if ∃rj ∈ N (ri ).
How to obtain si is explained later, but it is not difficult to see thefollowing property.
P ROPERTY 2. Let SG be the set of si maintained by ri on a slidingwindow, we have that

4.1 G2: Graph in Grid Index
We first present our index framework Graph in Grid index (orG2). Recall that our objective is to achieve real-time monitoring of
MaxRS in a stream environment, meaning that unnecessary computations have to be avoided. A dynamic graph, where a vertex isa rectangle and an edge shows the overlap between given two vertices, realizes this. If the weight of each vertex (rectangle) is 1, we
can see that s∗ is a part of the vertex with the largest number ofedges. To monitor s∗ with using the dynamic graph, the basic operation that we have to do is just to check the updated parts of the
dynamic graph. This is because only the updated parts may affects∗ . Motivated by this observation, we develop G2.
As described, the first idea is to maintain n rectangles on a slidingwindow by a graph. Vertices of the graph are the rectangles, and if
two rectangles overlap each other, there is an edge between them.

s∗ = argmax si .w.
si ∈SG(2)

Furthermore, even if some vertices (rectangles) expire, other vertices need no maintenances, because the corresponding edges areheld by older vertices.
P ROPERTY 3. Given ri ∈ V , and when the older vertices than ri
expire, si does not change.
We next have to consider the case where m new rectangles (objects) are generated. Due to the graph structure, we need to check
whether the m rectangles overlap with the existing rectangles. It is
obvious that simple computation takes O(mn) time. To alleviate
this, we employ a grid structure like the one shown in Figure 5,320

Algorithm 1: Monitoring algorithm using G2

𝑐0,3

𝑐1,3

𝑐2,3

𝑐3,3

𝑐0,2

𝑐1,2

𝑐2,2

𝑐3,1

𝑐0,1

𝑐1,1

𝑐2,1

𝑐3,2

Mapping(R) // R is the set of new rectangles
C ′ ← the set of the cells where new objects are mapped′
3 G2-Update(C ) // rectangle overlap computation′
4 for ∀c ∈ C do
5for ∀ri ∈ c.V where r has new edges do
6si ← Local-Plane-Sweep(N (ri ) ∪ {ri })12s∗ ← argmaxsi ∈S si .w
return s∗

7
8

𝑐0,0

𝑐1,0

𝑐2,0

𝑐3,0

Figure 5: An example of G2

Recall that given a set of rectangles, the plane-sweep algorithm
sweeps a horizontal line from the bottom to the top among the rectangles. To obtain si , however, we only need to sweep the horizontal line from the bottom to the top of ri . Local-Plane-Sweep(·)
in Algorithm 1 (line 6) is optimized to do so. Although the timecomplexity does not vary, the practical execution time is reduced.
The following simple example highlights the efficiency of ourincremental approach.

which is the second idea. When dataset updates frequently occur,
grid structure is more suitable than complex structures like R-tree
and Quad-tree [4]. Each cell in the gird is assigned an identifier andits size is fixed, as shown in Figure 5. Note that each cell ci,j maintains the graph constructed by the mapped rectangles, denoted by
Gi,j = (Vi,j , Ei,j ). Therefore, Definition 5 is rewritten as follows.

E XAMPLE 4.2. Assume that the graph in Figure 4 is the graphmaintained by one of the cells in Figure 5. Assume further thatm = 1 and r6 is the new rectangle mapped to the cell. Algorithm 1 checks the vertices overlapping with r6 , and in this case,(r5 , r6 ) is inserted to r5 .E. Algorithm 1 next executes Local-PlaneSweep({r5 , r6 }) and obtains s5 . If s5 .w > s∗ .w, s∗ is replacedby s5 .

D EFINITION 6 (G RAPH Gi,j ). Gi,j = (Vi,j , Ei,j ) is a dynamic
graph maintained by ci,j of a grid. Vi,j is a set of given sizedrectangles that are mapped to ci,j and on a sliding-window, andEi,j is a set of direct edges. The condition of direct edges follows
Definition 5.
For example, Figure 5 illustrates an example of a G2 and G3,0 .
When m new rectangles are generated, we map them to the cellswith which they overlap. (So, a new rectangle may be mapped tomultiple cells.) We then update the graphs in the cells where new
objects are mapped.

Time complexity. As discussed before, lines 1–3 take O(c′ m′ n′ )time. Let v be the number of vertices to which new edges are inserted. Also, let e be the average number of edges of the above
vertices, then lines 4–6 take O(ve log e) time since Local-PlaneSweep(·) for a vertex takes O(e log e) time. Therefore, when m
new objects are generated, Algorithm 1 takes O(c′ m′ n′ +ve log e)time.

Complexities. The time complexity of the rectangle mapping isO(m). Let c′ and m′ respectively be the number of cells where
new objects are mapped and the average number of new objects
mapped to the cells. Also, let n′ be the average number of vertices
in the cells where new objects are mapped, and the time complexityof the graph update is O(c′ m′ n′ ). In practice, we have that n′ ≪n. We next consider storage cost. Let ∑V be the set of all vertices
in
the
grid,
then
we
know
that
|V
|
=
|Vi,j |. Similarly, |E| =∑|Ei,j |, where E is the set of all edges in the grid. Recall thateach vertex ri maintains si and its storage cost is O(|V |). We cantherefore conclude that the storage cost of G2 is O(|V | + |E|).

5.

ENHANCED SOLUTION

Algorithm 1 can identify where to update and compute si maintained by ri efficiently since N (ri ) is easily obtained by the graphrepresentation. In fact, however, the most time consuming operation in Algorithm 1 is Local-Plane-Sweep(·) (line 6). Algorithm
1 executes Local-Plane-Sweep(·) whenever ri .E is updated, thus
it is intuitively seen that the approach degrades the performance inthe case where the number of r.E updates is large. We observe thefollowing usual cases that motivate to enhance G2.

4.2 Monitoring Algorithm with G2
We design an online monitoring algorithm using G2, and Algorithm 1 illustrates the high level algorithm.

1. The ri .E update increases si .w but it is less than s∗ .w.

Algorithm description. Consider an instance when m new rectangles are generated and the m oldest rectangles expire. As describedin Section 4.1, we first update G2 (lines 1–3). Lines 4–6 are designed based on the following idea. Given the set S of the spaces
each of which (i.e., si ) is maintained by ri ∈ V , we know that si
has to be correct due to Equation (2). In addition, if a new edge isinserted to ri .E, si may change because N (ri ) varies. We therefore need to compute si if ri .E is updated. The plane-sweep algorithm is an optimal solution to find the space with the maximum
weight covered by the given rectangles [12]. Hence, we employ theplane-sweep algorithm to compute si (line 6). Note that the inputof this plane-sweep algorithm is only N (ri ) ∪ {ri }. To summarize, for ∀ri ∈ V , where ri .E has new edges and V is the vertex
set maintained by a given cell c of G2, Algorithm 1 executes theplane-sweep algorithm locally, denoted by Local-Plane-Sweep(·)(lines 4–6). After that, we can correctly monitor s∗ .

2. The ri .E update does not increase si .w.
To consider a more concrete situation, we give Example 5.1, andTable 3 shows the weights of each vertex ri and si of the graph in
Figure 4.

Table 3: Weights of vertex ri and si of the graph in Figure 4
Vertex ri
r1
r2
r3
r4
r5
r6

321

ri .w
10
30
15
25
20
5

si .w
55
45
40
45
25
5

𝑐3,0 . 𝑤 = 4

𝑐3,0 . 𝑤 = 7

𝐺3,0

𝑐3,0 . 𝑤 = 4

𝐺3,0

3

4

𝐺3,0

3

4

1

4

1

2

3
2

2

2

3

2

3
1

1
2

2

2

2

2

1

2

2

2

3

𝑅3,0

𝑅3,0

𝑅3,0

(a) An instance when the rectangle overlap computation has been executed.

31(b) An instance when new rectangles are
mapped to c3,0 .

1(c) An instance when the rectangle overlap computation between V3,0 and R3,0in Figure 6(b) has been executed.

Figure 6: An example of G3,0 (followed by Figure 5) and R3,0 of c3,0 in an aG2 and its dynamic update where the weight of eachvertex is 1.
ci,j .w, i.e., the upper-bound weight maintained by ci,j . Basically,ci,j .w is set as follows.

E XAMPLE 5.1. Assume the same situation as Example 4.2 ands∗ = s1 . Before (r5 , r6 ) is inserted to r5 .E, s5 .w = 20, andafter the insertion, we obtain s5 .w = 25. However, it is obviousthat the edge (r5 , r6 ) insertion to r5 .E does not affect s∗ , whichcorresponds to the case 1. In addition, even if r6 overlaps with
r2 and does not overlap with r3 , s2 keeps the same and does not
become s∗ . This corresponds to the case 2.

ci,j .w = max si′ .w,
si′ ∈Si,j(4)

where Si,j is the set of si′ maintained by ri′ ∈ Vi,j . Given a set of
new rectangles r′ that are mapped to ci,j , ci,j .w is updated by thefollowing equation.
∑ ′ci,j .w ← ci,j .w +
r .w
(5)

The observation in Example 5.1 suggests that we may not have tocompute si even when ri .E is updated. Therefore, by enhancing
G2, we aim at eliminating such unnecessary computation and improving query processing efficiency. The enhanced solution achieves
this by an upper-bounding technique.

We give a simple example of how to dynamically update upperbound weights below.
E XAMPLE 5.2. Figure 6 shows an example of G3,0 and R3,0 wherec3,0 follows Figure 5. We first assume the situation of Figure 6(a),and note that the value shown next to each vertex is the upperbound weight. Then we see that c3,0 .w = 4, which is the maximum
value among the upper-bound weights of V3,0 . Next we assume thatthree new rectangles are mapped to c3,0 , which are maintained in
R3,0 , as shown in Figure 6(b). From Equation (5), c3,0 .w is updated to 7. We finally assume Figure 6(c), where the three rectangles in R3,0 have been checked whether they overlap with the vertices (rectangles) in V3,0 or not. Note that the upper-bound weight
maintained by each vertex is updated and c3,0 .w is also updated to
4 as the result of the rectangle overlap computation.

5.1 Aggregate G2
It has been shown in the past that data structures considering
aggregate results work well for query processing which deal withaggregate functions such as sum and count [30]. The monitoring
MaxRS problem considers sum function, then we know that G2
can be extended to deal with aggregate values like aR-tree [19].
We propose aG2 (aggregate G2), which is essentially G2. The
main difference between G2 and aG2 is that aG2 employs upperbound weights. Given a graph in an aG2, each vertex ri of thegraph maintains si .w, which is the upper-bound weight of si . How
to compute si .w depends on algorithms, so we briefly introduce ourapproach to compute si .w here (the detail is described in Section
5.2). Given the graph Gi,j = (Vi,j , Ei,j ) maintained by a cell ci,jin an aG2, we have a vertex ri′ ∈ Vi,j and si′ . Consider rectangles
rj ′ where (ri′ , rj ′ ) is newly inserted to ri′ .E, si′ .w is computedby the following Equation.
∑
rj ′ .w(3)si′ .w = si′ .w +From Equations (3)–(5), we have the following property.
P ROPERTY 4. ci,j .w ≥ si′ .w ≥ si′ .w for ∀ri′ ∈ Vi,j .
Because of generations and expirations of rectangles, those upperbound weights may vary dynamically, but our branch-and-boundalgorithm (introduced later) dynamically updates the upper-boundweights so that Property 4 is kept. At the same time, this property
provides the correctness of our branch-and-bound algorithm.
As well as G2, we discuss about the storage cost of an aG2 below.

Not only the vertices but also the cells in aG2 maintain upper-boundweights. Before we introduce the upper-bound weight maintainedby ci,j , we have to note that in aG2, ci,j maintains

P ROPERTY 5. An aG2 has the same storage cost as a G2, i.e.,O(|V | + |E|) where V and E are respectively the sets of all thevertices and the edges in the (a)G2.

• Gi,j : the graph defined by Definition 6, and• Ri,j : a set of rectangles that have been mapped to ci,j but
have not yet been checked whether they overlap with vertices
in Vi,j or not (denoted by rectangle overlap computation).

P ROOF. To prove Property 5, we have to discuss about the storage
costs of vertices, edges, and upper-bound weights. Let ni,j andn′i,j be the size of Vi,j in G2 and aG2, respectively. Because Vi,j ∩R∅ in aG2, we have that ni,j = n′i,j + |Ri,j |, thereby |V | =∑i,j =′(ni,j + |Ri,j |). The number of edges in aG2 may be less thanthat of G2 but it takes O(E) cost. Let V ′ be the set of Vi,j of

The new rectangles mapped to ci,j are initially maintained in Ri,j .
When we execute the rectangle overlap computation, the rectangles in Ri,j are moved to Vi,j . Now we introduce how to compute

322

∑ ′
aG2, and |V | > |V ′ | =ni,j . The storage cost of upper-boundweights maintained by vertices is O(|V ′ |). Let C be the set of cellsof an aG2, and the storage cost of upper-bound weights maintainedby the cells is O(|C|). We know that |C| ≪ |V ′ | in practice.
Therefore we can complete the proof.
□

Algorithm 2: Branch-and-bound algorithm using aG2
Rnew ← the set of newly generated rectangles
for ∀r ∈ Rnew do
3
if r is mapped to ci,j then4ci,j .w ← ci,j .w + r.w
5Ri,j ← Ri,j ∪ {r}1
2

5.2 Branch-and-Bound Algorithmc ← {ci,j | s∗ is in ci,j }if s∗ expired (c = ∅) then8c ← argmax ci,j .w // C is the set of cells in aG26

As described in Section 5.1, each cell and vertex in an aG2 maintain the upper-bound weights. This enables us to process a continuous MaxRS query while pruning unnecessary computations.
Specifically, we can obtain two pruning rules, which can reduce
the number of executions of Local-Plane-Sweep(·). Assume an
instance when m new rectangles are generated, the upper-boundweight of each cell is obtained by Equation (5). Given s∗ , we firstobtain the following pruning rule.

7

ci,j ∈C

OverlapComputation(c)∗∗10 s ← ExactWeightComputation(s , c)
11 for ∀ci,j ∈ C\{c} do
12
if ci,j .w > s∗ .w then13
OverlapComputation(ci,j )9

14

P RUNING RULE 1. Given a cell ci,j in the aG2, and if ci,j .w <s∗ .w, all the vertices in Vi,j do not have s∗ . Therefore we do notneed to compute the exact si′ of ri′ ∈ Vi,j .

15
16

The above case efficiently prunes the computation of the exact si′ .
However, we are likely to hold the case where ci,j .w ≥ s∗ .w,
since ci,j .w is the maximum value among the set of the upperbounds maintained by vertices in Gi,j or more (See Equation(5)).
In this case, we focus on each vertex in Vi,j , and then apply thenext pruning rule.

Input: ci,j // a cell in aG2ci,j .w ← 0′
2 for ∀r ∈ Ri,j do
3for ∀r ∈ Vi,j do
4
if r′ overlaps with r then5r.E ← r.E ∪ {(r, r′ )}6s.w ← s.w + r′ .w
1

7
8

From the above pruning rules, we can focus only on cells and vertices with non-zero probability to have s∗ . Note that the above
pruning rules assume that s∗ is given, although s∗ might expire. Ifs∗ expires, we first obtain a temporal s∗ , and the temporal s∗ isretrieved from the cell c that satisfies

9
10
11
12
13

ci,j ∈C

return s∗

Algorithm 3: OverlapComputation(ci,j )P RUNING RULE 2. Given a cell ci,j in the aG2, and we assume
that ci,j .w ≥ s∗ .w. Given a vertex ri′ ∈ Vi,j , if si′ .w < s∗ .w, ri′does not have s∗ , thus we do not need to compute the exact si′ .

c = argmax ci,j .w,

if ci,j .w > s∗ .w thens∗ ← ExactWeightComputation(s∗ , ci,j )(6)where C is the set of cells in the aG2. To keep the efficiency of thepruning rules, the weight maintained by the temporal s∗ should belarge as much as possible. It is intuitive that a cell with large upperbound weight probably has the space with large weight, thereby
we employ this heuristic. From the above discussion, we designa branch-and-bound algorithm, which efficiently updates s∗ and is
illustrated in Algorithm 2.

if ci,j .w < s.w thenci,j .w ← s.w
if ci,j .w < r′ .w thenci,j .w ← r′ .w
s′ .w ← r′ .w
Vi,j ← Vi,j ∪ {r′ }Ri,j ← Ri,j \{r′ }and-bound approach is employed (lines 11–15 in Algorithm 2) toguarantee the correct s∗ .
Given a cell ci,j , we first apply Pruning rule 1, and if ci,j .w >s∗ .w, we update (i.e., decrease) ci,j .w by OverlapComputation(ci,j )(lines 12–13). Again we apply Pruning rule 1 to ci,j , and if ci,j .w >s∗ .w again, ExactWeightComputation(s∗ , ci,j ), which we explained
above, is executed. In the case where we compute the exact si′
maintained by ri′ ∈ Vi,j , in ExactWeightComputation(s∗ , ci,j ),and si′ .w > s∗ .w, s∗ is updated (line 10 in Algorithm 4). These
operations are executed for ∀ci,j ∈ C\{c}, and after that, we cankeep monitoring the correct s∗ .

Algorithm description. Consider an instance when m new rectangles are generated and the m oldest rectangles expire. We first map
the newly generated rectangles to the corresponding cells ci,j while
updating the upper-bound weight ci,j .w and Ri,j (lines 1–5). Next,
we update (or find a temporal) s∗ to enhance the pruning efficiency(line 6–10). Let c is the cell holding s∗ (if s∗ expires, we retrievec that satisfies Equation (6)), we execute OverlapComputation(c)(line 9), which is illustrated in Algorithm 3. OverlapComputation(c)updates the graph in c and c.w. More specifically, we check whether
rectangles in R of the cell c overlap with the rectangles (vertices)in V , and if overlap, new edges are inserted while updating theupper-bound weights maintained by the vertices and c (lines 3–8
in Algorithm 3). After that, ExactWeightComputation(s∗ , c) is executed (line 10 in Algorithm 2), which is illustrated in Algorithm
4. In ExactWeightComputation(s∗ , c), we apply Pruning rule 2 toeach vertex ri . If si .w > s∗ .w, we execute Local-Plane-Sweep(·)
for ri , and update s∗ if necessary (lines 6–10 in Algorithm 4). Also,
c.w is kept so that it satisfies Equation (4). From the above procedures, we obtain the updated (or temporal) s∗ , and then a branch-

Time complexity. OverlapComputation(ci,j ) takes O(|Vi,j ||Ri,j |).
Let C ′ be the set of the cells that OverlapComputation(·) is executed, and the amortized time to compute the rectangle overlapping is O(|C ′ ||Vi,j ||Ri,j |). Let v ′ be the number of the vertices
that Local-Plane-Sweep(·) is executed. Also let e′ be the average number of edges of the above vertices, and the total cost of
ExactWeightComputation(·, ·) is O(v ′ e′ log e′ ). When m new objects are generated, Algorithm 2 takes O(|C ′ ||Vi,j ||Ri,j |+v ′ e′ log e′ )(amortized) time. Recall the time complexity of Algorithm 1, andnote that |C ′ ||Vi,j ||Ri,j | ≤ c′ m′ n′ and v ′ e′ log e′ < ve log e.
Correctness. The correctness of Algorithm 2 is proven by Property 4. In Algorithms 2–4, we define the condition that we cannot
prune OverlapComputation(·) and ExactWeightComputation(·, ·)as “>” instead of “≥,” e.g., line 12 of Algorithm 2. This is because323

Algorithm 4: ExactWeightComputation(s∗ , ci,j )Algorithm 5: UpperboundUpdate(ri )Input: s∗ , ci,j // ci,j is a cell in aG2
1 ci,j .w ← 0
2 for ∀ri′ ∈ Vi,j do3
ρ←04
if s∗ ̸= ∅ then5ρ ← s∗ .w
6
7
8
9
10

Input: ri // a vertex of a given cell.
R(ri ) ← the set of vertices that are included in N (ri ) but have notbeen executed Plane-Sweep(·)
2 τ ← si .w
3 for ∀r ∈ R(ri ) do
4
if r overlaps with si then5
τ ← τ + r.w
6
if τ > s∗ .w then7
si .w ← τ
8
break
1

if si′ .w > ρ thensi′ ← Local-Plane-Sweep(N (ri′ ∪ {ri′ }))si′ .w ← si′ .w
if si′ .w > s∗ .w thens∗ ← si′

9
10

11
12
13

if ci,j .w < si′ .w thenci,j .w ← si′ .w

11
12
13

return s∗

14
15
16

we monitor one of the spaces with the maximum weight, thus ifs∗ .w = ci,j .w for example, we keep monitoring s∗ , and this does
not sacrifice the correctness. If applications require all spaces withthe maximum weight like the AllMaxRS problem [9], we just needto define the condition as “≥.”

17
18

5.3 Discussion
To demonstrate the efficiency and practicality of Algorithm 2,
we review the following conceivable approaches that can tight theupper-bound weights maintained by rectangles more than Algorithm 2.
1. An approach that all rectangles ri maintain all the overlapped
spaces on ri .
2. An additional approach of Algorithm 2 that computes the
maximum space weight among the common spaces on ri andrj when (rj , ri ) is inserted to ri .E.
3. An additional approach of Algorithm 2 that tries to decrease
si .w when si .w > s∗ .w.
We show that these approaches do not guarantee the reduction oftime complexity, rather, the worst-case time complexity becomesworse than Algorithm 2.
Approach 1. Given a rectangle ri , we assume that Si is the setof the overlapped spaces on ri . Since ri maintains all the overlapped spaces on ri , we can compute the tightest si .w. However, given m′ new rectangles overlapping with ri , we need at leastO(m′ log |Si |) time in practice1 to compute the tightest si .w. Because |Si | ≥ |ri .E|, we may have that O(m′ log |Si |) is larger than
the time cost of the plane-sweep algorithm, i.e., O(|ri .E| log |ri .E|).
To bound the worst time complexity, we execute Local-Plane-Sweep(·),
if O(m′ log |Si |) > O(|ri .E| log |ri .E|) (if we can estimate thissituation). Then the worst-case time complexity is the same as Algorithm 1, thus is worse than Algorithm 2. Note that this approachis impractical because we cannot bound the number of spaces maintained by rectangles.

if τ < ρ thenτ ← min(τ + r.w, ρ)
if τ > s∗ .w thensi .w ← τ
break

From the above discussion, we see that more storage and nonreasonable computational costs are required to tight the upper-boundweights. The upper-bounding cost of Algorithm 2 is reasonable andthe worst-case time complexity is better than the above approaches.

6.

APPLICATION TO RELATED PROBLEMSIn this section, we address two problems of approximate monitoring MaxRS and monitoring top-k MaxRS. We solve these problems efficiently by employing the branch-and-bound algorithm using aG2 with simple extensions.

Approximate Monitoring MaxRS

To improve query processing efficiency, some applications require not the exact but approximate results [25]. In this case, it isimportant to bound the error rate, thus, given a user-tolerance error
ϵ (0 ≤ ϵ < 1), the objective of this problem is to continuously
monitor a space s with the weight s.w that satisfies

Approach 3. Given a vertex ri in an aG2, and when si .w > s∗ .w,
this approach tries to decrease si .w. This approach is illustrated1

ρ ← r.w + ri .w
for r′ ∈ N (ri )\{r} do
if r overlaps with r′ thenρ ← ρ + r′ .w

by Algorithm 5, which may be executed after line 6 of Algorithm
4. Assume an instance when si is computed, and let R(ri ) be theset of vertices that are included in N (ri ) after the instance. In
other words, si has been computed based on N (ri )\R(ri ). In
a nut shell, this approach computes si .w by checking whether agiven r ∈ R(ri ) overlaps with si (line 4) or the rectangle r′ ∈N (r)\{r} (line 12). Due to the latter case, this approach does notnecessarily add r.w to si .w, which may result in less si .w thanthe original Algorithm 4. This approach however needs an extra
O(|R(ri )||N (ri )|) time for each ri where si .w > s∗ .w. Recall
that Local-Plane-Sweep(N (ri )∪{ri }) takes O(|N (ri )| log |N (ri )|)time, and we may have that O(|R(ri )||N (ri )|) > O(|N (ri )| log |N (ri )|).
It would be better to execute Algorithm 5 only in the case where|R(ri )||N (ri )| < 2|N (ri )| log |N (ri )| (since the plane-sweep algorithm needs 2n log n operations). We can therefore see that thisapproach does not work well if |R(ri )| is large. Also, this approach increases the worst-case time complexity, which means noguarantee to reduce the time complexity of Algorithm 2. Our experimental results also show that this approach does not guarantee
the acceleration of query processing.

6.1

Approach 2. Recall that an optimal way to compute the maximum
space weight is the plane-sweep algorithm, thereby this approach isequivalent to the exact si computation. That is, this approach does
not make sense.

else

s.w ≥ (1 − ϵ)s∗ .w.

In the case where Si is indexed by an R-tree or a Quad-tree.

324

Algorithm 2 can deal with this problem by respectively replacing
Pruning rules 1 and 2 with Pruning rules 3 and 4, which are shown
below.

Algorithm 6: Branch-and-bound algorithm using aG2 for continuous top-k MaxRS queries
Execute lines 1–5 in Algorithm 2
C ′ ← {∀ci,j | ∃s ∈ S ∗ is in ci,j }′∗3 if C = ∅ (all spaces in S expire) then4C ′ ← argmax ci,j .w // C is the set of cells in aG2
1

P RUNING RULE 3. Given a cell ci,j in the aG2 and the space s
monitored by our approximate algorithm, if (1 − ϵ)ci,j .w < s.w,
we do not compute the exact si′ of ri′ ∈ Vi,j .

2ci,j ∈C

OverlapComputation(C ′ )∗∗′6 S ← ExactWeightComputation(S , C )′7 for ∀ci,j ∈ C\C do
8
Execute lines 12–15 in Algorithm 2

P RUNING RULE 4. Given a cell ci,j in the aG2 and the spaces monitored by our approximate algorithm, if (1 − ϵ)ci,j .w ≥s.w, we cannot prune OverlapComputation(ci,j ) by Pruning rule
3. Given a vertex ri′ ∈ Vi,j , if (1 − ϵ)si′ .w < s.w, we do notcompute the exact si′ .

59return S ∗We demonstrate that our approximate algorithm (which is theapproximate version of Algorithm 2) guarantees the error bound.
Table 4: Configuration of parameters

T HEOREM 1. Our approximate algorithm always guarantees thats.w ≥ (1 − ϵ)s∗ .w.

Parameter
Window-size, n [×1000]
Generation rate, mSide length of a rectangle, lError rate, ϵkTo prove Theorem 2, we need to introduce the following lemmas.
L EMMA 1. Assume that we are monitoring s that satisfies s.w ≥(1 − ϵ)s∗ .w before applying Pruning rule 3 to a cell ci,j . It is
guaranteed that Pruning rule 3 does not lose that s.w ≥ (1 −ϵ)s∗ .w.
P ROOF. If ci,j .w < s∗ .w and (1 − ϵ)ci,j .w < s.w, it is trivial
that (1 − ϵ)s∗ .w ≤ s.w due to the assumption. On the other hand,
if ci,j .w ≥ s∗ .w, we have that (1 − ϵ)ci,j .w ≥ (1 − ϵ)s∗ .w.
Therefore if s.w > (1 − ϵ)ci,j .w, s.w > (1 − ϵ)s∗ .w.
□

This section provides our experimental results on the performances of our algorithms. Recall that this is the first work of monitoring MaxRS problem, so there is no existing algorithm that candeal with this problem. Therefore, to show the efficiency of theincremental approach of our algorithms, we use an algorithm with
non-incremental approach as comparison. That is, we evaluatednaive plane-sweep [12, 18], the algorithm using G2 (Section 4),
and the branch-and-bound algorithms using aG2 (Sections 5 and
6). For easy recognition, our algorithms are represented by G2 andaG2. Recall that naive plane-sweep is an optimal in-memory algorithm for computing s∗ from scratch, and the algorithm proposed in[8, 9] also uses naive plane-sweep in the case where all objects fit
in the main memory. All algorithms were implemented in C++, andall experiments were conducted on a PC with 3.4GHz Intel Core i7
processor and 32GB RAM.

L EMMA 2. Assume that we are monitoring s that satisfies s.w ≥(1 − ϵ)s∗ .w before applying Pruning rule 4 to a vertex ri′ . It is
guaranteed that Pruning rule 4 does not lose that s.w ≥ (1 −ϵ)s∗ .w.
P ROOF. Essentially the same as the proof of Lemma 1.

Values100, 250, 500, 750, 1000
50, 100, 200, 500, 1000
100, 500, 1000, 1500, 2000
0, 0.1, 0.2, 0.3, 0.4, 0.5
1, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50□

Now, we are ready to prove Theorem 1.
P ROOF. As long as we are monitoring s that satisfies s.w ≥ (1 −ϵ)s∗ .w, Pruning rules 3 and 4 do not lose the bound, which can beseen from Lemmas 1 and 2. We here assume that we are monitoring s that satisfies s.w < (1 − ϵ)s∗ .w. Let c∗ be the cell holding s∗ , and we have that s∗ .w ≤ s∗ .w ≤ c∗ .w. Therefore, inthis case, we definitely cannot prune OverlapComputation(c∗ ) andExactWeightComputation(s∗ , c∗ ) by Pruning rules 3 and 4, and s
is replaced by s∗ . This means that s cannot be the result, thus weconclude that Theorem 2 is true from the contradiction.
□

7.1

6.2 Monitoring Top-k MaxRS
If the requirement is to monitor not only a single space but multiple spaces with the largest weight, a continuous top-k MaxRS queryis a promising solution. This query achieves the requirement while
controlling the result size as Definition 4 describes.
We know that Pruning rules 1 and 2 are based on a threshold,and the threshold is s∗ .w, i.e., the (temporal) top-1 weight. It is
intuitively known that the threshold is set as the kth largest weightin continuous top-k MaxRS queries.
Algorithm 6 illustrates the high level algorithm. Although thealgorithm for continuous top-k MaxRS queries is essentially thesame as Algorithm 2, the main modification is to deal with the set
S ∗ of the k spaces with the maximum weight. We do not show
OverlapComputation(C ′ ) and ExactWeightComputation(S ∗ , C ′ ) because they are also essentially the same as Algorithms 3 and 4, respectively.

7. EXPERIMENTS

Parameters. Table 4 summarizes the parameters used in the experiments and bold values are default values. Note that a given
rectangle is a square in the experiments, thus the size of a rectangle
is l × l, i.e., 1000 × 1000 by default.
Evaluation. In Section 7.2, we investigate the impact of Algorithm
5. In Section 7.3, to investigate the performances of the algorithms
w.r.t. monitoring MaxRS, we varied three parameters, n, m, and l,2

325

Setting

Datasets. We used a synthetic dataset and three real datasets. In
the synthetic dataset, we generated objects under uniform distribution. The cardinality of this synthetic dataset is 10,000,000, and therange of each coordinate is [0, 1000000]. The three real datasets are
T-Drive [31], Geolife [34], and Roma2 , which are the sets of continuously generated GPS data. The objects in the real datasets exist
over a very wide range, thus we selected the objects existing aroundrespective main areas. The cardinalities of T-Drive, Geolife, andRoma are 5,037,794, 3,662,876, and 8,368,858, respectively. The
objects in the datasets are sorted in order of generation time, andwe normalized the range of each coordinate to [0, 1000000]. In
the above four datasets, the weight of a given object is a real-value
randomly chosen from [0, 1000].

http://crawdad.org/index.html

2

10

1

10

10

0

−1

100 200 300 400 500 600 700 800 9001000

4

10

3

10

2

10

1

10

10

−1

10

2

10

1

10

0

10

G2

0

200

400

600

800

1000

2

10

5

10

4

10

3

10

2

10

1

G2

aG2

0

Window size [K] (T−Drive)

Window size [K] (Geolife)

Window size [K] (Roma)

naive plane−sweep
10

3

10

2

10

1

10

0

0

(c) Geolife
Figure 7: Impact of nG2naive plane−sweep

aG2

200

400

600

800

1000

10

4

10

3

10

2

10

1

0

200

Generation rate (T−Drive)(a) Synthetic

G2

400

600

(b) T-Drive(c) Geolife
Figure 8: Impact of m

T-Drive
6.547
5.952
6.229

Geolife
152.644202.127217.541(d) Roma

naive plane−sweep

aG2

800

Generation rate (Geolife)

1000

10

4

10

3

10

2

10

1

0

200

400

G2

600

aG2

800

1000

Generation rate (Roma)(d) Romathus our algorithms also need longer computation time. However,
we can see that our algorithms are more efficient than naive planesweep in the four datasets, as expected. Naive plane-sweep is not
scalable, which is shown in the case of large n. Moreover, aG2
scales better than G2 (the computation time is shown in log-scale).
aG2 updates the result more than 2 times faster than G2 in the four
datasets.

Table 5: Computation time [msec]
Synthetic
0.799
0.796
0.812

10

naive plane−sweep

aG2

1

Generation rate (Synthetic)

Algorithm
Algo. 2
Algo. 5 with cond.
Algo. 5

10

3

G2

10
100 200 300 400 500 600 700 800 9001000

aG2

−1

4

10
100 200 300 400 500 600 700 800 9001000(b) T-Drive

Computation time [msec]

Computation time [msec]

naive plane−sweep

10

100 200 300 400 500 600 700 800 9001000(a) Synthetic

3

naive plane−sweep

aG20

Window size [K] (Synthetic)

10

G2

Computation time [msec]

1010Computation time [msec]

3

naive plane−sweep

aG2

Computation time [msec]

10

G2

Computation time [msec]

4Computation time [msec]

Computation time [msec]

naive plane−sweep
10

Roma
55.19649.24554.837and measured the average computation time to update s∗ . We alsomeasured the practical error rate and computation time of aG2 byvarying ϵ to investigate the performance of our approximate algorithm in Section 7.4. Let s be the space monitored by our approximate algorithm, and the practical error is defined by 1 − s.w/s∗ .w.
Finally, we measured the average computation time to update S ∗by varying k in Section 7.5.

Impact of m. Next, we study the impact of the generation rate,i.e., the number of objects generated at the same time. Although
the practical average generation rates of the three real datasets areless than 50 objects (per second), we employ larger generation rates
to investigate the scalability of our algorithms. Figure 8 shows theresults. Because naive plane-sweep computes s∗ from scratch, it
is not affected by m basically. The computation time of our algorithms increases as m increases. When m is large, the upper-boundweights maintained by cells and vertices are likely to become large,
which results in the same observation as large n. Note that even acase of large m, e.g., m = 1000, we can observe that aG2 still
updates the result faster than naive plane-sweep.

7.2 Impact of Algorithm 5
We first study the impact of Algorithm 5 in our default setting.
Table 5 shows the result. In Table 5, “Algo. 5 with cond.” isdenoted by Algorithm 2 with Algorithm 5 in the case where theupper-bounding cost is less than the plane-sweep algorithm. We
can see that Algorithm 5 provides a trivial impact for all the four
datasets and does not outperform Algorithm 2. We observed that
|R(ri )| in Algorithm 5 is large in Geolife, thus Algorithm 5 provides a negative impact. Therefore we do not employ Algorithm 5
since it is not scalable .

Impact of l. User-specified rectangle size also has impacts on
the performances of continuous MaxRS query processing, because
large rectangles tend to overlap with others. Figure 9 shows the results. We can see that aG2 keeps outperforming naive plane-sweep,
but the tendencies are different between the datasets. In the uniform
distribution, i.e., Figure 9(a), G2 and aG2 are not much affected byl, but in the real datasets, the computation time of our algorithms(and naive plane-sweep) increase as l increases. We observed thatthe distributions of the real datasets are skewed. Therefore many
rectangles overlap with each other, then G2 and aG2 are likely to
encounter the case that Local-Plane-Sweep(·) is not avoided.

7.3 Results on monitoring MaxRS
Impact of n. We study the impact of the number of objects ona sliding-window, and Figure 7 shows the results. All the algorithms need longer computation time as n increases. In terms ofnaive plane-sweep, this is intuitive since its cost is O(n log n).
It is also intuitive that the increase of the number of overlapped
spaces due to the increase of n is likely to lose the chances which
avoid OverlapComputation(·) and ExactWeightComputation(·, ·),7.4

Results on monitoring Approximate MaxRS

We evaluated our approximate branch-and-bound algorithm us-

326

3

10

2

10

1

10

0

10

naive plane−sweep

aG2

−1

0

500

1000

1500

2000

10

4

10

3

10

2

10

1

10

0

G2

naive plane−sweep

aG20

Side length of rectangle (Synthetic)(a) Synthetic

500

1000

1500

2000

10

4

10

3

10

2

10

1

10

0

G2

naive plane−sweep

aG2

Computation time [msec]

10

G2

Computation time [msec]

4Computation time [msec]

Computation time [msec]

naive plane−sweep
10

0

500

1000

1500

2000

10

4

10

3

10

2

10

1

10

0

0

500

G2

1000

aG2

1500

2000

Side length of rectangle (T−Drive)

Side length of rectangle (Geolife)

Side length of rectangle (Roma)(b) T-Drive(c) Geolife(d) Roma

Figure 9: Impact of l

0.7
0.6
0.5
0.4
0.3
0.2

6

Computation time [msec]

Computation time [msec]

5
4
3
2
1

0.1
0.1

0.2

0.3

0.4

0
0

0.5

120
100
80
60
40

0.1

0.2

0.3

0.4

0
0

0.5

0.1

Epsilon (T−Drive)(a) Comp. time (Synthetic)

0.2

0.3

0.4

40
30
20
10
0
0

0.5

aG2

aG2

0.3

0.3

0.3

Error rate

0.3

Error rate

0.4

0.2

0.1

0.1

0.2

0.3

0.4

Epsilon (Synthetic)(e) Error rate (Synthetic)

0.5

0.2

0.1

0
0

0.1

0.2

0.3

0.4

0
0

0.5

Epsilon (T−Drive)

0.1

0.2

0.3

0.4

0.5

(f) Error rate (T-Drive)(g) Error rate (Geolife)
Figure 10: Impact of ϵ

7.5

0.5

0.2

0.1

Epsilon (Geolife)

ing aG2 by varying ϵ. Although an approximate algorithm for onetime computation of MaxRS queries has been proposed in [25],this algorithm cannot be used for comparison due to three reasons.
First, this algorithm is based on randomized sampling, thus the answers returned by this algorithm and our algorithm are different.
Second, the answer returned by this algorithm varies every time,
which is not suitable as monitoring algorithm. Last, repeating such
one-time computation is shown to be inefficient in Section 7.3. We
therefore focus on our algorithm, and the experimental results areshown in Figure 10.
From Figures 10(a)–10(d), although its impact is different between the datasets, we can see that the computation time decreases
as ϵ increases. This result satisfies the requirement that needs fastercomputation with an approximate answer. In the synthetic dataset,it seems that the computation time does not decrease so much (Figure 10(a)), but even when ϵ = 0, the computation time is about
0.8 [msec], which is fast enough. From Figures 10(e)–10(h), we
can see that as ϵ increases, the practical error also increases but
is less than ϵ. The results show that the relationship between thequery processing efficiency and the quality of the result is tradeoff, but an interesting observation is that the practical error rates in
the cases of the real datasets are very small.

0.4

aG2

0.4

0
0

0.3

0.5

0.4

0.1

0.2

(d) Comp. time (Roma)

0.5

0.4

0.2

0.1

Epsilon (Roma)(c) Comp. time (Geolife)

0.5
aG2

50

Epsilon (Geolife)(b) Comp. time (T-Drive)

0.5

aG2

20

Epsilon (Synthetic)

Error rate

60
aG2

140

Error rate

Computation time [msec]

aG2

0.8

0
0

160

7
aG2

Computation time [msec]

1
0.9

0
0

0.1

0.2

0.3

0.4

0.5

Epsilon (Roma)(h) Error rate (Roma)

Results on monitoring Top-k MaxRS

To evaluate our branch-and-bound algorithm for continuous topk MaxRS queries, we conducted an experiment by varying k. We
compare our algorithm with naive plane-sweep. Although naive
plane-sweep is for one-time computation, this algorithm can deal
with top-k MaxRS queries without sacrificing the computation cost.
We do not evaluate G2 since its performance is not better than aG2.
Figure 11 shows the results. Again, naive plane-sweep is notaffected by k since it scans all rectangles on a sliding-window. As
k increases, the computation time of aG2 increases, but we can seethat the increase of the computation time of aG2 is slight for all
the four datasets. These results confirm that the pruning rules keep
efficient and avoid unnecessary computation.

8.

CONCLUSION

In this paper, we addressed a novel problem of monitoring MaxRS
and its variants, i.e., monitoring approximate MaxRS and top-k
MaxRS. In the environments where spatio-temporal objects are generated frequently, monitoring and analysis of objects are often required, and a continuous MaxRS query is useful to support suchrequirements. Unfortunately, the existing solutions [8, 25] focus
on static objects, thus are not efficient in our problem. Motivated

327

3

10

2

10

1

10

10

0

−1

0

5 10 15 20 25 30 35 40 45 50

k (Synthetic)(a) Synthetic

10

4

10

3

10

2

10

1

10

0

0

naive plane−sweep

aG2
10

10

10

5 10 15 20 25 30 35 40 45 50

k (T−Drive)

4

3

2

0

5 10 15 20 25 30 35 40 45 50

k (Geolife)(b) T-Drive(c) Geolife
Figure 11: Impact of kby this, we proposed the first algorithm that can incrementally update the exact result. This algorithm incorporates our index framework G2 (Graph in Grid index) which supports efficient query processing. We extended G2 and proposed aG2 (aggregate G2) anda branch-and-bound algorithm using aG2. The branch-and-boundalgorithm accelerates the query processing efficiency. Moreover,
we showed that the branch-and-bound algorithm can deal with themonitoring approximate MaxRS and the top-k MaxRS problems
with simple modifications. To demonstrate the efficiency of our algorithms, we conducted experiments using synthetic and real datasets.
The results show that the branch-and-bound algorithm using aG2 issuperior to the one-time computation approach and the algorithm
using G2.
As shown (but not theoretically) in Section 5.3, we need extra
computation and storage costs to tight the upper-bound weights
more. Hence, it is interesting to theoretically explore (or clarify
the impossibility of) an approach that can tight the upper-bound themost without sacrificing the computational cost and storage cost. It
is also interesting to develop an efficient algorithm that can deal
with multiple continuous MaxRS queries at the same time. These
are the works that need to be considered in the future.
Acknowledgment. This research is partially supported by the Grantin-Aid for Scientific Research (A)(26240013) of MEXT, Japan,
and JST, Strategic International Collaborative Research Program,
SICORP.

9. REFERENCES[1] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues
in data stream systems. In PODS, pages 1–16, 2002.
[2] J. Bao, M. F. Mokbe, and C.-Y. Chow. Geofeed: A location aware news feedsystem. In ICDE, pages 54–65, 2012.
[3] M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang. Continuous
monitoring of distance-based range queries. IEEE TKDE, 23(8):1182–1199,
2011.
[4] M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li. Continuous reverse knearest neighbors queries in euclidean space and in spatial networks. The VLDB
Journal, 21(1):69–95, 2012.
[5] L. Chen, G. Cong, X. Cao, and K.-L. Tan. Temporal spatial-keyword top-k
publish/subscribe. In ICDE, pages 255–266, 2015.
[6] Z. Chen, Y. Liu, R. C.-W. Wong, J. Xiong, X. Cheng, and P. Chen. Rotating
maxrs queries. Information Sciences, Elsevier, 305:110–129, 2015.
[7] Z. Chen, Y. Liu, R. C.-W. Wong, J. Xiong, G. Mai, and C. Long. Efficientalgorithms for optimal location queries in road networks. In SIGMOD, pages
123–134, 2014.
[8] D.-W. Choi, C.-W. Chung, and Y. Tao. A scalable algorithm for maximizing
range sum in spatial databases. PVLDB, 5(11):1088–1099, 2012.
[9] D.-W. Choi, C.-W. Chung, and Y. Tao. Maximizing range sum in external
memory. ACM TODS, 39(3):21, 2014.
[10] Y. Du, D. Zhang, and T. Xia. The optimal-location query. In SSTD, pages
163–180. 2005.
[11] J. Huang, Z. Wen, J. Qi, R. Zhang, J. Chen, and Z. He. Top-k most influential
locations selection. In CIKM, pages 2377–2380, 2011.
[12] H. Imai and T. Asano. Finding the connected components and a maximum

328

naive plane−sweep

aG2

Computation time [msec]

10

naive plane−sweep

aG2

Computation time [msec]

4Computation time [msec]

Computation time [msec]

naive plane−sweep
10

10

4

10

3

10

2

10

1

0

aG2

5 10 15 20 25 30 35 40 45 50

k (Roma)(d) Romaclique of an intersection graph of rectangles in the plane. Journal of algorithms,
Elsevier, 4(4):310–323, 1983.
[13] C. Li, Y. Gu, J. Qi, G. Yu, R. Zhang, and W. Yi. Processing moving knn queries
using influential neighbor sets. PVLDB, 8(2):113–124, 2014.
[14] Y. Liu, R. C.-W. Wong, K. Wang, Z. Li, C. Chen, and Z. Chen. A new approachfor maximizing bichromatic reverse nearest neighbor search. Knowledge andInformation Systems, Springer, 36(1):23–58, 2013.
[15] K. Mouratidis, S. Bakiras, and D. Papadias. Continuous monitoring of spatial
queries in wireless broadcast environments. IEEE TMC, 8(10):1297–1311,
2009.
[16] K. Mouratidis and D. Papadias. Continuous nearest neighbor queries oversliding windows. IEEE TKDE, 19(6):789–803, 2007.
[17] K. Mouratidis, D. Papadias, and M. Hadjieleftheriou. Conceptual partitioning:
an efficient method for continuous nearest neighbor monitoring. In SIGMOD,
pages 634–645, 2005.
[18] S. C. Nandy and B. B. Bhattacharya. A unified algorithm for finding maximum
and minimum object enclosing rectangles and cuboids. Computers &Mathematics with Applications, Elsevier, 29(8):45–61, 1995.
[19] D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient olap operations in spatial
data warehouses. In SSTD, pages 443–459. 2001.
[20] J. Qi, R. Zhang, L. Kulik, D. Lin, and Y. Xue. The min-dist location selection
query. In ICDE, pages 366–377, 2012.
[21] S. Rahul and Y. Tao. On top-k range reporting in 2d space. In PODS, pages
265–275, 2015.
[22] J. B. Rocha-Junior, A. Vlachou, C. Doulkeridis, and K. Nørvåg. Efficient
processing of top-k spatial preference queries. PVLDB, 4(2):93–104, 2010.
[23] C. Sheng and Y. Tao. New results on two-dimensional orthogonal range
aggregation in external memory. In PODS, pages 129–139, 2011.
[24] Y. Sun, J. Qi, Y. Zheng, and R. Zhang. K-nearest neighbor temporal aggregate
queries. In EDBT, pages 493–504, 2015.
[25] Y. Tao, X. Hu, D.-W. Choi, and C.-W. Chung. Approximate maxrs in spatial
databases. PVLDB, 6(13):1546–1557, 2013.
[26] Y. Tao, C. Sheng, C.-W. Chung, and J.-R. Lee. Range aggregation with set
selection. IEEE TKDE, 26(5):1240–1252, 2014.
[27] S.-H. Wu, K.-T. Chuang, C.-M. Chen, and M.-S. Chen. Diknn: an
itinerary-based knn query processing algorithm for mobile sensor networks. In
ICDE, pages 456–465, 2007.
[28] T. Xia, D. Zhang, E. Kanoulas, and Y. Du. On computing top-t most influential
spatial sites. In VLDB, pages 946–957, 2005.
[29] M. L. Yiu, X. Dai, N. Mamoulis, and M. Vaitis. Top-k spatial preference
queries. In ICDE, pages 1076–1085, 2007.
[30] M. L. Yiu and N. Mamoulis. Multi-dimensional top-k dominating queries. The
VLDB Journal, 18(3):695–718, 2009.
[31] J. Yuan, Y. Zheng, X. Xie, and G. Sun. Driving with knowledge from thephysical world. In SIGKDD, pages 316–324, 2011.
[32] D. Zhang, Y. Du, T. Xia, and Y. Tao. Progressive computation of the min-dist
optimal-location query. In VLDB, pages 643–654. t, 2006.
[33] J. Zhang, W.-S. Ku, M.-T. Sun, X. Qin, and H. Lu. Multi-criteria optimal
location query with overlapping voronoi diagrams. In EDBT, pages 391–402,
2014.
[34] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations andtravel sequences from gps trajectories. In WWW, pages 791–800, 2009.
[35] Z. Zhou, W. Wu, X. Li, M. L. Lee, and W. Hsu. Maxfirst for maxbrknn. In
ICDE, pages 828–839, 2011.