File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: ROAM: A Fundamental Routing Query on Road Networks with Efficiency

TitleROAM: A Fundamental Routing Query on Road Networks with Efficiency
Authors
KeywordsRoad Networks
Query Performance
Indexing
Graph Algorithms
Issue Date2019
PublisherInstitute of Electrical and Electronics Engineers . The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69
Citation
IEEE Transactions on Knowledge and Data Engineering, 2019, Epub How to Cite?
AbstractNovel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes s and t , and an area A on road network graph G , is there a 'good' route (e.g., short enough path) P from s to t that crosses A in G ? In a taxi-sharing system, s and t can be a taxi's current and destined locations, and A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a ρ -route, which is an s - t path that passes A , with a length of at most (1+ρ) times the shortest distance between s and t . The existence of a ρ -route implies that a service or task located at A can be found for a given moving object m , and that m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms.
Persistent Identifierhttp://hdl.handle.net/10722/275412
ISSN
2017 Impact Factor: 2.775
2015 SCImago Journal Rankings: 2.087

 

DC FieldValueLanguage
dc.contributor.authorLuo, S-
dc.contributor.authorCheng, R-
dc.contributor.authorKao, B-
dc.contributor.authorXiao, X-
dc.contributor.authorZhou, S-
dc.contributor.authorHu, J-
dc.date.accessioned2019-09-10T02:42:03Z-
dc.date.available2019-09-10T02:42:03Z-
dc.date.issued2019-
dc.identifier.citationIEEE Transactions on Knowledge and Data Engineering, 2019, Epub-
dc.identifier.issn1041-4347-
dc.identifier.urihttp://hdl.handle.net/10722/275412-
dc.description.abstractNovel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes s and t , and an area A on road network graph G , is there a 'good' route (e.g., short enough path) P from s to t that crosses A in G ? In a taxi-sharing system, s and t can be a taxi's current and destined locations, and A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a ρ -route, which is an s - t path that passes A , with a length of at most (1+ρ) times the shortest distance between s and t . The existence of a ρ -route implies that a service or task located at A can be found for a given moving object m , and that m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms.-
dc.languageeng-
dc.publisherInstitute of Electrical and Electronics Engineers . The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69-
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering-
dc.rightsIEEE Transactions on Knowledge and Data Engineering. Copyright © Institute of Electrical and Electronics Engineers .-
dc.rights©20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.subjectRoad Networks-
dc.subjectQuery Performance-
dc.subjectIndexing-
dc.subjectGraph Algorithms-
dc.titleROAM: A Fundamental Routing Query on Road Networks with Efficiency-
dc.typeArticle-
dc.identifier.emailCheng, R: ckcheng@cs.hku.hk-
dc.identifier.emailKao, B: kao@cs.hku.hk-
dc.identifier.authorityCheng, R=rp00074-
dc.identifier.authorityKao, B=rp00123-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/TKDE.2019.2906188-
dc.identifier.hkuros302951-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats