Efficient KNN Join Over Dynamic High-Dimensional Data

RAIDS Lab Authors

Zhengyi Yang

(corresponding author)

Director

Details

Research Area

Tags

Resources

Awards

Abstract

Given a user dataset U and an object dataset I in high-dimensional space, a kNN join query retrieves each object in dataset U its k nearest neighbors from the dataset I. kNN join is a fundamental and essential operation in applications from many domains such as databases, computer vision, multi-media, machine learning, recommendation systems, and many more. The datasets in real world often update dynamically on insertion or deletion of objects. However, existing algorithms of dynamic kNN join lack support for deletion and batch update, which are important in real-life applications. In this paper, we propose a new method of kNN join over dynamic high-dimensional data. Specifically, our method features lazy updates, batch operations, and optimised deletions. Experiments on real-world datasets show that our method outperforms the existing algorithms of naive RkNN join and HDR Tree by up to 5 and 4 times, respectively.

Author Affiliations

@inproceedings{ukey2022efficient,
  title = {Efficient kNN Join over Dynamic High-Dimensional Data},
  author = {Ukey, Nimish and Yang, Zhengyi and Zhang, Guangjian and Liu, Boge and Li, Binghao and Zhang, Wenjie},
  editor = {Hua, Wen and Wang, Hua and Li, Lei},
  booktitle = {Databases Theory and Applications},
  year = {2022},
  publisher = {Springer International Publishing},
  address = {Cham},
  pages = {63--75},
  isbn = {978-3-031-15512-3}
}