Dense Nearest Neighborhood Query

EasyChair Preprint 6606

Abstract

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: Information Retrieval, Nearest Neighborhood query, grid index, spatial database

@booklet{EasyChair:6606,
  author    = {Hina Suzuki and Hanxiong Chen and Kazutaka Furuse and Toshiyuki Amagasa},
  title     = {Dense Nearest Neighborhood Query},
  howpublished = {EasyChair Preprint 6606},
  year      = {EasyChair, 2021}}