日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

Engineering Shortest Regular Category-Path Queries
Le-Duc Tung, Kento Emoto, Zhenjiang Hu

A Shortest Regular Category-Path (SRCP) query is a variant of constrained shortest path queries, in which a candidate pathof minimum total length has to visit a number of typed locations in a specific way according to a regular expression over thetypes of locations such as banks, convenience stores, police stations, etc. Types of locations are referred to as categories. This
problem is important for flexible routing in road networks. In this paper, we first show that this problem can be solved by asequence of Single Source Shortest Path (SSSP) searches; as a result, any fast SSSP algorithm can be applied to speed up its
computation. Next, we progressively engineer an efficient solution that optimizes the sequence of SSSP searches. Finally, we
do some experiments on the full American road network (with over 20 million vertices and nearly 60 million edges), which
has shown that our solution is practical and scalable for large, real-world road networks.

of thousands of locations, which makes the problem dif-

1 Introduction

ficult to solve efficiently.

In road networks, locations usually belong to one or

Much research in recent years has focused on propos-

more specific categories such as bank, clothing store,

ing queries to express some practical problems related to

shopping mall, etc. Finding shortest paths based on thesecategories. Li et al. [5] introduced Trip Planning Queries

categories is very useful and practical. For example,

to find the shortest path going from a starting location,

when working hour is up, on the way back home we wantpassing through at least one location from each category

to buy some clothes, but we need to withdraw money inin a user-specified set of categories and ending at a desti-

advance. Hence, we should find the shortest path fromnation category. Rice et al. [8] proposed an exact solution

the office (o) to the home (h), visiting a Bank (B) fol-for the same problem with one destination location andlowed by a Clothing store (C), or a Shopping mall (S).

called it Generalized Traveling Salesman Path problem.

This query is reasonable because in reality there must be

In parallel to Li’s work, Sharifzadeh et al. [11] addressed

an ATM and a clothing store in a shopping mall. Figure 1

a query called Optimal Sequenced Route query in whichshows an example of a network with three categories anda total order over all categories is specified. Rice et al. [9]one of the shortest paths satisfying the above query. In

considered a Generalized Shortest Path query that is sim-

real-life datasets, one category consists of up to hundreds

ilar to the Optimal Sequenced Route query but with one

Le-Duc Tung, 総合研究大学院大学（総研大), Dept. of Informatics, The Graduate University for Advanced Studies(SOKENDAI).
Kento Emoto, 九 州 工 業 大 学, Dept. of Artificial Intelligence, Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology.
Zhenjiang Hu, 国立情報学研究所, Programming ResearchLaboratory, Information Systems Architecture Research Division, National Institute of Informatics (NII).

destination location. Recently, Li et al. [6] proposed another query that allows partial order constraints between
different categories, e.g., a gas station must be visited before a restaurant but other locations can be visited in anarbitrary order. Although there are many queries havebeen proposed, there is a lack of queries that can directly
express alternative routes such as the simple query shownin the first paragraph.

• We first introduce the SRCP query that covers

In this paper, we discuss a novel query called the Short-a class of existing queries such as trip planning

est Regular Category-Path (SRCP) Query. It is an ex-

queries, optimal sequenced route queries, optimal

tension of the Generalized Shortest Path Query [9] inroute queries with arbitrary order constraints, gen-which alternation operators “|” are added to express al-eralized traveling salesman path queries, and gener-

ternative routes in the query. This extension makes thealized shortest path queries.

query more powerful and flexible. The example in the• We then establish a dynamic programming formu-

first paragraph can be described in the SRCP query as alation for the SRCP query algorithm, which shows

triple “⟨o, h, BC | S⟩”. One naive solution is enumeratingthat the SRCP query can be answered by a series

all possible total order constraints in the query and eval-of single source shortest path searches. This is veryuating them independently. However, this naive solution

useful because we can utilize any fast single source

produces a significant amount of repeated computations,shortest path search (sequential or parallel search) toand is not practical for large datasets. Our approach isgain the best performance.

several orders of magnitude faster. In case of Trip Plan-• Finally we progressively engineer an efficient algo-ning Queries, our algorithm can produce an exact answer

rithm for answering the SRCP query by using two

and its time complexity is exponential in the number offorward and backward optimizations. Experimental

categories.

results showed that the algorithm is practical to real-

Barrett et al. [1] introduced a formal-language-

life datasets.

constrained shortest path query, in which shortest paths

The rest of this paper is organized as follows. Sec-are constrained by a formal language describing require-tion 2 gives a formal definition of the Shortest Regularments on labels associated with the nodes/edges of theCategory-Path query. In Sect. 3 we introduce a basic so-graph. The SRCP query can be seen as a special class oflution based on dynamic programming and then engineer

this query, in which constraints are regular expressions

it to get an efficient algorithm for answering the SRCP

over categories of nodes. Barret’s algorithm computes aquery. The expressiveness of the SRCP query is also dis-

product graph of the original graph and a nondeterminis-

cussed in this section. A set of experiments with large

tic finite automaton constructed from the regular expres-datasets is showed in Sect. 4. Section 5 discusses somesion. One advantage of this approach is that we can eas-

related works and Sect. 6 concludes the paper.

ily reduce the problem to a point-to-point shortest pathsearch on the product graph. However, it becomes non-

2 SRCP Queries

trivial to apply speedup techniques (e.g Contraction Hi-

In this section, we formally give a definition for theerarchies [3]) to the point-to-point shortest path search

SRCP query and SRCP problem. At the end of the sec-

because the product graph is highly depended on user-tion, we briefly discuss a naive solution that enumerates

defined queries. Different to their approach, we reduce

all permutations and evaluate them seperately, which is is

the problem to a series of single source shortest pathinefficient in answering the SRCP query.

searches on the input graph and the underlying implementation of a single source shortest path search is in-

2. 1 Premininaries

dependent of our algorithm. Consequently, we can uti-

Definition 2.1. (Graph and Shortest Path) Let G =lize any fast algorithm for the single source shortest path

(V, E, w) be a weighted digraph, where V is the set ofsearch.

nodes in G, E ⊆ V × V is the set of edges in G, andOur contributions are summarized as follows.

w : E → R+ is a function mapping each edge in G to a

{Ci ⊆ V | 1 ≤ i ≤ k} be a set of categories of nodes in
BB

G, and R be an SRE over Ci s. An SRCP query is repre-hsented as a triple ⟨s, t, R⟩, where s, t ∈ V . s is called astarting node and t a target node.
Definition 2.5. (Satisfying path) A path Ps,tC=

⟨v1 , v2 , . . . , vk ⟩ from s to t is said to satisfy an SRE RoCSover a set of distinguished categories if the concatena-Btion of categories of these nodes spells out R. Such apath is denoted by Ps,R,t .

Figure 1

An example of a graph whose nodes belong to

one of the categories: Bank (B), Clothing store (C),Definition 2.6. (Shortest Regular Category-Path (SRCP))min
Given an SRCP query ⟨s, t, R⟩, an SRCP is a path Ps,R,t

Shopping mall (S). h denotes the home, o denotes the office.

satisfying R, and for every path Ps,R,t in G satisfying R,

The path shaded in grey is the shortest path satisfying the

we have:

SRCP query “⟨o, h, BC | S⟩”

mincost(Ps,R,t) ≤ cost(Ps,R,t ).
min
We refer cost(Ps,R,t) as dR (s, t).

positive, real-valued weight.
Let Ps,t = ⟨v1 , v2 , . . . , vq ⟩ be any path in G from

Definition 2.7. (SRCP problem) An SRCP problem is tofind an SRCP for a given SRCP query.

node s = v1 ∈ V to node t = vq ∈ V , such that,

Figure 2 shows an example SRCP query and paths sat-for 1 ≤ i < q, (vi , vi+1 ) ∈ E. Let cost(Ps,t ) =∑′1≤i<q w(vi , vi+1 ) be the cost of Ps,t . A path Ps,tisfying the query. The input graph has five categories

is called a shortest path from s to t if ∀Ps,t ∈ G, we

the same shape and color. Because of alternations in the′have cost(Ps,t)

minquery, it is possible to have many optimal paths Ps,R,t≤ cost(Ps,t ). The shortest path cost,

O, G, B, V, and Y. Nodes in the same category have′cost(Ps,t), is denoted by d (s, t).

that have the same optimal cost dR (s, t). Also note that

Definition 2.2. (Category) A category is a set of vertices

there is no requirement that two nodes in two different

in a graph.

categories must be directly connected. For example, theDefinition 2.3. (Simplified Regular Expression (SRE))

optimal path ⟨s, o1 , g1 , y1 , . . . , v1 , . . . , t⟩ spells out the

The syntax for SREs is:constraint “OGYV”, however the node y1 in Y connects to

R ::= ∗C ∗ | RR | R “|” R
Here C is a category, i.e., a terminal symbol. R1 | R2

the node v1 in V through two other nodes although Y andV are contiguous in the constraint.

denotes the alternation, matching either R1 or R2 . The

A naive approach for the SRCP problem is to gener-

expression R1 R2 denotes the concatenation. “ ∗” is theate all total order constraints Ri following the input SRE

combination of the wildcard (matching any terminal sym-R, then evaluate sub queries ⟨s, t, Ri ⟩ independently bybol) and the Kleene star, matching any sequence of pos-

efficient algorithms for total order constraints (e.g. al-sible categories. The concatenation binds more strongly

gorithms for optimal sequenced route [11] or general-than the alternation. For simplicity, we use “C” as anized shortest path [9]), and finally take the minimum costabbreviation of “ ∗C ∗”.

from results of each sub queries. This approach is easy
but contains many redundant computations between the

2. 2 SRCP Queries

evaluations of sub queries. In the next section we show

Definition 2.4. (Shortest Regular Category-Path (SRCP)

another approach to solve the problem and engineer an

Query) Given a weighted digraph G = (V, E, w), letefficient algorithm which is several orders of magnitute

y3
O

v2

v

g2

G

Figure 3

B
V

C
u

o2

b1

t

y1

g1

s

o1

Singleton graph GC

v1

Y
g3

y2

a sink.
gen dag R = let ⟨sc, GR , sk ⟩ = rec R in dag
where

Figure 2

rec C

An SRCP query example ⟨s, t, O (GY | B) V⟩. All= let d = newEdge(C)in ⟨source(d), d, target(d)⟩edges have the same weight of 1. Two of the optimalrec (R1 R2 )solutions are shaded in grey and pink. dR (s, t) = 9

faster than the naive one.

= (rec R1 ) ⊖ (rec R2 )rec (R1 |R2 )= (rec R1 ) : (rec R2 )⟨sc 1 , GR1 , sk 1 ⟩⊖ ⟨sc 2 , GR2 , sk 2 ⟩= ⟨sc 1 , seq(GR1 , GR2 ), sk 2 ⟩⟨sc 1 , GR1 , sk 1 ⟩3 Engineering an efficient SRCP algorithm
In this section, we first propose a dynamic programming solution to solve the SRCP problem. The solution
reduces the SRCP problem to a series of single source
shortest path searches. Next, we engineer an efficient algorithm by applying some optimizations on a graph representation of the SRCP query. Finally the expressiveness of the SRCP query is discussed.

: ⟨sc 2 , GR2 , sk 2 ⟩= ⟨sc 1 ⊙ sc 2 , merge(GR1 , GR2 ), sk 1 ⊙ sk 2 ⟩Given an SRE R, the recursive function rec computes
a triple ⟨sc, GR , sk ⟩ where sc and sk are the source andsink vertex in the constraint graph GR , respectively. For
the terminal case C, we create a singleton graph GC containing only one edge d labeled by the category C. The
source vertex of GC is the source vertex of d, and thesink vertex is the target vertex of d. Figure 3 shows anillustration of GC . The function seq is to construct a new

3. 1 Dynamic Programming Formulation
3. 1. 1 SRE as Directed Acyclic GraphFirst, we introduce a constraint graph GR that is a directed acyclic graph (DAG) representing the semantics ofSREs in SRCP queries. To avoid confusion with nodes in
the input graph G (road network), we use the term “vertex” to refer a node in GR . Vertices of GR are object
identifiers (OIDs) that are integers uniquely identifying
a vertex. A Skolem function ⊙ is used to create a fresh
OID by taking two input OIDs [10]. Edges of GR arelabeled by categories. The graph GR is constructed by arecursive function on the structures of SREs.
Given an SRE R, the following function gen dag generates a constraint graph GR for R. Note that, the generated graph is special in the sense that it has a source andconstraint graph by first replacing sk1 in GR1 and sc2
in GR2 by a new OID w = sk1 ⊙ sc2 , then unioning
these two constraint graphs. The function merge is toconstruct a new constraint graph by first replacing sc1 in
GR1 and sc2 in GR2 by a new oid sc12 = sc1 ⊙sc2 , andthen replacing sk1 in GR2 and sk2 in GR2 by a new OID
sk12 = sk1 ⊙ sk2 , finally unioning these two constraintgraphs.
To present the semantics of the whole query Q =⟨s, t, R⟩, we introduce a query graph that is createdfrom the constraint graph GR by attaching an in-comingedge labeled by {s} to the source vertex of GR , andan out-going edge labeled by {t} to the sink vertexof GR . Figure 4 shows a query graph of the query⟨s, t, O (GY | B) V⟩. Two sets {s} and {t} are called
dummy categories.

optimal cost of the SRCP of the query ⟨s, ci,j , Ri ⟩ where

3

0

{s}0

Figure 4

Y3

G2
1

O1

2

B4

4

V5

5

{t}6

Ri is the SRE corresponding to a subgraph of GR that
6

The query graph of the query ⟨s, t, O (GY | B) V⟩.

Superscripts of categories are equivalent row indices in the
DP table. Integers in vertices are OIDs. The subgraph from

includes all paths from the source vertex of GR to thesource vertex of the edge labeled Ci .
For example, consider the query ⟨s0 , t6 , O1 (G2 Y3 | B4 )V5 ⟩, the equivalent DAG is shown in Fig. 4. The value
X[3, 1] will represent the optimal cost of the SRCP of thethe vertex 1 to the vertex 5 is the constraint graphquery ⟨s, y1 , R3 ⟩ in which R3 = O1 G2 corresponding tocorresponding to the SRE O (GY | B) V

the subgraph having edges from the vertex 1 (the source
3. 1. 2 Dynamic Programming Formulation

vertex of GR ) to the vertex 3 (the source vertex of the

Next, we formalize a dynamic programming formu-edge Y3 ).

lation for the SRCP problem by using the query graph.
Given an SRCP query Q = ⟨s, t, R⟩, we establish a table X in order to store values during computation. Eachrow in the table corresponds to a category of an edgein the graph GQ . Therefore, the table X has |E(GQ )|rows, and g columns where g is the maximum number ofnodes of categories in the query. “X[i, j]” is the value
for the j-th node in the category at the row i. For simplicity, we add superscripts to categories in the query
to denote their row indices in the table. For example,
with the user-defined query ⟨s, t, O (GY | B) V⟩, we have⟨s0 , t6 , O1 (G2 Y3 | B4 ) V5 ⟩.
The table X is computed according to a topologicalsort of the query graph GQ as follows. For each vertex u
in the topological sort, we generate a computation step,
inu → outu , whereinu= {ri|(v, u) ∈ E(QG ), C ri = l(v, u)}

Proof. We prove this by induction on the sequence ofcomputation steps 1 ≤ k ≤ N , in which N is the number of computation steps (the number of vertices in GR ).
For the base case, where k = 1, then this claim istrivially true, because X[0, 1] is the optimal cost for thequery ⟨s, c0,1 , R0 ⟩ = ⟨s, s, {s}⟩ which has dR (s, s) =0.
For the induction step, k > 1. Let u be the vertex
in GR that generates the k-th computation step. Fora set of vertices Vu that are before the vertex u in the
topological sort of GR , let Eu be a set of edges related to vertices in Vu , and ps be a set of row indicesof categories on the edges in Eu . Our induction hypothesis assumes that this claim holds true for all values
X[i, •], i ∈ ps. Let consider the (k + 1)-th computation
step generated by the vertex v in GR , that is inv → outv ,in which inv and outv is the set of row indices of all

outu = {ro|(u, w) ∈ E(QG ), C ro = l(u, w)},
computing values of the rows in the list outu by using

in-coming and out-going edges of the vertex v, respec-

values in the rows in the list inu , in which l(u, v) istively. It is clear that inv ⊆ ps. Since each ci,j is aa function to get a label of the edge (u, v). Computa-

member of category C i , i ∈ outv , j = 0 . . . |C i |, it suf-

tion steps form a dynamic programing formulation forfices to find the shortest path cost from nodes in cate-

the SRCP problem. Following is the computing formula-gories C r , r ∈ inv to ci,j . It follows from our induc-tion of the computation step inu → outu . ∀i ∈ outu ,tion hypothesis that the value of X[i, j] is computed by

if i = 0 then X[i, j] = 0. If i > 0, X[i, j] =min { min r {X[r, l] + d (cr,l , ci,j )}}, where, C is
r

r∈inu

0≤l<|C |the category corresponding to the r-th row in the DP table, ci,j is the j-th node in the category C i .
Lemma 3.1. Value X[i, j] in the DP table represents themin { min r {X[r, l] + d (cr,l , ci,j )}}.

r∈inv

0≤l<|C |Corollary 3.2. Let m be the row index of the dummy category of t. Value X[m, 0] represents the cost of SRCP of
the query ⟨s, t, R⟩.
Figure 5 shows a table contained costs during the com-putation of the query ⟨s0 , t6 , O1 (G2 Y3 | B4 ) V5 ⟩. The

0order of computation steps is as follows.
1st step:[0] → [1][1]

→ [2, 4]

3rd step:

[2]

→ [3]

4th step:[3, 4]→ [5]2nd step:1

5th step:[5] → [6]The optimal cost dR (s, t) = 9 of the query is stored at

0

O

1

2

G

2

3

6

Y

3

7

4

B

6

V

6

{t}

9

3
4

the last row (index = 6) of the table.

45

3. 1. 3 Single Source Shortest Path (SSSP) search

2

{s}

2
2

1

7

A computation step “xs → ys” is to compute values
in rows in the list ys by using rows in xs. Let Uxs be aunion of categories corresponding to rows in xs and Uys
be a union of categories corresponding to rows in ys, thenthe step “xs → ys” is equivalent to computing values forthe nodes in category Uys from values of the nodes in cat-

Figure 5

A table of shortest path costs for the query in

Fig. 2. The first column contains names of categories. The
first row contains indices of nodes in a category. Each row
contains shortest path costs from s to a node in a category
via some previous categories. Curve arrows on the left
indicate computation steps and its orders.

egory Uxs . This can be done by using a many-to-many
shortest path search from the nodes in Uxs to the nodes

SSSP algorithm to implement, such as Contraction Hier-in Uys . However, such a many-to-many search leads toarchies technique [3] [9], Delta-Stepping [7], PHASE [2],many redundant computations due to repeatedly visiting

etc. This is useful because we can apply different effi-

the input graph. By creating a super-node s′ and edges
from s′ to the nodes u in Uxs with weights being values

cient fast SSSP algorithms for different kinds of graphs(road networks, social networks, etc.)

of u in the table [9], we can efficiently compute values

Optimization is trying to reduce the number of ver-for the nodes in Uys by using a single shortest path searchtices N in the constraint graph GR , because this willfrom s′ until all nodes in Uys are settled (Assume that we

reduce the number of computation steps in the algo-use Dijkstra algorithm).

rithm.

Theorem 3.3. Given a weighted digraph G = (V, E, w)

For example, two queries ⟨s, t, (OGYV | OBV)⟩ andFirst, N depends on the user-defined query.

and an SRCP query Q = ⟨s, t, R⟩. Let GR = (VR , ER )⟨s, t, O (GY | B) V⟩ have the same meaning, but the for-be a constraint graph of R and Tsssp be the complexity

mer needs 6 computation steps and the latter needsof a single source shortest path search, the cost of our

only 5. Second, consider the Trip Planning Query thatalgorithm is O(|VR |Tsssp ), and the space complexity ofis to find the shortest path going through at least one

the algorithm is O(|ER |).

point in each category of a given set of categories C =Corollary 3.4. Given a weighted digraph G=(V, E, w) and an SRCP query Q = ⟨s, t, R⟩. Let{C1 , C2 , . . . , Ck }. It can be presented in SRCP query as⟨s, t, R1 | R2 | . . . | Rk! ⟩ where Ri s are permutations of

GR = (VR , ER ) be a constraint graph of R. When a Di-

the set C, i = 1 . . . k!. In this case, N will be (k + 1)k!

jkstra algorithm with a Fibonacci heap is used for SSSP

which is not practical even for small k (e.g. k = 5. See

searches, our algorithm answers Q in the time complexityof O(|VR |(|E| + |V |log|V |)).
One advantage of this approach is that it is independent of the underlying SSSP search. We can use any fast

Sect. 4 for more discussion). The next section will discuss how to engineer an efficient algorithm for answering
the SRCP query.

3. 2 Optimizing the Query Structurea single source vertex and a single sink vertex. It starts

Optimization is to reduce the size of the query graphfrom the source vertex of GQ , considers vertices com-

GQ . In particular, there are two measures for the size ofing from a common vertex and the same edges, groups

the query graph: the number of vertices and the number

them to create a new vertex in a deterministic query graphof edges. The number of vertices affects the time com-

DGQ , and ends as reaching the sink vertex. We call thisplexity and the number of edges affects the space com-

process is a forward optimization.

plexity which is the size of the dynamic programming

Algorithm 1 describes the forward optimization. The

table. Here, we focus on the problem of optimizing theidea is scanning the query graph GQ from its source ver-time complexity, therefore the problem can be definedtex to its sink vertex, and grouping vertices that comeas finding a graph with the minimum number of vertices

from the same vertex with the same categories. A vertex

that generates exactly the same total order constraints asin the deterministic query graph DGQ is correspondent

a given query graph.

to a set of vertices in GQ . Initially, the graph DGQ con-

The query graph is a subclass of non-deterministic fi-

tains only the source vertex of GQ . For each vertex nx innite state automatons (NFA) [4]. It is well known thatthe DGQ and each categories c, we find a set of vertices

NFA minimization is computationally hard, and cannot

ny in GQ that can be reached from a vertex in nx (seein general be solved in polynomial time. There exists

the line 6 in Alg. 1). If ny is not existing in DGQ , thena well-known algorithm for minimizing NFAs [4]. The

we have to add it to DGQ before adding an edge fromalgorithm computes a minimal equivalent deterministic

nx to ny with the label c to DGQ . The vertex ny will

finite automaton (DFA) with respect to the number ofbe added to a set next for the next loop. The problem isvertices. It consists of two steps: determinization andhow to store the sets of vertices in DGQ in an efficient

minimization. The determinization step is to compute a

way which supports “looking” and “comparison”. HereDFA from an NFA, then the DFA is minimized to get a

we use a hash-table, and sets are sorted before inserting

minimal DFA.

to the hash-table.

Ström [13] has proposed two simplified algorithms for

Figure 9 describes an example of the forward optimiza-

the two steps determinization and minimization in thetion for the query ⟨s, t, C1 C4 C6 C9 | C1 C4 C7 C9 | C1 C5 C7case of word graphs which represent a set of hypothe-

C9 | C2 C8 C9 | C3 C8 C9 ⟩. We start from the vertex 0, at thisses in speed recognition system. A word graph is a DAG

time, the graph DGQ contains only one vertex createdwith exactly one source vertex and one sink vertex. In

from the vertex 0. Because there is only one edge fromthis section we applied these algorithms to optimize thethe vertex 0, therefore a new vertex in DGQ contains

query graph which has a similar structure to word graphs.

only the vertex 1. In the next step, since there are 3 out-

3. 2. 1 Forward optimization (determinization)

going edges of the same category C1 from the vertex 1 in

A deterministic finite state automaton (DFA) has a

the graph GQ , we can group target vertices into one set

property that, given a sequence of categories, there is{2, 3, 4} and create a new vertex in DGQ . Two vertices

at most one path in the DFA that generates it. The key

7 and 8 in G are also coming from vertices in the sameto the determinization algorithm is to identify the corre-set {2, 3, 4} with the same categories C4 , thus we also

spondences between a set of vertices in the original graphgroup them to create a new vertex in DGQ , This proce-and a vertex in its DFA graph. This leads to an exponen-

dure is performed until reaching the sink vertex of GQ .

N

tial computation because there are 2 sets of vertices in a

Note that vertex ids in the graph DGQ are different withgraph of N vertices. However, the algorithm can be sim-those in the graph GQ .

plified in the case of the query graph that is a DAG with

C4
2

0

3

C1

9

C5

1

10

C7

4

11

C9
C9
C9

12

C8

C2

Algorithm 1: Determinization(GQ , DGQ )input: A query graph GQ

8

C7

C4

C1
C1
s

C6
7

5

15

t

16

: A deterministic query graph DGQ

invariant: l(u, v) returns a label of the edge(u, v)

C9

13

C3

C9

/* scG is the source vertex of GQ

C86

output14*/
Figure 6

The query graph of the query⟨s, t, C1 C4 C6 C9 | C1 C4 C7 C9 | C1 C5 C7 C9 | C2 C8 C9 | C3 C8 C9 ⟩
C4

C6

2

C4

C1
C1
0

s

C7

3

C1

9

C5

1

10

C7

4

C2

8

7

11

C9
C9
C9

12

C8
5

15

13

16

foreach nx ∈ next do
foreach category C ∈ GQ dony ← {v | (u, v) ∈ E(GQ ), u ∈ nx ,

6

C7
5

8

C4
C5
2

7

if ny .empty then8

continue;

C7
6

C8
3

10

if ny ∈/ V (DGQ ) then
add ny to V (DGQ );

11

C9
C9

add ny to next;

12

C9
9

C3

else

9
10

C6

C2

next ← {};

4

14

7

C1

3

l(u, v) == C};

Vertices need to be grouped1

while !(next.empty) do

5

t

C8

s

2

C9
6

0

n0 ← {scGQ }; next ← n0 ;C9

C3

Figure 7

1

12

t

13

13

end

14

add (nx , ny ) with label C to

C9
C9

C8
4

E(DGQ );

11

end

15

Figure 8

The deterministic query graph (vertices havebeen re-indexing)
Figure 9

end

16
17

end

18

next ← next;

Forward optimization.
19end

3. 2. 2 Backward optimization (minimization)
This optimization is applied to the deterministic graphactly the same sequence of categories.

that is the result from the forward optimization. If mul-

Algorithm 2 shows the implementation of our back-tiple vertices go to the same vertex with the same set ofward optimization. We initialize the minimal determin-

categories, then we can group them into one vertex. Be-

istic query graph M DGQ with the sink vertex in the in-cause the deterministic query graph is a DAG in which

put deterministic query graph DGQ . Then we scan theedges go from the source vertex towards the sink vertex,

graph DGQ from the sink vertex back to the source ver-we will process vertex from the sink vertex util reachingtex to add new equivalent vertices to the graph M DGQ .

the source vertex. We call this process backward opti-

For each pair of vertices, what we need to compare is the

mization. This process is the same as minimizing a DFA

categories on the out-going edges and the vertices that

because it merges any pair of vertices that generate ex-they go to (see lines 11-20 in Alg. 2). For each vertex,

7

Algorithm 2: Minimization(DGQ , M DGQ )input: A deterministic query graph DGQ

C6
C7
5

8

C4
0

s

C1

C5

1

C7

2

C2

6

C9
C9
C9

9

C8
3

12

t

graph M DGQ

C9

10

C3

: A minimal deterministic query

output13: l(u, v) returns a label of the edge

invariant

C9C8
4(u, v)

11/* skDGQ is the sink vertex of DGQ
Figure 10

Step 1, 2, 3

*/

7

C6
C7
5

C9

C4
0

s

C1

C5

1

C7

2

C2

C9

8

6

C9
9

C8
3

12

t

13

C9

10

C3

C9
C8
4

1

n0 ← {skDGQ }; next ← n0 ;2while !(next.empty) do

3next ← {};4nu ← {};

5foreach ny ∈ next do

6

foreach u ∈ ny do

11

Figure 11

ρ(u) ← {⟨C, ny ⟩ | (u, v) ∈ E(DGQ ),7

Step 4v ∈ ny , C ← l(u, v)};

7

C6
C7
5

0

s

C1

C5

1

C7

2

C2

6

C9
C9

C8

12

t

13

C9

10

C3

Step 5, 6, 7
4

0

C1
1

C4

C7C6

C5

C7
5
C8

2

C2

end

11

foreach u ∈ nu do

12nx ← {v | v ∈ nu , ρ(v) == ρ(u)};13

if nx ∈/ V (M DGQ ) then11

Figure 12
s

10

C9
C8
4

end

9

C9
9

3

add u to nu ;

8
8

C4

C9
6

7

t

8

3

14

add nx to V (M DGQ );15

add nx to next;

16

end

17

foreachC3

Figure 13

C ∈ {l(u, v)|(u, v) ∈ DGQ , v ∈ ny } do

Minimal deterministic query graphadd (nx , ny ) with label C to18

E(M DGQ );Figure 14

Backward optimization

end

19

end

we maintain a set of tuples of out-going edge’s label and20

equivalent target vertex. If a group of vertices has the

21

end

same set of categories and for each category they flow to

22

next ← next;

the same vertex, then we merge them to create a new vertex in the graph M DGQ . Figure 14 describes a processcause the number of elements in each row is the numberof our backward optimization.

of nodes in the equivalent category, the size of the DP

3. 2. 3 Optimization of the DP table

table becomes large when the query contains a ”long”

The number of rows in the DP table in our solution is

total order constraints, leading to out-of-memory errors.

equal to the number of edges in the query graph GQ . Be-

Therefore we need to efficiently manage the DP table.

One solution is creating the DP table dynamically. As

egories (there is no specific order specified in the query).

discussed earlier, the DP table is constructed according

A TPQ/GTSPP query with a set of k categories is written

to a topological sort of the query graph of a query. Whenin our SRCP query as follows.

considering a node in that order, in-coming edges are⟨s, t, R1 | R2 | . . . | Rk! ⟩used to compute values for rows corresponding to out-

where Ri s (i = 1 . . . k!) are permutations of the set

going edges, and never used again. Thus, after each com-

C = {C1 , C2 , . . . , Ck }.

putation step, we need not store rows corresponding toin-coming edges.

3. 3. 4 Optimal Route Queries with Arbitrary Order Constraints
This query is to find the shortest path that starts from a

3. 3 Expressivenessstarting point and covers a user-specified set of categories

In this section, we will show how to use the SRCP

(e.g. {gas station, museum, park, restaurant}) [6]. How-

query to express some existing queries of total order con-ever, here the user can specify order constraints between

straints or partial order constraints.

some specific categories of the set, e.g. a gas station must

3. 3. 1 Generalized Shortest Path (GSP) Queries

be visited before a restaurant, while other categories canThis query is to find the shortest path from a starting

be visited in an arbitrary order. Such order constraints arepoint to a destination point, passing at least one point

expressed in a visit order graph, in which each vertex isfrom each of a set of specified categories in a specified

a category, an edge from a category Ci to a category Cjorder [9]. A GSP is expressed in our SRCP query as fol-denotes that Ci must be visited before Cj .
To express the optimal route queries with arbitrary or-lows.
⟨s, t, C1 C2 . . . Ck ⟩der constraints in our SRCP query, there are two things

where s and t are the starting point and destination point,need to be done. First, we need generate total order con-respectively.

straints from the visit order graph, then put them together

3. 3. 2 Optimal Sequenced Route (OSR) Queries

by using alternation operators in the SRCP query. A sim-

An OSR query is to find the shortest path starting fromple way to generate the total order constraints is first enu-

a given point and passing through a number of categories

merating all permutations of the set of categories, andin a particular order [11]. This query is different withthen filtering out permutations that do not satisfy con-the GSP query in the sense that the destination is not astraints in the visit order graph. Second, we need to cre-point but a category. To express this query in our SRCPate an artificial destination node t′ for the SRCP query,′

query, we create an artificial destination node t in thewhich is done by adding edges with the weight of 0 from

input graph, and add edges with the weight of 0 fromnodes in all categories in the set to t′ . The SRCP query is

nodes in the last category of the order constraints to t′ .

finally as the follows.

The SRCP query is then as follows.
⟨s, t’, C1 C2 . . . Ck ⟩3. 3. 3 Trip Planning Queries/Generalized Trav-⟨s, t’, R1 | R2 | . . . | Rl ⟩where Ri s (i = 1 . . . l) are total order constraints satisfying the visit order graph.

eling Salesman Path Problem Queries(TPQ/GTSPP)

4 Implementation and Evaluation

A trip planning query [5] or generalized traveling

We implemented a framework†1 to answer the SRCP

salesman path problem query [8] is to find the short-query. The overview of our framework is showed in theest path from a starting point to a destination point thatpasses through at least one point from each of a set of cat-

†1 http://www.prg.nii.ac.jp/members/tungld/srcp-July2014.tar.gz

User-defined Query

Graph

Full USA road network, having 23, 947, 347 nodes and58, 333, 344 edges.

We borrow the graph from the

SRCP Query System
ParserCSs Generation

Determinization

Minimization

CSs Execution

benchmarks of the 9th DIMACS implementation challenge †3 . It takes about 25 minutes to preprocess thegraph using CH technique.
The following programs are implemented and used in

Optimal Cost

our experiments to compare results of discussed algoFigure 15

The overview of our framework

rithms.
• gsp: the algorithm proposed by Rice [9] to answer

Fig. 15. The system takes an SRCP as input, parses it to

the Generalized Shortest Path Query that uses total

get a graph of the query, then optimizes the graph by twoorder constraints ⟨s, t, C1 C2 . . . Ck ⟩.

steps “determinization” and “minimization”. Next, the• perm: a naive algorithm to answer the SRCP query

system will generate a sequence of computation steps.

by evaluating sub-queries for all total order con-Each computation step is executed by a single source

straints, then taking the minimal cost from the sub

shortest path search. For simplicity, we just compute thequeries. Sub-queries are implemented by the gsp al-

optimal cost for the optimal path satisfying the query.

gorithm.

However, one can extract the optimal path by keeping
traces of computation steps.
For the implementation of a single source shortest path,
we used a fast algorithm proposed by Rice [9], which has• srcp-noopt: our solution for the SRCP query without optimization.
• srcp-opt: our solution for the SRCP query with optimization.

been engineering based on the speed-up technique called

Categories used in queries in this section will be gen-Contraction Hierarchies. Contraction Hierarchies (CH)erated randomly and they have an equal the number oftechnique currently is one of the fastest speed-up tech-nodes.

nique for shortest path problem. Its idea is preprocessing
a graph by adding shortcuts to the graph so that shortest

4. 2 Results

path costs are preserved. Shortcuts are then intensively

4. 2. 1 Trip Planning Queries/Generalized Trav-

used by a bidirectional Dijkstra algorithm to speed up theeling Salesman Path Problem Queries

shortest path search.

(TPQ/GTSPP)
We measure the performance of our solution for the

4. 1 Environment

trip planning queries which are expensive queries. The

All our experiments have done on a Macbook Pro ma-

Trip Planning Queries (TPQ) with k categories is writtenchine which has a 2.6 GHz Intel Core i5, 8 GB 1600
MHz DDR3 memory, clang-503.0.40 (based on LLVM

in SRCP as follows.
⟨s, t, R1 | R2 | . . . | Rk! ⟩3.4svn). Programs were compiled with optimization level

where Ri s are permutations of the set C

3. We used a library of contraction hierarchies written by
Robert Geisberger†2 in C++ to access to contraction hi-{C1 , C2 , . . . , Ck }, i = 1 . . . k!.

erarchies of a graph.

then change the size of categories. The naive solution

Experiments were performed with a graph of the=First, we fix the number of categories being 5, andthat generates all permutations of categories requires 720†3 9th DIMACS implementation challenge: shortest paths.
†2 http://algo2.iti.kit.edu/source/contraction-hierarchies-20090221.tgz 2006. http://www.dis.uniroma1.it/challenge9/.

Figure 16

TPQ/GTSP queries. Vary the size of categories,

Figure 18

Optimal Sequenced Route Queries/Generalized
Shortest Path Queries (g = 10, 000)

fix the number of categories (k = 5)

factorial time. This experiments show the important roleof optimizations in our solution.
It should also be noted that the performance of our solution is proportional to the number of computation steps.
Although different computation steps have different listsof “input” categories and different lists of“output” categories, they have quite similar performance.
4. 2. 2 Optimal Sequenced Route Queries/Generalized
Shortest Path Queries (OSR/GSP)
Figure 17

TPQ/GTSP queries. Vary the number ofcategories, fix the size of categories (g = 10, 000)

To see the performance of our algorithm when answering the query GSP, we compare it to the algorithm proposed by Rice [9]. As can be seen in the Fig. 18, two algorithms have the same performance when the number ofcomputation steps ((5 + 1) ∗ 5!). Without optimization,categories is changed. This is easy to understand because

our algorithm generates 482 computation steps which isfor this query our algorithm leads to the same dynamic

nearly half of that of the naive solution. By using op-

programing table as that of gsp algorithm. Moreover,timizations, the number of computation steps reduces tothere is no improvement on the structure of the query5

32 (2 ) that is more practical. Performance of algorithms

when applying optimizations, thus the overhead is veryis represented in the Fig. 16. It shows that our algorithm

small.

is quite scalable when the size of categories is increased.

4. 2. 3 Queries with multiple levels of options

Next, we will see the effect of the number of cate-

To see the impact of alternation operators ( | ) for agories on the performance of the query. We fix the size

given query on the performance of our optimal algorithm,of each category and change the number of categories in

we do experiments with queries which have different lev-the query. As indicated by Fig. 17, we see significant im-els of options. We fix the number of categories in a query.

provements in query times when the number of categories

Starting with a query without options, we insert one “ | ”

is increased. Although the naive solution can reduces theoperator to make it having one level, then insert a newnumber of computation steps twice, it is still following an

one “ | ” to make one more level, and so on. In particular,queries in which constraints are on a set of nodes in agraph instead of individual nodes/edges. There are manysolutions proposed to answer such queries. Each solution
is for a specific kind of constraints over categories.
Trip Planning Queries [5] is the query that has no ordered constraints. The existence of multiple choices per
category makes the problem difficult to solve. The complexity of the TPQ is NP-Hard. Several approximation
algorithms are proposed. These algorithms are based onnearest neighbor searches. A feasible path is formed by
Figure 19

iteratively visiting the nearest neighbor of the last nodes

Queries with multiple levels of options

added to the path from all nodes in the categories that(g = 10, 000)

have not been visited yet. The second one is the minimum
Q1

Q2

Q3

Q4

Q5

Q6

Q7

perm

9

10

11

12

13

14

15

srcp-opt

9

8

7

6

5

4

3

Table 1

The number of computation steps in each query

distance algorithm, a novel greedy algorithm, which results a much better approximation bound. The algorithmchooses a set of nodes, one node per one category in thequery. These nodes are chose so that the total distancefrom the start node to it and from it to the end node is thewe use the following queries.
Q1 = ⟨s, t, C1 C2 C3 C4 C5 C6 C7 C8 ⟩minimum among nodes in the same categories. The algorithm then create a path by following these nodes in near-

Q2 = ⟨s, t, C1 | C2 C3 C4 C5 C6 C7 C8 ⟩est neighbor order. Rice et al. [8] proposed an exact so-

Q3 = ⟨s, t, C1 | (C2 | C3 C4 C5 C6 C7 C8 )⟩lution for the Generalizes Traveling Salesman Path Prob-

Q4 = ⟨s, t, C1 | (C2 | (C3 | C4 C5 C6 C7 C8 ))⟩lem Query (GTSPP) that is similar to TPQ. The algorithm

Q5 = ⟨s, t, C1 | (C2 | (C3 | (C4 | C5 C6 C7 C8 )))⟩

is building a product graph of the original graph G =Q6 = ⟨s, t, C1 | (C2 | (C3 | (C4 | (C5 | C6 C7 C8 ))))⟩(V, E) and a covering graph built on the power set of

Q7 = ⟨s, t, C1 | (C2 | (C3 | (C4 | (C5 | (C6 | C7 C8 )))))⟩
Figure 19 shows the result. It is interesting that whenthe query’s categories. Finding the answer of the GTSPP

there are more options in the SRCP query, our algorithm
becomes faster. Looking the Table 1 that shows the number of computation steps for each query, we see that thereason of such good performance is due to the numberof computation steps is decreased, leading to a decreaseof the running time of our algorithm. Meanwhile, if we
use the perm algorithm, then the number of computation
steps will be increased because there are many redundant
computation steps generated.

5 Related Works
The category-constrained shortest path problem isa variant of regular-language-constrained shortest pathquery is finding the shortest path in the product graph.
The time complexity is 2k (|E| + |V |k + |V |log|V |), in
which k is the number of categories in the query. The
algorithm is then improved by incorporating the graphpreprocessing technique called Contraction Hierarchies,
resulting in the time complexity of O(2k (m′ + |V |k),in which m′ is the number of edges of the preprocessedgraph.
In parallel to Li et al.’s work [5], Sharifzadeh et al [11]proposed the optimal sequenced route query (OSR) thatis similar to TPQ but imposes a total order constraints
over categories. In other words, OSR query is to find theshortest path between two given nodes that visits at least
one node per each category in a specified order. They

proposed tow algorithms to operate on the Euclidean dis-search algorithm computes the optimal paths in reversetance. The first one is LORD, a light threshold-based iter-manner similar to R-LORD algorithm [11]. However, in-ative algorithm. First, LORD uses a greedy search to findstead of loading nodes belonging to the last category, thean threshold (upper-bound) for the cost of the optimal

backward search retrieves the set of candidate nodes that

path. The greedy search is a successive nearest neigh-may be part of the optimal path, which belong to any

bor search from the starting node to the last category.

categories contained in the visit order graph. The for-Then, the LORD finds the optimal path in the reverse

ward search is similar to a greedy algorithm. It also use

order, from the last category to the starting node. Dur-the backward search algorithm for backtracking process,ing the finding, it updates the threshold value and uses

eliminating some nodes that cannot be a part of the op-

it to prune nodes that cannot belong to the optimal path.

timal path. Both algorithms have the time complexity of

The second algorithm is R-LORD, an extension of theO(N 2 · 2k ), in which k is the number of categories in the

LORD, that uses R-tree to efficiently examine the thresh-

visit order graph and N is the total number of nodes inold values. However, both algorithms are impractical tothe data set (road network or spatial database).

road networks where nearest neighbor searches are very
expensive. Thus, another algorithm, progressive neigh-6 Conclusions and Future Worksbor exploration (PNE), has been proposed in the paper.

In this paper, we have introduced the SRCP query for

The idea of the PNE is incrementally create the set offinding the optimal path constrained by categories. The

candidate paths. At each step it needs two nearest neigh-query is very flexible to express several important prob-

bor searches: one is to expand the current best candidate

lems such as trip planning queries, optimal sequenced

path, the other is to refine that path by replacing the lastroute queries, and optimal route queries with arbitrary

node in the path by a new node.

order constraints. We have proposed a dynamic pro-

Sharifzadeh et al. [12] introduced a pre-processing ap-

gramming based solution to solve the problem. We haveproach for the OSR query by using additively weighted

shown that the problem can be solved by a sequence ofVoronoi diagrams. This approach is efficient and practi-

single source shortest path searches. This result is im-

cal compared with R-LORD algorithm, however, one of

portant because we can use any fast single source short-the disadvantages is that it is not flexible when requir-

est path search even with preprocessing to speed up theing fixed sequences among categories. Rice et al. ci-

query. By exploiting the DAG representation of a query,

teRice2013 proposed another approach using Contrac-

we can easily derive an efficient algorithm for answeringtion Hierarchies technique and dynamic programming for

the query.

the Generalized Shortest Path (GSP) query that is the

In the future, we will apply the latest parallel algo-same as the OSR query. Its advantage is that it can berithm for single source shortest path searches, which isapply for any possible set of node categories in a query.

called parallel hardware-accelerated shortest path trees

Our work is inspired by the idea of applying dynamic(PHASE) algorithm [2]. Another future work is to ex-

programming from Rice et al.’s work.

tend the query language so that it can express constraints

Being close to our SRCP query is the optimal routeon edges of the optimal path.

queries with arbitrary order constraints proposed by
Li et al. [6]. This query considers the partial order con-

Acknowledgment

straints over categories, which is described by a visit or-

The authors wish to thank Akimasa Morihata for fruit-

der graph. Two algorithms have been proposed namely

ful discussion of earlier work in this paper. We thankBackward search and Forward search. The backward

Kiminori Matsuzaki for suggesting the use of a directedacyclic graph in analyzing queries. Also, thanks are to
IPL and POPP members for their useful comments.

References[ 1 ] Barrett, C., Jacob, R., and Marathe, M.: FormalLanguage-Constrained Path Problems, SIAM J. Comput.,Vol. 30, No. 3(2000), pp. 809–837.
[ 2 ] Delling, D., Goldberg, A. V., Nowatzyk, A., and Werneck, R. F.: PHAST: Hardware-Accelerated Shortest Path
Trees, Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium, IPDPS ’11, 2011,
pp. 921–931.
[ 3 ] Geisberger, R., Sanders, P., Schultes, D., and Delling,
D.: Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, Proceedings of the 7th International Conference on Experimental Algorithms, WEA’08,
2008, pp. 319–333.
[ 4 ] Hopcroft, J. E. and Ullman, J. D.: Introduction To Automata Theory, Languages, And Computation, AddisonWesley Longman Publishing Co., Inc., Boston, MA, USA,
1st edition, 1990.
[ 5 ] Li, F., Cheng, D., Hadjieleftheriou, M., Kollios, G., andTeng, S.-H.: On Trip Planning Queries in Spatial Databases,
Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases, SSTD’05, 2005,
pp. 273–290.

[ 6 ] Li, J., Yang, Y., and Mamoulis, N.: Optimal RouteQueries with Arbitrary Order Constraints, IEEE Trans. on
Knowl. and Data Eng., Vol. 25, No. 5(2013), pp. 1097–
1110.
[ 7 ] Meyer, U. and Sanders, P.: Delta-Stepping: A Parallel
Single Source Shortest Path Algorithm, Proceedings of the
6th Annual European Symposium on Algorithms, ESA ’98,
1998, pp. 393–404.
[ 8 ] Rice, M. N. and Tsotras, V. J.: Exact Graph Search
Algorithms for Generalized Traveling Salesman Path Problems, Proceedings of the 11th International Conference on
Experimental Algorithms, SEA’12, 2012, pp. 344–355.
[ 9 ] Rice, M. N. and Tsotras, V. J.: Engineering Generalized
Shortest Path Queries, Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013),
ICDE ’13, 2013, pp. 949–960.
[10] Serge, A., Peter, B., and Suciu, D.: Data on the Web:
From Relations to Semistructured Data and XML, Morgan
Kaufmann Publishers, San Francisco, California, 2000.
[11] Sharifzadeh, M., Kolahdouzan, M., and Shahabi, C.:
The Optimal Sequenced Route Query, The VLDB Journal,
Vol. 17, No. 4(2008), pp. 765–787.
[12] Sharifzadeh, M. and Shahabi, C.: Processing Optimal
Sequenced Route Queries Using Voronoi Diagrams, Geoinformatica, Vol. 12, No. 4(2008), pp. 411–433.
[13] Ström, N.: Automatic continuous speech recognition
with rapid speaker adaptation for human/machine interaction, PhD Thesis, KTH, Stockholm, 1997.