Additively Weighted Voronoi Diagrams for Optimal Sequenced Route Queries¤

Abstract

The Optimal Sequenced Route (OSR) query strives to ¯nd a route of minimum length starting from a given source location and passing through a number of typed locations in a speci¯c sequence imposed on the types of the locations. In this paper, we propose a precomputation approach to OSR query in vector spaces. We exploit the geometric properties of the solution space and theoretically prove its relation to Additively Weighted Voronoi diagrams. Our approach recursively accesses these diagrams to incrementally build the optimal sequenced route. Our experimental results verify that our pre-computation approach outperforms the previous index-based approaches in terms of query response time.

-

Suppose that we are planning a Saturday trip in town as following: ¯rst we intend to visit a shopping center in the afternoon to check the season's new arrivals, then we plan to dine in an Italian restaurant in early evening, and ¯nally, we would like to watch a speci¯c movie at late night. Naturally, we intend to drive the minimum overall distance to these destinations. In other words, we need to ¯nd the locations of the shopping center si, the Italian restaurant rj , and the theater tk that shows the speci¯c movie, which driving toward them considering the sequence of the plan shortens our trip (in terms of distance or time). Note that in this example, a time constraint enforces the order in which these destinations are to be visited; we usually do not have dinner in the afternoon, or do not go for shopping ¤This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC), IIS-0238560 (PECASE), IIS-0324955 (ITR), and unrestricted cash gifts from Google and Microsoft. Any opinions, ¯ndings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily re°ect the views of the National Science Foundation. 8 7 6 r2 5 4 3 s4 1 2 3 4 5 6 7 8 9 10 11 12

Figure 1: 3 di®erent types of point sets at late night. This type of query is also essential in other application domains such as crisis management, air tra±c °ow management, supply chain management, and video surveillance.

We call this type of query, where the order of the sequence in which some points must be visited is enforced and cannot be changed, the Optimal Sequenced Route or OSR query. Similar types of the planning queries have received recent attention by the database community [ 5, 9, 3, 2 ] to solve problems in the domains of air tra±c °ow and supply chain management, which shows the importance of these query types. We use the ¯rst example described above as our running example throughout the paper. Figure 1 shows three di®erent types of point sets shown by white, black and gray circles, which represent shopping centers, Italian restaurants, and theaters, respectively, and a starting point q (shown by 4). The distance between two points is their Manhattan distance. Here, the route (q; s1; r1; t1) (shown with solid lines in the ¯gure) with the length of 12 units is the optimum answer to our query. One can show that OSR query may not be optimally answered by simply performing a series of independent nearest neighbor queries at di®erent locations (e.g., 15unit length route (q; s2; r2; t2)).

We, for the ¯rst time, introduced the OSR query in [ 8 ] and proposed two online approaches for vector and metric spaces (e.g., road networks). The R-LORD algorithm of [ 8 ] subsequently performs range queries utilizing an R-tree index structure to ¯lter out the points that cannot possibly be on the optimal route, and then builds the optimal route in reverse sequence (i.e., from ending to the starting point). In this paper, we exploit the geometry of the OSR problem space to propose a novel pre-computation algorithm which utilizes Voronoi diagrams for processing OSR queries in vector spaces. In our running examples, we use Manhattan distance in R2 which is a representative of the network distance if the road network consists of a set of north-south and east-west roads [ 1 ]. 1.1

Contributions

Assume that we are only interested in the optimal sequenced routes that follow a ¯xed sequence M . For example, assume that this ¯xed sequence for Figure 1 is (white; black; grey). Suppose we can partition the space of points of interest (e.g., R2) into regions each including all the points with a common OSR. For instance, in Figure 1, there are many points similar to q for which the optimal sequenced route to a white, then a black, and ¯nally a grey point is the route (s1; r1; t1). Suppose that our partitioning identi¯es the region including these points. Furthermore, assume that the partitioning also identi¯es the region corresponding to each and every possible route (si; rj ; tk) to a white, a black, and a grey point. Assume that we associate and store all regions and their corresponding OSRs. Therefore, for a given starting point q we can address the OSR query with sequence M by simply locating the unique region that includes q and reporting its corresponding optimal sequenced route. In Section 3, we prove that such partitioning exists as an Additively Weighted Voronoi diagram, a speci¯c type of general Voronoi diagrams. We theoretically exploit interesting properties of these diagrams which makes them appropriate data structures for e±cient OSR query processing.

We enhance the above query processing approach by exploiting an interesting property of OSRs proved in Lemma 1 (see Section 3). The lemma states that if (s1; r1; t1) is q's optimal route to a white, a black, and a grey point, then (r1; t1) is s1's optimal route to a black and then a grey point. Recursively, (t1) is r1's optimal route to a grey point. Lemma 1 enables us to avoid storing the complete OSR corresponding to each region of the diagram for a given sequence M ; we store only the ¯rst point of the OSR for each region of the Voronoi diagram (e.g., s1 for the region corresponding to (s1; r1; t1)). Instead, we require to compute and store the Voronoi diagrams corresponding to all su±xes of M .

For instance, to answer queries with sequence (white; black; grey) in Figure 1, our approach requires the diagrams corresponding to three sequences (white; black; grey), (black; grey), and (grey). We refer to these diagrams as the OSR-Voronoi family of sequence (white; black; grey). Now, we iteratively process a given OSR query. For the starting point q, we ¯rst ¯nd s1, the white point associated with the region including q in the diagram of (white; black; grey). Then, we ¯nd r1, the black point stored with the region including s1 in the diagram of (black; grey). Finally, we seek for t1, the grey point corresponding to the region including r1 in the diagram of (grey). Now, the ¯nal OSR of q is the route (s1; r1; t1), which includes s1, r1, and t1 in the order of their retrieval.

Our OSR query processing using Voronoi diagrams best suits the applications where the sequences of user's interest are known in advance. This allows precomputation of the corresponding diagrams. Notice that using the OSR-Voronoi family of a sequence M , we can address OSR queries of all su±x sequences of M . Through extensive experiments with a realworld dataset, we show that our approach signi¯cantly outperforms the R-LORD approach proposed in [ 8 ] in terms of response time. We also show that the o®-line process used to build the OSR-Voronoi family of a single sequence is reasonably fast. With a given sequence M , this pre-computation phase takes O(PjiM=1j jUMi j log jUMi j) computation steps. 2 2.1

Preliminaries

Formal Problem De¯nition

In this section, we describe the terms and notations used in [ 8 ] to formally de¯ne the OSR query. We use the same notations throughout the paper .

Let U1; : : : ; Un be n sets, each containing points in a d-dimensional space Rd, and D(:; :) be a distance metric de¯ned in Rd where D(:; :) obeys the triangular inequality. To illustrate, in the example of Figure 1, U1, U2, and U3 are the sets of black, white, and gray points, representing restaurants, shopping centers and theaters, respectively. We ¯rst de¯ne the following four terms. De¯nition 1: Given n, the number of point sets Ui, we say M = (M1; M2; : : : ; Mm) is a sequence if and only if 1 · Mi · n for 1 · i · m. That is, given the point sets Ui, a user's OSR query is valid only if she asks for existing location types. For the example of Figure 1 where n = 3, (2; 1; 2) is a sequence (specifying a shopping center, a restaurant, and a shopping center), while (3; 4; 1) is not a sequence because 4 is not an existing point set. We use sf x(M; i) = (Mi+1; : : : ; Mm) to refer to the su±x of M with size m ¡ i.

De¯nition 2: We say R = (p1; p2; : : : ; pr) is a route if and only if pi 2 Rd for each 1 · i · r. We use p ©R = (p; p1; : : : ; pr) to denote a new route that starts from starting point p and goes sequentially through p1 to pr. The route p © R is the result of adding p to the head of route R. We use sf x(R; i) = (pi+1; : : : ; pr) to refer to the su±x of R with size r ¡ i.

De¯nition 3: We de¯ne the length of a route R = (p1; p2; : : : ; pr) as

r¡1 L(R) = X D(pi; pi+1) i=1 (1) Note that L(R) = 0 for r = 1. For example, the length of the route (s2; r2; s3) in Figure 1 is 4 units where D is the L1 norm (i.e., Manhattan distance).

De¯nition 4: Let M = (M1; M2; : : : ; Mm) be a sequence. We refer to the route R = (p1; p2; : : : ; pm) as a sequenced route that follows sequence M if and only if pi 2 UMi where 1 · i · m. In Figure 1, (s2; r2; s3) is a sequenced route that follows (2; 1; 2) which means that the route passes only through a white, then a black and ¯nally a white point.

Now, we formally de¯ne the OSR query.

De¯nition 5: For a given starting point q in Rd and the sequence M = (M1; M2; : : : ; Mm), the Optimal Sequenced Route (OSR) Query, Q(q; M ), is de¯ned as ¯nding a sequenced route R = (p1; : : : ; pm) that follows M where the value of the following function L is minimum over all the sequenced routes that follow M : L(q; R) = D(q; p1) + L(R) (2) Note that L(q; R) is in fact the length of route Rq = q © R. Throughout the paper, we use Q(q; M ) = (p1; p2; : : : ; pm) to denote the answer to the OSR query Q. Without loss of generality, we assume that this optimal route is unique for given q and M . For the example in Section 1 where (U1; U2; U3) = (black; white; gray), M = (2; 1; 3), and D(:; :) is the shortest path distance, the answer to the OSR query is Q(q; M ) = (s1; r1; t1).

One special variation of OSR is when the user asks for an optimal sequenced route that ends in a given destination q0. A special case of this query is where she intends to return to her starting location q. This variation of OSR can simply be addressed by de¯ning a new point set Un+1 = fq0g and a new sequence M 0 = (M1; : : : ; Mm; n + 1). Consequently, Q(q; M 0) will be the optimal route following M which ends in q0.

Table 1 summarizes the notations we use throughout the paper. 2.2

Voronoi Diagrams

The general Voronoi diagram of a given set S including points in Rd partitions the space into regions each including all points with a common closest point in the given set according to a distance metric d(:; :). The region corresponding to the point p contains all the points q 2 Rd for which we have 8p0 2 S; p0 6= p ) d(q; p) · d(q; p0) (3) The equality holds for the points on the borders of p's and p0's regions. Incorporating arbitrary distance metrics d(:; :) in the above equation results in di®erent variations of Voronoi diagrams. Figure 2 shows the standard Voronoi diagram of nine points in R2 where the distance metric is Euclidean. We refer to the region V (p) containing the point p as its Voronoi cell. We also refer to point p as the generator of Voronoi cell V (p).

Now assume that S is a set of points p 2 Rd each assigned a weight w(p) 2 R. We de¯ne the distance metric d(x; p) as D(x; p) + w(p) where D(:; :) denotes a distance metric. Without loss of generality, we assume that D(:; :) is Euclidean distance. The Additively Weighted (AW) Voronoi diagram of the points in S with respect to distance function D(:; :) is de¯ned using Equation 3. Here, the cell corresponding to point p p contains all the points q 2 Rd for which we have 8p0 2 S; p0 6= p ) D(q; p)+w(p) · D(q; p0)+w(p0) (4) Figure 3 illustrates the AW-Voronoi diagram of a set of 13 points labeled with their positive weights.

The Computational Geometry literature generally uses negative weights in Equation 4 to de¯ne the AWVoronoi diagrams. When negative weights are assigned to points p, their AW-Voronoi diagram can be seen as the standard Voronoi diagram of a set of d-dimensional balls each centered at a point p with a radius equal to the absolute value of w(p). Here, the set S includes balls such as b centered at a point p. The distance d(q; b) between a ball b and the point q outside b is the smallest Euclidean distance between q and any point inside b. The literature uses this view to de¯ne the AWVoronoi diagram of the centers of a set of balls (e.g., disks in R2) [ 6 ]. Each region of the space is assigned to a unique ball which is the common closest ball of all points inside that region. Figure 4 illustrates de¯ning the AW-Voronoi diagram of ¯ve points with negative weights w(p) < 0 using ¯ve corresponding disks. Here, d(q; c), the distance of a point q to a disk c centered at p with radius r = ¡w(p) is de¯ned as D(q; p) ¡ r. As the ¯gure shows, point q which is inside the cell of disk c (corresponding to point p) is closer to disk c than to disk c0. It also shows that some points such as p00 have empty cells. That is, no point in the space is closer to the disk c00 than to any other disk.

The AW-Voronoi diagram demonstrates the following properties: Property AWV-1 With Euclidean distance (i.e. L2 norm) as metric D(:; :) in Equation 4, the cell edges are either straight lines or hyperbolic curves [ 6 ].

Property AWV-3 The AW-Voronoi diagram of n points consists of at most O(n) connected edges [ 7 ]. 3

OSR and AW-Voronoi Diagrams

Assume that we are only interested in the optimal sequenced routes that follow a ¯xed sequence M (i.e., Q(q; M ) for points such as q). Suppose we can partition the space Rd into regions each including all the points q with a common OSR. That is, for any two points x and y inside the same region, we have Q(x; M ) = Q(y; M ). Assume that for each region, we pre-compute this common OSR. Furthermore, we store all regions and their corresponding OSRs for the given sequence M . Therefore, for a given starting point q we can address the query Q(q; M ) by simply locating the region including q and reporting its corresponding optimal route.

In this section, we show that the above partitioning which facilitates processing OSR queries exists as an AW-Voronoi diagram. We prove that a unique property of optimal sequenced routes enables us to employ this partitioning. First, we prove Lemma 1 which states that the optimal route from pi that follows a su±x of the original sequence M is the same as the corresponding su±x of the optimal route from q that follows M . Lemma 1. Given the sequence M = (M1; : : : ; Mm) and the starting point q, if Q(q; M ) = R = (p1; : : : ; pm), then for any 1 · i < m, we have Q(pi; M 0) = sf x(R; i) where M 0 = sf x(M; i).

Proof. The proof is by contradiction. Assume that Q(pi; M 0) = R0 = (p01; : : : ; p0m¡i). Obviously sf x(R; i) = (pi+1; : : : ; pm) follows sequence M 0, therefore we have L(pi; R0) < L(pi; (pi+1; : : : ; pm)). We add L(q; (p1; : : : ; pi)) to the both sides of this inequality to get:

L(q; (p1; : : : ; pi; p01; : : : p0m¡i)) < L(q; (p1; : : : ; pm)) The above inequality shows that the answer to Q(q; M ) must be (p1; : : : ; pi; p01; : : : ; p0m¡i) which clearly follows sequence M . This contradicts our assumption that Q(q; M ) = (p1; : : : ; pm).

This property of the OSRs implies that only the last point of the optimal sequenced route Q(q; M ) (i.e., pm) must necessarily be the closest point of UM to its previous point in the route (i.e., pm¡1).

Here, we utilize the special case of Lemma 1 for the ¯rst point of the route (i.e., p1 for i = 1). For instance, if the optimal route from point q to a white, a black, and a grey point is (s1; r1; t1), then the optimal route from the point s1 to a black then a grey point is (r1; t1) (see Figure 1). Therefore, if we identify the white point s1 with which the optimal route from q to a white, a black, then a grey point starts (i.e., the ¯rst point of the route) and we know that the optimal route from s1 to a black and then a grey point is (r1; t1), we have found the optimal route from q (we just append s1 to the head of (r1; t1)). The following lemma identi¯es this ¯rst point.

Lemma 2. Given the sequence M and the starting point q, if there exists a point p1 2 UM1 so that 8p01 2 UM1 ; p01 6= p1

Proof. The proof is by contradiction. Assume that Q(q; M ) = (p01; : : : ; p0m) starts with p01 6= p1. By definition, the length of q © Q(q; M ) is minimum over all the routes which follow sequence M . It is clear that the route p1 © Q(p1; M 0) follows M , so we have

L(q; (p1 © Q(p1; M 0))) ¸ L(q; Q(q; M )) (6) Lemma 1 states that we have Q(p01; M 0) = (p02; : : : ; p0m) where M 0 = sf x(M; 1). Hence, we get

Q(q; M ) = p01 © Q(p01; M 0) Therefore, we replace Q(q; M ) in Equation 6 to get

L(q; p1 © Q(p1; M 0)) ¸ L(q; p01 © Q(p01; M 0)) Finally, we use the de¯nition of function L() to change Equation 8 as follows for the point p01 6= p1: D(q; p1)+L(p1; Q(p1; M 0)) ¸ D(q; p01)+L(p01; Q(p01; M 0)) (9) The above inequality contradicts the one given in the assumption of the lemma. (7) (8)

In the example of Figure 1, U1, U2, and U3 are the sets of black, white, and gray points, respectively. For the sequence M = (2; 1; 3), we have M 0 = (1; 3) and Q(s1; M 0) = (r1; t1); Q(s2; M 0) = (r3; t3);

Q(s3; M 0) = (r1; t1); Q(s4; M 0) = (r1; t1) D(q; s1) + L(s1; Q(s1; M 0)) = 3 + (7 + 2) = 12 D(q; s2) + L(s2; Q(s2; M 0)) = 2 + (3 + 9) = 14 D(q; s3) + L(s3; Q(s3; M 0)) = 4 + (8 + 2) = 14 D(q; s4) + L(s4; Q(s4; M 0)) = 5 + (9 + 2) = 16 According to Lemma 2, the OSR of q to a white, a black and a grey point starts with s1 followed by Q(s1; M 0) = (r1; t1).

We now strive to ¯nd the locus of all points in space whose OSR that follows a given sequence starts with a point p1 and hence all share a common OSR for that sequence. In Figure 1, for any white point si, there are points such as q whose optimal routes given the sequence (white; black; grey) start with si. Notice that the rest of their optimal route is the same (e.g., (r1; t1) for s1) and depends only on the location of point si and the given sequence (e.g., (black; grey)).

Theorem 1. Let M = (M1; M2; : : : ; Mm) be a given sequence and M 0 = sf x(M; 1). The locus of all points q with a common optimal sequenced route Q(q; M ) which starts with p1 is inside p1's cell in the AW-Voronoi diagram of the set of points in UM1 where the weight of each point p is w(p) = L(p; Q(p; M 0)). Their common optimal route is Q(q; M ) = p1 © Q(p1; M 0).

Proof. Let the set S = UM1 and w(p) = L(p; Q(p; M 0)). According to the de¯nition of the AW-Voronoi cell of p1 given by Equation 4, for the point q inside this cell we get 8p01 2 UM1 ; p01 6= p1 D(q; p1)+L(p1; Q(p1; M 0)) < D(q; p01)+L(p01; Q(p01; M 0)) Therefore, according to Lemma 2 the optimal route Q(q; M ) is p1 © Q(p1; M 0) which clearly starts with p1, the generator of the Voronoi cell including q.

Given a sequence M , we refer to the AW-Voronoi diagram of the points p in UM1 using the weights w(p) = L(p; Q(p; M 0)) where M 0 = sf x(M; 1), as the

OSR-Voronoi diagram of the sequence M . Fig

ure 5a illustrates the OSR-Voronoi diagram of sequence (white; black; grey) (i.e., M = (2; 1; 3)). The distance function D(:; :) is Manhattan distance and each white point si is labeled with its weight (i.e., L(si; Q(si; (1; 3))). The OSR-Voronoi diagram has some interesting properties whose proofs are omitted due to lack of space: Property OSRV-1 All points in the OSR-Voronoi diagram of the sequence M (any p 2 UM1 ) have positive weights.

Property OSRV-2 Given the sequence M , if for the points p and p0 2 UM1 we have Q(p; M 0) = Q(p0; M 0) = (p2; : : : ; pm) and D(p; p2) = D(p; p0) + D(p0; p2) where M 0 = sf x(M; 1), then p is a trivial point in OSR-Voronoi diagram of sequence M . That is, the Voronoi cell of p is empty and no OSR that follows M starts with p. 4

OSR Query Processing using Voronoi Diagrams OSR

In this section, we describe our OSR query processing approach that utilizes OSR-Voronoi diagrams de¯ned in Section 3. Assume that we have already built the OSR-Voronoi diagram of a given sequence M . The user asks for the OSR Q(q; M ) given a starting point q. Subsequently, we locate the Voronoi cell which contains q in the OSR-Voronoi diagram of M . According to Theorem 1, the OSR of q starts with the generator of this cell (e.g., s1 in Figure 5a). This point is then followed by the result of another OSR query (i.e., Q(s1; M 0)). If we already knew the answer to this second query, we immediately report user's desired route as s1 © Q(s1; M 0). Now the problem is that the we need the OSR-Voronoi diagram of sequence M 0 to answer the second OSR query. Repeating the same reasoning for M 0 veri¯es that we will require the OSR-Voronoi diagrams of all su±xes of the original sequence M . That is, to ¯nd the OSR which follows M = (M1; : : : ; Mm) we need the OSR-Voronoi diagrams of all sequences (Mi; : : : ; Mm) for all 1 · i · m. We refer to these diagrams as the OSR-Voronoi family of M . For instance, to answer queries with sequence (white; black; grey) in

Query Processing

Here, we assume that we have already built the OSRVoronoi family of a given sequence M . Subsequently, we employ this set of diagrams to answer the OSR query Q(q; M ). Section 4.2 shows how we recursively build all these diagrams.

We describe our query processing approach using the example of Figure 1. Notice that here the sequence is (white; black; grey) and the distance function D(:; :) is Manhattan distance. We have already built and loaded the OSR-Voronoi diagrams of sequences (white; black; grey), (black; grey), and (grey) illustrated in Figures 5a, 5b, and 5c, respectively. Notice that the last diagram is the standard Voronoi diagram on grey points as the OSR of a point q which follows the sequence (grey) is simply the closest grey point to q (see Lemma 1 for i = m ¡ 1). First, we locate the cell containing q in the OSR-Voronoi diagram of (white; black; grey). Following Theorem 1, our OSR starts with s1, the generator of this cell (see Figure 5a). The rest of the OSR is the same as the OSR of s1 which follows (black; grey). Hence, we next ¯nd r1, the generator of the cell containing s1 in the OSR-Voronoi diagram of (black; grey) shown in Figure 5b. Finally, we ¯nd the closest grey point to r1 as the generator of the cell containing r1 in the OSR-Voronoi diagram of (grey) (see Figure 5c). The OSR of point q which follows sequence (white; black; grey) is (s1; r1; t1) built using the three subsequently retrieved points. Figure 6 shows the pseudo-code of our OSR query processing approach as a recursive function ComputeOSR(point, sequence). 4.2

Data Structures

The OSR-Voronoi diagrams are instances of AWVoronoi diagrams whose weights are constrained by geometry. Therefore, we build them using any algorithm for building AW-Voronoi diagrams. The algorithm proposed by Karavelas and Yvinec [ 4 ] computes the diagram of n points in O(n log n) steps. Our approach utilizes the OSR-Voronoi diagrams of all su±xes of a sequence M to ¯nd the OSRs that follow M . Therefore, to answer queries with sequence (white; black; grey) in Figure 1, we require the OSR-Voronoi diagrams of this sequence together with those of sequences (black; grey) and (grey). In general, for a given sequence M , we require jM j OSR-Voronoi diagrams of all su±xes of M to answer Q(q; M ). Hence, the pre-computation phase takes O(PjiM=1j jUMi j log jUMi j) computation steps.

We incrementally build the OSR-Voronoi family of (white; black; grey) as follows. First, we build the OSRVoronoi diagram of (grey) shown in Figure 5c which is simply the standard Voronoi diagram of the set of grey points T = ft1; t2; t3g with respect to Manhattan distance [ 6 ]. Second, for each black point ri we ¯nd the generator grey point of the cell containing ri in this OSR-Voronoi diagram. In Figure 5c, each black point is connected to its corresponding grey generator by a solid line. We assign the distance between the point ri and its corresponding grey point to the weight of ri. For instance, we assign w(r1) = 2. Third, we build the OSR-Voronoi diagram of (black; grey) using the set of black points R = fr1; r2; r3g and their weights (see Figure 5b). Similar to the previous step, for each white point si we locate rx, the generator of the cell which contains si in the diagram built in this step and assign D(si; rx) + w(rx) to the weight of si. For example, the weight of s1 is 7 + 2 = 9. Finally, we build the OSRVoronoi diagram of (white; black; grey) using the set of white points S = fs1; s2; s3; s4g with respect to their corresponding weights (see Figure 5a). Figure 7 shows the pseudo-code of the above algorithm.

Once we computed the OSR-Voronoi family of a sequence, we require to store the boundaries of the Voronoi cells corresponding to each OSR-Voronoi diagram of the family. However, with Euclidean distance, these boundaries consist of curved edges and hence cannot be stored as simple polygons. This problem can be Function BuildOSRVoronois(sequence M = (M1; : : : ; Mm))

Returns OSR-Voronoi diagrams 1. OSRV ((Mm)) = the standard Voronoi diagram of UMm 2. for each p in UMm 3. w(p) = 0 4. i = m ¡ 1 5. while i > 0 do f 6. M0 = sfx(M; i) 7. for each p in UMi f 8. V (p0) = the cell containing p in the OSRV (M0) 9. p0 = the generator of V (p0) 10. w(p) = D(p; p0) + w(p0) 11. 12.

g OSRV (sfx(M; i ¡ 1)) = the AW-Voronoi diagram of UMi i = i ¡ 1 13. rgeturn OSRV 's solved in the two following ways. Each solution guarantees that given a starting point q, we can easily determine the cell containing q.

1. The cells are approximated by convex polygons and consequently these polygons are stored. The polygons are also indexed by a spatial index structure such as R-tree. Therefore, the cell containing the starting point q is easily retrieved by a spatial contains() query. This solution introduces an error in OSR query processing proportional to the approximation error. 2. Instead of storing the cells, the neighborhood graph of the cell generators is stored (similar to Delaunay graph for the general Voronoi diagrams [ 6 ]). Vertices of the graph are the generators of the OSRVoronoi diagram of M . There is a graph edge connecting p and p0 i® V (p) and V (p0) have common boundaries. Now, to determine the inclusion of a starting point q in a cell, we start traversing the graph from any vertex p. We iteratively visit the vertex p0, the neighbor of the current vertex p which minimizes D(q; p0) + w(p0) among p's neighbors and p itself. When no such a vertex is found, q is inside the Voronoi cell of the current vertex p. 5

Performance Evaluation

We conducted several experiments to evaluate the performance of our proposed approach. We compared the query response time of our Voronoi-based approach (denoted by OSRV) with that of our R-LORD algorithm proposed in [ 8 ]. We also evaluated our new OSRV approach with respect to its overall time required to build the OSR-Voronoi family of a given query. We evaluated OSRV by investigating the e®ect of the following two parameters on its performance: 1) size of sequence M in Q(q; M ) (i.e., number of points in the optimal route), and 2) cardinality of the datasets (i.e., Pn i=1 jUij).

We used a real-world dataset which is obtained from the U.S. Geological Survey (USGS) and consists of 950; 000 locations of di®erent businesses (e.g., schools) in the entire country. Table 2 shows the characteristics of this dataset. In our experiments, we randomly selected sets of 40K, 70K, 250K and 500K, and 950K Points Hospital Summit Church Populated place points from this dataset. We used CGAL's implementation of [ 4 ] to implement the OSR-Voronoi diagrams 1. We ran 1000 OSR queries from random starting points on a DELL Precision 470 with Xeon 3.2 GHz processor and 3GB of RAM.

In the ¯rst set of experiments, we study the performance of OSRV in terms of query time. Figure 8a shows the query response time for our OSRV and R-LORD approaches when the number of points in optimal route (i.e., jM j) varies from 3 to 12. All the required diagrams ¯t in main memory, so the reported time represents CPU time. While the ¯gure depicts the experimental results on 250K USGS dataset, the trend is the same with those of our other datasets with di®erent cardinalities. Figure shows that OSRV always outperforms R-LORD. As expected, R-LORD performs slower with the bigger sequences as it requires more range queries on the R-tree. In contrast, OSR query with OSRV has almost no cost in time. OSRV's response time is unnoticeably increasing as OSRV consists of a sequence of only jM j point locations on our e±cient AW-Voronoi diagrams.

Figure 8b illustrates the result of our second set of experiments on the impact of the cardinality of the dataset on the e±ciency of OSRV. We varied the cardinality of our real datasets from 40K to 950K and ran OSR queries of sequence size jM j = 6. Figure 8b shows that OSRV's performance is not much a®ected by the dataset size and veri¯es the scalability of OSRV. This is while the processing time of R-LORD moderately increases for larger datasets. For example, R-LORD's query response time is 0:09 seconds for 40; 000 points, and it increases by a factor of 16 when the number of points increases to 950; 000 by a factor of 24. Consequently, OSRV is the superior approach although RLORD also exhibits a reasonable performance for large datasets.

The last experiment aims to measure the time required to build the diagrams in the OSR-Voronoi family of a given sequence. Note that this is a batch process which is performed o®-line. Figure 8c illustrates the average build time for di®erent sizes of the sequence M for 250K dataset. Moreover, Figure 8d depicts the result of the same experiment for di®erent dataset cardinalities when the sequence size is 6. Figure 8c shows that it takes only 9 minutes to build 12 OSR-Voronoi diagrams needed for the OSR query of a sequence of size 12. However, Figure 8d shows that despite its excellent performance for small datasets, OSRV's procedure for building the OSR-Voronoi family of a sequence of size 6 takes about 36 minutes for the 950K dataset. This is still a reasonable performance for an o®-line process.

R-LORD OSRV

R-LORD

OSRV We believe that upgrading main-memory AW-Voronoi diagrams to their secondary-memory versions will signi¯cantly improve OSRV's o®-line performance for large datasets. 6

Related Work

In an independent research, Li et al. [ 5 ] studied Trip Planning Queries (TPQ), a class of queries similar to our OSR query. With a TPQ, the user speci¯es a subset (not a sequence) of location types R and asks for the optimal route from her starting location to a speci¯ed destination which passes through at least one database point of each type in R. In particular, TPQ eliminates the sequence order of OSR to de¯ne a new query. Consequently, ¯nding accurate solutions to TPQ becomes NP-hard as the size of candidate space significantly grows. The paper proposes several approximation methods to provide near-optimal answers to TPQs. In theory, OSR algorithms are able to address address TPQ queries. This can be done by running any OSR algorithm jRj! times, each time using a permutation of point types in R as the sequence M and returning the optimal route among all the resulted routes. This exponentially complex solution is ine±cient in practice. The approximation algorithms of [ 5 ] are designed to handle the exponential growth of the problem's search space.

Terrovitis et al. [ 9 ] addressed k-stops shortest path problem for spatial databases. The problem seeks for the optimal path from a starting location to a given destination which passes through exactly k intermediate points of the location database. The k-stops problem is a specialized case of OSR queries. To be speci¯c, OSR reduces a k-stops problem to query Q(q; M ) where q is the starting location, M = (1; : : : ; 1), jM j = k, and U1 is the single given point set representing the location database. The destination is considered by the variation of the above OSR query described in Section 2.1. A major drawback is that [ 9 ] only considers Euclidean space. 7

Conclusions and Future work

We studied the problem space of the OSR query in vector spaces. We exploited the geometric properties of the solution space and identi¯ed the AW-Voronoi diagrams as its corresponding geometric representation. In particular, we proved that given a sequence M the locus of all points with a common optimal sequenced route R is the cell of the ¯rst point of R in a AWVoronoi diagram whose weights depend on the sequence M . Based on our theoretical ¯ndings, we proposed a novel OSR query processing approach using a family of pre-computed AW-Voronoi diagrams. Through experiments with a real-world dataset, we showed that our approach signi¯cantly outperforms the previous solutions to OSR query in terms of response time.

While in this paper we adapted AW-Voronoi diagrams for OSR queries, we believe that these diagrams can also be used to answer a variation of OSR query where the sequence is not important (TPQ problem [ 5 ]). An orthogonal problem is studying e±cient algorithms to store the AW-Voronoi diagrams in secondary storage.

References

[1] Y. Du , D. Zhang , and T. Xia . The Optimal-Location Query . In Proceedings of SSTD'05 , pages 163 { 180 , 2005 .

[2] C. du Mouza , P. Rigaux , and M. Scholl . E± cient Evaluation of parameterized pattern queries . In Proceedings of CIKM'05 , pages 728 { 735 . ACM, 2005 .

[3] M. Hadjieleftheriou , G. Kollios, P. Bakalov , and V. J. Tsotras . Complex Spatio-Temporal Pattern Queries . In Proceedings of VLDB'05 , pages 877 { 888 , 2005 .

[4] M. I. Karavelas and M. Yvinec . Dynamic Additively Weighted Voronoi Diagrams in 2d . In Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02) , pages 586 { 598 , London, UK, 2002 . SpringerVerlag.

[5] F. Li , D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng . On Trip Planning Queries in Spatial Databases . In Proceedings of SSTD'05 , pages 273 { 290 . Springer, August 2005 .

[6] A. Okabe , B. Boots , K. Sugihara , and S. N. Chiu . Spatial Tessellations, Concepts and Applications of Voronoi Diagrams . John Wiley and Sons Ltd., 2nd edition , 2000 .

[7] Y. Ostrovksy-Berman . Computing Transportation Voronoi Diagrams in Optimal Time . In Proceedings of the 21st European Workshop on Computational Geometry (EWCG'05) , pages 159 { 162 , 2005 .

[8] M. Sharifzadeh , M. Kolahdouzan , and C. Shahabi . The Optimal Sequenced Route. The VLDB Journal , 2006 . To appear.

[9] M. Terrovitis , S. Bakiras , D. Papadias , and K. Mouratidis . Constrained Shortest Path Computation . In Proceedings of SSTD'05 , pages 181 { 199 . Springer, August 2005 .