Distributed similarity queries in metric spaces

Similarity queries, including range queries and k nearest neighbor (kNN) queries, in metric spaces 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 pr...

Full description

Saved in:
Bibliographic Details
Main Authors: YANG, Keyu, DING, Xin, ZHANG, Yuanliang, CHEN, Lu, ZHENG, Baihua, GAO, Yunjun
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/4438
https://ink.library.smu.edu.sg/context/sis_research/article/5441/viewcontent/Yang2019_Article_DistributedSimilarityQueriesIn.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5441
record_format dspace
spelling sg-smu-ink.sis_research-54412021-09-07T07:25:32Z Distributed similarity queries in metric spaces YANG, Keyu DING, Xin ZHANG, Yuanliang CHEN, Lu ZHENG, Baihua GAO, Yunjun Similarity queries, including range queries and k nearest neighbor (kNN) queries, in metric spaces 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), to support efficient metric similarity queries in the distributed environment. AMDS uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronous process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop efficient similarity search algorithms using AMDS. Extensive experiments using real and synthetic data demonstrate the performance of metric similarity queries using AMDS. Moreover, the AMDS scales sublinearly with the growing data size. 2019-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4438 info:doi/10.1007/s41019-019-0095-7 https://ink.library.smu.edu.sg/context/sis_research/article/5441/viewcontent/Yang2019_Article_DistributedSimilarityQueriesIn.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Similarity query Metric space Range query Algorithm kNN query Distributed processing Databases and Information Systems Theory and Algorithms
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Similarity query
Metric space
Range query
Algorithm
kNN query
Distributed processing
Databases and Information Systems
Theory and Algorithms
spellingShingle Similarity query
Metric space
Range query
Algorithm
kNN query
Distributed processing
Databases and Information Systems
Theory and Algorithms
YANG, Keyu
DING, Xin
ZHANG, Yuanliang
CHEN, Lu
ZHENG, Baihua
GAO, Yunjun
Distributed similarity queries in metric spaces
description Similarity queries, including range queries and k nearest neighbor (kNN) queries, in metric spaces 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), to support efficient metric similarity queries in the distributed environment. AMDS uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronous process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop efficient similarity search algorithms using AMDS. Extensive experiments using real and synthetic data demonstrate the performance of metric similarity queries using AMDS. Moreover, the AMDS scales sublinearly with the growing data size.
format text
author YANG, Keyu
DING, Xin
ZHANG, Yuanliang
CHEN, Lu
ZHENG, Baihua
GAO, Yunjun
author_facet YANG, Keyu
DING, Xin
ZHANG, Yuanliang
CHEN, Lu
ZHENG, Baihua
GAO, Yunjun
author_sort YANG, Keyu
title Distributed similarity queries in metric spaces
title_short Distributed similarity queries in metric spaces
title_full Distributed similarity queries in metric spaces
title_fullStr Distributed similarity queries in metric spaces
title_full_unstemmed Distributed similarity queries in metric spaces
title_sort distributed similarity queries in metric spaces
publisher Institutional Knowledge at Singapore Management University
publishDate 2019
url https://ink.library.smu.edu.sg/sis_research/4438
https://ink.library.smu.edu.sg/context/sis_research/article/5441/viewcontent/Yang2019_Article_DistributedSimilarityQueriesIn.pdf
_version_ 1770574795887345664