File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/TKDE.2019.2906188
- Scopus: eid_2-s2.0-85088127063
- WOS: WOS:000546878300012
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: ROAM: A Fundamental Routing Query on Road Networks with Efficiency
Title | ROAM: A Fundamental Routing Query on Road Networks with Efficiency |
---|---|
Authors | |
Keywords | Road Networks Query Performance Indexing Graph Algorithms |
Issue Date | 2020 |
Publisher | Institute 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, 2020, v. 32 n. 8, p. 1595-1609 How to Cite? |
Abstract | Novel 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 Identifier | http://hdl.handle.net/10722/275412 |
ISSN | 2023 Impact Factor: 8.9 2023 SCImago Journal Rankings: 2.867 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Luo, S | - |
dc.contributor.author | Cheng, R | - |
dc.contributor.author | Kao, B | - |
dc.contributor.author | Xiao, X | - |
dc.contributor.author | Zhou, S | - |
dc.contributor.author | Hu, J | - |
dc.date.accessioned | 2019-09-10T02:42:03Z | - |
dc.date.available | 2019-09-10T02:42:03Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | IEEE Transactions on Knowledge and Data Engineering, 2020, v. 32 n. 8, p. 1595-1609 | - |
dc.identifier.issn | 1041-4347 | - |
dc.identifier.uri | http://hdl.handle.net/10722/275412 | - |
dc.description.abstract | Novel 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.language | eng | - |
dc.publisher | Institute of Electrical and Electronics Engineers . The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69 | - |
dc.relation.ispartof | IEEE Transactions on Knowledge and Data Engineering | - |
dc.rights | IEEE 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.subject | Road Networks | - |
dc.subject | Query Performance | - |
dc.subject | Indexing | - |
dc.subject | Graph Algorithms | - |
dc.title | ROAM: A Fundamental Routing Query on Road Networks with Efficiency | - |
dc.type | Article | - |
dc.identifier.email | Cheng, R: ckcheng@cs.hku.hk | - |
dc.identifier.email | Kao, B: kao@cs.hku.hk | - |
dc.identifier.authority | Cheng, R=rp00074 | - |
dc.identifier.authority | Kao, B=rp00123 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/TKDE.2019.2906188 | - |
dc.identifier.scopus | eid_2-s2.0-85088127063 | - |
dc.identifier.hkuros | 302951 | - |
dc.identifier.hkuros | 318665 | - |
dc.identifier.volume | 32 | - |
dc.identifier.issue | 8 | - |
dc.identifier.spage | 1595 | - |
dc.identifier.epage | 1609 | - |
dc.identifier.isi | WOS:000546878300012 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1041-4347 | - |