Distributed k-Nearest Neighbor Queries in Metric Spaces

Xin Ding, Yuanliang Zhang, Lu Chen, Yujun Gao, Baihua Zheng

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)

Abstract

Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments using real and synthetic data demonstrate the performance of MkNN using AMDS. Moreover, the AMDS scales sub-linearly with the growing data size.
Original languageEnglish
Title of host publicationWeb and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings
EditorsJianliang Xu, Yoshiharu Ishikawa, Yi Cai
Number of pages17
Volume1
PublisherSpringer
Publication date2018
Pages236-252
ISBN (Electronic)978-3-319-96890-2
DOIs
Publication statusPublished - 2018
EventSecond International Joint Conference, APWeb-WAIM 2018 - Macau, China
Duration: 23 Jul 201825 Jul 2018

Conference

ConferenceSecond International Joint Conference, APWeb-WAIM 2018
CountryChina
CityMacau
Period23/07/201825/07/2018
SeriesLecture Notes in Computer Science
Volume10987
ISSN0302-9743

Fingerprint

Location based services
Resource allocation
Communication
Processing
Experiments

Keywords

  • Algorithm
  • Metric space
  • Publish/subscribe
  • Query processing
  • k nearest neighbor query

Cite this

Ding, X., Zhang, Y., Chen, L., Gao, Y., & Zheng, B. (2018). Distributed k-Nearest Neighbor Queries in Metric Spaces. In J. Xu, Y. Ishikawa, & Y. Cai (Eds.), Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings (Vol. 1, pp. 236-252). Springer. Lecture Notes in Computer Science, Vol.. 10987 https://doi.org/10.1007/978-3-319-96890-2_20
Ding, Xin ; Zhang, Yuanliang ; Chen, Lu ; Gao, Yujun ; Zheng, Baihua. / Distributed k-Nearest Neighbor Queries in Metric Spaces. Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings. editor / Jianliang Xu ; Yoshiharu Ishikawa ; Yi Cai. Vol. 1 Springer, 2018. pp. 236-252 (Lecture Notes in Computer Science, Vol. 10987).
@inproceedings{75ba7f47dc3c416e8d5ecfec604daa63,
title = "Distributed k-Nearest Neighbor Queries in Metric Spaces",
abstract = "Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments using real and synthetic data demonstrate the performance of MkNN using AMDS. Moreover, the AMDS scales sub-linearly with the growing data size.",
keywords = "Algorithm, Metric space, Publish/subscribe, Query processing, k nearest neighbor query",
author = "Xin Ding and Yuanliang Zhang and Lu Chen and Yujun Gao and Baihua Zheng",
year = "2018",
doi = "10.1007/978-3-319-96890-2_20",
language = "English",
volume = "1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "236--252",
editor = "Jianliang Xu and Yoshiharu Ishikawa and Yi Cai",
booktitle = "Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings",
address = "Germany",

}

Ding, X, Zhang, Y, Chen, L, Gao, Y & Zheng, B 2018, Distributed k-Nearest Neighbor Queries in Metric Spaces. in J Xu, Y Ishikawa & Y Cai (eds), Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings. vol. 1, Springer, Lecture Notes in Computer Science, vol. 10987, pp. 236-252, Second International Joint Conference, APWeb-WAIM 2018 , Macau, China, 23/07/2018. https://doi.org/10.1007/978-3-319-96890-2_20

Distributed k-Nearest Neighbor Queries in Metric Spaces. / Ding, Xin; Zhang, Yuanliang; Chen, Lu; Gao, Yujun; Zheng, Baihua.

Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings. ed. / Jianliang Xu; Yoshiharu Ishikawa; Yi Cai. Vol. 1 Springer, 2018. p. 236-252 (Lecture Notes in Computer Science, Vol. 10987).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Distributed k-Nearest Neighbor Queries in Metric Spaces

AU - Ding, Xin

AU - Zhang, Yuanliang

AU - Chen, Lu

AU - Gao, Yujun

AU - Zheng, Baihua

PY - 2018

Y1 - 2018

N2 - Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments using real and synthetic data demonstrate the performance of MkNN using AMDS. Moreover, the AMDS scales sub-linearly with the growing data size.

AB - Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments using real and synthetic data demonstrate the performance of MkNN using AMDS. Moreover, the AMDS scales sub-linearly with the growing data size.

KW - Algorithm

KW - Metric space

KW - Publish/subscribe

KW - Query processing

KW - k nearest neighbor query

UR - http://www.scopus.com/inward/record.url?scp=85050519952&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-96890-2_20

DO - 10.1007/978-3-319-96890-2_20

M3 - Article in proceeding

VL - 1

T3 - Lecture Notes in Computer Science

SP - 236

EP - 252

BT - Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings

A2 - Xu, Jianliang

A2 - Ishikawa, Yoshiharu

A2 - Cai, Yi

PB - Springer

ER -

Ding X, Zhang Y, Chen L, Gao Y, Zheng B. Distributed k-Nearest Neighbor Queries in Metric Spaces. In Xu J, Ishikawa Y, Cai Y, editors, Web and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings. Vol. 1. Springer. 2018. p. 236-252. (Lecture Notes in Computer Science, Vol. 10987). https://doi.org/10.1007/978-3-319-96890-2_20