Efficient parallel processing of high-dimensional spatial kNN queries

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

  • Tao Jiang
  • Bin Zhang
  • Dan Lin
  • Yunjun Gao
  • Qing Li

Related Research Unit(s)

Detail(s)

Original languageEnglish
Journal / PublicationSoft Computing
Online published2 May 2022
Publication statusOnline published - 2 May 2022

Abstract

Some efficient top-k algorithms, i.e., Fagin's Algorithm, threshold algorithm (TA), and best position algorithm (BPA), can be used to answer k nearest neighbor (kNN) queries. However, extending the existing algorithms without further changes to the algorithms themselves would not be efficient since there are the different characteristics between the kNN queries and top-k queries. For example, the kNN queries are more distance-sensitive rather than the position of data points. Second, it is necessary to add some novel parallel heuristics and pruning policies for the kNN queries. Third, there are still many redundant random accesses among FA, TA, and BPA. In this paper, we address aforementioned these problems and take these algorithms to answer parallel kNN (PkNN) queries in spatial databases. We integrate the advantages of the B + -tree and Open MP programming and propose three efficient parallel kNN query algorithms, namely distance priority-based PkNN, optimized PkNN, and partition-based PkNN. Our performance evaluation shows that our proposed algorithms achieve significant improvement in comparison with existing algorithms, i.e., BPA and BPA2. In addition, our approaches are also capable of returning kNN results incrementally which greatly shorten the query response time and enhance user experience.

Research Area(s)

  • Nearest neighbor queries, Parallel, Algorithm, Performance, Spatial database, NEAREST-NEIGHBOR SEARCH, TREE

Citation Format(s)

Efficient parallel processing of high-dimensional spatial kNN queries. / Jiang, Tao; Zhang, Bin; Lin, Dan et al.

In: Soft Computing, 02.05.2022.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review