High-dimensional kNN joins with incremental updates |
| |
Authors: | Cui Yu Rui Zhang Yaochun Huang Hui Xiong |
| |
Affiliation: | (1) Monmouth University, West Long Branch, NJ 07764, USA;(2) University of Melbourne, Carlton, Victoria, 3053, Australia;(3) University of Texas - Dallas, Dallas, TX 75080, USA;(4) Rutgers, the State University of New Jersey, Newark, NJ 07102, USA |
| |
Abstract: | The k Nearest Neighbor (kNN) join operation associates each data object in one data set with its k nearest neighbors from the same or a different data set. The kNN join on high-dimensional data (high-dimensional kNN join) is a very expensive operation. Existing high-dimensional kNN join algorithms were designed for static data sets and therefore cannot handle updates efficiently. In this article, we propose a novel kNN join method, named kNNJoin +, which supports efficient incremental computation of kNN join results with updates on high-dimensional data. As a by-product, our method also provides answers for the reverse kNN queries with very little overhead. We have performed an extensive experimental study. The results show the effectiveness of kNNJoin+ for processing high-dimensional kNN joins in dynamic workloads. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|