Retrieving routes of interest over road networks

Wengen Li, Jiannong Cao, Jihong Guan, Man Lung Yiu, Shuigeng Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)

Abstract

In this paper, we propose route of interest (ROI) query which allows users to specify their interests with query keywords and returns a route such that (i) its distance is less than a distance threshold and (ii) its relevance to the query keywords is maximized. ROI query is particularly helpful for tourists and city explorers. For example, a tourist may wish to find a route from a scenic spot to her hotel to cover many artware shops. It is challenging to efficiently answer ROI query due to its NP-hard complexity. Novelly, we propose an adaptive route sampling framework that adaptively computes a route according to a given response time, and gradually improve the quality of the route with time. Moreover, we design a suite of route sampling techniques under this framework. Experiments on real data suggest that our proposed solution can return high quality routes within a short response time.
Original languageEnglish
Title of host publicationWeb-Age Information Management - 17th International Conference, WAIM 2016, Proceedings
PublisherSpringer Verlag
Pages109-123
Number of pages15
ISBN (Print)9783319399362
DOIs
Publication statusPublished - 1 Jan 2016
Event17th International Conference on Web-Age Information Management, WAIM 2016 - Nanchang, China
Duration: 3 Jun 20165 Jun 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9658
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Web-Age Information Management, WAIM 2016
CountryChina
CityNanchang
Period3/06/165/06/16

Keywords

  • Randomized algorithm
  • Route of interest
  • Route sampling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this