TY - JOUR
T1 - Nearest base-neighbor search on spatial datasets
AU - Jang, Hong Jun
AU - Hyun, Kyeong Seok
AU - Chung, Jaehwa
AU - Jung, Soon Young
N1 - Funding Information:
This work was supported by the National Research Foundation of Korea (NRF) Grant Funded by the Korean Government (MSIP) (NRF-2016R1A2B1014013) and by Basic Science Research Program through the National Research Foundation of Korea (NRF) Funded by the Ministry of Education (2016R1D1A1B03930907)
Publisher Copyright:
© 2019, Springer-Verlag London Ltd., part of Springer Nature.
PY - 2020/3/1
Y1 - 2020/3/1
N2 - This paper presents a nearest base-neighbor (NBN) search that can be applied to a clustered nearest neighbor problem on spatial datasets with static properties. Given two sets of data points R and S, a query point q, distance threshold δ and cardinality threshold k, the NBN query retrieves a nearest point r (called the base-point) in R where more than k points in S are located within the distance δ. In this paper, we formally define a base-point and NBN problem. As the brute-force approach to this problem in massive datasets has large computational and I/O costs, we propose in-memory and external memory processing techniques for NBN queries. In particular, our proposed in-memory algorithms are used to minimize I/Os in the external memory algorithms. Furthermore, we devise a solution-based index, which we call the neighborhood-augmented grid, to dramatically reduce the search space. A performance study is conducted both on synthetic and real datasets. Our experimental results show the efficiency of our proposed approach.
AB - This paper presents a nearest base-neighbor (NBN) search that can be applied to a clustered nearest neighbor problem on spatial datasets with static properties. Given two sets of data points R and S, a query point q, distance threshold δ and cardinality threshold k, the NBN query retrieves a nearest point r (called the base-point) in R where more than k points in S are located within the distance δ. In this paper, we formally define a base-point and NBN problem. As the brute-force approach to this problem in massive datasets has large computational and I/O costs, we propose in-memory and external memory processing techniques for NBN queries. In particular, our proposed in-memory algorithms are used to minimize I/Os in the external memory algorithms. Furthermore, we devise a solution-based index, which we call the neighborhood-augmented grid, to dramatically reduce the search space. A performance study is conducted both on synthetic and real datasets. Our experimental results show the efficiency of our proposed approach.
KW - Group version of nearest neighbor query
KW - Information technology
KW - Nearest base-neighbor query
KW - Spatial databases
KW - k-nearest neighbor query
UR - http://www.scopus.com/inward/record.url?scp=85069641510&partnerID=8YFLogxK
U2 - 10.1007/s10115-019-01360-3
DO - 10.1007/s10115-019-01360-3
M3 - Article
AN - SCOPUS:85069641510
SN - 0219-1377
VL - 62
SP - 867
EP - 897
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 3
ER -