PaperlayerView exact revision on arXiv

Source-linked AI summary

Keyword-aware Optimal Route Search

Xin Cao, Lisi Chen, Gao Cong, Xiaokui Xiao

arXiv:1208.0077v1cs.DB

TL;DR

Existing route-planning methods do not support flexible queries combining keyword coverage with a budget and an objective such as popularity. The paper defines this NP-hard query and proposes approximation algorithms; its empirical studies report that the algorithms answer queries efficiently, with BucketBound and Greedy running faster.

  • Problem

    Existing trip-planning and route-search solutions do not provide enough flexibility for users to specify keyword coverage and a budget while optimizing a separate route objective.

    Source: §1 · p. 1

  • Method

    The paper defines KOR and proposes OSScaling and BucketBound with provable approximation bounds, plus a greedy approach.

    Source: §1 · p. 2

  • Results

    The empirical studies report that all proposed algorithms answer KOR queries efficiently, while BucketBound and Greedy run faster.

    Source: §6 · p. 12

  • Takeaways & Limitations

    KOR provides a formal route-search problem for combining keyword coverage, a budget constraint, and an optimized objective score.

    Source: §1 · p. 1, §6 · p. 12

    The greedy algorithm may fail to find a feasible route even when one exists, because it selects the next node at each step.

    Source: §3.4 · p. 8

Abstract

from arXiv · show

Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from his hotel is within 4 hours." However, none of the algorithms in the existing work on route planning can be used to answer such queries. Motivated by this, we define the problem of keyword-aware optimal route query, denoted by KOR, which is to find an optimal route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We devise an approximation algorithm OSScaling with provable approximation bounds. Based on this algorithm, another more efficient approximation algorithm BucketBound is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently, while the BucketBound and Greedy algorithms run faster. The empirical studies also offer insight into the accuracy of the proposed algorithms.

1. INTRODUCTION

Existing trip-planning routes may not meet users’ needs, while route search offers limited flexibility for expressing them. KOR formalizes route selection under keyword and budget constraints, and the paper proposes bounded approximation algorithms and a greedy approach.

1. INTRODUCTION

  • KOR seeks a route that covers user-specified keywords and satisfies a budget while optimizing a separate objective, balancing preferences such as popularity against travel time.The paper notes that existing route-planning solutions do not offer enough flexibility for these requirements.Source: §1 · p. 1
  • OSScaling scales edge objective values and tracks labels for partial routes; its returned route has an objective score no worse than the stated bound relative to the optimum.The label records covered keywords, scaled and original objective scores, and budget score; its worst-case complexity is polynomial in several input measures but exponential in the number of query keywords.Source: §1 · pp. 1–2
  • BucketBound is more efficient than OSScaling and returns a route with objective score at most β times the score of OSScaling’s route.It groups partial routes into buckets by their best possible objective scores and returns a feasible route in the same bucket as OSScaling’s route.Source: §1 · p. 2
  • The greedy approach extends a route by selecting the next location while considering all three query criteria, but it may violate keyword coverage or the budget constraint.The paper reports that its empirical studies examine efficiency and approximation accuracy.Source: §1 · p. 2
  • The KOR query is NP-hard, and the paper presents OSScaling, BucketBound, and a greedy approach to answer it approximately.OSScaling and BucketBound have provable performance bounds; empirical studies use a graph extracted from Flickr photos.Source: §1 · pp. 1–2

2. PROBLEM STATEMENT

KOR is defined over a graph whose locations carry keywords and whose edges have attributes used for an objective and a budget. The query seeks an optimal source-to-target route that covers the requested keywords within the budget; even simplified versions are computationally hard.

2. PROBLEM STATEMENT

  • A graph has locations as nodes and directed routes as edges; each node carries a keyword set, and the paper considers directed graphs while noting extension to undirected graphs is straightforward.The graph may represent a road network or historical user trajectories, with edge attributes depending on the source.Source: §2 · p. 2
  • Each edge has an objective value and a budget value, and the paper allows any two attributes to serve these roles for different applications.For example, popularity may be the objective and travel time the budget.Source: §2 · p. 2
  • KOR seeks a source-to-target route that covers every query keyword and meets the budget limit while minimizing its objective score.The query is parameterized by source and target locations, a keyword set, and a budget limit.Source: §2 · pp. 2–3
  • KOR is NP-hard: when every node already covers all query keywords, it reduces to the weight-constrained shortest path problem.The paper also relates versions without the budget constraint to the generalized traveling salesman problem.Source: §2 · p. 3
  • The keyword-aware top-k route query extends KOR by returning k routes with the smallest objective scores that cover the keywords and satisfy the budget.The routes share the given start and end locations.Source: §2 · p. 3

3. ALGORITHMS

This section presents preprocessing and three KOR solvers: OSScaling, BucketBound, and a greedy algorithm, describing their search strategies and guarantees. It also discusses the greedy algorithm’s prioritization options and how OSScaling and BucketBound extend to top-k route queries.

3.1 Pre-processing

  • Preprocessing uses Floyd–Warshall to find, for each node pair, a path minimizing objective score and a path minimizing budget score; the algorithms use their scores, not the paths themselves.The stored scores require O(|V|^2) space.Source: §3.1 · p. 3
  • A disk-resident B+-tree inverted file indexes each distinct location-description word to the identifiers of nodes whose descriptions contain it.The index consists of a vocabulary and a posting list for each word.Source: §3.1 · p. 3

3.2 Approximation Algorithm OSScaling

  • OSScaling scales edge objective values and prunes dominated partial-route labels, returning a route with objective score at most 1/(1−ǫ) times the optimum when a feasible route exists.The algorithm runs in time polynomial in the budget constraint, 1/ǫ, and graph size, but exponential in the number of query keywords.Source: §3.2 · pp. 3–4
  • OSScaling bounds the number of labels stored at each node by using scaled-objective dominance, though this can discard a label with a better original objective score and miss the optimum.Lemma 1 gives an upper bound on labels per node; the number maintained is usually much smaller in practice.Source: §3.2 · p. 4
  • OSScaling scales edge objective scores to integers to obtain an approximation bound, with ε trading query speed for route accuracy.Its proof establishes OS(RGS) ≥ OS(ROS) and derives a (1−ε)-scaled score bound.Source: §3.2 · pp. 5–6
  • OSScaling’s optimizations seek feasible routes early to tighten the upper bound and use locations of very infrequent query words to prune labels that cannot yield a feasible result.The rare-word strategy finds locations of the least frequent word using an inverted file and tests budget conditions before extending labels further.Source: §3.2 · p. 6

3.3 Approximation Algorithm BucketBound

  • BucketBound returns a feasible route when it shares a bucket with OSScaling’s route, has approximation ratio β/(1−ε), and processes fewer labels in practice despite the same worst-case complexity.It selects labels from the lowest-order non-empty bucket and terminates once the bucket condition is met; it can also determine when no feasible route exists.Source: §3.3 · pp. 6–7

3.4 Greedy Algorithm

  • The greedy algorithm has no performance guarantee and repeatedly chooses an uncovered-keyword node using a score that balances objective and budget scores.Parameter α controls that balance; the selected node is intended to keep the resulting route within budget while minimizing its objective score.Source: §3.4 · p. 7
  • Greedy-1 selects one next-best node per step, while Greedy-2 selects two, trading greater accuracy for larger search space; either may miss a feasible route, with worst-case time O(mn) and O(2mn), respectively.Source: §3.4 · p. 8
  • When budget compliance takes priority, Greedy instead stops if extending the partial route would exceed the budget, so the returned route may not cover every query keyword.This modification checks whether L.BS + BS(σl,t) > ∆ rather than whether the keyword set is empty.Source: §3.4 · p. 8

3.5 Keyword-aware Top-k Optimal Route Search

  • OSScaling and BucketBound extend to KkR by tracking the top k routes and using k-dominance, while Greedy is omitted because it cannot guarantee a feasible route.OSScaling uses the kth-best route’s budget score as an upper bound for pruning; BucketBound stops after finding k feasible routes in the lowest-order nonempty bucket.Source: §3.5 · p. 8

4.1 Experimental Settings

The experiments compare OSScaling, BucketBound, and two greedy variants on Flickr-derived and generated graphs. They vary query keyword counts and use a popularity-based objective, omitting brute force because it was much slower.

4.1 Experimental Settings

  • The study compared OSScaling, BucketBound, Greedy-1, and Greedy-2, with the greedy variants selecting the top-1 and top-2 locations.Source: §4.1 · p. 8
  • Brute force was at least 2 orders of magnitude slower than OSScaling and could not finish within 1 day, so it was omitted.Source: §4.1 · p. 8
  • The Flickr dataset contains 1,501,553 geo-tagged photos from 30,664 users, clustered into 5,199 locations with 9,785 tags.Locations were connected by edges when consecutive photos from the same user showed travel between places less than one day apart.Source: §4.1 · p. 8
  • On Flickr edges, Euclidean distance supplied the budget value, while popularity was estimated from the fraction of trips using each edge.Route popularity was the product of edge probabilities; its logarithmic inverse transformed the maximization objective into minimization.Source: §4.1 · p. 8
  • Four additional scalability datasets used 5,000, 10,000, 15,000, and 20,000 New York road-network nodes, with random tags and edge objective scores.Travel distance was the budget score for these generated graphs.Source: §4.1 · p. 9
  • Each dataset had five query sets with 2, 4, 6, 8, or 10 keywords and 50 randomly generated queries per set; runs used VC++ on a 2.66GHz Xeon X5650 with 4GB RAM.Source: §4.1 · p. 9

4.2 Experimental Results

Across the experiments, BucketBound consistently ran faster than OSScaling, while accuracy and runtime varied with algorithm parameters and query settings. The proposed algorithms also scaled on tested datasets, and the example routes reflected different distance budgets.

4.2.1 Efficiency of Different Algorithms

  • On Flickr, BucketBound was usually 8–10 times faster than OSScaling, while Greedy-1 was fastest and Greedy-2 slowed sharply as keywords increased.BucketBound’s early termination after finding a feasible route in the bucket containing OSScaling’s route generates fewer labels.Source: §4.2.1 · p. 9

4.2.2 Accuracy of Approximation Algorithms

  • BucketBound’s relative ratio stayed below β and its accuracy was better than Greedy-1 and Greedy-2, especially for more keywords or larger Δ.Greedy algorithms failed to find feasible routes for about 10%–20% of queries; their ratios were measured only on queries where they found feasible routes.Source: §4.2.2 · p. 10
  • As α increased, Greedy’s relative ratio worsened while it found feasible routes for more queries; Greedy-2 consistently outperformed Greedy-1.At α=0, both greedy variants had their best average ratios and largest failure percentages; at α=1, they found feasible results on more queries but had worse relative accuracy.Source: §4.2.2 · p. 10

4.2.3 Comparing OSScaling and BucketBound

  • With equal theoretical approximation bounds, BucketBound ran consistently faster than OSScaling, while OSScaling achieved better relative ratios.The comparison used Δ=6 km, β=1.2, and six query keywords.Source: §4.2.3 · p. 10

4.2.5 Experiments on More Datasets

  • On a synthetic dataset of 5,000 nodes, runtime comparisons matched Flickr results, and relative ratios were qualitatively similar.The experiments used ε=0.5 and β=1.2.Source: §4.2.5 · p. 11

4.2.6 Scalability

  • With six keywords and Δ=30 km, all proposed algorithms scaled well with dataset size, while relative ratios changed only slightly.The relative-ratio details were omitted.Source: §4.2.6 · p. 11

4.2.7 Example

  • For the example query, OSScaling returned the most popular feasible route under each distance limit: 9 km and 6 km produced different routes.The 9 km route exceeded the 6 km limit and was pruned when that smaller budget was used.Source: §4.2.7 · p. 11

5. RELATED WORK

Related work addresses route search, spatial keyword queries, and route recommendation, but differs from KOR in its constraints, output, or query formulation.

5. RELATED WORK

  • TPQ seeks a shortest route covering specified categories, while OSR adds category ordering; KOR adds a budget constraint, and these algorithms do not answer it.OSR specifies only a starting location, whereas TPQ specifies both start and end locations.Source: §5 · p. 11
  • MRPSR unifies TPQ and OSR, but its heuristics are not applicable to KOR; related length-bounded text-relevance queries also differ, and their greedy algorithm does not guarantee feasibility.Kanza et al.'s subsequent work incorporates interactive user feedback when selecting the next object.Source: §5 · p. 11
  • Continuous route planning under delay updates and interactive trip planning from user feedback address problems distinct from KOR.Interactive itineraries are constructed iteratively based on user preferences and a time budget.Source: §5 · pp. 11–12
  • MARK finds the shortest route meeting keyword-similarity thresholds, rather than optimizing KOR's objective under its constraints.MARK requires at least one matching object per keyword.Source: §5 · p. 12
  • Collective spatial keyword search returns objects rather than a budget-constrained route, while route-recommendation works do not account for keywords as KOR does.Spatial keyword search also retrieves single objects rather than routes.Source: §5 · p. 12

6. CONCLUSION AND FUTURE WORK

The paper defines KOR and proposes approximation algorithms for its NP-hard query problem. Its experiments report efficient query answering, with BucketBound and Greedy running faster, and future work targets preprocessing costs through graph partitioning.

6. CONCLUSION AND FUTURE WORK

  • Empirical studies find all proposed algorithms capable of answering KOR queries efficiently, while BucketBound and Greedy run faster.The studies also examine approximation accuracy.Source: §6 · p. 12
  • KOR seeks an optimal route covering user-specified keywords while satisfying a budget constraint and optimizing an objective score; answering KOR is NP-hard.Source: §6 · p. 12
  • The paper proposes OSScaling and BucketBound with provable approximation bounds, plus a greedy approximation algorithm.Source: §6 · p. 12
  • Future work would partition large graphs into subgraphs and preprocess within each, storing best objective and budget scores between border nodes to reduce preprocessing time and space.Source: §6 · p. 12
Loading 1208.0077v1…