File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: MPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks

TitleMPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks
Authors
Issue Date2019
PublisherIEEE 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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/275198
ISSN

 

DC FieldValueLanguage
dc.contributor.authorLuo, S-
dc.contributor.authorKao, CM-
dc.contributor.authorWu, X-
dc.contributor.authorCheng, CK-
dc.date.accessioned2019-09-10T02:37:35Z-
dc.date.available2019-09-10T02:37:35Z-
dc.date.issued2019-
dc.identifier.citation35th IEEE International Conference on Data Engineering (ICDE 2019), Macau, China, 8-11 April 2019, p. 1310-1321-
dc.identifier.issn1084-4627-
dc.identifier.urihttp://hdl.handle.net/10722/275198-
dc.description.abstractWe 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.languageeng-
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178-
dc.relation.ispartofInternational Conference on Data Engineering. Proceedings-
dc.rightsInternational 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.titleMPR — A Partitioning-Replication Framework for Multi-Processing kNN Search on Road Networks-
dc.typeConference_Paper-
dc.identifier.emailKao, CM: kao@cs.hku.hk-
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hk-
dc.identifier.authorityKao, CM=rp00123-
dc.identifier.authorityCheng, CK=rp00074-
dc.identifier.doi10.1109/ICDE.2019.00119-
dc.identifier.hkuros303000-
dc.identifier.spage1310-
dc.identifier.epage1321-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats