Continuous Skyline Queries for Moving Objects
Marwan Othman El-Rais Omar Khairy El -Morsy

ABSTRACT
The literature on the skyline algorithms so far mainly deal with queries for static query points over static datasets. With the increasing number of mobile service applications and users, the need for continuous skyline query processing has become more pressing. The continuous skyline operator involves not only static but also dynamic dimensions. In this paper, we examine the spatio-temporal coherence of the problem and propose a continuous skyline query processing strategy for moving query points. First, we distinguish the data points that are permanently in the skyline and use them to derive a search bound. Second, we investigate into the connection between data points’ spatial positions and their dominance relationship, which provides an indication on where to find changes of skyline and how to update the skyline continuously. Based on the analysis, we propose a kinetic-based data structure and an efficient skyline query processing algorithm. We analyze the space and time costs of the proposed method and conduct an extensive experiment to evaluate the proposal. To the best of our knowledge, this is the first work on continuous skyline query processing.

shown in Figure 1, there are a set of hotels and for each hotel, we have its distance from the beach (x axis) and its price (y axis). The interesting hotels are all the points not worse than any other point in both distance from the beach and the price. Hotels 2, 4 and 6 are interesting and can be derived by the skyline query, for their distances to the beach and prices are preferable to any other hotels. Note that a point of the minimum value in any dimension is a skyline point – hotels 2 and 6 for example. hotel price sk yline
1 2 3 4 5 6

distance to beach

Figure 1: An example of skyline in static scenario

1. INTRODUCTION
With rapid advances in miniaturization of electronics, wireless communication and positioning technologies, the acquisition and transmission of spatio-temporal data using mobile devices is becoming pervasive. This fuels the demand for location-based services (LBS)[12, 3, 16, 15]. Skyline query retrieves from a given dataset a subset of interesting points that are not dominated by any other point [4]. Skyline query is an important operator of LBS. For example, mobile users could be interested in restaurants that are near, reasonable in pricing, and provide good food, service, and view. The skyline query result is based on the current location of the user, which changes continuously when the user moves. Existing work on skyline queries assumes static setting, where the distances from the query point to the data points do not change. Using the common example in the literature In the above query, the skyline is obtained with respect to a static query point, and in this case, it is the origin of the both axis. Now, let us change the example to the scenario of a tourist walking about to choose a restaurant for dinner. For ease of illustration, we again only consider two factors, namely the distance to the restaurant and the average price of the food. Different from the previous example, the distance from the tourist to a restaurant is not fixed since the tourist is a moving object. Figure 2 shows the changes on the skyline due to the movement. In the figure, positions of the restaurants are drawn in the X-Y plane, while the table shows their prices. A tourist as the query point moves as the arrow indicates from time t1 to t2 . The skyline, i.e. interesting restaurants, changes with respect to the tourist’s position. Skylines at different times are indicated by different line chains. Such problem is common in moving databases [3, 9, 7], and the lack of research in this area motivated our work presented in this paper. In this paper, we address the problem of continuous skyline query processing, where the skyline query point is a moving object and the skyline changes continuously due to the query point’s movement. We solve the problem by exploiting its spatio-temporal coherence. First, we distinguish the data points that are permanently in the skyline and use them to derive a search bound to constrain the contin-

.

y
1 2 t2 4 6 3 5 qu e ry po i n t a t t 1 s k y l i n e a t t2 s k y l i n e a t t1

Restaurant

Price

1 2 3 4 5 6 x

6 5.8 4 2.8 1 2

Figure 2: An example of skyline in mobile environment uous skyline query processing. Second, we investigate the connection between data points’ spatial locations and their dominance relationship, which provides indication of where to find changes of skyline and update it. Third, to efficiently support processing continuous skyline queries, we propose a kinetic-based data structure and propose associated efficient query processing algorithm. The paper presents the space and time cost analysis of the proposed method. It also reports on an extensive experimental study, which includes a comparison with an existing method adopted for the application. The results show that the proposed method is efficient with respect to storage space and continuous skyline queries. To the best of our knowledge, this is the first work on continuous skyline queries in mobile environment. The rest of this paper is organized as follows. In Section 1, we present the preliminaries including our problem statement and a brief review of related work. In Section 3, we carry out a detailed analysis on the problem. In Section 4, we propose our solution which continuously maintains the skyline for moving query points through efficient update. Experimental results are presented in Section 5. Finally, we conclude in Section 6.

vyi . When it is stationary, vxi and vyi are zero. We use T uple(i) to represent the i-th data tuple in the database. Users are moving in 2D plane. Each of them moves in velocity (vqx , vqy ), starting from position (xq , yq ). They pose continuous skyline queries during the movement, which involve both distance and all other static dimensions. Such queries are dynamic due to change in spatial variables. In our solution, we only want to compute the skyline for (xq , yq ) at the start time 0. Subsequently, continuously query processing is conducted for each user by updating instead of computing a new skyline from scratch each time. Without loss of generality, we restrict our discussion in what follows to the MIN skyline annotation [4], in which smaller values of distance or attribute pij are preferred in comparison to determine dominance between two points.

2.2 Related Work
2.2.1 Algorithms for Static Skyline Query
Borzonyi, Kossmann and Stocker [4] for the first time introduced the skyline operator into database systems by extending the SQL SELECT statement with an optional SKYLINE OF clause. Two processing algorithms Block Nested Loop (BNL) and Divide-and-Conquer (D&C) were proposed. Basically, BNL sequentially scans the whole data file and compares each new point to all skyline candidates kept in memory. Only those points not dominated by others are kept as skyline candidates. The D&C approach divides the whole dataset into several partitions such that each can fit in memory. A local skyline is computed for each partition, and the final skyline is obtained by correctly merging these local skylines. In [14], Tan, Eng and Ooi proposed two progressive processing algorithms: Bitmap and Index. In the Bitmap approach, every dimension value of a point pt is represented by a few bits, and pt itself is transformed into a bit vector by concatenating those bits of all dimensions. In a top-down fashion, vectors of all points form a bit matrix. Whether a given point is in the skyline can be answered without referring to other points, by retrieving some specific bit columns from the matrix and applying bit-wise and operation on them. On the other hand, the Index approach uses a novel transformation to map each point into a single dimensional space such that they can be indexed by a B+ -tree. The skyline computation is conducted in several batches, whose number equals that of all distinct values on all dimension in the whole dataset. Within each batch, relevant points are fetched from each partition with the aid of the B+ -tree, and over all those points a local skyline is computed. After each batch the local skyline is merged into the final skyline with unqualified points correctly excluded. Kossmann, Ramsak and Rost [8] proposed a Nearest Neighbor (NN) method to process skyline queries progressively. It first carries out a NN search on the dataset indexed by an R∗ -tree, and then inserts the NN point into the skyline. The NN point also determines a region which only contains points dominated by NN and thus can be pruned. The remaining part of the space is partitioned into two parts based on the NN point, and both are inserted into a to-do list. Then the algorithm removes a part from the to-do list and process it recursively, until the list is empty. Recently, Papadias, Zhang and Tao [11] proposed a new progressive algorithm named Branch−and−Bound Skyline

2. 2.1

PRELIMINARIES Problem Statement

In LBS, most of the queries are continuous queries [15]. Unlike snapshot queries that are evaluated only once, continuous queries require continuous evaluation as the query results become invalid with the change of location and time. Continuous skyline query processing has to re-compute the skyline when the query location and objects move. Due to the spatio-temporal coherence of the movement, the skyline will change in a smooth manner. Notwithstanding, updating the skyline of the previous moment will be more efficient than conducting a snapshot query at each moment. We limit the data and query points moving in a 2D (2dimensional) space for an intuitive illustration. The statement is however sufficiently general for high-dimensional space too. We have a set of n data points in the format (i = 1, ..., n), where xi and yi are positional coordinate values in the space, vxi and vyi are respectively velocity in X and Y dimension, while pij ’s (j = 1, ..., m) are the static non-spatio attributes. They will not change with time. For a moving object, xi and yi are updated using vxi and

(BBS) based on the best-first nearest neighbor (BF-NN) algorithm [6]. It first enqueues all the entries of the R∗ -tree root into a heap sorted on their mindist’s to the query point. Then the entry e on the heap top will be dequeued and will be discarded if it is dominated by some skyline point. Otherwise it is either expanded, and enqueue its sub-entries if it is an intermediate entry, or it is inserted into the skyline if it is a point. However, unlike BF-NN, BBS uses L1 norm to compute mindist, and only enqueues those entries that are not dominated by any skyline point. In a slightly different context, Balke, Guntzer and Zheng [1] addressed the skyline operation over web databases where different dimensions are stored in different data sites. Their algorithm first retrieves values in every dimension from remote data sites using sorted access in round-robin on all dimensions, until all dimension values of an object, called the terminating object, have been retrieved. Then all non-skyline objects will be filtered out from all those objects with at least one dimension value retrieved.

period of query life time.

2.3 Time Parameterized Distance Function
Since the distance between moving query point and data point is involved in the skyline operator in our problem, we therefore present some background about the changing distance in the moving context. For a moving data point pti starting from (xi , yi ) with velocity (vix , viy ), and a query point starting from (xq , yq ) and moving with (vqx , vqy ), the distance between them can be expressed as a function of √ time t: dist(q(t), pti (t)) = a · t2 + b · t + c, where a, b and c are constants determined by their starting positions and velocities: a = (vix − vqx )2 + (viy − vqy )2 ; b = 2 · [(xi − xq ) · (vix − vqx ) + (yi − yq ) · (viy − vqy )]; c = (xi − xq )2 + (yi − yq )2 . For the sake of simplicity, we use function fi (t) = a·t2 +b·t+c to denote the square of the distance. When data point pti is static, a, b and c are still determined by formulas above with vix = viy = 0.

2.4

Terminologies

2.2.2

KDS and Continuous Queries for Moving Objects

Basch, Guibas and Hershberger [2] proposed a conceptual framework for kinetic data structures (KDS) as a means to maintain continuously evolving attributes of mobile data. The KDS keeps the desired relationship between data by storing all those data in some structures specific to the relationship. The contents in KDS do not change unless the relationship between some data points has been changed. In this way, the data retrieval result based on the desired relationship can be maintained when the data points move continuously. KDS and its underlying ideas have inspired some database query processing techniques that utilize events to maintain the query result. Mokhtar, Su and Ibarra [9] proposed an event-driven approach to maintain the result of k-NN query on moving objects while time elapses. Their approach starts with a list of all moving objects that are are sorted by their current distance to the query point. Then events indicating when a moving object will change position in the list with its neighbor are computed based on the movement parameters of moving objects. All those events are pushed into a priority queue, which gives priority to events that will happen earlier. The problem of maintaining k-NN query result is transformed into the problem of maintaining the list of moving objects. As time progresses, events are processed and the order of moving objects are maintained, thus making k-NN query result always available in the object list. Instead of keeping all moving objects in ascending order of distance to query point, Iwerks, Samet and Smith [7] present another event-driven method to maintain continuous k-NN queries on moving objects. Based on the fact that window queries are cheaper to maintain on moving objects than kNN queries, the authors proposed the Continuous Windowing (CW) k-NN algorithm. The CW k-NN algorithm first gets all those objects within a specific distance d around the query point. And if at least k objects are found, all the final k nearest neighbors must be among these objects and only they need to be checked. Otherwise, the search will be extended outwards with the distance d adjusted. Here events indicating when and which objects will move into the distance d around the query point are computed first, and processed gradually to maintain the query result during the

In this subsection, we define the terminologies used in this paper. We use dist(pt1 , pt2 ) to represent the Euclidean distance between two points pt1 and pt2 . For two points pt1 and pt2 , if dist(pt1 , q) ≤ dist(pt2 , q) and pt1 .pk ≤ pt2 .pk , ∀k, and at least one < holds, i.e., ∃k, such that pt1 .pk < pt2 .pk . we say pt1 dominates pt2 . We say pt1 and pt2 are incomparable if pt1 does not dominate pt2 and pt1 is not dominated by pt2 . We use pt1 pt2 to represent that pt1 dominates pt2 , and pt1 ∼ pt2 that they are incomparable. In kinetic data structures, a certificate is a conjunction of algebraic conditions, which guarantees the correctness of some relationship to be maintained between mobile data objects [2]. In this paper, we use a certificate to ensure the status of a data point valid within a period of time t. For example, a certificate of a point can guarantee it staying in the skyline for a period of time t. Beyond t, its certificate is invalid. An event will trigger a process to update the certificate. The process may result in a change of the skyline.

3. ANALYSIS OF THE CHANGE ON SKYLINE
In this section, we start the analysis of the change of skyline in continuous query processing. We first point out the search bound that can be used to filter out unqualified data points in determining skyline for a moving query point. Then we carry out an analysis of the skyline change due to the movement, which reveals some insights that can be used to update the skyline for the query. The update algorithms will be presented in the next section.

3.1 Skyline on Static Non-spatio Dimensions
Although in our problem the skyline operator involves both dynamic and static dimensions, some data points could be always in the skyline no matter how data points and query points move. This is because they have domineering static non-spatial values, which guarantee that no other objects can dominate them. We denote this type of skyline points as SKns and the whole set of skyline points as SKall . We call SKns static partial skyline, and SKall complete skyline. It is obvious that SKns is always on the complete skyline as time elapses because its underlying advantage on static non-spatio values does not change as data points and query point move.

We call points in SKns permanent skyline points. In this way, we distinguish those points always in the complete skyline from the rest of whole dataset. The benefit of this discrimination is threefold: 1. It extracts the unchanging part of a continuous skyline query result from the complete skyline SKall , and thus in query processing efforts can be concentrated on the changing part only, i.e., SKall − SKns . We name the changing part SKchg , and call those points in it volatile skyline points. In continuous skyline query processing, only SKchg is needed to be kept tracked for each query. In this manner, we can reduce the overall processing cost. 2. This discrimination reduces the size of data to be sent to clients. Every time when change happens, only SKchg as query result is needed to be transferred, which is beneficial to real mobile applications where clients and servers are usually connected via limited bandwidth. 3. Static partial skyline SKns also provides indication of search bound for processing a continuous skyline query, as we will discuss next. We use pt1 pt2 to represent that pt1 dominates pt2 for all m static nonspatio dimensions.

d istance 2 p t5 p t4 p t3

p t2 p t1 0 tx < p t1 , p t2 , tx > time

Figure 3: An example of distance functions become part of SKchg after that moment. For the former, after time tx , si must be dominated by a skyline point sj in SKall . For the latter, when nsp enters the skyline after time tx those points that used to dominate nsp before tx must stop dominating it. That moment tx is indicated by an intersection of two distance function curves. We use to represent an intersection shown in Figure 3, where at time tx point pt2 is getting closer to query than point pt1 but before that moment the inequality relationship is on the contrary. ¿From the figure, we can see that such an intersection only alters pt1 and pt2 ’s presence in or absence from SKchg if it does cause change. Because before and after the intersection, the only change of comparison is dist(q, pt1 ) < dist(q, pt2 ) to dist(q, pt2 ) < dist(q, pt1 ). Apparently if no intersections happen, skyline does not change at all, because the inequality relationship between all points’ distances to query point remains unchanged. Nevertheless, not every intersection will necessarily cause the skyline to change. We need to investigate the conditions in which an intersection causes pt1 and pt2 to enter or leave the skyline, since the intersection does not affect any other points not involved in it. Whether an intersection causes skyline to change is relevant to which set pt1 and pt2 belong to just before time tx , i.e., SKns , SKchg or SKall (neither of the former two, i.e., not in SKall ). We have following Lemmas to clearly describe the possibilities. Lemma 3.3.1. An intersection has no influence on the skyline if one of the following conditions holds before tx : (1) pt1 ∈ SKns and pt2 ∈ SKns (2) pt1 ∈ SKns and pt2 ∈ SKchg (3) pt1 ∈ SKall and pt2 ∈ SKns (4) pt1 ∈ SKall and pt2 ∈ SKchg (5) pt1 ∈ SKall and pt2 ∈ SKall Proof. 1. Both pt1 and pt2 will still be in the skyline after tx because they are permanent skyline points. 2. Obviously pt1 does not leave the skyline. Assume that pt2 leaves the skyline after tx , there must be another skyline point s dominating it, i.e., dist(q, s) < dist(q, pt2 ) for t > tx and ∀k, s.pk ≤ pt2 .pk . Since intersection does not change the distance inequality relationship between s and pt2 , dist(q, s) <

3.2 Search Bound
Since SKns is always contained in SKall , for any point not in SKns to enter SKall it must be incomparable to anyone in SKns . More specifically, it must have advantage in distance to query point since it is dominated with respect to all static dimensions by at least one point in SKns . This leads to the following Lemma 3.2.1. Lemma 3.2.1. At any time t, if spf is the farthest point in SKns to the query point, then any point pt not nearer to the query point than spf is not in the complete skyline. Proof. Obviously pt ∈ SKns , thus ∃sp ∈ SKns s.t. / ∀k, sp.pk ≤ pt.pk and at least one inequality holds. ¿From dist(q, sp) ≤ dist(q, spf ) and dist(q, spf ) ≤ dist(q, pt), we get dist(q, sp) ≤ dist(q, pt) by transitivity. Because of disadvantage in both spatial and non-spatio dimensions, pt is dominated by sp at time t so that it is not in the complete skyline. Lemma 3.2.1 indicates a search bound for skyline on all dimensions. This can be used to filter out part of unqualified points in query processing: those ones that are farther away than all points in SKns cannot be in the skyline.

3.3 Change of the Skyline
When the query point q and data points move, their distance relationships may change. It causes the skyline to change as well. As discussed in Section 3.1, such changes only happen to SKchg , i.e. SKall − SKns . It is also mentioned in Section 2.3 that the square of distance from each point to query point can be described as a function of time t. Figure 3 illustrates an example of such functions of several points with respect to the moving query point. Intuitively, a skyline point si in SKchg before time tx may leave the skyline after that moment. On the other hand, a non-skyline point nsp at time tx may enter the skyline and

dist(q, pt2 ) also holds for t < tx . Thus s dominates pt2 before tx , which contradicts pt2 ∈ SKchg before tx . Therefore pt2 does not leave the skyline either, and there is no influence on the skyline. 3. Since pt1 ∈ SKall before tx , there must be at least / one skyline point s ∈ SKall dominating it. Because dist(q, s) < dist(q, pt1 ) does not change after the intersection, s still dominates pt1 and thus pt1 will not enter the skyline. Since pt2 is a permanent skyline point, it will not leave the skyline. 4. Due to the same reasoning as in (3), pt1 will not enter the skyline after tx . Due to the same reasoning in (2), pt2 itself will not leave the skyline after tx . 5. Due to the same reasoning as in (3), neither pt1 nor pt2 will not enter the skyline after tx .

Table 1: Intersections and possible skyline changes pt1 SKns SKchg SKall pt2 SKns — √ — SKchg — √ — SKall √ √ —

Lemma 3.3.2. An intersection may have influence on the skyline if one of the following conditions holds before tx : (1) pt1 ∈ SKns and pt2 ∈ SKall (2) pt1 ∈ SKchg and pt2 ∈ SKns (3) pt1 ∈ SKchg and pt2 ∈ SKchg (4) pt1 ∈ SKchg and pt2 ∈ SKall Proof. 1. Obviously pt1 will not leave skyline after tx . Since pt2 ∈ SKall before tx there must be at least / one skyline point in SKall dominating it. If pt1 is the only dominating pt2 before tx , after tx pt1 will stop dominating pt2 and no other skyline points still dominate it. Consequently, pt2 will enter the skyline after tx . 2. Obviously pt2 will not leave skyline after tx . But if ∀k, pt2 .pk ≤ pt1 .pk holds, pt2 will become dominating pt1 and causes pt1 to leave the skyline, since dist(q, pt2 ) < dist(q, pt1 ) holds after tx . 3. If ∀k, pt2 .pk ≤ pt1 .pk holds, pt2 will become dominating pt1 and causes pt1 to leave the skyline, because dist(q, pt2 ) < dist(q, pt1 ) holds after tx . Due to the same reasoning as in (2) of Lemma 3.3.1, pt2 itself will not leave the skyline since no other points become dominating it after tx . 4. Due to the same reasoning as in (1), pt2 may enter the skyline after tx . We postpone to later the discussion on whether pt2 will become dominating pt1 and make it leave skyline.

Proof. Assume that pt1 will be dominated by pt2 and leave the skyline after tx , we have pt2 pt1 . Because pt2 is not in SKall before tx , in SKall there must exist at least one pt3 dominating pt1 , i.e. pt3 pt2 . For simplicity of presentation we assume that pt3 is the only one skyline point of such kind. By transitivity we have pt3 pt1 . But because pt1 is in SKchg distance from pt3 to query point must be larger than that from pt1 before tx , otherwise pt3 pt1 means pt1 ’s absence from SKchg . Thus for pt2 to dominate pt1 after tx , it must first become incomparable to pt3 , which requires that an intersection between pt1 and pt3 must happen no later than tx . If the time of intersection is earlier than tx , however, pt2 will be in SKchg before tx . Thus that time must just be tx . Therefore three points must have their distance function curves intersect at the same point, and is not the only intersection at time tx . Note that pt3 cannot be pt1 in the above proof. Otherwise, before tx , we have pt1 pt2 . Thus, ∃k, such that pt1 .pk < pt2 .pk because we assume that their static non-spatio parameter values are not same for every dimensions. It leads to pt2 can not dominate pt1 after tk because pt1 .pk < pt2 .pk still holds.

d istance 2 p t2 p t2 in S K c hg !

p t3

p t1 0 tx -D t tx

< p t1 , p t2 , tx > < p t1 , p t3 , tx > < p t3 , p t2 , tx > time

Figure 4: Multiplex intersection example Figure 4 shows such a scenario, and we call such an intersection multiplex intersection. One feasible processing strategy for this situation is to only consider if pt2 has the chance to enter SKchg . We need to check if pt1 is the only one that used to dominate pt2 . We ignore the possibility that pt2 might enter the skyline and start dominating pt1 at the same time. That possibility is indicated by other intersections at the same time, each of which is to be processed in isolation. Let us still refer to the example in Figure 4. According to the strategy above the intersection will be ignored. After time tx , both pt2 and pt3 are in SKall but pt1 is not. This result can be achieved as long as the three intersections are correctly processed one by one according to our discussion above, regardless of the order in which they are

Table 1 lists all possibilities attached to an intersection. For the possibility that pt1 comes from SKchg and pt2 from SKall , an interesting issue is whether pt2 can dominate pt1 after time tx . Lemma 3.3.3. For an intersection in which pt1 ∈ SKchg and pt2 ∈ SKall before tx , pt1 will not be dominated by pt2 and leave the skyline after tx if no other intersection happens at the same time and the static nonspatio parameter values of pt1 and pt2 are not same for every dimensions.

processed. Now, let us look at the processing of the intersections in the order listed in the figure. First, does not change the skyline, because pt1 does not dominate pt2 and thus pt2 will not enter SKchg though it is getting closer to query point than pt1 . Second, will cause pt1 to leave SKchg because pt1 starts dominating it. Finally, will cause pt2 enter SKchg because pt3 is the only one that used to dominate pt2 and now it stops dominating due to its distance to query point becomes larger. The procedures of other processing orders are similar and thus omitted due to space constraint. An extreme situation is that many distance function curves are involved in the same multiplex intersection. Our processing strategy can also ensure the correct change as long as each legal intersection is processed correctly in isolation. In fact, this situation is rather special and happens seldom because it requires that all those points involved to be on the same circle centered at the query point. This situation only happens to the minority data points in usual distributions, and it becomes more infrequent in the moving context. To summarize the above analysis, we only need to take into account two primitive cases in which the skyline may change. Case 1. Just before time tx , si ∈ SKchg and ∃sj ∈ SKall s.t. sj si . At time tx an intersection between their distance function curves happens. Then from time tx on, si ∈ SKchg and leaves the skyline because sj / si , and sj ∈ SKall still. Case 2. Just before time tx , nsp ∈ SKall and ∃si ∈ / SKall s.t. si nsp. At time tx an intersection between their distance function curves happens. Then from time tx on, nsp ∈ SKchg if ∀sj ∈ SKall , we do not have sj nsp. Case 1 determines a skyline change, whereas suggests a possibility of change which requires further checking. For si and sj in Case 1, the relationship of their distances to the query point can be described formally in Corollary 3.3.1. Similarly for nsp and si in Case 2, we have Corollary 3.3.2. Corollary 3.3.1. For Case 1, ∃ ε > 0, dist(q, sj ) > dist(q, si ) holds for any time t ∈ (t − ε, t). But for t ∈ (t, t + ε), dist(q, sj ) < dist(q, si ) holds. Corollary 3.3.2. For Case 2, ∃ ε > 0, dist(q, nsp) > dist(q, si ) holds for any time t ∈ (t − ε, t). But for t ∈ (t, t + ε), dist(q, nsp) < dist(q, si ) holds. Corollary 3.3.1 indicates where to find a potential dominating sj for a volatile skyline point si . For a period of time before the change, such sj must be out of the circle determined by query point q and si . We use Cir(q, si ) to denote the circle whose center is q and radius is the distance from q to si , i.e., dist(q, si ). Corollary 3.3.2 indicates that for the skyline point si involved in Case 2, the possible non-skyline point nsp is also out of circle Cir(q, si ) for a period of time before the change. Namely, the distance from each current skyline point (permanent or volatile) provides indication of future change of skyline.

is to pre-compute and store all possible intersections of any pair of distance function curves, and then process each one when its time comes according to the discussion in Section 3.3. This method produces many "false hits" which actually do not cause skyline changes as we have shown in Table 1. To reduce storing and processing of unnecessary possibilities, we compute and store intersections in an evolving way taking into account the current skyline, rather than compute all intersections at the very beginning. Specifically, first we get the initial skyline and compute some intersections of the distance curves in terms of the current skyline points. Then when some intersections happen and the skyline is changed, we further compute intersections in terms of updated skyline. By looking into near future, we ensure that the skyline query result keeps updated, and more information will be obtained later for updating the skyline in farther future. Given the current skyline points, we only keep those intersections with the likelihood to change the skyline in the future according to Table 1. Besides, we keep all the current skyline points sorted based on their distance to the query point. At each evolving step, we only compute those possible intersections that involve points between two adjacent skyline points si and si+1 and will happen before si and si+1 stop being adjacent. Therefore we need to keep track of any intersection between two skyline points that are adjacent to each other in the sorted order. d istance 2 s3

s2 pt 2 pt 1

s1 0 tc ur t2 t2,3 t1,3 t1,2 time

Figure 5: An example of evolving intersections In Figure 5, for example, s1 , s2 and s3 are three adjacent skyline points between time [0, tcur ], while pt1 and pt2 are two non-skyline points between s1 and s2 . At an evolving step of time tcur , only those intersections in dot will be computed and stored for future processing. Next evolving step is at time t2 and pt2 will enter the skyline if s1 is the only skyline point dominating it. The further next evolving step is at time t2,3 . If s2 is a volatile skyline point and s3 s2 , intersection will cause s2 to leave the skyline from time t2,3 onwards. Otherwise it means an exchange of positions only. Either case causes the order of skyline points to change. For future maintenance, intersection will replace since now s1 and s3 are adjacent. Thus, at time tcur only three intersections will be computed and stored for later processing, less than half of the total intersections in the figure.

3.4 Continuous Skyline Query Processing
Based on the above observations, we now address the issues of the continuous skyline query processing. A naive way

4.

DATA STRUCTURE AND ALGORITHMS

The analysis presented in Section 3 provides us a basis for adapting the kinetic data structure for supporting continuous skyline query processing. The query results need to

be modified only when some existent skyline points leave or non-skyline points enter the skyline. What we need to do is to decide when such cases happen and then what actions to take. Certificates (see subsection 2.4) can be defined to certify no such instance occur within a period of time, thus ensuring the skyline result does not change within that period of time. If any certificate fails, an update on the skyline is required. In our method, each skyline point si ∈ SKchg has a certificate corresponding to Case 1 in Section 3.3, since only volatile skyline points may be dominated by other skyline points and leave the skyline. That certificate will fail when another skyline point becomes dominating si , and then we must remove si from the skyline. Corresponding to Case 2 we also have certificates, though it is not so straightforward as Case 1. At time t, non-skyline point nsp might be dominated by more than one skyline point. For nsp to enter the skyline it must get closer to query point q than all other points dominating it. It is difficult to keep track of all dominators for nsp and predict when nsp will get closer to q than any of them, because those dominators themselves might change as well. We choose another strategy. The earliest time t when nsp gets closer than any of those dominators is recorded. And when that time t comes, conditions in Case 2 will be checked to determined whether nsp will really enter the skyline.

Cert. si sj nspij

Table 2: Certificates and events Objective Event ∀si ∈ SKchg , sj ∈ SKall , s.t. sj si → dist(q, si ) < dist(q, sj ) ∀nspj ∈ SKall , ∀si ∈ SKall , s.t. si nspj → dist(q, si ) ≤ dist(q, nspj ) ∀si ∈ SKall , s.t. ∃sj ∈ SKall ∧ sj si ∧sj = si .next in Lsp → dist(q, si ) < dist(q, sj ) self = si peer = sj self = si peer = nspj self = si peer = sj

ordij

4.1 Implementation Details
Based on the analysis in Section 3, it is obvious that the static partial skyline not only constitutes the unchanging part of the skyline but also provides a search bound for other points that can be in the complete skyline. Besides, the distance from each skyline point (permanent or volatile) provides indication of future changes. Thus, it is beneficial to keep all skyline points in an ordered structure such that the observations from the analysis can be applied efficiently in query processing. We use a bidirectional linked list, named Lsp to store all current skyline points, which are sorted in ascending order of their distances to the query point. For each current skyline point we keep an entry of form (f lag, tuple id, a, b, c, tv , tskip ). f lag is a boolean variable indicating if the skyline point is in SKns . tuple id is the tuple identifier which can be used to access the record. a, b, c are coefficients of the distance function between this point and query point q, introduced in Section 2.3. tv is only available to each changing skyline point, indicating its validity time. tskip is the time when the skyline point will exchange its position with its successor in Lsp . Besides Lsp for all skyline points, a global priority queue Qe is used to hold all events derived from certificates to represent future skyline changes, with preference being given to earlier events. Next we define the certificates and events to be used in our solution.

4.2 Certificates and Events
We define three kinds certificates, which are listed in Table 2. The first column is the name of a certificate, the second is what the certificate to guarantee, and the third lists the data points involved in the certificate. An event occurs when any certificate fails due to distance change resulting from the movement of the query point. Each event is in the form of (type, time, self, peer), where

type represents the kind of its certificate; time is a future time instance when the event will happen; and self and peer respectively represent skyline point and relevant data point involved in the event. Certificate si sj ensures for an existent volatile skyline point si that any other skyline point sj with the potential to dominate si (sj si ) keeps being farther to query point q than si , therefore si is not dominated by any of them and stays in the skyline. Here self and peer respectively point to si ’s and sj ’s entries in Lsp . Certificate nspij ensures for a non-skyline point nsp that all those skyline points currently dominating it keeps being closer to query point q than nsp, therefore nps is prevented from entering the skyline. When a certificate of this kind fails at time, nsp will get closer to query point q than one skyline point si , but whether it will enter the skyline or not depends on whether si is the only one that used to dominate it. This will be checked when an event of this kind is being processed (in Section 4.4). Here self points to si ’s entry in Lsp , whereas peer is the tuple identifier of data point nsp. Besides, we define another kind of certificate ordij , which ensures for an existent skyline point si that its successor sj in ordered list Lsp keeps being farther to query point q than it. This sj does not have the potential to dominate si , otherwise an si sj certificate will be used instead. Here self points to the entry of the predecessor skyline point in the pair, and peer to the successor. Certificate ordij not only keeps the order of all skyline points in Lsp , but also implies a way to simplify event computation and evolvement. For Case 1 described in Section 3.3, it also involves a position exchange in Lsp , i.e. just before sj dominating it sj must be its successor. And we need to determine if an exchange in Lsp really results in si sj event. In this sense, we only need to check for si its successor to compute a possible si sj event. If si does have an event of si sj type, the event’s time value is exactly si ’s validity time tv . If si has no si sj event, its validity time is set to infinity. An event of certificate nspij with self = si is supposed to have a time stamp no later than si .tv , and those events with a later time are not processed. For each current skyline point si , we only need to consider the earliest event (si becomes invalid or exchanges with its successor), and postpone the further ones after processing the earliest one. This helps preclude unnecessary events to be processed, and thus reducing the processing time. In our proposed method, the Lsp initially contains the current skyline points, and the priority queue contains events that will happen in the nearest future time to cause the

skyline to change. As time elapses, every due event is dequeued from the priority queue and processed based on its type. While processing due events and updating the skyline result accordingly, the procedure also creates new events that will happen in later future and that will cause skyline changes. Thus the event queue evolves with due events being dequeued and new events being enqueued, providing correct information for maintaining the skyline by looking into near future. At any time t after all due events are processed, Lsp is the correct skyline with respect to the moving query point q’s current position.

4.3 Initialization
We partition the dataset D into two groups: the set of static partial skyline points SKns , and the rest D = D − Kns . We pre-compute SKns and store it as a system constant. Thus, the initialization produces two outcomes: the changing part, i.e. SKchg , of complete skyline with respect to the starting position of the query point, and the earliest events that will be used later to update the skyline. Algorithm Initialization(q) Input: q is the query point Output:the skyline for q’s starting position the event queue to be used in maintenance // load SKns into skyline list 1. for each si in Skns 2. Compute a, b, c in terms of q; 3. Insert an entry (1, si , a, b, c, ∞, ∞) into Lsp ; // search bound determined by SKns 4. dbnd = dist(Lsp .last, q); // compute initial skyline 5. Search the grid cell cellorg in which q lies; 6. while there still exist grid cells unsearched 7. for each cell celli on next outer surrounding circle 8. if (mindist(q, celli ) ≥ dbnd ) 9. break; 10. else Search celli ; // compute events 10. for each si from Lsp .last.prev to Lsp .f irst 11. CreateEvents(si , q); // handle last skyline point specially 12. tnext = Qe .f irst.time; 13. slast = Lsp .last; 14. tnsp = ∞; peer = null; 15. C = Cir(q(tnext ), slast ) − Cir(q, slast ) 16. for each point nsp in C 17. for each sj from slast to Lsp .f irst 18. t = time nsp will get closer to q than sj ; 19. if ((t ≥ sj .tv ) or (t ≥ sj .tskip )) continue; 20. if (∀k, sj .pk ≤ nsp.pk ) 21. Enqueue (sj , t, nsp, nspij ) to Qe ; 22. break; Figure 6: Initialization framework To compute SKchg over static dataset for the query point’s starting position, in order to use the search bound determined by static partial skyline SKns and reduce intermediate steps to access data tuples when computing events, we use the grid file to index all data points. Grid file provides a regular partition of space and at most two-disk-access feature for any single record [10]. In our solution for the static

dataset, we use the simplest uniform 2D grid file that divides the data space into h × v cells to index D , and the data points within each cell are stored in one disk page. For the similar reasons we use a hash based method [13] to index moving data points in D . The data space is also divided into regular cells, with each representing a bucket to hold all those moving data points within its extent. Data points can move across adjacent cells with the velocities in its tuple, which is monitored by a pre-processing layer and declared in an explicit update request to the database. An update request can also change a data point’s speed. How to deal with the updates of moving data points to maintain the correct skyline will be addressed in Section 4.5. Except for the difference on underlying indexing schemas, the initializations for static and moving datasets share the same framework and events creation algorithms. The initialization framework based on the grid file is presented in Figure 6. First all permanent skyline points in SKns are inserted into Lsp according to their distance to query point q’s starting position. The farthest distance is recorded in variable dbnd as the search bound. Then starting from cell cellorg where q’s starting position lies, all grid cells are searched in a spiral manner that those on an inner surrounding circle are searched before those on an outer one. During the search, those cells farther than dbnd are pruned. In line 7 of Figure 6, mindist(q, celli ) is computed. After all cells are searched or pruned, the algorithm CreateEvents is invoked for each skyline point si from outer to inner, to compute all events for all skyline points except for the last one. After the loop, we compute a possible nspij event for those points out of the last skyline point slast . That computation does not involve all outer non-skyline points of slast ’s, instead it is limited to an estimated region. This region C is the difference between the two circles determined by slast and query point q at two different times, the current time and the earliest event time tnext in the future. The later is represented by q(tnext ). Because only the non-skyline points in that region have chance to get closer to query point than slast and enter the skyline before tnext . Points in a grid cell that is not pruned by the search bound dbnd are sequentially compared to the current skyline points in Lsp , which is adjusted with deletion or insertion if necessary. Algorithm CreateEvents is presented in Figure 7. For a given skyline point si in Lsp , the algorithm first computes the time t when si and the next skyline point sj in Lsp will exchange their position in the list, i.e. when sj will get closer to q than si . If t is later than sj ’s skip time or si ’s validity time, it is ignored. Otherwise, it means an si sj event depending on sj ’s validity time if si ∈ SKchg , or it is a simple order change event. Then for each non-skyline point nsp between Cir(q, si ) and Cir(q, sj ), the algorithm computes nspij event by looping on all skyline points in the inner of nsp. Once an nsp event is derived , the loop on all inner skyline points is halted. All events created are enqueued into the event queue.

4.4

Updating the Skyline

In maintaining the skyline, the due events are dequeued and processed according to it type, and new events are computed based on the new position of query point. As in the initialization, the event of points out of the last skyline point is computed in a special way with an estimated search re-

Algorithm CreateEvents(si , q) Input: si is a skyline point in Lsp q is the query point Output:upcoming events for si 1. peer = null; // compute events with next skyline point in Lsp 2. sj = si .next; 3. t = time si and sj will exchange position; 4. if ((t < sj .tskip ) and (t < sj .tv )) 5. if (!si .f lag) 6. if ((t < si .tv ) and (∀k, sj .pk ≤ si .pk )) 7. si .tv = t; peer = sj ; 8. else si .tskip = t; // enqueue relevant events 9. if (peer = null) 10. Enqueue (si , si .tv , rep, si sj ) to Qe ; 11. if (si .tskip < si .tv ) 12. Enqueue (si , si .tskip , sj , ordij ) to Qe ; // compute events involving non-skyline points 13. for each point nsp between Cir(q, si ) and Cir(q, sj ) 14. for each sj from si to Lsp .f irst t = time nsp will get closer to q than sj ; 15. 16. if ((t ≥ sj .tv ) or (t ≥ sj .tskip )) continue; 17. if (∀k, sj .pk ≤ nsp.pk ) 18. Enqueue (sj , t, nsp, nspij ) to Qe ; 19. break; Figure 7: Create events

Algorithm updateSkyline(tcur ) Input: tcur is the current time Output:updated Lsp and Qe 1. slast = Lsp .last; 2. while (Qe .f irst.time == tcur ) 3. evt = Qe .dequeue; // call corresponding process for evt 4. Process evt in terms of evt.type; 5. if (slast = Lsp .last) return; 6. slast = Lsp .last; 8. tnext = Qe .f irst.time; 9. C = Cir(q(tnext ), slast ) − Cir(q(tcur ), slast ) 10. for each point nsp in C 11. for each sj from slast to Lsp .f irst 12. t = time nsp will get closer to q than sj ; 13. if ((t ≥ sj .tv ) or (t ≥ sj .tskip )) continue; 14. if (∀k, sj .pk ≤ nsp.pk ) 15. Enqueue (sj , t, nsp, nspij ) to Qe ; 16. break; Figure 8: Update the skyline Process si sj event e 1. si = e.self ; sj = e.peer; 2. Delete si from Lsp ; 3. si = sj .prev; 4. CreateEvents(si , q); Figure 9: Process si sj event

gion. Algorithm updateSkyline is presented in Figure 8. The actions to process each kind of events are described respectively in Figures 9 to 11. For an si sj event, si is removed from the skyline and new events are computed for si ’s predecessor because its successor skyline point in Lsp has been changed. For an nspij event, the non-skyline point nsp will be checked against all those skyline points closer to the query point, to see if they will enter the skyline. If not, a possible new nsp event is computed. Otherwise it will be added into the skyline and events will be computed for itself and its predecessor. For an ordij event the Lsp is correctly adjusted by switching si and sj , and events are computed for themselves and their predecessor.

4.5

Updating the Moving Plan

If a moving data point mpti ’s moving plan changes, e.g., its velocity and its distance function, will change and intersections with other ones will also be changed as a consequence, which invalidates those events computed based on mpti ’s old distance function curve. Figure 12 shows how a data point’s velocity change causes the intersections of the function curves to change. Thus, it may cause the skyline to change. To ensure correct distance computation with updates, we need to add for each moving object’s tuple a field tupt indicating its last update time. We define an update request for any moving data point mpti in the form update(id, x, y, vx , vy ). id is mpti ’s identifier which can be used to locate its tuple directly. x and y represent its current position. vx and vy represent its current speed. When such an update request comes in, we have to check if mpti has moved to a new cell and if its speed has been changed since the last update. If x and y indicate that mpti has moved to a different cell, we

Process nspij event e 1. si = e.self ; nsp = e.peer 2. dominated = FALSE; // check inner skyline points 3. for each sj in Lsp from si .prev to first 4. if (∀k, sj .pk ≤ nsp.pk ) 5. dominated = TRUE; 6. break; //nsp does not enter the skyline this time 7. if (dominated) 8. sk = si .prev; 9. t = time nsp will get closer to q than sk ; 10. if ((t < sk .tv ) and (t < sk .tskip ) and (∀k, sk .pk ≤ nsp.pk )) 11. Enqueue (sk , t, nsp, nspij ) to Qe ; 12. else // nsp enters the skyline 13. Insert nsp into Lsp before si ; 14. sj = si .prev; 15. CreateEvents(sj , q); 16. CreateEvents(sj .prev, q); Figure 10: Process nspij event Process ordij event e 1. si = e.self ; sj = e.peer; 2. Switch si and sj ’s positions in Lsp ; 3. CreateEvents(si , q); 4. CreateEvents(sj , q); 5. if (sj .prev = null) 6. CreateEvents(sj .prev, q); Figure 11: Process ordij event

d istance 2 p t4 new curve p t3 p t2 p t1 0 tupt o ld curve time

Figure 12: An example of the change of moving plan

need to remove it from the old one and insert it into the new one. If vx and vy indicate that mpti ’s speed has been changed, we need to remove old events relevant to mpti and compute new ones based on its new speed. This algorithm is presented in Figure 13. To facilitate location of events involving a data point efficiently, the priority event queue is implemented using a B+ -tree, and each current skyline point si has a list of pointers to all those events whose self is si . It also can be seen in Figure 12 that right at the time, an update request comes in the skyline does not change abruptly. To keep the skyline correct, the update request is only processed after all due events are processed, i.e., updateMotion(req) at time tu executes after updateSkyline(tu ) completes.

Algorithm updateMotion(req) Input: req is an update request Output:updated hash index, tuple and Qe 1. cell1 = T uple(req.id).cell; 2. cell2 = Hash(req.x, req.y); 3. if (cell1 = cell2 ) 4. T uple(req.id).cell = cell2 ; 5. remove req.id from cell1 and insert it to cell2 ; 6. if ((req.vx == T uple(req.id).vx ) and (req.vy == T uple(req.id).vy )) 7. return; 8. T uple(req.id).vx = req.vx 9. T uple(req.id).vy = req.vy 10. T uple(req.id).tupt = tcur // Adjust relevant events 11. for each si in Lsp from Lsp .f irst 12. if (si .tuple id == req.id) 13. Delete all si ’s events; 14. CreatEvents(si , q); 15. return; 16. Delete all si ’s events with peer == req.id; 17. if (dist(q, T uple(req.id)) ≤ dist(q, si )) 18. break; 19. nsp = req.id; 20. for each sj from si to Lsp .f irst 21. t = time nsp will get closer to q than sj ; 22. if ((t ≥ sj .tv ) or (t ≥ sj .tskip )) continue; 23. if (∀k, sj .pk ≤ nsp.pk ) 24. Enqueue (sj , t, nsp, nspij ) to Qe ; 25. break; Figure 13: Handle the change of moving plan

4.6 Cost Analysis
The space cost incurred by our method consists of two components: the space used to keep the skyline and that used to store events. For a d-dimensional dataset with N points subject to independent distribution, the size of its skyline is nsky = O((log N )d−1 /(d − 1)!) as presented in [5]. Since there are m static dimensions involved in skyline operator in our assumption in Section 2.1, the size of skyline on static dimensions is |SKns | = O((log N )m−1 /(m − 1)!), and the size of skyline on all dimensions is |SKall | = O((log N )m /m!) at any time. Thus the size of changing part is |SKchg | = |SKall | − |SKns | = O((log N )m−1 (log N − m)/m!) at any time. Now we consider the number events at any time. In our method, any si sj event or ordij event is determined by an underlying intersection between two adjacent skyline points’ distance function curves. Therefore, the maximum number of events of these two kinds are |SKall | − 1, the number of such intersections. For nspij events, the worst case is that every non-skyline point is involved in such an event, which means the number of nspij events is N − |SKall | at most. By summing up all events, the number of total events in the worst case is N − 1. The IO cost in our method is mainly incurred by CreateEvents, which accesses all non-skyline points between the circles of two adjacent skyline points in Lsp . This access can be regarded as a special region query over the dataset indexed by grid file, asking for points between two circles with same center but different radiuses. The IO cost of such query can be estimated with a simple probabilistic model. Let the data space be a 2D unit space, and the outer and inner circles have radii r1 and r2 respectively. Then the area
2 2 of the query circle is S = π · (r1 − r2 ), and the query will 2 2 access S · P = π · (r1 − r2 ) · P grid cells (pages). Let us compare the time cost of continuous skyline query to that of using snapshot skyline queries. Assume N snapshot queries are triggered within a time period [t1 , t2 ], and the cost of each is Ci . Then the total and average cost of PN PN i=1 Ci respectively. More that method are i=1 Ci and N snapshot queries incur higher total processing cost, while each single snapshot query’s cost may vary little from the average cost C because of the static processing fashion. For the same time period, our method computes the initial skyline and events at time t1 , and then updates the skyline only when some certificate fails before t2 . Suppose the number of certificate failures during [t1 , t2 ] is N (including the initialization), and the cost of each is Ci , the total and average PN PN i=1 Ci cost of our method are respectively. i=1 Ci and N The number of certificate failures N is a constant in a fixed time period, therefore the average cost C is determined by the total cost only. It makes little sense to compare the total costs of these two methods. If too many snapshot queries are triggered the total cost will be very high, while few snapshot queries deteriorate the result accuracy. To ensure a fair comparison of average costs, we set N = N in our experiment. In other words, we trigger snapshot queries by assuming when the skyline changes is known, which is gained from our method. The experimental study results in the next section show that our method even outperforms the privileged snapshot query

method.
Log of IO Count

1.E+06 1.E+05 1.E+04 1.E+03 1.E+02 1.E+01 100K

BBS CSQ

1.2 1.0

BBS CSQ

CPU Time (s)

5. EXPERIMENTAL EVALUATION
In this section we present the results of our experiments conducted on a desktop PC running on Microsoft Windows XP professional. The PC has a Pentium IV 2.6GHz CPU and 1GB main memory. All experiments were programmed in ANSI C++.

0.8 0.6 0.4 0.2 0.0 100K

300K

500K Cardinality

700K

900K

300K

500K Cardinality

700K

900K

5.1 Experiments on Static Dataset
For the static dataset we mainly explored into the effects of cardinality and non-spatio dimensionality on the performance. We used synthetic datasets of data points with spatial attributes (x and y) and two to five static nonspatio attributes. For each dataset, all data points are distributed independently within the spatial space domain of 10, 000 × 10, 000, and their non-spatio attribute values range independently from 1 to 100,000. The cardinality of datasets ranges from 100K to 1M. For each set of data we executed 100 continuous queries moving in random directions. For each query, we randomly generated a point within the data space as the starting position of the moving query point. The speed of each moving query point is also randomly determined and ranges from 10 to 30. Each query ends as soon as the query point moves out of the data space extent. The experiment results to be reported are the average values of those 100 queries, if not explicitly stated otherwise. Because currently BBS algorithm is the most efficient one for computing skyline for a static query point [11], we implemented and used it for comparison. At each time instance, the BBS algorithm is invoked to re-compute the skyline in terms of the query point’s new position. It is worth noting that BBS can not correctly tell when the skyline changes as our method does. The comparison was carried out on a fair basis. The same set of randomly generated queries are used by both methods on the dataset of the same size. Processing costs, IO count and CPU time, in both methods are amortized over the same number of time units when the skyline changes.
160000 120000

(a) IO
Maximum Average
Event & Skyline
120 100 80 60 40 20

(b) CPU time
|SKall| |SKns| Due events

Queue Size

80000

40000

0 100K

300K

500K Cardinality

700K

900K

0 100K

300K

500K Cardinality

700K

900K

(c) Event queue size

(d) Skyline size and due events

Figure 14: Effect of dataset cardinality

is much smaller compared to the maximum size, and it does not exceed 6% of the cardinality. Figure 14(d) shows the effect of cardinality on skyline size and the number of events being processed at any time unit. It can be seen that complete skyline size roughly increases as cardinality increases, but the average number of due events at any time unit of skyline change never exceeds 4, which indicates the efficiency of our maintenance strategy. By comparing Figure 14(c) and 14(d) we can see that some events may be not processed at all before the query ends. In a real application, we can take advantage of this observation to further reduce the queue size. The lifetime of a query can be estimated in a specific scenario, e.g., in 2 hours or this afternoon, and any event whose due time later than it will be prevented from being enqueued.

5.1.1

Effect of Cardinality 5.1.2 Effect of Non-spatio Dimensionality
In this set of experiments, we used datasets of 500K points with non-spatio dimensionality ranging from two to five to evaluate the effect of non-spatio dimensionality on our solution. The settings are the same as in Section 5.1.1. Figure 15(a) and 15(b) show the IO and CPU cost respectively. Again our maintenance method outperforms the BBS method. As the non-spatio dimensionality increases the gap of costs keeps steady. Figure 15(c) shows that the event queue size decreases as the non-spatio dimensionality increases. The probability that one volatile skyline point will be dominated by others is lower when more dimensions are involved, because all dimensions are independent in our dataset. This may reduce the number of events. Figure 15(d) shows the effect of non-spatio dimensionality on skyline size and the number of events being processed at any time unit. It can be seen that both static partial skyline and complete skyline size increases rapidly as non-spatio dimensionality increases, but the average number of due events at any time unit is drastically much smaller. This indicates that our maintenance strategy still works efficiently.

In this set of experiments, we used datasets of two nonspatio attributes to evaluate the effect of cardinality on our method, by comparing it with the BBS method. For both indices, R∗ -tree and grid file, we set the data page size to 1K bytes. Figure 14(a) shows that as cardinality increases the logarithm of IO count of our maintenance method grows steadily, and nearly 2 orders of magnitude less than that of BBS. Figure 14(b) shows that as cardinality increases the CPU time cost of our maintenance solution grows steadily, in a rate much less than that of BBS. At each time instance, our maintenance solution does not need to search the whole dataset again to re-compute the skyline from scratch, instead it mainly involves event processing which consists less computation of distance and comparison of attribute values than BBS, which does a totally new search via R∗ -tree. This processing behavior difference leads to the difference on processing costs. Figure 14(c) shows the effect of cardinality on event queue size at any time unit. The maximum size is gained throughout all 100 queries. It can be seen that the queue event size increases as the cardinality increases, the average queue size

1.E+06

BBS CSQ

3 2.5

BBS CSQ

Log of IO Count

1.E+05

CPU Time (s)

2 1.5 1 0.5

processing cost may stop increasing and go back to a lower level. Beside, higher ratio of moving data update still incurs higher processing costs.
15000 10% 8% 6% 10000
CPU Time (s)
6 5.5 5 4.5 4 3.5 3 2.5 10% 8% 6% 4%

1.E+04

1.E+03

2

3

4

5

2

3

4

5

Non-spatio Dimensionality

Non-spatio Dimensionality

IO Count

1.E+02

0

4%

5000

(a) IO
70000 56000 42000 28000 14000 0 2 3 4 5 Non-spatio Dimensionality
Event & Skyline

(b) CPU time
4000 |SKall| |SKns| Due events 0 30 60 90 120 3000 Update Interval

Maximum Average

2 30 60 90 120

Update Interval

Queue Size

2000

(a) IO

(b) CPU time

1000

Figure 16: Effect of update
2 3 Cardinality 4 5
10000 9000 10% 8% 6% 4%
4.3 4.1 10% 8% 6% 4%

0

7000 6000 5000 4000

CPU Time (s)

(c) Event queue size

(d) Skyline size and due events
IO Count

8000

3.9 3.7 3.5 3.3 3.1 2.9

Figure 15: Effect of non-spatio dimensionality

5.2 Experiments on Moving Dataset
For the moving dataset we mainly explored into the effects of mobility on the performance. We used the dataset of 500K data points with spatial attributes (x and y) and two static non-spatio attributes. Every point in each dataset moves within the 2-dimensional extent with a speed ranging from 10 to 30. Periodically, a number of moving data points send in update requests. Queries are picked up in the same way as on static datasets.

3000 0 5 10 15 20

0

5

10 Skew Factor - Theta

15

20

Skew Factor - Theta

(a) IO

(b) CPU time

Figure 17: Effect of speed distribution

6. CONCLUSION
In this paper, we address the problem of continuous skyline query processing. The method, using the kinetic data structure, is based on the analysis that explores the spatiotemporal coherence of the problem. Our solution does not need to compute the skyline from scratch at every time instance. Instead, the possible change from one time to another is predicted and processed accordingly, thus making the skyline query result updated and available continuously. Our solution is experimentally evaluated to be effective and efficient.

5.2.1

Effect of Update

In this set of experiments, the initial speeds of all 500K points were uniformly distributed in the range of 10 to 30. We investigate into two aspects of moving data points update: update interval length and the ratio of points requesting update. We varied the update interval length from 30 to 120 time units and update ratio from 4% to 10%. Figure 16(a) shows the IO count decreases as the update interval increases, and higher ratio of moving data update incurs more IO counts. Longer update interval reduces the amortized update cost which involves changing tuple and recomputing events. While higher update ratio increases update cost at every update time. The similar trend is seen for the CPU time shown in Figure 16(b).

7. REFERENCES

5.2.2

Effect of Speed Distribution

In this set of experiments, we fixed the moving data points update interval to 60, varied the update ratio from 4% to 10% to see the effect of skewed initial speed distributions. The skew factor theta ranges from 0, which means a uniform distribution, to 20, which means 80% data points have speed lower than the top 20% largest speeds. Each data point’s speed still varies from 10 to 30. Figure 17(a) shows that when theta equals to 15, the IO cost reaches the highest. In Figure 17(b), CPU time increases slowly as theta increases from 0 to 15, and then decreases when theta equals to 20. As the number of faster moving data points increases the processing cost first also increases. When that number is large enough, however, the

[1] W.-T. Balke, U. G¨ntzer, and J. X. Zheng. Efficient u distributed skylining for web information systems. In EDBT, 2004. [2] J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. In SODA, 1997. [3] R. Benetis, C. Jensen, G. Karciauskas, and S. Saltenis. Nearest neighbor and reverse nearest neighbor queries for moving objects. IDEAS, 2002. [4] S. Borzonyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, 2001. [5] C. Buchta. On the average number of maxima in a set of vectors. Source Information Processing Letters, 33(2), 1989. [6] G. Hjaltason and H. Samet. Distance browsing in spatial database. ACM TODS, 24(2), 1999. [7] G. S. Iwerks, H. Samet, and K. Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In VLDB, 2003.

[8] D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: An online algorithm for skyline queries. In VLDB, 2002. [9] H. Mokhtar, J. Su, and O. Ibarra. On moving object queries. In PODS, 2002. [10] J. Nievergelt and H. Hinterberger. The grid file: an adaptable, symmetric multikey file structure. ACM TODS, 9(1), 1984. [11] D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In SIGMOD, 2003. [12] S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the positions of continuously moving objects. In SIGMOD, 2000. [13] Z. Song and N. Roussopoulos. Hashing moving objects. In MDM, 2001. [14] K. Tan, P. Eng, and B. Ooi. Efficient progressive skyline computation. In VLDB, 2001. [15] X. Xiong, M. F. Mokbel, W. G. Aref, and S. E. Hambrusch. Scalable spatio-temporal continuous query processing for location-aware services. In SSDBM, 2004. [16] J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. Lee. Location-based spatial queries. In SIGMOD, 2003.