Nearest base-neighbor search on spatial datasets

Hong Jun Jang, Kyeong Seok Hyun, Jaehwa Chung, Soon Young Jung

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)867-897
Number of pages31
JournalKnowledge and Information Systems
Issue number3
Publication statusPublished - 2020 Mar 1

Bibliographical note

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.


  • Group version of nearest neighbor query
  • Information technology
  • Nearest base-neighbor query
  • Spatial databases
  • k-nearest neighbor query

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Nearest base-neighbor search on spatial datasets'. Together they form a unique fingerprint.

Cite this