File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/ICDE.2019.00119
- Scopus: eid_2-s2.0-85067912655
- WOS: WOS:000477731600112
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: MPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks
Title | MPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks |
---|---|
Authors | |
Keywords | Adaptive approach Knn search Road network |
Issue Date | 2019 |
Publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178 |
Citation | 35th IEEE International Conference on Data Engineering (ICDE 2019), Macau, China, 8-11 April 2019, p. 1310-1321 How to Cite? |
Abstract | We study the problem of executing road-network k-nearest-neighbor (kNN) search on multi-core machines. State-of-the-art kNN algorithms on road networks often involve elaborate index structures and complex computational logic. Moreover, most kNN algorithms are inherently sequential. These make the traditional approach of parallel programming very costly, laborious, and ineffective when they are applied to kNN algorithms. We propose the MPR (Multi-layer Partitioning-Replication) mechanism that orchestrates CPU cores and schedules kNN query and index update processes to run on the cores. The MPR mechanism performs workload analysis to determine the best arrangement of the cores with the objective of optimizing quality-of-service (QoS) measures, such as system throughput and query response time. We demonstrate the effectiveness of MPR by applying it to a number of state-of-the-art kNN indexing methods running on a multi-core machine. Our experiments show that multi-processing using our MPR approach requires minimal programming effort. It also leads to significant improvements in query response time and system throughput compared with other baseline parallelization methods |
Persistent Identifier | http://hdl.handle.net/10722/275198 |
ISSN | 2023 SCImago Journal Rankings: 1.306 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Luo, S | - |
dc.contributor.author | Kao, CM | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Cheng, CK | - |
dc.date.accessioned | 2019-09-10T02:37:35Z | - |
dc.date.available | 2019-09-10T02:37:35Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | 35th IEEE International Conference on Data Engineering (ICDE 2019), Macau, China, 8-11 April 2019, p. 1310-1321 | - |
dc.identifier.issn | 1084-4627 | - |
dc.identifier.uri | http://hdl.handle.net/10722/275198 | - |
dc.description.abstract | We study the problem of executing road-network k-nearest-neighbor (kNN) search on multi-core machines. State-of-the-art kNN algorithms on road networks often involve elaborate index structures and complex computational logic. Moreover, most kNN algorithms are inherently sequential. These make the traditional approach of parallel programming very costly, laborious, and ineffective when they are applied to kNN algorithms. We propose the MPR (Multi-layer Partitioning-Replication) mechanism that orchestrates CPU cores and schedules kNN query and index update processes to run on the cores. The MPR mechanism performs workload analysis to determine the best arrangement of the cores with the objective of optimizing quality-of-service (QoS) measures, such as system throughput and query response time. We demonstrate the effectiveness of MPR by applying it to a number of state-of-the-art kNN indexing methods running on a multi-core machine. Our experiments show that multi-processing using our MPR approach requires minimal programming effort. It also leads to significant improvements in query response time and system throughput compared with other baseline parallelization methods | - |
dc.language | eng | - |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178 | - |
dc.relation.ispartof | International Conference on Data Engineering. Proceedings | - |
dc.rights | International Conference on Data Engineering. Proceedings. Copyright © IEEE Computer Society. | - |
dc.rights | ©2019 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 | Adaptive approach | - |
dc.subject | Knn search | - |
dc.subject | Road network | - |
dc.title | MPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Kao, CM: kao@cs.hku.hk | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Kao, CM=rp00123 | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.identifier.doi | 10.1109/ICDE.2019.00119 | - |
dc.identifier.scopus | eid_2-s2.0-85067912655 | - |
dc.identifier.hkuros | 303000 | - |
dc.identifier.spage | 1310 | - |
dc.identifier.epage | 1321 | - |
dc.identifier.isi | WOS:000477731600112 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1084-4627 | - |