# Reverse Skyline Computation over Sliding Windows

Authors: Junchang Xin; Zhiqiong Wang; Mei Bai; Guoren Wang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Reverse skyline queries have been used in many real-world applications such as business planning, market analysis, and environmental monitoring. In this paper, we investigated how to efficiently evaluate continuous reverse skyline queries over sliding windows. We first theoretically analyzed the inherent properties of reverse skyline on data streams and proposed a novel pruning technique to reduce the number of data points preserved for processing continuous reverse skyline queries. Then, an efficient approach, called Semidominance Based Reverse Skyline (SDRS), was proposed to process continuous reverse skyline queries. Moreover, an extension was also proposed to handlen-of-N and (
n
1
,
n
2
)-of-N reverse skyline queries. Our extensive experimental studies have demonstrated the efficiency as well as effectiveness of the proposed approach with various experimental settings.


---

## Body

## 1. Introduction

The skyline operator [1] and its variations [2–15] have been widely applied in many applications involving multicriteria decision-making. Specifically, given a set P of points, the s
k
y
l
i
n
e of P comprises all the points which are notdominated by any other point in P. Generally, a small value is assumed to be better in all dimensions. Here, we say a point x
dominates another one y, if x is not worse than y for all dimensions (∀
i
,
x
[
i
]
≤
y
[
i
]), and x is better than y for at least one dimension (∃
j
,
x
[
j
]
<
y
[
j
]). Figure 1 illustrates an example of skyline in a 2-D space, where points a and g on the bottom-left line are the skyline points.Figure 1
Example of skyline and its variations.As a variation of skyline, given a query point,dynamic skyline [4–7] contains all the points which are near to the query point in all dimensions. As illustrated in Figure 1, the query point is b
=
(
b
[
1
]
,
b
[
2
]
), and the dynamic skyline with respect to b is {
h
,
q
,
c
}. The other points are farther to b than h (or q, c) in all dimensions.Compared with dynamic skyline,reverse skyline is proposed from an opposite perspective. If q is one of the dynamic skyline points of x, then x is called areverse skyline point of q [7]. As shown in Figure 1, b is a reverse skyline point of q, since q is contained in the dynamic skyline of b. The reverse skyline query is very useful for many applications. For example, in an online used car trading system, each used car is evaluated in various aspects such as brand, price, and mileage. If a dealer wants to take a new used car to sell, it is desirable for the car to attract as many customers as possible. Intuitively, if a customer is interested in an existing car in the trading system, s/he might be also interested in the dynamic skyline cars of this car. Therefore, we can conduct a reverse skyline query with respect to the new one to retrieve all the cars in the system and find the cars whose dynamic skyline contains the new one. The bigger the number of reverse skyline is, the better it is.In such applications, the dealer may want to continuously monitor the trading system for selecting the customers who will recommend the new used car. As the price of used cars is always fluctuant, the information too long before may not be quite relevant to the current used car recommendation. Therefore, we tend to only focus on the most recent (e.g., within a week) used car information, that is, the reverse skyline query over sliding windows.Although reverse skyline query processing has been well studied in recent years [7, 10–13], there is only one previous work,Divide-and-Conquer Reverse Skyline (DCRS) [16], that has studied the reverse skyline over sliding windows. Once the sliding window moves, a new point is inserted into the window and the oldest point is expired from the window. Reverse skyline query over the sliding window will return the reverse skyline result in the current sliding window once the sliding window moves. The DCRS algorithm needs to preserve all points in the sliding window, which will consume a lot of memory space, and the maintenance of such a large number of points usually consumes a large amount of CPU time. In this paper, we propose an efficient algorithm, calledSemidominance Based Reverse Skyline (SDRS), to continuously answer the reverse skyline on data streams. Our contributions can be summarized as follows:(i)
We propose an efficient algorithm SDRS to process the reverse skyline queries over the sliding window. By using the semidominance relationships and first-in-first-out property of the sliding window, SDRS only maintains a small number of points in the sliding window. Also, by maintaining a reasonable structure of each reserved point, SDRS can quickly calculate the new reverse skyline once the sliding window moves.
(ii)
By building and maintaining a 2DR-tree, SDRS is easily extended to deal with n-of-N and (
n
1
,
n
2
)-of-N reverse skyline queries over the sliding window.
(iii)
Last but not least, extensive experiments show that our proposed SDRS approach can efficiently support continuous reverse skyline queries, includingn-of-N reverse skyline queries and (
n
1
,
n
2
)-of-N reverse skyline queries.


## 2. Related Work

Dynamic skyline was first introduced by Papadias et al. [4, 5]. Given a query point, dynamic skyline can return all the points which are near to the query point in all dimensions. Sharifzadeh and Shahabi [17] proposed the concept of spatial skyline queries, and the derived spatial attributes of each point were defined by Euclidean distances from the point to some query points. Deng et al. [6] presented the multisource skyline query in the application of road networks, in which the dynamic attributes of each mapped point were defined as the relative network distances to multiple query points. Chen and Lian [18, 19] proposed generic metric skyline query, and the dynamic attributes of each point were defined in arbitrary metric space. Dellis and Seeger [7] considered the case that all the dynamic attributes were the absolute coordinate differences to the query point. For the sake of simplicity, in this paper, we adopt the definition of dynamic attributes the same as Dellis and Seeger [7].Based on the concept of dynamic skyline, Dellis and Seeger [7] proposed the reverse skyline and presented an effective pruning method to reduce the search space of the reverse skyline computation. Lian and Chen [10, 11] formalized both monochromatic and bichromatic probabilistic reverse skyline query on uncertain data and proposed effective pruning methods to reduce the search space of query processing. Wu et al. [13] investigated the bichromatic reverse skyline on precise data and proposed several nontrivial heuristics that can optimize the access order of R-tree to reduce the I/O cost considerably. Wang et al. [20] and Min [21] investigated the reverse skyline queries in wireless sensor networks. Lim et al. [22–24] proposed a new reverse skyline query processing method that processed a query over moving objects or a continuous reverse skyline query efficiently. The proposed algorithm makes a verification range to guarantee the result of the reverse skyline query, whenever the new objects appear or moving objects move. A novel algorithm is proposed in [25], which is an efficient method to process the reverse skyline, by using an approach based on two pruning methods, the search-area pruning method and the candidate-objects pruning method, but in which it should refine the candidate list because there can be false positives in the candidate list after pruning phase. The reverse skyline processing techniques above cannot be used directly in rapid updated data stream applications.There are some works that have been proposed to address the skyline query processing on data streams. Lin et al. [26] explored the problem of computing skyline against various different sliding windows. Tao and Papadias [27] studied the skyline computation in stream environments and developed efficient techniques to improve space/time efficiency. Morse et al. [28] introduced the continuous time-interval skyline operator to continuously compute the current skyline on a data stream and presented a LookOut algorithm for evaluating such queries efficiently. Sarkas et al. [29] studied the streaming categorical skylines and proposed some novel techniques for maintaining the skyline of categorical data in a streaming environment. Zhang et al. [30] investigated the problem of minimizing the communication overhead in client-server architectures, where the server continuously maintains the skyline of dynamic objects. Zhang et al. [31, 32] studied the problem of continuous, probabilistic skyline query and proposed some novel, efficient techniques to improve the efficiency. However, the existing works usually focus on skyline query processing on data streams, whereas ours concentrates on a more complex query (i.e., reverse skyline) processing on data streams.Bai et al. [33] proposed a probabilistic reverse skyline algorithm over the sliding window by using some probability pruning methods. Liu et al. [34] proposed an algorithm to process reverse k-skyband. The reverse skyline computation on data streams was first studied by Zhu et al. [16]. They proposed an efficient algorithm DCRS to process continuous reverse skyline query by employing an improved DC-Tree index [35]. Firstly, the dataset in sliding window is divided into 2
d pieces according to query point q, and a modified DC-Tree is constructed for each piece of dataset. Secondly, the modified DC-Tree recursively divides its dataset into 2
d equal pieces until the terminate condition is met. The intermediate nodes maintain the local first and second skylines by merging the corresponding results in their children, while the leaf nodes store the data points directly. Finally, DCRS algorithm runs a window query on each global skyline point to get the current reverse skyline when new arrival point belongs to global first or second skylines. Obviously, it is necessary to preserve all the data in sliding window for DCRS algorithm, which costs not only a lot of memory space but also a lot of CPU time. As a result, in this paper, we focus on reducing the number of the data points to be preserved and improve the space/time efficiency for computing continuous reverse skyline as a consequence. Moreover, an extension is also proposed to handle n-of-N and (n
1, n
2)-of-N reverse skyline queries.


## 3. Problem Statement

We first recall two important concepts calledfull-dominance andsemidominance [20], respectively.Definition 1 (full-dominance [20]).
A pointx full-dominates y with regard to query point q
(
x
⪯
-
q
y
), if it holds that (1) ∀
i
∈
D
(
x
[
i
]
-
q
[
i
]
)
(
y
[
i
]
-
q
[
i
]
)
≥
0
∧
x
[
i
]
-
q
[
i
]
≤
y
[
i
]
-
q
[
i
] and (2) ∃
j
∈
D
(
x
[
j
]
-
q
[
j
]
)
(
y
[
j
]
-
q
[
j
]
)
>
0
∧
x
[
j
]
-
q
[
j
]
<
y
[
j
]
-
q
[
j
].Definition 2 (semidominance [20]).
A pointx semidominates y with regard to query point q
(
x
⪯
˙
q
y
), if it holds that (1) ∀
i
∈
D
(
x
[
i
]
-
q
[
i
]
)
(
y
[
i
]
-
q
[
i
]
)
≥
0
∧
x
[
i
]
-
q
[
i
]
≤
2
y
[
i
]
-
q
[
i
] and (2) ∃
j
∈
D
(
x
[
j
]
-
q
[
j
]
)
(
y
[
j
]
-
q
[
j
]
)
>
0
∧
x
[
j
]
-
q
[
j
]
<
2
y
[
j
]
-
q
[
j
].Figure2 illustrates an example of full-dominance and semidominance on dataset {
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
} in a 2-D space. We can see that point b full-dominates a with regard to q, since a and b are in the same side of q, and meanwhile b has smaller distance to q than a on both dimensions. Though b has smaller distance to q than e on both dimensions, point b does not full-dominate e with regard to q, because they are not in the same side of q. Similarly, the points, that is, b
-
h, are not full-dominated by any others.Figure 2
Full-dominance and semidominance.In order to explain semidominance more clearly, for each pointx
∈
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
}, we use foursquare point x
m to stand for the midpoint between the original point x and query point q. We can see that point f semidominates e with regard to q, since the midpoint f
m between f and q full-dominates e. Similarly, point b semidominates a, point c semidominates d, point d semidominates c, and point h semidominates g, while the solid points b, f, and h are not semidominated by any others.It has been theoretically proved in [20] that we can make use of semidominance to conduct reverse skyline queries, as shown in Theorem 3.Theorem 3 (see [20]).
Given a query pointq and a dataset P, any point p
∈
P is a reverse skyline point of q, if there does not exist any other point p
′
∈
P such that p
′
⪯
˙
q
p.According to Theorem3, all the points that are not semidominated by others constitute the reverse skyline. We use P to present an append-only data stream in a d-dimensional space D (i.e., d
=
|
D
|), and each element (point) x
∈
P has a label κ
(
x
) to indicate its position in P. Let P
N denote the most recent N elements in P. Then, the reverse skyline on data stream can be formally defined as in Definition 4.Definition 4 (reverse skyline on data stream).
Given a query pointq and a data stream P, areverse skyline on data stream according to query point q continuously retrieves all the points in the most recent N points P
N that are not semidominated by any other points in P
N.


## 4. Semidominance Based Reverse Skyline

In this section, we present the details of SDRS approach. Specifically, some important properties and query processing techniques are discussed in Sections4.1 and 4.2, respectively.


### 4.1. Preliminaries

Suppose there are two pointsp and p
′ in data stream P such that p
′ semidominates p. According to Definition 4, point p is not a reverse skyline point if p
′ belongs to P
N. As a result, point p will never be a reverse skyline point if point p
′ is younger than p. Therefore, we can get Lemma 5 as follows.Lemma 5.
A data pointp will never be a reverse skyline point if it is semidominated by a younger point p
′.Proof.
Since we havep
′
⪯
˙
q
p, point p is not a reverse skyline point when p
′
∈
P
N. Moreover, since we also have κ
(
p
′
)
>
κ
(
p
), p will expire earlier than p
′. Therefore, point p will never be a reverse skyline point.Consider the example in Figure2 where points arrive according to their alphabetic ordering. Suppose point h just arrives and the length of sliding window is 8; then current P
N
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
}. Since it is semidominated by a younger point (i.e., point b), point a will never be a reverse skyline point on the basis of Lemma 5. Similarly, points c, e, and g are semidominated by some younger points; all of them cannot be the reverse skyline points. Obviously, it will not result in any false negative after abandoning any of a, c, e, and g but may lead to false positive if all of them are discarded.As illustrated in Figure3, now points e, f are in P
N; f can semidominate e and κ
(
e
)
<
κ
(
f
). When a new point i arrives, point i would be judged as a reverse skyline point if we only preserve point f; f cannot semidominate i. However, the truth is quite opposite; point i is not a reverse skyline point as point e semidominates i. Moreover, point i cannot be a reverse skyline point before point e expires. The reason for this problem is that the preserved points cannot semidominate all the points which are semidominated by the discarded points. The new point would be considered as a reverse skyline point when it is semidominated by the discarded points but not semidominated by the preserved points.Figure 3
An example of false positive.Now, we will present a very important characteristic of semidominance which helps us to solve the above problem.Lemma 6 (see [20]).
Ifx
⪯
-
q
y and y
⪯
˙
q
z, then x
⪯
˙
q
z.Lemma6 shows that if one point x can full-dominate another point y, all the points which are semidominated by y can also be semidominated by x. Therefore, the false positive problem could be avoided if all the points which are not full-dominated by a younger point are preserved. Let S
N denote the set of points which are not full-dominated by a younger point; that is,(1)
S
N
=
p
∣
p
∈
P
N
,
∄
p
′
∈
P
N
,
κ
p
′
>
κ
p
∧
p
′
⪯
-
q
p
.Then, the data points inS
N can be divided into three categories:(i)
Reverse Skyline Point (RP). The data point which is not semidominated by any other point in P
N.
(ii)
Candidate Point (CP). The data point which is semidominated by an older point rather than a younger point in P
N.
(iii)
Assistant Point (AP). The data point which is semidominated by a younger point in P
N but not full-dominated by any younger point in P
N.We useR
N, C
N, and A
N to denote the sets of reverse skyline points, candidate points, and assistant points, respectively. Continue the example in Figure 2, since only point a is full-dominated by the point which is younger than it (i.e., point b), S
N
=
{
b
,
c
,
d
,
e
,
f
,
g
,
h
}. Points b, f, and h are not semidominated by any other point; therefore they are reverse skyline points; namely, R
N
=
{
b
,
f
,
h
}. And point d is a candidate point because it is semidominated by the older point c; namely, C
N
=
{
d
}. The remaining c, e, and g are assistant points as each of them is semidominated by a younger point; namely, A
N
=
{
c
,
e
,
g
}.A candidate pointp tends to be semidominated by several points, and it will still be a candidate point if any of them belongs to P
N. Apparently, the youngest one among them is the one who determines when point p can become a reverse skyline point, calling it thepredecessor of p (denoted as p
r
e
(
p
)). Meanwhile, we set an attribute ρ
(
p
) for p to record the position of p
r
e
(
p
); namely, ρ
(
p
)
=
κ
(
p
r
e
(
p
)
).Next, we will discuss the correctness of only keeping the data points inS
N.Lemma 7.
A data pointp will never be a reverse skyline point if it is full-dominated by a younger point p
′.Proof.
It can be immediately deducted from Lemmas6 and 5.Theorem 8.
A newly arriving pointp must be a reverse skyline point or a candidate point. Moreover, if p is a candidate point, then its predecessor p
r
e
(
p
) must belong to S
N.Proof.
Sincep is a newly arriving point and the points which are younger than p do not exist in P
N, p is either a reverse skyline point or a candidate point.
We use apagoge to prove the second part. Suppose pointp is a candidate point, while its predecessor p
r
e
(
p
) does not belong to S
N. According to the definition of S
N, there must be a point p
′ in P
N which is younger than p
r
e
(
p
) satisfying p
′
⪯
-
q
p
r
e
(
p
). According to Lemma 6, we can infer p
′
⪯
-
q
p
r
e
(
p
)
∧
p
r
e
(
p
)
⪯
˙
q
p
⇒
p
′
⪯
˙
q
p. We have κ
(
p
)
>
κ
(
p
′
)
>
κ
(
p
r
e
(
p
)
) and p
′
⪯
˙
q
p, which contradict the prerequisite that pre(p) is the predecessor of point p. Therefore, the proof is completed.Lemma7 shows that a discarded point will never be a reverse skyline point. Thus, false negative will not happen if we preserve all the points in S
N. Theorem 8 shows that whether the new arriving point is a reverse skyline point or a candidate point can be decided by the points in S
N. And if this point is a candidate point, we can get its predecessor correctly according to S
N and also know when it may become a reverse skyline point. Therefore, only preserving the points in S
N cannot result in any false positive.Based on the analysis above, we can get Theorem9 directly.Theorem 9.
S
N is the minimum information that needs to be preserved to process a continuous reverse skyline query over sliding windows.Proof.
It can be immediately deducted from Theorems9 and 8.


### 4.2. SDRS Algorithm

In this section, we will introduce the data structures and details of our SDRS approach successively.Data Structure. The whole data space is divided into 2
d different regions. Full-dominance relationship and semidominance relationship only exist between two data points when they are in the same region according to Definitions 1 and 2. When a new data point arrives, we just need to figure out its full-dominance relationship and semidominance relationship with the points whose region is just the same one as the new arriving point’s (when the new arriving point has the same values as the query point’s in some dimensions, it belongs to more than one region). Therefore, to shorten the time we need to figure that out, we can divide R
N, C
N, and A
N into 2
d regions depending on query point, respectively, and build up an in-memory R-tree for the points in each region, as showed in Figure 4.Figure 4
Data structure.Dominance Relationships. Since our techniques are based on R-trees, the relationship between point p and R-tree entry e must be involved. We use e.min and e.max to denote the lower-left corner and the upper-right corner of entry e; there are several main relationships being presented as follows.If pointp full-dominates e.min, all the points in e are full-dominated by p. If point p cannot full-dominate e.max, all the points in e are not full-dominated by p. Otherwise, point p full-dominates e.max but does not full-dominate e.min; there may be some points that are full-dominated by p. As showed in Figure 5(a), the dark shadow region is the full-dominated region of e; when point p is in this region, all the data points in e are full-dominated by p; while the light shadow region is candidate full-dominated region of entry e, we need to access each child of e to make sure which ones of these points are full-dominated by p.Figure 5
Dominance relationships.
(a)
(b)
(c)If pointp semidominates e.min, all the points in e are semidominated by p. If point p cannot semidominate e.max, all the points in e are not semidominated by p. Otherwise, point p semidominates e.max but does not semidominate e.min; there may be some points which are semidominated by p. As showed in Figure 5(b), the dark shadow region is the semidominated region of e; when point p is in this region, all the data points in e are semidominated by p; while the light shadow region is candidate semidominated region of entry e, we need to access each child of e to make sure which ones of these points are semidominated by p.Ife.max semidominates p, all the points in e semidominate p. If e.min does not semidominate p, all the points in e cannot semidominate p. Otherwise, e.min semidominates p and e.max does not semidominate p; there may be some points in e that can semidominate p. In Figure 5(c), the dark shadow region is the semidominating region of entry e; when point p is in this region, each point in e semidominates p; while light shadow region is candidate semidominating region of entry e, we need to access each child of e to make sure which ones of these points can semidominate p.For each entrye in R-tree, a label κ
(
e
) should be reserved. κ
(
e
) represents the largest label of its child node. For a leaf node e
′, its label is κ
(
p
) if point p corresponds to the leaf node e
′.Query Processing. Algorithm 1 describes the frame of SDRS. When a new point p arrives, if its label κ
(
p
)
>
N, the oldest point o in S
N is expired if κ
(
o
)
=
κ
(
p
)
-
N (Lines 2–4). Then find the set D
C of points whose predecessor is o, and remove D
C from C
N to R
N (Lines 5–7). Next, find the predecessor l
p of p. Find the set D
f of points which are full-dominated by p in S
N and delete D
f from S
N (Lines 8–10). Find the set D
s of points which are semidominated by p in S
N and remove D
s from R
N and C
N to A
N (Lines 11–14). Finally, deal with p according to κ
(
l
p
) (Lines 15–19).Algorithm 1:Semidominance Based Reverse Skyline.
while  a new data point  p  arrives  do
if  κ
(
p
)
>
N  then
if  the oldest point o  κ
(
o
)
=
κ
(
p
)
-
N  then
S
N
=
S
N
-
{
o
};
findD
c
⊆
C
N whose predecessor is expired;
C
N
=
C
N
-
D
c;
R
N
=
R
N
+
D
c;
find the predecessorl
p of point p;
findD
f
⊆
S
N full-dominated by p;
S
N
=
S
N
-
D
f;
findD
s
⊆
S
N semi-dominated by p;
R
N
=
R
N
-
D
s;
C
N
=
C
N
-
D
s;
A
N
=
A
N
+
D
s;
if  l
p  exists in  S
N  then
ρ
(
p
)
=
κ
(
l
p
);
C
N
=
C
N
+
{
p
};
else
R
N
=
R
N
+
{
p
};
return;Algorithm2 describes how to find the predecessor of new point p. First, find the R-tree set S
R that p belongs to (Line 2). Then deal with all the entries of R-trees in S
R (Lines 3-4). If entry e is an intermediate entry, according to the dominance relationship from e to p, different methods are applied (Lines 7–13). If entry e is a leaf entry, the predecessor of p is found (Lines 14–17).Algorithm 2:Find predecessor of new point.
initializeκ
=
0;
find theR-tree set S
R that point p belongs to;
for  each  R
in  S
R  do
insert all entries in the root ofR into a heap H by descending order of κ
(
e
);
while  H  is not empty  do
remove the top entrye from H;
if  e  is an intermediate entry  then
if  e.max
⁡
⪯
˙
q
p  then
κ
=
κ
(
e
);
break;
for  each child
e
i  of  e  do
if  e.min
⁡
⪯
˙
q
p  then
inserte
i into H by descending order of κ
(
e
);
else if  e
⪯
˙
q
p  then
κ
=
κ
(
e
);
break;
return  κ;Algorithm3 describes how to find the set D
s that contains all the points which are semidominated by the new point p but not full-dominated by p. First, find the R-tree set S
R that p belongs to (Line 2). Then deal with all the entries of R-trees in S
R (Lines 3-4). If entry e is an intermediate entry, according to the dominance relationship from p to e, different methods are applied (Lines 7–13). If e is leaf node, according to different dominance relationship from p to e, use different approach (Lines 14–17).Algorithm 3:Remove D
f and compute D
s.
initialize setsD
s
=
∅;
find theR-tree set S
R that point p belongs to;
for  each  R  in  S
R  do
insert all entries in the root ofR into a heap H;
while  H  is not empty  do
remove the top entrye from H;
if  e  is an intermediate entry  then
if  p
⪯
-
q
e
.
m
i
n  then
remove all points ine from S
N;
else
for  each child  e
i  of  e  do
if  p
⪯
˙
q
e
.
m
a
x  then
inserte
i into H;
else if  p
⪯
-
q
e  then
removee from S
N;
else if  p
⪯
˙
q
e  then
removee from D
s;
balanceR in a bottom-up fashion;
return  D
s;Algorithms1, 2, and 3 can continuously maintain the reverse skyline queries efficiently. SDRS can prune some redundant data and minimize the number of points which are reserved in the sliding window, so it can reduce the time and space cost greatly.


## 4.1. Preliminaries

Suppose there are two pointsp and p
′ in data stream P such that p
′ semidominates p. According to Definition 4, point p is not a reverse skyline point if p
′ belongs to P
N. As a result, point p will never be a reverse skyline point if point p
′ is younger than p. Therefore, we can get Lemma 5 as follows.Lemma 5.
A data pointp will never be a reverse skyline point if it is semidominated by a younger point p
′.Proof.
Since we havep
′
⪯
˙
q
p, point p is not a reverse skyline point when p
′
∈
P
N. Moreover, since we also have κ
(
p
′
)
>
κ
(
p
), p will expire earlier than p
′. Therefore, point p will never be a reverse skyline point.Consider the example in Figure2 where points arrive according to their alphabetic ordering. Suppose point h just arrives and the length of sliding window is 8; then current P
N
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
}. Since it is semidominated by a younger point (i.e., point b), point a will never be a reverse skyline point on the basis of Lemma 5. Similarly, points c, e, and g are semidominated by some younger points; all of them cannot be the reverse skyline points. Obviously, it will not result in any false negative after abandoning any of a, c, e, and g but may lead to false positive if all of them are discarded.As illustrated in Figure3, now points e, f are in P
N; f can semidominate e and κ
(
e
)
<
κ
(
f
). When a new point i arrives, point i would be judged as a reverse skyline point if we only preserve point f; f cannot semidominate i. However, the truth is quite opposite; point i is not a reverse skyline point as point e semidominates i. Moreover, point i cannot be a reverse skyline point before point e expires. The reason for this problem is that the preserved points cannot semidominate all the points which are semidominated by the discarded points. The new point would be considered as a reverse skyline point when it is semidominated by the discarded points but not semidominated by the preserved points.Figure 3
An example of false positive.Now, we will present a very important characteristic of semidominance which helps us to solve the above problem.Lemma 6 (see [20]).
Ifx
⪯
-
q
y and y
⪯
˙
q
z, then x
⪯
˙
q
z.Lemma6 shows that if one point x can full-dominate another point y, all the points which are semidominated by y can also be semidominated by x. Therefore, the false positive problem could be avoided if all the points which are not full-dominated by a younger point are preserved. Let S
N denote the set of points which are not full-dominated by a younger point; that is,(1)
S
N
=
p
∣
p
∈
P
N
,
∄
p
′
∈
P
N
,
κ
p
′
>
κ
p
∧
p
′
⪯
-
q
p
.Then, the data points inS
N can be divided into three categories:(i)
Reverse Skyline Point (RP). The data point which is not semidominated by any other point in P
N.
(ii)
Candidate Point (CP). The data point which is semidominated by an older point rather than a younger point in P
N.
(iii)
Assistant Point (AP). The data point which is semidominated by a younger point in P
N but not full-dominated by any younger point in P
N.We useR
N, C
N, and A
N to denote the sets of reverse skyline points, candidate points, and assistant points, respectively. Continue the example in Figure 2, since only point a is full-dominated by the point which is younger than it (i.e., point b), S
N
=
{
b
,
c
,
d
,
e
,
f
,
g
,
h
}. Points b, f, and h are not semidominated by any other point; therefore they are reverse skyline points; namely, R
N
=
{
b
,
f
,
h
}. And point d is a candidate point because it is semidominated by the older point c; namely, C
N
=
{
d
}. The remaining c, e, and g are assistant points as each of them is semidominated by a younger point; namely, A
N
=
{
c
,
e
,
g
}.A candidate pointp tends to be semidominated by several points, and it will still be a candidate point if any of them belongs to P
N. Apparently, the youngest one among them is the one who determines when point p can become a reverse skyline point, calling it thepredecessor of p (denoted as p
r
e
(
p
)). Meanwhile, we set an attribute ρ
(
p
) for p to record the position of p
r
e
(
p
); namely, ρ
(
p
)
=
κ
(
p
r
e
(
p
)
).Next, we will discuss the correctness of only keeping the data points inS
N.Lemma 7.
A data pointp will never be a reverse skyline point if it is full-dominated by a younger point p
′.Proof.
It can be immediately deducted from Lemmas6 and 5.Theorem 8.
A newly arriving pointp must be a reverse skyline point or a candidate point. Moreover, if p is a candidate point, then its predecessor p
r
e
(
p
) must belong to S
N.Proof.
Sincep is a newly arriving point and the points which are younger than p do not exist in P
N, p is either a reverse skyline point or a candidate point.
We use apagoge to prove the second part. Suppose pointp is a candidate point, while its predecessor p
r
e
(
p
) does not belong to S
N. According to the definition of S
N, there must be a point p
′ in P
N which is younger than p
r
e
(
p
) satisfying p
′
⪯
-
q
p
r
e
(
p
). According to Lemma 6, we can infer p
′
⪯
-
q
p
r
e
(
p
)
∧
p
r
e
(
p
)
⪯
˙
q
p
⇒
p
′
⪯
˙
q
p. We have κ
(
p
)
>
κ
(
p
′
)
>
κ
(
p
r
e
(
p
)
) and p
′
⪯
˙
q
p, which contradict the prerequisite that pre(p) is the predecessor of point p. Therefore, the proof is completed.Lemma7 shows that a discarded point will never be a reverse skyline point. Thus, false negative will not happen if we preserve all the points in S
N. Theorem 8 shows that whether the new arriving point is a reverse skyline point or a candidate point can be decided by the points in S
N. And if this point is a candidate point, we can get its predecessor correctly according to S
N and also know when it may become a reverse skyline point. Therefore, only preserving the points in S
N cannot result in any false positive.Based on the analysis above, we can get Theorem9 directly.Theorem 9.
S
N is the minimum information that needs to be preserved to process a continuous reverse skyline query over sliding windows.Proof.
It can be immediately deducted from Theorems9 and 8.


## 4.2. SDRS Algorithm

In this section, we will introduce the data structures and details of our SDRS approach successively.Data Structure. The whole data space is divided into 2
d different regions. Full-dominance relationship and semidominance relationship only exist between two data points when they are in the same region according to Definitions 1 and 2. When a new data point arrives, we just need to figure out its full-dominance relationship and semidominance relationship with the points whose region is just the same one as the new arriving point’s (when the new arriving point has the same values as the query point’s in some dimensions, it belongs to more than one region). Therefore, to shorten the time we need to figure that out, we can divide R
N, C
N, and A
N into 2
d regions depending on query point, respectively, and build up an in-memory R-tree for the points in each region, as showed in Figure 4.Figure 4
Data structure.Dominance Relationships. Since our techniques are based on R-trees, the relationship between point p and R-tree entry e must be involved. We use e.min and e.max to denote the lower-left corner and the upper-right corner of entry e; there are several main relationships being presented as follows.If pointp full-dominates e.min, all the points in e are full-dominated by p. If point p cannot full-dominate e.max, all the points in e are not full-dominated by p. Otherwise, point p full-dominates e.max but does not full-dominate e.min; there may be some points that are full-dominated by p. As showed in Figure 5(a), the dark shadow region is the full-dominated region of e; when point p is in this region, all the data points in e are full-dominated by p; while the light shadow region is candidate full-dominated region of entry e, we need to access each child of e to make sure which ones of these points are full-dominated by p.Figure 5
Dominance relationships.
(a)
(b)
(c)If pointp semidominates e.min, all the points in e are semidominated by p. If point p cannot semidominate e.max, all the points in e are not semidominated by p. Otherwise, point p semidominates e.max but does not semidominate e.min; there may be some points which are semidominated by p. As showed in Figure 5(b), the dark shadow region is the semidominated region of e; when point p is in this region, all the data points in e are semidominated by p; while the light shadow region is candidate semidominated region of entry e, we need to access each child of e to make sure which ones of these points are semidominated by p.Ife.max semidominates p, all the points in e semidominate p. If e.min does not semidominate p, all the points in e cannot semidominate p. Otherwise, e.min semidominates p and e.max does not semidominate p; there may be some points in e that can semidominate p. In Figure 5(c), the dark shadow region is the semidominating region of entry e; when point p is in this region, each point in e semidominates p; while light shadow region is candidate semidominating region of entry e, we need to access each child of e to make sure which ones of these points can semidominate p.For each entrye in R-tree, a label κ
(
e
) should be reserved. κ
(
e
) represents the largest label of its child node. For a leaf node e
′, its label is κ
(
p
) if point p corresponds to the leaf node e
′.Query Processing. Algorithm 1 describes the frame of SDRS. When a new point p arrives, if its label κ
(
p
)
>
N, the oldest point o in S
N is expired if κ
(
o
)
=
κ
(
p
)
-
N (Lines 2–4). Then find the set D
C of points whose predecessor is o, and remove D
C from C
N to R
N (Lines 5–7). Next, find the predecessor l
p of p. Find the set D
f of points which are full-dominated by p in S
N and delete D
f from S
N (Lines 8–10). Find the set D
s of points which are semidominated by p in S
N and remove D
s from R
N and C
N to A
N (Lines 11–14). Finally, deal with p according to κ
(
l
p
) (Lines 15–19).Algorithm 1:Semidominance Based Reverse Skyline.
while  a new data point  p  arrives  do
if  κ
(
p
)
>
N  then
if  the oldest point o  κ
(
o
)
=
κ
(
p
)
-
N  then
S
N
=
S
N
-
{
o
};
findD
c
⊆
C
N whose predecessor is expired;
C
N
=
C
N
-
D
c;
R
N
=
R
N
+
D
c;
find the predecessorl
p of point p;
findD
f
⊆
S
N full-dominated by p;
S
N
=
S
N
-
D
f;
findD
s
⊆
S
N semi-dominated by p;
R
N
=
R
N
-
D
s;
C
N
=
C
N
-
D
s;
A
N
=
A
N
+
D
s;
if  l
p  exists in  S
N  then
ρ
(
p
)
=
κ
(
l
p
);
C
N
=
C
N
+
{
p
};
else
R
N
=
R
N
+
{
p
};
return;Algorithm2 describes how to find the predecessor of new point p. First, find the R-tree set S
R that p belongs to (Line 2). Then deal with all the entries of R-trees in S
R (Lines 3-4). If entry e is an intermediate entry, according to the dominance relationship from e to p, different methods are applied (Lines 7–13). If entry e is a leaf entry, the predecessor of p is found (Lines 14–17).Algorithm 2:Find predecessor of new point.
initializeκ
=
0;
find theR-tree set S
R that point p belongs to;
for  each  R
in  S
R  do
insert all entries in the root ofR into a heap H by descending order of κ
(
e
);
while  H  is not empty  do
remove the top entrye from H;
if  e  is an intermediate entry  then
if  e.max
⁡
⪯
˙
q
p  then
κ
=
κ
(
e
);
break;
for  each child
e
i  of  e  do
if  e.min
⁡
⪯
˙
q
p  then
inserte
i into H by descending order of κ
(
e
);
else if  e
⪯
˙
q
p  then
κ
=
κ
(
e
);
break;
return  κ;Algorithm3 describes how to find the set D
s that contains all the points which are semidominated by the new point p but not full-dominated by p. First, find the R-tree set S
R that p belongs to (Line 2). Then deal with all the entries of R-trees in S
R (Lines 3-4). If entry e is an intermediate entry, according to the dominance relationship from p to e, different methods are applied (Lines 7–13). If e is leaf node, according to different dominance relationship from p to e, use different approach (Lines 14–17).Algorithm 3:Remove D
f and compute D
s.
initialize setsD
s
=
∅;
find theR-tree set S
R that point p belongs to;
for  each  R  in  S
R  do
insert all entries in the root ofR into a heap H;
while  H  is not empty  do
remove the top entrye from H;
if  e  is an intermediate entry  then
if  p
⪯
-
q
e
.
m
i
n  then
remove all points ine from S
N;
else
for  each child  e
i  of  e  do
if  p
⪯
˙
q
e
.
m
a
x  then
inserte
i into H;
else if  p
⪯
-
q
e  then
removee from S
N;
else if  p
⪯
˙
q
e  then
removee from D
s;
balanceR in a bottom-up fashion;
return  D
s;Algorithms1, 2, and 3 can continuously maintain the reverse skyline queries efficiently. SDRS can prune some redundant data and minimize the number of points which are reserved in the sliding window, so it can reduce the time and space cost greatly.


## 5. Extensions

In this section, we extend the proposed SDRS algorithm to supportn-of-N and (
n
1
,
n
2
)-of-N reverse skyline queries.


### 5.1.n-of-N Reverse Skyline

Firstly, we introduce the definition ofn-of-N reverse skyline. P
n denotes the most recent n points in P
N.Definition 10 (n-of-N reverse skyline).
Given the recentN points P
N in the sliding window, n
-of-
N
reverse skyline computes the reverse skyline in the most recent n points which are not semidominated by the points in P
N.According to Definition10, we propose a new definition l
p to solve this problem. For a data point p
∈
P
N, we use l
p to denote the newest point which can semidominate p and arrive before p. In such a case, every point in P
N has a predecessor point l
p, and we use κ
(
l
p
) to denote l
p’s label. If p has no l
p, κ
(
l
p
) equals 0.For every point inP
N, we compute its l
p. Construct a 2D R-tree index on κ
(
l
p
)
,
κ
(
p
). If the current label is t, we execute a range query 0
,
t
-
n, [
t
-
n
+
1
,
t
] on the 2D R-tree. For a point p
∈
P
N, if κ
(
l
p
) is in the range [
0
,
t
-
n
] and κ
(
p
) is in the range [
t
-
n
+
1
,
t
], p is the n-of-N reverse skyline. Through retrieving the whole 2D R-tree index, we can find all the n-of-N reverse skyline points.


### 5.2.(
n
1
,
n
2
)-of-N Reverse Skyline

In this section, we introduce the definition of(
n
1
,
n
2
)-of-N reverse skyline firstly. p
n
1 denoted the most recent n
1 points in P
N and p
n
2 denoted the most recent n
2 points in P
N.Definition 11 ((
n
1
,
n
2
)-of-N reverse skyline).
Given the recentN points P
N in the sliding window and n
1
>
n
2, (
n
1
,
n
2
)
-of-
N
reverse skyline computes the reverse skyline points in the set P
n
1
-
P
n
2.According to Definition11, we propose a new definition r
p to solve the problem. For a point p
∈
P
N, we can use r
p to denote the oldest point which can semidominate p and arrive after p. Specifically, (1) r
p
⪯
˙
q
p, (2) κ
(
r
p
)
>
κ
(
p
), and (3) ∄
x
∈
P
N, κ
(
p
)
<
κ
(
x
)
<
κ
(
r
p
) such that x
⪯
˙
q
p. κ
(
r
p
) denotes the label of r
p. If a point p has no r
p, κ
(
r
p
) equals ∞.For every point inP
N, we compute its l
p and r
p. Construct a 2D R-tree index on κ
(
l
p
)
,
κ
(
p
). If the current label is t, we execute a range query 0
,
t
-
n
1, [
t
-
n
1
+
1
,
t
-
n
2
] on the 2D R-tree. For a point p
∈
P
N, if κ
(
l
p
) is in the range [
0
,
t
-
n
] and κ
(
p
) is in the range [
t
-
n
+
1
,
t
], we need further judgment. If κ
(
r
p
) is in the range [
t
-
n
2
+
1
,
∞
], p is the (
n
1
,
n
2
)-of-N reverse skyline. Through retrieving the whole 2D R-tree index and executing a further judgment, we can find all the (
n
1
,
n
2
)-of-N reverse skyline points.


## 5.1.n-of-N Reverse Skyline

Firstly, we introduce the definition ofn-of-N reverse skyline. P
n denotes the most recent n points in P
N.Definition 10 (n-of-N reverse skyline).
Given the recentN points P
N in the sliding window, n
-of-
N
reverse skyline computes the reverse skyline in the most recent n points which are not semidominated by the points in P
N.According to Definition10, we propose a new definition l
p to solve this problem. For a data point p
∈
P
N, we use l
p to denote the newest point which can semidominate p and arrive before p. In such a case, every point in P
N has a predecessor point l
p, and we use κ
(
l
p
) to denote l
p’s label. If p has no l
p, κ
(
l
p
) equals 0.For every point inP
N, we compute its l
p. Construct a 2D R-tree index on κ
(
l
p
)
,
κ
(
p
). If the current label is t, we execute a range query 0
,
t
-
n, [
t
-
n
+
1
,
t
] on the 2D R-tree. For a point p
∈
P
N, if κ
(
l
p
) is in the range [
0
,
t
-
n
] and κ
(
p
) is in the range [
t
-
n
+
1
,
t
], p is the n-of-N reverse skyline. Through retrieving the whole 2D R-tree index, we can find all the n-of-N reverse skyline points.


## 5.2.(
n
1
,
n
2
)-of-N Reverse Skyline

In this section, we introduce the definition of(
n
1
,
n
2
)-of-N reverse skyline firstly. p
n
1 denoted the most recent n
1 points in P
N and p
n
2 denoted the most recent n
2 points in P
N.Definition 11 ((
n
1
,
n
2
)-of-N reverse skyline).
Given the recentN points P
N in the sliding window and n
1
>
n
2, (
n
1
,
n
2
)
-of-
N
reverse skyline computes the reverse skyline points in the set P
n
1
-
P
n
2.According to Definition11, we propose a new definition r
p to solve the problem. For a point p
∈
P
N, we can use r
p to denote the oldest point which can semidominate p and arrive after p. Specifically, (1) r
p
⪯
˙
q
p, (2) κ
(
r
p
)
>
κ
(
p
), and (3) ∄
x
∈
P
N, κ
(
p
)
<
κ
(
x
)
<
κ
(
r
p
) such that x
⪯
˙
q
p. κ
(
r
p
) denotes the label of r
p. If a point p has no r
p, κ
(
r
p
) equals ∞.For every point inP
N, we compute its l
p and r
p. Construct a 2D R-tree index on κ
(
l
p
)
,
κ
(
p
). If the current label is t, we execute a range query 0
,
t
-
n
1, [
t
-
n
1
+
1
,
t
-
n
2
] on the 2D R-tree. For a point p
∈
P
N, if κ
(
l
p
) is in the range [
0
,
t
-
n
] and κ
(
p
) is in the range [
t
-
n
+
1
,
t
], we need further judgment. If κ
(
r
p
) is in the range [
t
-
n
2
+
1
,
∞
], p is the (
n
1
,
n
2
)-of-N reverse skyline. Through retrieving the whole 2D R-tree index and executing a further judgment, we can find all the (
n
1
,
n
2
)-of-N reverse skyline points.


## 6. Experimental Evaluation

In this section, we experimentally compare our proposed SDRS algorithm against the only existing DCRS algorithm [16] using real dataset-stock data from the Yahoo Financial website and some synthetic datasets. The stock data contains 10 M stock records. Each record contains 4 attributes: price, volume, growth, and capital size. We evaluate the performance of SDRS and DCRS in 2D stock dataset (containing attributes price and volume) and 4D stock dataset when the sliding window sizes are 10 K, 100 K, 1 M, and 10 M. The experimental results are shown in Figure 6.Figure 6
Experimental results of real dataset-stock.
(a)
Space usage versus window size
(b)
Result size versus window size
(c)
Response time versus window sizeFigure6(a) shows the space usage in terms of the number of points kept in the sliding window against N. DCRS needs to preserve all the points in the sliding window. Our SDRS only preserves a small number of the points in the sliding window. When the dimensionality is increased, the number of the preserved points is also increased. Figure 6(b) records the number of the result against N. Figure 6(c) records the response time of the two algorithms for 2D and 4D stock datasets. The response time of SDRS is greatly shorter than that of DCRS because of the filtering policies. From Figure 6, we can see that our SDRS performs much better than DCRS in the real dataset-stock dataset.The synthetic datasets contain three different distributions, including Uniformly Distributed, Clustered, and Anticorrelated Distributed Datasets [1, 7]. Uniformly Distributed Dataset consists of points randomly generated from a unit square. Anticorrelated Distributed Dataset consists of points which are around the antidiagonal. While the Clustered Dataset comprises ten randomly centered clusters, each of them consists of an equal number of points and follows a multivariate Gaussian distribution whose covariance is a 0.05-diagonal matrix and mean vector is equal to its associated centroid. All experiments are performed on a machine with Intel Core 2  1.86 GHz CPU, 1 GB memory, and 80 GB hard disk. Table 1 summarizes the parameters involved in our experiments.Table 1
Experimental parameters.
Parameter
Range& default
Dimensionality
2, 3,4, 5, 6
Window size
10 K, 100 K, 1 M, 10 M, 100 M


### 6.1. Reverse Skyline on Data Stream

We first evaluate the impact of sliding window sizeN. The following is shown in Figures 7, 8, and 9. Figure 7 shows the space usage in terms of the maximal number of points kept in S
N against N. For three data distributions, DCRS must reserve all the points in the sliding window, while SDRS reserves only a small part of the points in the sliding window, since the filtering policies in SDRS can prune many redundant points. Figure 8 records the maximal number of the result against N in three data distributions. Figure 9 records the response time of the two algorithms against sliding window size N. The response time of SDRS is greatly shorter than DCRS in all the data distributions because of the filtering policies. From Figures 8 and 9, we can see that the number of the results is increased, and the response time of SDRS becomes longer with the increase of sliding window size N. Because, with the increase of N, more points in the window should be calculated, then result number will be more and the response time will be longer.Figure 7
Space usage versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 8
Result size versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 9
Response time versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetNext, we evaluate the impact of dimensionalityd. The following is shown in Figures 10, 11, and 12. Figure 10 shows the space usage in terms of the maximal number of points kept in S
N against d. The points reserved in SDRS are only a small part of the whole points in the sliding window because the filtering policies can prune many redundant points, while DCRS must keep all the points in the sliding window. Figure 11 records the maximal number of the result against d in three data distributions. Figure 12 records the response time of the two algorithms against d; the response time of SDRS is greatly smaller than DCRS because of the filtering policies in SDRS. From Figures 11 and 12, the number of the results is increased, and the response time of SDRS becomes longer with the increase of dimensionality d. Because, with the increase of d, more calculations are needed to compute the dominance relationships between two points and the dominance relationship becomes harder, then result number will be more and the response time will be longer.Figure 10
Space usage versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 11
Result size versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 12
Response time versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


### 6.2.n-of-N Reverse Skyline

In this section, maintenance time and processing time are used to evaluate the algorithm performance ofn-of-N reverse skyline query. Maintenance time is the time of constructing the 2D R-tree index, while the processing time is the query time of n-of-N reverse skyline query. In order to evaluate the algorithm performance stably, we generate 1000 random values as n and carry out 1000 continuously n-of-N reverse skyline queries. Finally we record the average value of 1000-query time as the processing time.As shown in Figures13 and 14, Figure 13 records the maintenance time in 2D and 5D against sliding window size N in three data distributions and Figure 14 records the processing time in 2D and 5D against N in both data distributions. With the increase of N, maintenance time and processing time have a little increase. Because, with the increase of window size N, the number of points in R-tree is increased, maintenance time and processing time have a little increase. The maintenance time and processing time in 5D are much longer than those in 2D, because the calculation in 5D is more complex than that in 2D, and the reserved points in 5D are much more than those in 2D.Figure 13
Maintenance time forn-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 14
Processing time forn-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


### 6.3.(
n
1
,
n
2
)-of-N Reverse Skyline

In this section, maintenance time and processing time are used to evaluate the algorithm performance of(
n
1
,
n
2
)-of-N reverse skyline query. Maintenance time is the time of constructing the 2D R-tree index, while the processing time is the query time of (
n
1
,
n
2
)-of-N reverse skyline query. In order to evaluate the algorithm performance stably, we generate 1000 random values as n
1, n
2 equal n
1
+
500 and then carry out 1000 continuously (
n
1
,
n
2
)-of-N reverse skyline queries. Finally, we record the average value of the 1000-query time as the processing time.As shown in Figures15 and 16, Figure 15 records the maintenance time in 2D and 5D against N in three data distributions and Figure 16 records the processing time in 2D and 5D against N in both data distributions. Maintenance time and processing time have a little increase with the increase of N, because the number of reversed points in R-tree has a little increase. The calculation in 5D is more complex than that in 2D, so maintenance time and processing time in 5D are much longer than those in 2D.Figure 15
Maintenance time for(
n
1
,
n
2
)-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 16
Processing time for(
n
1
,
n
2
)-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


## 6.1. Reverse Skyline on Data Stream

We first evaluate the impact of sliding window sizeN. The following is shown in Figures 7, 8, and 9. Figure 7 shows the space usage in terms of the maximal number of points kept in S
N against N. For three data distributions, DCRS must reserve all the points in the sliding window, while SDRS reserves only a small part of the points in the sliding window, since the filtering policies in SDRS can prune many redundant points. Figure 8 records the maximal number of the result against N in three data distributions. Figure 9 records the response time of the two algorithms against sliding window size N. The response time of SDRS is greatly shorter than DCRS in all the data distributions because of the filtering policies. From Figures 8 and 9, we can see that the number of the results is increased, and the response time of SDRS becomes longer with the increase of sliding window size N. Because, with the increase of N, more points in the window should be calculated, then result number will be more and the response time will be longer.Figure 7
Space usage versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 8
Result size versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 9
Response time versus window size.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetNext, we evaluate the impact of dimensionalityd. The following is shown in Figures 10, 11, and 12. Figure 10 shows the space usage in terms of the maximal number of points kept in S
N against d. The points reserved in SDRS are only a small part of the whole points in the sliding window because the filtering policies can prune many redundant points, while DCRS must keep all the points in the sliding window. Figure 11 records the maximal number of the result against d in three data distributions. Figure 12 records the response time of the two algorithms against d; the response time of SDRS is greatly smaller than DCRS because of the filtering policies in SDRS. From Figures 11 and 12, the number of the results is increased, and the response time of SDRS becomes longer with the increase of dimensionality d. Because, with the increase of d, more calculations are needed to compute the dominance relationships between two points and the dominance relationship becomes harder, then result number will be more and the response time will be longer.Figure 10
Space usage versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 11
Result size versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 12
Response time versus dimensionality.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


## 6.2.n-of-N Reverse Skyline

In this section, maintenance time and processing time are used to evaluate the algorithm performance ofn-of-N reverse skyline query. Maintenance time is the time of constructing the 2D R-tree index, while the processing time is the query time of n-of-N reverse skyline query. In order to evaluate the algorithm performance stably, we generate 1000 random values as n and carry out 1000 continuously n-of-N reverse skyline queries. Finally we record the average value of 1000-query time as the processing time.As shown in Figures13 and 14, Figure 13 records the maintenance time in 2D and 5D against sliding window size N in three data distributions and Figure 14 records the processing time in 2D and 5D against N in both data distributions. With the increase of N, maintenance time and processing time have a little increase. Because, with the increase of window size N, the number of points in R-tree is increased, maintenance time and processing time have a little increase. The maintenance time and processing time in 5D are much longer than those in 2D, because the calculation in 5D is more complex than that in 2D, and the reserved points in 5D are much more than those in 2D.Figure 13
Maintenance time forn-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 14
Processing time forn-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


## 6.3.(
n
1
,
n
2
)-of-N Reverse Skyline

In this section, maintenance time and processing time are used to evaluate the algorithm performance of(
n
1
,
n
2
)-of-N reverse skyline query. Maintenance time is the time of constructing the 2D R-tree index, while the processing time is the query time of (
n
1
,
n
2
)-of-N reverse skyline query. In order to evaluate the algorithm performance stably, we generate 1000 random values as n
1, n
2 equal n
1
+
500 and then carry out 1000 continuously (
n
1
,
n
2
)-of-N reverse skyline queries. Finally, we record the average value of the 1000-query time as the processing time.As shown in Figures15 and 16, Figure 15 records the maintenance time in 2D and 5D against N in three data distributions and Figure 16 records the processing time in 2D and 5D against N in both data distributions. Maintenance time and processing time have a little increase with the increase of N, because the number of reversed points in R-tree has a little increase. The calculation in 5D is more complex than that in 2D, so maintenance time and processing time in 5D are much longer than those in 2D.Figure 15
Maintenance time for(
n
1
,
n
2
)-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated DatasetFigure 16
Processing time for(
n
1
,
n
2
)-of-N query.
(a)
Uniform Dataset
(b)
Clustered Dataset
(c)
Anticorrelated Dataset


## 7. Conclusions

Despite its importance in real-world applications, reverse skyline computation on data streams has not been well studied. Therefore, in this paper, we focus on the problem of efficiently computing reverse skyline against sliding windows over an append-only data stream. Specifically, we present an effective pruning approach to minimize the number of points to be kept in the sliding window and propose efficient semidominance based on approach SDRS for processing continuous reverse skyline queries. Moreover, we also propose an extension for handlingn-of-N and (
n
1
,
n
2
)-of-N reverse skyline queries. Our extensive experiments have demonstrated the efficiency and effectiveness of our proposed SDRS approach under various experimental settings.



---

*Source: 649271-2015-12-16.xml*