Download PDFOpen PDF in browser

Dense Nearest Neighborhood Query

EasyChair Preprint no. 6606

14 pagesDate: September 13, 2021


A nearest neighbor (NN) query is a principal factor in applications that handle multidimensional vector data, such as location-based services, data mining, and pattern recognition. Meanwhile, a nearest neighborhood (NNH) query is a query to find dense neighborhoods. However, it cannot find desired groups owing to strong restrictions such as fixed group size in previous studies. Thus, in this paper, we propose a dense nearest neighborhood (DNNH) query, which is a query without strong constraints, and three efficient algorithms to solve the DNNH query. The proposed methods are divided into clustering-based and expanding-based methods. The expanding-based method can efficiently find a solution by reducing unnecessary processing using a filtering threshold and expansion breaking criterion. Experiments on various datasets confirm the effectiveness and efficiency of the proposed methods.

Keyphrases: grid index, Information Retrieval, Nearest Neighborhood query, spatial database

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Hina Suzuki and Hanxiong Chen and Kazutaka Furuse and Toshiyuki Amagasa},
  title = {Dense Nearest Neighborhood Query},
  howpublished = {EasyChair Preprint no. 6606},

  year = {EasyChair, 2021}}
Download PDFOpen PDF in browser