Free Essay

Continuous Skyline Queries for Moving Objects

In: Computers and Technology

Submitted By omarmorsy
Words 11922
Pages 48
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.…...

Similar Documents

Premium Essay

Skyline Aviation-Final Draft

...MANAGEMENT 3620 skyline aviation operation and resource management analysis. SKYLINE AVIATION OPERATION AND RESOURCE MANAGEMENT ANALYSIS – SKYLINE AVIATION. SUMMARY: This document outlines a project plan to evaluate and analyze the operations and resource management strategies of “Skyline Aviation”, a world renowned custom aircraft manufacturing company who has been in the business for over half a century. Safety, luxury, and efficiency has been the vision and manufacturing custom air transport solution to serve its customer base is the mission of Skyline Aviation for the last several years. The company has been operating with increasing revenues and profit margin until lately. Due to the fierce competition Skyline Aviation has recently lost considerable market share. The company has not only lost the business, but also has given up a significant part of its seasoned and experienced work force in the hands of new and upcoming competition. The purpose of this document is to review and analyze some of the processes and procedures being followed and monitored to improve enterprise wide operations of Skyline Aviation. It also includes proposals to alternative practices and methodologies using Total Quality Management, Supply Chain Management and inventory control to reduce operating costs, enhance quality, increase employee morale, and find ways and means to incorporate value added innovative solutions to its existing product line. It will also suggest methods to...

Words: 3756 - Pages: 16

Premium Essay

Queries

...  Assignment #7 – Queries A query expressed in a high-level query language such as SQL must first be scanned, parsed, and validated. The scanner identifies the language tokens, such as SQL keywords, attributes names, and relation names in the text of the query, whereas the parser checks the query syntax to determine whether it is formulated according to the syntax rules of the query language. The query must also be validated, by checking that all attribute and relation names are valid and semantically meaningful names in the schema of the particular database being queried. An internal representation of the query is then created, usually as a tree data structure called a query tree. It is also possible to represent the query using a graph data structure called a query graph. The DBMS must then devise an execution strategy for retrieving the result of the query from the database files. A query typically has many possible execution strategies, and the process of choosing a suitable one for processing a query is known as query optimization. Optimization in a database makes things work smoothly. One heuristic rule is to use SELECT operation before using the JOIN or other Binary operations. This is because the resultant size of the file from a Binary operation such as JOIN is usually a multiplicative function of the sizes of the input files. So, The SELECT operation reduces the size of a file so it must be used before the JOIN or other binary Operation. Secondly, we can......

Words: 345 - Pages: 2

Free Essay

Moving

...”We are moving to California,” my father said. “This is a great opportunity for a better education.” My father had just arrived at our apartment in Queens, New York City from a long business trip. When he told me, I did not know what to think. This must have been the third time already, having to move from Korea to Poland and back, and then from Korea to New York right after. Though I felt uncomfortable moving frequently, it made me learn to avoid attachments to my surroundings. I felt like I had nothing to hold on to anymore; it seemed like I would have to leave everything behind again. Despite the challenges, these events also brought me to a positive realization of what is important in my life, one being my family. When we lived in New York, my family and I did not have much; however, as a family we were there for each other. My mother, sister, brother and I settled in a single bedroom apartment, while my father was away for business. My uncles, cousins and grandparents lived in the same neighborhood, so we had many gatherings, which drew us all close together. Since my relatives were so involved in my life, I inevitably gained support and guidance from them, which helped me find the second important thing to hold on to, my dream. As I increasingly recognized and valued the support of my family, I gained motivation and focus toward my dream of becoming a nurse. My mother and grandfather especially influenced me. My mother has been a nurse for many years; vividly......

Words: 501 - Pages: 3

Premium Essay

Continuous Improvement

...Continuous Improvements Concept of Continuous Improvement Filed under: Management of Process Quality, Structures and Teams — Tags: continuous improvement, employee involvement, Kaizen, operator ownership, SPC — Nameer @ 8:00 pm Continuous improvement is based on a Japanese Concept called Kaizen, is the philosophy of continually seeking ways to improve operations. It invloves identifying benchmarks of excellent practices and instilling a sense of employee ownership of the process. The focus can be on: * Reducing the length of time required to process requests for loans in bank * The amount of scrap generated at a milling machine or the number of employee injuries. * Continuous improvement can also focus on problems with customers or suppliers, such as customers who request frequent changes in shipping quantities and suppliers that to maintain high quality. The bases of the continuous improvement philosophy are the beliefs that virtually any aspect of an operation can be improved and that the people most closely associated with an operation are in the best position to identify the changes that should be made. Consequently, employee involvement plays a big role in continuous improvement programs. Getting Started with Continuous Improvement Instilling a philosophy of continuous improvement in an organization may be a  lengthy process, and several steps are essential to its eventual success. 1. Train employees in the methods of statistical process control......

Words: 347 - Pages: 2

Premium Essay

Business Objects

...Business Objects Developer Internal Req #: 5216 Client Req #: ST7080 Client: State of WI – DOT Location: Madison, WI The desired candidate will possess an advanced knowledge and skill with Business Objects Reporting Tools including Universe Designer, WEBI & DESKI Report Development and Dashboard Designer. They will possess strong analysis and design skills and be familiar with Business Intelligence and Data warehousing concepts. A solid understanding of relational data structures and proficiency in SQL development is a requirement. Prior experience with Business Objects XI Version 3 is preferred. This position will work directly with the DMV (Division of Motor Vehicles) Business Area to develop standard reports and universes for various projects. Mentor the business area on universe design and reporting. Excellent oral and written communication skills to be able to interact with staff at all levels of the DOT organization are a requirement. Additional skills should include: * Experience with dimensional models, Informatica ETL, Oracle, DB2, and MS Access * Collaborates with the team to define and follow DOT reporting standards and industry best practices * Strong problem solving and testing skills, and successful project leadership experience is a necessity * The selected contractor will show proof of experience in designing and implementing Business Objects Universes, reports and dashboards and have knowledge and experience in working......

Words: 518 - Pages: 3

Premium Essay

Moving in

...Well, the student year has already started, I’m all settled in but I still the painful process of researching housing options. Isn’t that crazy that you have to fight for the apartment you have never seen 5-6 months in advance?! Well, I got lucky to find my apartment and that was the best decision I could have made. I live in Neil Building; it’s student residential hall, located in South Campus. I absolutely love my place for the following reasons. Firstly, my apartment is fully furnished!!! Yes!! Can you imagine a tiny girl moving or assembling the furniture alone?! I wouldn’t be able to do that, that’s why my main search criteria was to find a furnished place. The studio has everything that person may need: desk, drawers, closet, shelves, bed and fully equipped kitchen. The only thing you need for move-in process is to move in with your luggage, that’s it! Secondly, there is a huge cafeteria Marketplace on the first floor of the building. They have numerous eating options, starting from salads and sandwiches and ending with pasta and soups! Btw, their broccoli and cheese soup is amazing! You may want to check it out! What I like the most is that residents of Neil Building have separate entrance to the café; you have to swipe your BuckID and you are already there. When it rains on weekend and I don’t feel like going out, I can just go down and use the magic door to access the food paradise. Thirdly, the staff at Neil Building is very helpful and friendly. For example,......

Words: 496 - Pages: 2

Premium Essay

Continuous Improvement

...Continuous Improvement Planning Process Dawn Martinez Grand Canyon University: EDA 577 October 1, 2014 Continuous Improvement Planning Process Edwards Deming created a four-step continuous improvement plan that guided educational organizations through a process that would lead to improved student performance (Bernhardt, 2013). The four-step process is used widely in school systems today. Continuous school improvement can be defined as a process of improving schools on an ongoing basis through planning, implementing, evaluating, and improving (Bernhardt, 2013). In order for the system to be effective, all staff members in the educational organization need to be involved and aware of the vision for the school. When an entire school is clear about what needs to be done to improve student performance, the entire school can move ahead and increasing student performance becomes the forefront of efforts made by everyone. This paper will discuss the continuous improvement plan of Patriot Elementary and the action planning steps that are present as well as how the improvement plan is correlated with the ISLLC 2008 Leadership Policy Standards. Evidence of Action Planning Steps When examining the Unified Improvement Plan (UIP) for Patriot Elementary, action planning steps are evident. When developing the UIP for each school year, the Accreditation Team begins by looking at the general demographics of the student population as well as the larger picture of the community as a......

Words: 1454 - Pages: 6

Premium Essay

Continuous Improvement

...Continuous improvement Nowadays, the company need to move and looking forward in order to be successful. The top management must make right decision and action in order to maintain sustainability of the company. They must take into consideration all consequences may arise when the decision taken comes to its implementation state. One of the technique can be apply to the company is continuous improvement. Walt Disney Company, Toyota and United States Environmental Protection Agency are some examples of organization that used continuous improvement as one of the technique used in their business operation. History behind the existence of Continuous Improvement Japan is one of the first countries that realize the existence of continuous improvement. Continuous improvement gives a good impact to the company and also the economy as whole. It was being stated by Ron Ashkenas who is the managing partner of Schaffer Consulting in his article. During 1950s, Japanese manufacturers did not emphasis on quality in the production of product. But then, they imposed a culture of analytical and systematic change. (Ashkenas, 2012) As a result, Japan became one of the countries that dominate key industries such as automobiles (e.g Toyota), telecommunications (e.g Fujitsu) and consumer electronics (e.g Sharp). It starting in 1970s when Japan was able to create low cost and produce quality products. For your information, people in Japan called continuous improvement as kaizen. Kaizen......

Words: 2244 - Pages: 9

Free Essay

What Is an Object

...Concept of Objects 1) Concept of Objects. Ans. An Object is an identifiable entity with certain characteristics and behaviour. You yourself are an example of an object. Your: Characteristics – Eyes, Ears, Nose, Hands, Legs. Behaviour – Walk, Talk, Eat ,Sleep, Dance. DOG. Its: Characteristics – Name, Colour, Breed. Behaviour – Barking, Wagging tail. BIKE. Its: Characteristics – No of gears, No of brakes, Wheels. Behaviour – Braking, Accelerating, Change gear. An object has a state. It has certain characteristics and attributes like size, shape and colour. A change in these attributes are called as the objects behaviour. Each object has a unique identity just as we all have our names to identify ourselves. Take for example TV: The screen size(17”), buttons for switching it on and off and channel change are its state. The motion picture of a TV is its behaviour. The serial number(TI974) which distinguishes it from other TVs is its identity. 2) Concept of converting real world objects into software objects. Ans. Our aim is to implement a real world object into a software object. Real world objects have physical characteristics(state) and behaviour. EXAMPLE – Motor Bike Characteristics - Two wheels, No of gears, Current gear. Behaviour – Braking, Accelerating, Changing gears. Software objects also have state and behaviour . • State is maintained through variables and data items. • Behaviour is implemented through functions called methods. Object -......

Words: 1404 - Pages: 6

Premium Essay

Continuous Accounting

...Continuous Auditing Jessica Hunt Accounting 510 Dr. Yining Chen December 3, 2014 Intorduction Generally auditing: is performed months after the business activities have actually occurred, based on a sampling approach, and includes reviewing of systems of approvals and reconciliations as well as policies and procedures. This method has been realized to provide auditors with only a narrow scope of evaluation and doesn’t really provide much value because of its lack of timeliness. Furthermore it has become evident that a need for timely and ongoing assurance over the effectiveness of risk management and control systems is crucial. This along with the environment of rising risks, and regulatory activity and compliance costs (complying with section 404 of the US Sarbanes-Oxley Act) makes this an optimal time to consider a new approach. Continuous auditing is a method used to perform control and risk assessment automatically on a more frequent basis (Coderre 2005). It enables auditors to continually gather from processes data that supports auditing activities (Deloitte 2010), and allows auditors to provide written results on the subject matter using one or a series of reports issued simultaneously (ISACA 2002). Continuous auditing leverages technology and opens database architecture to enable auditors to monitor a company’s systems over the internet using sensors and digital agents. Discrepancies between the records and the rules defined in the digital agents are......

Words: 2068 - Pages: 9

Premium Essay

Continuous Improvement

...Have the Continuous Improvement (Cl) efforts at Absa Bank’s Horizon Medium Business Banking unit, in the Gauteng West region successfully addressed the key concepts of Continuous Improvement as set out by Trollip, 2008? By Sinqobile Khobotho Ndlovu {20625261} Submitted in partial fulfillment of the requirements for the degree of Masters in Business Administration At the Nelson Mandela Metropolitan University (NMMU) Business School Research Supervisor: Mr. Bux Heather November 2008 Page 1 of 112 Declaration “I, Sinqobile K Ndlovu, declare that: • This work has not been previously accepted in substance for any degree and is not being concurrently submitted in candidature for any degree. • This dissertation is being submitted in partial fulfillment of the requirements for the degree of Masters in Business Administration. • The dissertation is the result of my independent work/investigation, except where otherwise stated. Other sources are acknowledged by referencing and a reference list is attached. • I hereby give consent for my dissertation, if accepted, to be available for photocopying and for loan, and for the title and summary to be made available to outside organizations.” Signed: …………………. Date: 20 December 2008 Page 2 of 112 Abstract Success in today’s highly competitive financial sector requires an organization to have a sustainable competitive advantage that would distinguish it from the rest.......

Words: 28188 - Pages: 113

Premium Essay

Continuous Auditing

...Introduction Technology plays a vital role in continuous auditing activities. As an automatic method, continuous auditing’s responsibility is to perform auditing activities more frequently which including control and risk assessments. With the aim of helping to automate the identification of anomalies or exceptions, analyze models, test controls and review trends, “Continuous” in this aspect of continuous reporting and auditing serves as the financial information’s real-time ability to be shared and checked. Continuous auditing presents that the financial information’s integrity can be evaluated at any given-point-time; as a result, financial information’s inefficient, frauds and errors could able to be verified constantly. In the other hand, we could consider continuous auditing as a very detailed audit. 1 Historical development of continuous auditing As a kind of audit method, it theoretical sources is from the traditional auditing method. The traditional auditing theory is the basis of analyzing the continuous auditing. Most of the auditing is a format of statutory audit, but not all the auditing is required by the statutory from the beginning. Under the freedom of market environment, we should strengthen research on audit risk, explore ways of audit risk management and control, continue to improve audit quality, and reduce audit risk. “In fact, the concept of “continuous auditing” has been around since the late 1980s. But the urgency that Sarbanes-Oxley has......

Words: 758 - Pages: 4

Free Essay

Query

...CREATING QUERIES Lesson 9 Introduction The real power of an Access 2007 database is in the ability to pull data for quick analysis, which is what happens when you run a query. Queries allow you to retrieve information from one or more tables based on a set of search conditions you define. Access 2007 will display your results in their very own table that you can analyze and manipulate further. This lesson will explain how to plan a query using a three-question planning process. You will learn how to use the Query Design command to run the query, as well as how to modify the query to hide fields or other information in your query results. Finally, it will show you how to save the query for later use. Using Queries Queries retrieve information from one or more tables based on a set of search conditions that you set up and then combine that information in a way that is easy for you to analyze. If you have used an Advanced Filter in Access 2007, then you have already run a very basic query on only one table. If you want to pull data from more than one table, though, you will need to use either the Query Design command or the Query Wizard. Before using the Access 2007 query tools, it is important to plan out the query using a logical process. Otherwise, you may not get the results you expect. Planning a Query There are three questions you need to answer when you are planning a query:  What do you want the results to look like? Identify every field or bit of......

Words: 2519 - Pages: 11

Free Essay

Object Oriented Programming -Java

........................................................................................ 4 Provide the UML diagrams for the given problem with clear explanations on the design decisions. Derive detailed Use Case diagram, Class diagram & a sequence diagram. Whenever necessary document the relevant assumptions you made. ...................................................................................... 4 TASK B ....................................................................................................................................................... 7 Provide an alternative OO design for the same problem ......................................................................... 7 Object Oriented Known as Methodology or paradigm to design a program using classes and objects. It simplifies the software development and maintenance. ......................................................................... 7 TASK C ....................................................................................................................................................... 9 There are many system design patterns available in system development. Critically evaluate singleton, factory and abstract factory design patterns and apply the most suitable design pattern for your system development................................................................................................................................. 9 TASK D .................................................

Words: 4819 - Pages: 20

Free Essay

Integrate a Business Analysis Method and an Object Oriented Approach to Develop a Query System for the Influence of an Engineering Change on Erp

...本研究以排量調節組為測試工件,圖 7 為排 MTS(Microsoft Transaction Server)開發環境架構,本 量調節組之實體爆炸圖。其設計變更後 PDM 之 研究採用了以下的規則。在所有有關連結資料庫的 EBOM 表更如圖 8 所示 設計變更後 MRP 之 MBOM 。 資料存取控制物件上,就使用 Delphi 內 「MTS Data 表更如圖 9 所示 吾人便可藉由 MRP 中 MBOM 表 。 Module」物件來進行開發。而在企業邏輯層中的系 更內之資料變化了解 PDM 之設計變更對 MRP 中 統物件,則使用「MTS Object」物件來進行開發。 物料之影響。 最後連結前端的系統控制物件,使用 「Active Server Object」物件來進行開發。其系統元件開發架構圖 如圖 5 所示。所開發完成之系統元件如圖 6 所示。 中衛PDM (PDM Client) Internet Browser 鼎新 (Workflow ERP Clie Ethernet 中衛PDM (PDM Oracle Server) Web Server 圖-7 排量調節組之實體爆炸圖 鼎新 (Workflow ERP SQL Server) 圖-4 系統實作架構 MTS 架構 企業元件 (Delphi : MTS 物件) 中衛PDM (PDM Oracle Serve Web Server 資料存取控制元件 系統控制元件 (Delphi : MTS 資料模組) (Delphi : ASP 物件) Delphi 企業元件開發架構圖 鼎新 (ERP Workflow SQL Server) 圖-8 設計變更後 PDM 之 EBOM 表更 圖-5 系統元件開發架構 圖-6 系統元件顯示圖 4 中國工業工程學會九十年度年會暨學術研討會,高雄,民國九十年十二月八日 圖-9 設計變更後 MRP 之 MBOM 表更 6.結論 本研究首先利用 ARIS 之 e-EPC 建立 PDM 系 統之工程變更審核作業及 ERP 系統運作流程之系 統環境,ARIS 之 e-EPC 是一種流程分析方法,而 UML 則是一種物件導向程式分析技術,從 ARIS 之 Integrate a Business Analysis Method and an Object Oriented Approach to Develop a e-EPC 與 UML 中取各其優點特色,藉此 ARIS 模 型,將事件導向程序鏈結圖轉換為 UML 架構,並 Query System for the Influence of an Engineering Change on ERP 以此 UML 架構的使用案例圖、循序圖以及相關的 分析圖,將流程模型轉換,以便提供工程變更所需 的資訊。 C. Ou-Yang*, C.H. Hwang*, 總觀以上而言,本研究的具體成果如下: Y.H. Cheng**, S.S. Lo** (1) 以 ARIS 之 e-EPC 為工具,將產品生命週期 *Department of Industrial Management 之工程變更流程由 PDM 至 MRP 系......

Words: 1087 - Pages: 5