k Nearest Neighbor Similarity Join Algorithm on High-Dimensional Data Using Novel Partitioning Strategy
Open Access
- 26 April 2022
- journal article
- research article
- Published by Wiley in Security and Communication Networks
- Vol. 2022, 1-16
Abstract
nearest neighbor similarity join on high-dimensional data has broad applications in many fields; several key challenges still exist for this task such as “curse of dimensionality” and large scale of the dataset. A new dimensionality reduction scheme is proposed by using random projection technique, then we design two novel partition strategies, including equal width partition strategy and distance split tree-based partition strategy, and finally, we propose nearest neighbor join algorithm on high-dimensional data based on the above partition strategies. We conduct comprehensive experiments to test the performance of the proposed approaches, and the experimental results show that the proposed methods have good effectiveness and performance.Keywords
Funding Information
- Science and Technology Research Plan Project of Henan Province (202102210357, 22IRTSTHN016, 61602231, JP21K17737, 2021CFB156)
- University of Henan Province (202102210357, 22IRTSTHN016, 61602231, JP21K17737, 2021CFB156)
- National Natural Science Foundation of China (202102210357, 22IRTSTHN016, 61602231, JP21K17737, 2021CFB156)
- Japan Society for the Promotion of Science (202102210357, 22IRTSTHN016, 61602231, JP21K17737, 2021CFB156)
- Hubei Natural Science Foundation (202102210357, 22IRTSTHN016, 61602231, JP21K17737, 2021CFB156)
This publication has 56 references indexed in Scilit:
- K Nearest Neighbour Joins for Big Data on MapReduce: A Theoretical and Experimental AnalysisIEEE Transactions on Knowledge and Data Engineering, 2016
- Scalable Algorithms for Nearest-Neighbor Joins on Big Trajectory DataIEEE Transactions on Knowledge and Data Engineering, 2015
- Parallel similarity joins on massive high‐dimensional data using MapReduceConcurrency and Computation: Practice and Experience, 2015
- Heads-Join: Efficient Earth Mover's Distance Similarity Joins on HadoopIEEE Transactions on Parallel and Distributed Systems, 2015
- Solutions for Processing K Nearest Neighbor Joins for Massive Data on MapReduce2015
- MELODY-JOIN: Efficient Earth Mover's Distance similarity joins using MapReduce2014
- A novel KNN join algorithms based on Hilbert R-tree in MapReduce2013
- Efficient processing of k nearest neighbor joins using MapReduceProceedings of the VLDB Endowment, 2012
- Parallel Top-K Similarity Join Algorithms Using MapReduce2012
- Bitmap Filtering: An Efficient Speedup Method for XML Structural Matching2007