High-dimensional kNN joins with incremental updates
Source: GeoInformatica, Volume 14, Number 1, January 2010 , pp. 55-82(28)
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.
Document Type: Research Article
Affiliations: 1: Monmouth University, West Long Branch, NJ, 07764, USA, Email: email@example.com 2: University of Melbourne, Carlton, Victoria, 3053, Australia, Email: firstname.lastname@example.org 3: University of Texas - Dallas, Dallas, TX, 75080, USA, Email: email@example.com 4: Rutgers, the State University of New Jersey, Newark, NJ, 07102, USA, Email: firstname.lastname@example.org
Publication date: January 1, 2010