Nearest base-neighbor search on spatial datasets
- Authors
- Jang, Hong-Jun; Hyun, Kyeong-Seok; Chung, Jaehwa; Jung, Soon-Young
- Issue Date
- 3월-2020
- Publisher
- SPRINGER LONDON LTD
- Keywords
- Information technology; k-nearest neighbor query; Group version of nearest neighbor query; Nearest base-neighbor query; Spatial databases
- Citation
- KNOWLEDGE AND INFORMATION SYSTEMS, v.62, no.3, pp.867 - 897
- Indexed
- SCIE
SCOPUS
- Journal Title
- KNOWLEDGE AND INFORMATION SYSTEMS
- Volume
- 62
- Number
- 3
- Start Page
- 867
- End Page
- 897
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/57525
- DOI
- 10.1007/s10115-019-01360-3
- ISSN
- 0219-1377
- Abstract
- 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 delta 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 delta. 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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - Graduate School > Department of Computer Science and Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.