# k Nearest Neighbor Similarity Join Algorithm on High-Dimensional Data Using Novel Partitioning Strategy

Authors: Youzhong Ma; Qiaozhi Hua; Zheng Wen; Ruiling Zhang; Yongxin Zhang; Haipeng Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

k 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 k 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.


---

## Body

## 1. Introduction

With the rapid development of emerging technologies such as big data [1, 2], Internet of things [3, 4], Deep Learning [5, 6], Adversarial Training [7, 8], Federated Learning [9], and 5G [10–12], the smart healthcare systems are becoming more and more pervasive and necessary in modern hospitals, and massive and diverse medical data have been accumulated by using a great volume of wearable sensors, the Internet of Medical Things [13, 14], or the Internet of Health Things [15, 16]. Medical data analysis, security, and privacy protection [17] are very important for using massive medical data. Many research works have been done, which can be used as the references to analyze the medical data and secure the Internet of Medical Things, such as the blockchain-based security approaches [18, 19], the security technologies in Internet of Internet of Vehicles [20, 21], Industrial Internet of Things [22–25], Artificial Intelligence of Things [26–28], Energy Internet [29], and Intelligent transportation [30, 31]. Similarity join operation plays an important role in medical data analysis [32, 33]. Threshold-based similarity join query on high-dimensional data can obtain all the data pairs whose distance is less than or equal to the given distance threshold, and it needs to know the distance threshold in advance; however, in many cases, it is hard or even impossible to get the distance threshold in advance, while k nearest neighbor similarity join (k NNJ) does not need to obtain the distance threshold in advance. k NNJ is always used as the preprocessing stage for classification or clustering task and has broad real applications in many data mining tasks, such as multimedia analysis, spatial data mining, time series, data streams, and social network. Taking similar medical image pairs detection as an example, in some cases, it is hard to make a definite diagnosis according to the medical images only; however, it is possible for us to obtain some similar medical images of the existed confirmed cases (k nearest neighbors) to help the doctors to make a final judgement on the unconfirmed diseases.In many applications, the target objects can be represented as vector forms through feature extraction in order to facilitate data processing, such as time series, videos, and trajectories, especially for the image processing tasks [34, 35]. With the continuous improvement of the accuracy of data acquisition equipment, the dimensionality of vectors representing the target objects will be very high, maybe hundreds of dimensions or even tens of thousands of dimensions. The calculation of the similarity or distance between the object pairs is a time costly operation. Most of the existed approaches conduct k NN join operation directly on the original dimensional space, so their performance is not ideal. It is an effective way to reduce the time cost of k NN join through reducing the dimensionality of the original data points. There are three contributions in the paper:(i)
We proposed an effective dimensionality reduction approach that can make sure that the data points in the projected space preserve the location relationship to some extent as in the original space.(ii)
We proposed two partition strategies, including equal width partition strategy and distance split tree-based partition strategy, and a novelk nearest neighbor join algorithm was proposed by using the above two partition strategies.(iii)
Comprehensive experiments are conducted, and the final results prove that our approaches have better effectiveness and performance.The other parts of the paper are arranged as follows. The detailed related research works are described in Section2. Section 3 displays the notations, problem definitions, and some theorems. The lower bound probability is figured out in Section 4. The k nearest neighbor join algorithm using random projection and partition strategies is described in Section 5. The detailed experimental results of the proposed approaches are displayed in Section 6. Section 7 makes a conclusion of the paper and points out the future research directions.


## 2. Related Works

Many researchers have conducted in-depth research on similarity join problems because of their broad applications and important role in data mining or machine learning context; several survey articles have conducted a comprehensive and detailed analysis of the similarity join problem literature [36, 37].k nearest neighbor join: an approximated k NN similarity join approach in metric spaces was proposed by Ferrada et al. [38], its time complexity is Θn3/2, and the empirical precision can reach up to 46%. Lu et al. [39] designed a novel approach called PCBJ by using Voronoi diagram, which can deal with exact k NN similarity join problems; however, its performance is not very good as the increase of data dimensionality. Dai et al. [40] proposed two novel k NN join algorithms based on the MapReduce framework, which are DSGMP-J using Distributed Sketched Grid and VDMP-J using Voronoi diagram; DSGMP-J [40] approach is easy to implement, but it ignores the real distribution of the dataset. Zhao et al. [41] designed an effective data partitioning scheme called k NN-DP, which can solve the load imbalance issues caused by the data skewness problem; two novel schemes called LSH+ and z-value+ were developed based on k NN-DP to deal with k NN join operations under MapReduce framework. Song et al. [42] conducted a detailed analysis of the common workflows of the several existing k NN algorithms and further analyzed their load balancing, accuracy rate, and overall complexity; finally, a choice guideline was given which can help select the suitable methods for a specific case. Song et al. [43] also conducted a detailed comparison among the existing k NN join approaches both theoretically and experimentally on the MapReduce platform. RankReduce approach [44] was proposed by using locality-sensitive hashing with MapReduce for processing k nearest neighbor query. Hu et al. [45] proposed an adaptive vk NN join algorithm by using the Voronoi diagram, which can eliminate many unnecessary computations. There still exist many other research works about k NN join problems in several applications, such as Trajectory Data [46], machine learning [47], and Hilbert R-tree-based k NN join algorithms [48].Top-k similarity join: Kim et al. [49] proposed two serial algorithms called the “divide-and-conquer algorithm” and “branch-and-bound algorithm” using the MapReduce framework, which can deal with Top-k similarity join problems efficiently. Chen et al. [50] developed a new distance function based on LSH and proposed an RDD-based Top-k similarity join algorithm using the Spark framework, and the test results proved that the RDD-based algorithm has better scalability and effectiveness than that of Hadoop. Ma et al. [51] developed a Top-k threshold estimation approach through sampling and designed an effective filtering solution by using the Symbolic Aggregate Approximation technique and then proposed a SAX-Top-k algorithm, which can deal with Top-k similarity join problem. Lei et al. [52] explored the similarity join problems for massive probabilistic dataset. The main idea of Lei et al. [52] is mapping the probabilistic data from the original space to the reduced dimensional space (one dimension), and then the range query on the one-dimensional space can be instead of the threshold-based similarity join query on the original space. Based on the above schemes, the authors proposed the Top-k Block Nested Loop Join Algorithm and Top-k Data Locality Preserving Join Algorithm, respectively. MELODY-JOIN [53] can improve the efficiency of the Top-k join on the histogram probabilistic dataset by using the standard lower bound space of the EMD distance; however, it cannot deal with the data skew problem efficiently. EMD-MPJ [54] proposed a novel Mapping-based Data Partitioning Framework that can solve the data skew problem. Heads-Join [55] made an extension to MELODY-JOIN [53] so that it can deal with both range similarity join and Top-k similarity efficiently.Threshold-based similarity join: Cristiani et al. [56] designed a novel randomized set join method whose recall can be up to 100%, and its performance is better than that of the existing approach theoretically and empirically. Gowanlock et al. [57] proposed several novel methods to accelerate the similarity self-join by making full use of the power and characteristic of GPU. There still exist some other research works which focus on the similarity join problem using GPU [58]. Sandes et al. [59] developed a novel filtering scheme that can speed up the exact set similarity join more efficiently. Ding et al. [60] exploited the privacy preserving problems in similarity join using MapReduce context. Wu et al. [61] proposed a novel parallel framework called SMS-Join which can support similarity join operations in metric space using the MapReduce paradigm. Ma et al. studied the similarity join problems for high-dimensional dataset through developing a novel dimension reduction approach based on the Piecewise Aggregate Approximation technique and proposed two algorithms called SAX-Based HDSJ [62] and Mp-V-SJQ [63].


## 3. Preliminaries

### 3.1. Notations

The notations used in this paper are listed in Table1.Table 1
Notations.
NotationMeaning of the notationn1,n2The data points’ number in the dataset.ϵThe width of each partition under equal width partition strategy.dThe data point’s dimensionality.dists1,s2The Euclidean distance of data points1 and data point s2.gsgs=a⋅s, a is a d-dimensional vector, and each element is a random variable that obeys p-stable distribution.πmsπms=g1s,g2s,…,gms.Δms1,s2Δms1,s2=distπms1,πms2.χ2mChi-square distribution with degree of freedomm.π1sminThe minimum projected value of data point s.π1smaxThe maximum projected value of data point s.lenThe width of all the projected values in one-dimensional space; that is,π1smin−π1smax.PNThe number of the partitions in one-dimensional space.PiTheith partition.


### 3.2. Problem Definition

The definitions of KNN and KNN join will be described in this subsection. Given two datasetsR∈ℜd and S∈ℜd, R=r1,r2,…,rn1, S=s1,s2,…,sn2, R=n1, and S=n2. ri is the ith data point from R, ri=ri1,ri2,…,rid,sj is the jth data point from S, sj=sj1,sj2,…,sjd, and the distance measurement used in the paper is the Euclidean distance denoted as distri,sj,(1)distri,sj=∑l=1dril−sjl2,where distri,sj>=0 and distri,sj equals 0 when r=s.Definition 1.
K Nearest Neighbor Join (KNN). For ad-dimensional datasetS∈ℜdand a query data pointr, the KNN operation ofronScan be recorded asknnr,S,kaiming to obtain theknearest neighbors ofrinS:
knnr,S,k=s1,s2,…,sk|si∈S,1≤i≤k; for each∀sj∈S−s1,s2,…,sk|si∈S,1≤i≤k, the distance meets the following requirements:
distr,s1≤distr,s2≤⋯≤distr,sk≤distr,sj.Definition 2.
K Nearest Neighbor Similarity Join (KNN Join). Given two datasetsR∈ℜdandS∈ℜd, the KNN similarity join operation on R and S can return theknearest neighbors for each data pointr∈Rfrom S, which can be denoted asknnJRS=r,knnr,S,k|for eachr∈R.


### 3.3. Theorems

Theorem 1.
Given twod-dimensional data pointss1ands2, thengs1−gs2/dists1,s2∼N0,1.Theorem 2.
Given twod-dimensional data pointss1ands2, thenΔm2s1,s2/dist2s1,s2∼χ2m.Theorem 3.
Ifdists1,s2≤ϵ, then the probability thatΔms1,s2is less than or equal tokϵwill be bigger than or equal to1−Pχ2>k2, which can be denoted as follows:PΔms1,s2≤|kϵdists1,s2≤ϵ≥1−Pχ2>k2.Theorem1, Theorem 2, and Theorem 3 have been proved by Ma et al. [64]. Theorem 3 indicates that if the Euclidean distance of the original space is less than or equal to ϵ, the probability that the distance of the projected space will be less than or equal to kϵ has the lower bound; that is, 1−Pχ2>k2. So we can project d-dimensional data point v into m-dimensional space m<d through πms=g1s,g2s,…,gms.Theorem 4.
Given threed-dimensional data pointsr,s1, ands2,r,s1,s2∈ℜd,U=Δm2r,s1/dist2r,s1∼χ2m,V=Δm2r,s2/dist2r,s2∼χ2m, and thenF=U/Vobeys the F distribution with degrees of freedom (m,m); that is,F=U/V∼Fm,m.Proof.
According to Theorem2, U=Δm2r,s1/dist2r,s1∼χ2m, and V=Δm2r,s2/dist2r,s2∼χ2m; that is to say, U and V both obey the χ2 distribution with freedom m.
Based on the definition of F distribution,F=U/m/V/m obeys the F distribution with degrees of freedom (m,m); that is, F=U/V∼Fm,m. □Theorem 5.
Ifdistr,s1≤distr,s2, then the probability thatΔmr,s1≤kΔmr,s2is bigger than 1-PF>k2; that is,PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2>1−PF>k2. F is the distribution with degrees of freedom (m,m); that is,F∼Fm,m.Proof.
(2)∵Δmr,s1≥0andΔmr,s2≥0,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2=PΔm2r,s1≤k2Δm2r,s2|distr,s1≤distr,s2=PΔm2r,s1dist2r,s1≤k2Δm2r,s2dist2r,s1|distr,s1≤distr,s2=PΔm2r,s1/dist2r,s1≤k2Δm2r,s2/dist2r,s1anddistr,s1≤distr,s2distr,s1≤distr,s2,∵Pdistr,s1≤distr,s2=1,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2=PΔm2r,s1dist2r,s1≤k2Δm2r,s2dist2r,s1=1−PΔm2r,s1dist2r,s1>k2Δm2r,s2dist2r,s1,∵Δm2r,s1dist2r,s1∼χ2manddistr,s1≤distr,s2,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2>1−PΔm2r,s1dist2r,s1>k2Δm2r,s2dist2r,s2=1−PΔm2r,s1/dist2r,s1Δm2r,s2/dist2r,s2>k2,according to theorem4,Δm2r,s1/dist2r,s1Δm2r,s2/dist2r,s2∼Fm,m,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distq,v2>1−PF>k2.According to Theorem5, when k = 1, if distr,s1≤distr,s2, then PΔmr,s1≤Δmr,s2|distr,s1≤distr,s2>1−PFm,m>1; it indicates that the probability that Δmr,s1≤Δmr,s2 has the lower bound: 1−PFm,m>1.We can conclude that ifs1 is closer to r than s2 in the original d-dimensional space, πms1 is still likely to be closer to πmr than πms2 in the projected m-dimensional space with lower bound probability 1−PFm,m>1.


## 3.1. Notations

The notations used in this paper are listed in Table1.Table 1
Notations.
NotationMeaning of the notationn1,n2The data points’ number in the dataset.ϵThe width of each partition under equal width partition strategy.dThe data point’s dimensionality.dists1,s2The Euclidean distance of data points1 and data point s2.gsgs=a⋅s, a is a d-dimensional vector, and each element is a random variable that obeys p-stable distribution.πmsπms=g1s,g2s,…,gms.Δms1,s2Δms1,s2=distπms1,πms2.χ2mChi-square distribution with degree of freedomm.π1sminThe minimum projected value of data point s.π1smaxThe maximum projected value of data point s.lenThe width of all the projected values in one-dimensional space; that is,π1smin−π1smax.PNThe number of the partitions in one-dimensional space.PiTheith partition.


## 3.2. Problem Definition

The definitions of KNN and KNN join will be described in this subsection. Given two datasetsR∈ℜd and S∈ℜd, R=r1,r2,…,rn1, S=s1,s2,…,sn2, R=n1, and S=n2. ri is the ith data point from R, ri=ri1,ri2,…,rid,sj is the jth data point from S, sj=sj1,sj2,…,sjd, and the distance measurement used in the paper is the Euclidean distance denoted as distri,sj,(1)distri,sj=∑l=1dril−sjl2,where distri,sj>=0 and distri,sj equals 0 when r=s.Definition 1.
K Nearest Neighbor Join (KNN). For ad-dimensional datasetS∈ℜdand a query data pointr, the KNN operation ofronScan be recorded asknnr,S,kaiming to obtain theknearest neighbors ofrinS:
knnr,S,k=s1,s2,…,sk|si∈S,1≤i≤k; for each∀sj∈S−s1,s2,…,sk|si∈S,1≤i≤k, the distance meets the following requirements:
distr,s1≤distr,s2≤⋯≤distr,sk≤distr,sj.Definition 2.
K Nearest Neighbor Similarity Join (KNN Join). Given two datasetsR∈ℜdandS∈ℜd, the KNN similarity join operation on R and S can return theknearest neighbors for each data pointr∈Rfrom S, which can be denoted asknnJRS=r,knnr,S,k|for eachr∈R.


## 3.3. Theorems

Theorem 1.
Given twod-dimensional data pointss1ands2, thengs1−gs2/dists1,s2∼N0,1.Theorem 2.
Given twod-dimensional data pointss1ands2, thenΔm2s1,s2/dist2s1,s2∼χ2m.Theorem 3.
Ifdists1,s2≤ϵ, then the probability thatΔms1,s2is less than or equal tokϵwill be bigger than or equal to1−Pχ2>k2, which can be denoted as follows:PΔms1,s2≤|kϵdists1,s2≤ϵ≥1−Pχ2>k2.Theorem1, Theorem 2, and Theorem 3 have been proved by Ma et al. [64]. Theorem 3 indicates that if the Euclidean distance of the original space is less than or equal to ϵ, the probability that the distance of the projected space will be less than or equal to kϵ has the lower bound; that is, 1−Pχ2>k2. So we can project d-dimensional data point v into m-dimensional space m<d through πms=g1s,g2s,…,gms.Theorem 4.
Given threed-dimensional data pointsr,s1, ands2,r,s1,s2∈ℜd,U=Δm2r,s1/dist2r,s1∼χ2m,V=Δm2r,s2/dist2r,s2∼χ2m, and thenF=U/Vobeys the F distribution with degrees of freedom (m,m); that is,F=U/V∼Fm,m.Proof.
According to Theorem2, U=Δm2r,s1/dist2r,s1∼χ2m, and V=Δm2r,s2/dist2r,s2∼χ2m; that is to say, U and V both obey the χ2 distribution with freedom m.
Based on the definition of F distribution,F=U/m/V/m obeys the F distribution with degrees of freedom (m,m); that is, F=U/V∼Fm,m. □Theorem 5.
Ifdistr,s1≤distr,s2, then the probability thatΔmr,s1≤kΔmr,s2is bigger than 1-PF>k2; that is,PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2>1−PF>k2. F is the distribution with degrees of freedom (m,m); that is,F∼Fm,m.Proof.
(2)∵Δmr,s1≥0andΔmr,s2≥0,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2=PΔm2r,s1≤k2Δm2r,s2|distr,s1≤distr,s2=PΔm2r,s1dist2r,s1≤k2Δm2r,s2dist2r,s1|distr,s1≤distr,s2=PΔm2r,s1/dist2r,s1≤k2Δm2r,s2/dist2r,s1anddistr,s1≤distr,s2distr,s1≤distr,s2,∵Pdistr,s1≤distr,s2=1,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2=PΔm2r,s1dist2r,s1≤k2Δm2r,s2dist2r,s1=1−PΔm2r,s1dist2r,s1>k2Δm2r,s2dist2r,s1,∵Δm2r,s1dist2r,s1∼χ2manddistr,s1≤distr,s2,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distr,s2>1−PΔm2r,s1dist2r,s1>k2Δm2r,s2dist2r,s2=1−PΔm2r,s1/dist2r,s1Δm2r,s2/dist2r,s2>k2,according to theorem4,Δm2r,s1/dist2r,s1Δm2r,s2/dist2r,s2∼Fm,m,∴PΔmr,s1≤kΔmr,s2|distr,s1≤distq,v2>1−PF>k2.According to Theorem5, when k = 1, if distr,s1≤distr,s2, then PΔmr,s1≤Δmr,s2|distr,s1≤distr,s2>1−PFm,m>1; it indicates that the probability that Δmr,s1≤Δmr,s2 has the lower bound: 1−PFm,m>1.We can conclude that ifs1 is closer to r than s2 in the original d-dimensional space, πms1 is still likely to be closer to πmr than πms2 in the projected m-dimensional space with lower bound probability 1−PFm,m>1.


## 4. Probability Computation

Whenm=1,k=1, the probability PFm,m>1 can be figured out based on the probability density of F distribution which is described as follows:(3)ψy=Γn1+n2/2n1/n2n1/2yn1/2−1Γn1/2Γn2/21+n1y/n2n1+n2/2,y>0,0,other.Given the freedom (1,1) and the upper quantile with 1, the probabilityPFm,m>1 can be calculated as the follows:(4)PF>1=∫1∞ψydy,=∫1∞Γ1+1/21/11/2y1/2−1Γ1/2Γ1/21+y1+1/2dy=∫1∞Γ1y−1/2Γ1/221+ydy∵Γ1=1,Γ1/2=π∴PF>1=∫1∞y−1/2π21+ydy=1π∫1∞1y1+ydy=2π∫1∞11+y2dy=2πarctany|1∞=2ππ2−π4=0.5.The result of the above computation shows that, given threed-dimensional data points r,s1, and s2, r,s1,s2∈ℜd, they can be reduced to 1-dimensional space through dot product with a d-dimensional vector a. If s1 is closer to r than s2 in the original d-dimensional space, the lower bound probability that π1s1 is still likely to be closer to π1r than π1s2 in the projected 1-dimensional space is 0.5.


## 5.k Nearest Neighbor Join Using Novel Partitioning Strategy

### 5.1. Algorithm fork Nearest Neighbor Join Using Novel Partitioning Strategy

Theorem5 shows that if s1 is closer to r than s2 in the original d-dimensional space, πms1 is still likely to be closer to πmr than πms2 in the projected m-dimensional space with the lower bound probability 1−PFm,m>1. The conclusion implies that data points in projected space maintain relative location relationship as in original dimensional space. So we proposed k nearest neighbor join algorithm using random projection (RP k NN); it includes two main stages: the first stage is responsible for dimension reduction and space partition, and the second stage is used to conduct k NN join in reduced dimensional space. Figure 1 shows the general framework of k nearest neighbor similarity join algorithm using novel partitioning strategy. The concrete process of the proposed algorithm is described in Algorithm 1. The getPartition routine projects all the data points into one-dimensional space and divides the data points into several partitions according to the specific partition strategy (line 1). For each partition Pi, its corresponding partition Pi¯, which needs to be compared with Pi, can be obtained through lines 3–9. If Pi is the leftmost partition, Pi¯←∪Pi∪Pi+1 (line 5). If Pi is the rightmost partition, Pi¯←∪Pi−1∪Pi (line 7); in other cases, Pi¯←Pi−1∪Pi∪Pi+1 (line 9). Finally, for each data point v∈Pi, k NN join routine is used to find its k nearest neighbors from Pi¯ (lines 10–12).Figure 1
Framework ofk nearest neighbor join algorithm using novel partitioning strategy.Algorithm 1: Algorithm for k nearest neighbor join using novel partitioning strategy.
Input:R, k //dataset, the number of nearest neighbors to findOutput:res //a set of pairs of data points(1)
partitions←get PartitionR,n;(2)
res←∅;(3)
fori=1;i≤partitions;i++ do(4)
ifi = = 1 then(5)
Pi¯⟵∪Pi∪Pi+1(6)
else ifi = =  partitions then(7)
Pi¯⟵∪Pi−1∪Pi(8)
else(9)
Pi¯⟵Pi−1∪Pi∪Pi+1(10)
fordata pointv∈Pi do(11)
temp←kNNJoink,v,Pi¯(12)
res←res∪temp(13)
return res.


### 5.2. Partition Strategy

#### 5.2.1. Equal Width Partition Strategy

All the data points are divided into several partitions with equal width. The total partition number can be set toPN=n. Suppose that π1smin is the minimum projected value of s in one-dimensional space and π1smax is the maximum projected value of s in one-dimensional space; that is π1smin=minπ1sj,sj∈R and π1smax=maxπ1sj,sj∈R; len is the width of all the projected values in one-dimensional space, len=π1smin−π1smax; ϵ is the width of each partition, ϵ=⌊len/PN⌋; given a data point s, its corresponding partition number is Pi=⌊π1s/ϵ⌋. The detailed procedure can be shown in Figure 2 and Algorithm 2.Figure 2
Equal width partition strategy.Algorithm 2: Equal width partition strategy.
Input:R, n //dataset, the cardinality of the datasetOutput:partitions //list of the sets that partition the dataset(1)
PN=n(2)
partitionsi←∅,∀i,0≤i≤PN(3)
π1smin=minπ1sj,sj∈R(4)
π1smax=maxπ1sj,sj∈R(5)
len=π1smin−π1smax(6)
ϵ=⌊len/PN⌋(7)
choose one vector randomly, recorded asa,∀e∈a∼N0,1(8)
//divideR¯ into PN partitions according to Pi, the data points which have the same Pi.(9)
//belong to the same partition, recorded aspartitions1,partitions2⋯,partitionsPN.(10)
for eachdata points∈R do(11)
π1s⟵g1s(12)
Pi=⌊π1s/ϵ⌋(13)
partitionsPi←Pi,π1s,s


#### 5.2.2. Distance Split Tree-Based Partition Strategy

The previous equal width partition strategy is easy to implement; however, it cannot deal with skewed dataset efficiently. According to our proposed approach, thed-dimensional data point s will be projected into one-dimensional space through π1s=g1s=v⋅a=∑i=1dsi∗ai; each element of a obeys standard normal distribution; that is: ai∼N0,1,i∈1,d. The projected value π1s is subject to normal distribution, so it is skewed. Figure 3 shows the distribution of the projected values.Figure 3
The distribution of the projected valuesπ1s: (a) dim = 128 and data science = 30000; (b) dim = 256 and data science = 30000; (c) dim = 512 and data science = 30000; (d) dim = 1024 and data science = 30000.
(a)(b)(c)(d)Theorem 6.
Given twod-dimensional data pointssanda,ai∼N0,1,i∈1,d,π1s=g1s=s⋅a=∑i=1dsi∗ai, and thenπ1s∼N0,∑i=1dsi2.Proof.
(5)∵ai∼N0,1,⇒siai∼N0,si2,∵π1s=∑i=1dsi∗ai,∴π1s∼N0,∑i=1dsi2,⇒π1sis subject to normal distribution and its variance is∑i=1dsi2.
Aiming to deal with the data skew problem, we proposed a novel partition strategy called distance split tree- (DST-) based partition strategy. Figure4 displays the structure of DST. The main idea of DST is that after the original d-dimensional data points are mapped into one-dimensional space, in the beginning, all the data points are divided into equal width partitions with threshold ϵ=π1smax−π1smin/2c, c is an adjustable parameter. max Num is the upper bound of data point count contained in each partition. Once the data point count in a specific partition exceeds max Num, the partition will be divided into two new partitions with equal width again and so on, and finally, a distance split tree is formed. For each leaf node, the level of the node’s hierarchy, the node number in the specific level, the count of the data, and the corresponding dataset are recorded. Based on the above information, the distance range corresponding to each leaf node can be calculated. The corresponding distance width of each node in the current level can be calculated: 1/2level−1ϵ. The corresponding distance range of the node can be calculated by orderNo in the level order No−1/2level−1ϵ,order No/2level−1ϵ. Thus, the distance range corresponding to the N2 node can be calculated: 3−1/23−1ϵ,3/23−1ϵ; that is, 2/4ϵ,3/4ϵ.
The construction of distance split tree: the construction process of the distance split tree is as follows: firstly, build a root nodeNroot, for each data point si∈R, and figure out its projected value in one-dimensional space π1si. Then all the data points are divided into equal width partitions with threshold ϵ, and the corresponding partition number of each vector si in the mapping space is obtained pid←⌊π1si/ϵ⌋. If the node with the number pid does not exist, a new child node with the number pid will be generated. If it already exists, si is inserted into the node pid, and its count value is increased by 1. Once the amount of data point in a node exceeds a given threshold, such as maxNum, the node will be further divided into two subnodes according to the distance range. Repeat this procedure, and finally, a distance split tree is generated.
Data partitions generated: after the distance split tree is constructed, the partitions set can be obtained through preorder traversal for distance split tree; only the leaf nodes are left as the member of the final partitions set. Then the obtained partitions set can be used in Algorithm 1.Figure 4
Distance split tree-based partition strategy.


## 5.1. Algorithm fork Nearest Neighbor Join Using Novel Partitioning Strategy

Theorem5 shows that if s1 is closer to r than s2 in the original d-dimensional space, πms1 is still likely to be closer to πmr than πms2 in the projected m-dimensional space with the lower bound probability 1−PFm,m>1. The conclusion implies that data points in projected space maintain relative location relationship as in original dimensional space. So we proposed k nearest neighbor join algorithm using random projection (RP k NN); it includes two main stages: the first stage is responsible for dimension reduction and space partition, and the second stage is used to conduct k NN join in reduced dimensional space. Figure 1 shows the general framework of k nearest neighbor similarity join algorithm using novel partitioning strategy. The concrete process of the proposed algorithm is described in Algorithm 1. The getPartition routine projects all the data points into one-dimensional space and divides the data points into several partitions according to the specific partition strategy (line 1). For each partition Pi, its corresponding partition Pi¯, which needs to be compared with Pi, can be obtained through lines 3–9. If Pi is the leftmost partition, Pi¯←∪Pi∪Pi+1 (line 5). If Pi is the rightmost partition, Pi¯←∪Pi−1∪Pi (line 7); in other cases, Pi¯←Pi−1∪Pi∪Pi+1 (line 9). Finally, for each data point v∈Pi, k NN join routine is used to find its k nearest neighbors from Pi¯ (lines 10–12).Figure 1
Framework ofk nearest neighbor join algorithm using novel partitioning strategy.Algorithm 1: Algorithm for k nearest neighbor join using novel partitioning strategy.
Input:R, k //dataset, the number of nearest neighbors to findOutput:res //a set of pairs of data points(1)
partitions←get PartitionR,n;(2)
res←∅;(3)
fori=1;i≤partitions;i++ do(4)
ifi = = 1 then(5)
Pi¯⟵∪Pi∪Pi+1(6)
else ifi = =  partitions then(7)
Pi¯⟵∪Pi−1∪Pi(8)
else(9)
Pi¯⟵Pi−1∪Pi∪Pi+1(10)
fordata pointv∈Pi do(11)
temp←kNNJoink,v,Pi¯(12)
res←res∪temp(13)
return res.


## 5.2. Partition Strategy

### 5.2.1. Equal Width Partition Strategy

All the data points are divided into several partitions with equal width. The total partition number can be set toPN=n. Suppose that π1smin is the minimum projected value of s in one-dimensional space and π1smax is the maximum projected value of s in one-dimensional space; that is π1smin=minπ1sj,sj∈R and π1smax=maxπ1sj,sj∈R; len is the width of all the projected values in one-dimensional space, len=π1smin−π1smax; ϵ is the width of each partition, ϵ=⌊len/PN⌋; given a data point s, its corresponding partition number is Pi=⌊π1s/ϵ⌋. The detailed procedure can be shown in Figure 2 and Algorithm 2.Figure 2
Equal width partition strategy.Algorithm 2: Equal width partition strategy.
Input:R, n //dataset, the cardinality of the datasetOutput:partitions //list of the sets that partition the dataset(1)
PN=n(2)
partitionsi←∅,∀i,0≤i≤PN(3)
π1smin=minπ1sj,sj∈R(4)
π1smax=maxπ1sj,sj∈R(5)
len=π1smin−π1smax(6)
ϵ=⌊len/PN⌋(7)
choose one vector randomly, recorded asa,∀e∈a∼N0,1(8)
//divideR¯ into PN partitions according to Pi, the data points which have the same Pi.(9)
//belong to the same partition, recorded aspartitions1,partitions2⋯,partitionsPN.(10)
for eachdata points∈R do(11)
π1s⟵g1s(12)
Pi=⌊π1s/ϵ⌋(13)
partitionsPi←Pi,π1s,s


### 5.2.2. Distance Split Tree-Based Partition Strategy

The previous equal width partition strategy is easy to implement; however, it cannot deal with skewed dataset efficiently. According to our proposed approach, thed-dimensional data point s will be projected into one-dimensional space through π1s=g1s=v⋅a=∑i=1dsi∗ai; each element of a obeys standard normal distribution; that is: ai∼N0,1,i∈1,d. The projected value π1s is subject to normal distribution, so it is skewed. Figure 3 shows the distribution of the projected values.Figure 3
The distribution of the projected valuesπ1s: (a) dim = 128 and data science = 30000; (b) dim = 256 and data science = 30000; (c) dim = 512 and data science = 30000; (d) dim = 1024 and data science = 30000.
(a)(b)(c)(d)Theorem 6.
Given twod-dimensional data pointssanda,ai∼N0,1,i∈1,d,π1s=g1s=s⋅a=∑i=1dsi∗ai, and thenπ1s∼N0,∑i=1dsi2.Proof.
(5)∵ai∼N0,1,⇒siai∼N0,si2,∵π1s=∑i=1dsi∗ai,∴π1s∼N0,∑i=1dsi2,⇒π1sis subject to normal distribution and its variance is∑i=1dsi2.
Aiming to deal with the data skew problem, we proposed a novel partition strategy called distance split tree- (DST-) based partition strategy. Figure4 displays the structure of DST. The main idea of DST is that after the original d-dimensional data points are mapped into one-dimensional space, in the beginning, all the data points are divided into equal width partitions with threshold ϵ=π1smax−π1smin/2c, c is an adjustable parameter. max Num is the upper bound of data point count contained in each partition. Once the data point count in a specific partition exceeds max Num, the partition will be divided into two new partitions with equal width again and so on, and finally, a distance split tree is formed. For each leaf node, the level of the node’s hierarchy, the node number in the specific level, the count of the data, and the corresponding dataset are recorded. Based on the above information, the distance range corresponding to each leaf node can be calculated. The corresponding distance width of each node in the current level can be calculated: 1/2level−1ϵ. The corresponding distance range of the node can be calculated by orderNo in the level order No−1/2level−1ϵ,order No/2level−1ϵ. Thus, the distance range corresponding to the N2 node can be calculated: 3−1/23−1ϵ,3/23−1ϵ; that is, 2/4ϵ,3/4ϵ.
The construction of distance split tree: the construction process of the distance split tree is as follows: firstly, build a root nodeNroot, for each data point si∈R, and figure out its projected value in one-dimensional space π1si. Then all the data points are divided into equal width partitions with threshold ϵ, and the corresponding partition number of each vector si in the mapping space is obtained pid←⌊π1si/ϵ⌋. If the node with the number pid does not exist, a new child node with the number pid will be generated. If it already exists, si is inserted into the node pid, and its count value is increased by 1. Once the amount of data point in a node exceeds a given threshold, such as maxNum, the node will be further divided into two subnodes according to the distance range. Repeat this procedure, and finally, a distance split tree is generated.
Data partitions generated: after the distance split tree is constructed, the partitions set can be obtained through preorder traversal for distance split tree; only the leaf nodes are left as the member of the final partitions set. Then the obtained partitions set can be used in Algorithm 1.Figure 4
Distance split tree-based partition strategy.


## 5.2.1. Equal Width Partition Strategy

All the data points are divided into several partitions with equal width. The total partition number can be set toPN=n. Suppose that π1smin is the minimum projected value of s in one-dimensional space and π1smax is the maximum projected value of s in one-dimensional space; that is π1smin=minπ1sj,sj∈R and π1smax=maxπ1sj,sj∈R; len is the width of all the projected values in one-dimensional space, len=π1smin−π1smax; ϵ is the width of each partition, ϵ=⌊len/PN⌋; given a data point s, its corresponding partition number is Pi=⌊π1s/ϵ⌋. The detailed procedure can be shown in Figure 2 and Algorithm 2.Figure 2
Equal width partition strategy.Algorithm 2: Equal width partition strategy.
Input:R, n //dataset, the cardinality of the datasetOutput:partitions //list of the sets that partition the dataset(1)
PN=n(2)
partitionsi←∅,∀i,0≤i≤PN(3)
π1smin=minπ1sj,sj∈R(4)
π1smax=maxπ1sj,sj∈R(5)
len=π1smin−π1smax(6)
ϵ=⌊len/PN⌋(7)
choose one vector randomly, recorded asa,∀e∈a∼N0,1(8)
//divideR¯ into PN partitions according to Pi, the data points which have the same Pi.(9)
//belong to the same partition, recorded aspartitions1,partitions2⋯,partitionsPN.(10)
for eachdata points∈R do(11)
π1s⟵g1s(12)
Pi=⌊π1s/ϵ⌋(13)
partitionsPi←Pi,π1s,s


## 5.2.2. Distance Split Tree-Based Partition Strategy

The previous equal width partition strategy is easy to implement; however, it cannot deal with skewed dataset efficiently. According to our proposed approach, thed-dimensional data point s will be projected into one-dimensional space through π1s=g1s=v⋅a=∑i=1dsi∗ai; each element of a obeys standard normal distribution; that is: ai∼N0,1,i∈1,d. The projected value π1s is subject to normal distribution, so it is skewed. Figure 3 shows the distribution of the projected values.Figure 3
The distribution of the projected valuesπ1s: (a) dim = 128 and data science = 30000; (b) dim = 256 and data science = 30000; (c) dim = 512 and data science = 30000; (d) dim = 1024 and data science = 30000.
(a)(b)(c)(d)Theorem 6.
Given twod-dimensional data pointssanda,ai∼N0,1,i∈1,d,π1s=g1s=s⋅a=∑i=1dsi∗ai, and thenπ1s∼N0,∑i=1dsi2.Proof.
(5)∵ai∼N0,1,⇒siai∼N0,si2,∵π1s=∑i=1dsi∗ai,∴π1s∼N0,∑i=1dsi2,⇒π1sis subject to normal distribution and its variance is∑i=1dsi2.
Aiming to deal with the data skew problem, we proposed a novel partition strategy called distance split tree- (DST-) based partition strategy. Figure4 displays the structure of DST. The main idea of DST is that after the original d-dimensional data points are mapped into one-dimensional space, in the beginning, all the data points are divided into equal width partitions with threshold ϵ=π1smax−π1smin/2c, c is an adjustable parameter. max Num is the upper bound of data point count contained in each partition. Once the data point count in a specific partition exceeds max Num, the partition will be divided into two new partitions with equal width again and so on, and finally, a distance split tree is formed. For each leaf node, the level of the node’s hierarchy, the node number in the specific level, the count of the data, and the corresponding dataset are recorded. Based on the above information, the distance range corresponding to each leaf node can be calculated. The corresponding distance width of each node in the current level can be calculated: 1/2level−1ϵ. The corresponding distance range of the node can be calculated by orderNo in the level order No−1/2level−1ϵ,order No/2level−1ϵ. Thus, the distance range corresponding to the N2 node can be calculated: 3−1/23−1ϵ,3/23−1ϵ; that is, 2/4ϵ,3/4ϵ.
The construction of distance split tree: the construction process of the distance split tree is as follows: firstly, build a root nodeNroot, for each data point si∈R, and figure out its projected value in one-dimensional space π1si. Then all the data points are divided into equal width partitions with threshold ϵ, and the corresponding partition number of each vector si in the mapping space is obtained pid←⌊π1si/ϵ⌋. If the node with the number pid does not exist, a new child node with the number pid will be generated. If it already exists, si is inserted into the node pid, and its count value is increased by 1. Once the amount of data point in a node exceeds a given threshold, such as maxNum, the node will be further divided into two subnodes according to the distance range. Repeat this procedure, and finally, a distance split tree is generated.
Data partitions generated: after the distance split tree is constructed, the partitions set can be obtained through preorder traversal for distance split tree; only the leaf nodes are left as the member of the final partitions set. Then the obtained partitions set can be used in Algorithm 1.Figure 4
Distance split tree-based partition strategy.


## 6. Time Complexity Analysis

In this section, we mainly analyze the time complexity of our proposed method. Given thed-dimensional dataset R and R=n, the total partition number is PN=n,Pi represents the ith partition, and Cost represents the total computations of the proposed method. The time complexity is as the follows:(6)Cost=∑i=1PNPi∗Pi∪Pi−1∪Pi+1∗d.In the best cases, all the data points inR are evenly distributed in each partition; that is, Pi=n, so(7)Cost=∑i=1PNn∗3∗n∗d=n∗n∗3∗n∗d=3∗n3/2∗d.The time complexity in the best case can be recorded asOn3/2d.In the worst case, supposing that all the data points are included in one partition, then the time complexity should beOn2d. Because the projected values of the proposed method obey normal distribution, it is between the best case and the worst case, so the time complexity of the proposed method lies in On3/2d,On2d.


## 7. Experimental Analysis

We conducted experiments to test the effectiveness and performance of the proposed methods,k nearest neighbor join algorithm using random projection with equal width partition strategy (RP k NNEW) and k nearest neighbor join algorithm using random projection with distance split tree-based partition strategy (RP k NNDST), and made comparisons between our proposed methods and the existing methods including a KNN [38] and the brute force method with Block Nested Loop Join Strategy (BNLJ). a KNN [38] is a relatively new research work on k NN similarity join problem, and it also adopted the algorithms based on the partitioning strategy.Experimental settings: our tests are performed on HP workstation, and the configurations are as follows: CPU: Intel Xeon Gold 6136 @ 3.00 GHz, memory: 128 GB, disk: 2 TB, OS: 64-bit Windows 10, and 12 cores. Table2 describes the parameters and their values. The bold fonts represent the default values.Table 2
Experimental settings.
Experimental parametersValues of the parametersReturned number:k10, 20, 30, 40, and 50Dimensionality:d128, 256, 512, and 1024Data size:N10000, 20000, 30000, 40000, and 50000Datasets: the datasets adopted in our experiments are synthetic data, the elements of the vector are uniformly distributed in the range [0, 1], and the dimensionality of the datasets includes 128, 256, 512, and 1024. The datasets are listed in Table3.Table 3
Datasets descriptions.
DatasetNumberDim.Data size (M)Data-128-110,00012811.3Data-128-220,00012822.5Data-128-330,00012833.8Data-128-440,00012845Data-128-550,00012856.3Data-256-330,00025667.6Data-512-110,00051245Data-512-220,00051290Data-512-330,000512135.1Data-512-440,000512180.1Data-512-550,000512225.1Data-1024-330,000960270


### 7.1. Precision versus Data Size

It can be concluded that RPk NNEW has the best precision among the above three approaches, including a KNN, RP k NNEW, and RP k NNDST; in some cases, the precision of RP k NNEW is more than 50%. However, Figure 5 shows that the precision of a KNN, RP k NNEW, and RP k NNDST is not very stable for different data size, and the precision of RP k NNDST is between that of a KNN and RP k NNEW.Figure 5
Precision versus data size.


### 7.2. Precision versus Dimension

Figure6 displays the precision of a KNN, RP k NNEW, and RP k NNDST under different dimension. The proposed method RP k NNEW has the best precision; although the precision of RP k NNEW varies under different dimension, it is always higher than 40% under all conditions. The precision of RP k NNDST is relatively stable under different dimension, and it is lower than that of RP k NNEW. Because RP k NNDST adopts the distance tree-based partition strategy and all the data points will be distributed into different partitions more evenly, every partition will not contain much more data points, so its precision will decrease to some extent compared with RP k NNEW. The precision of our proposed methods, including RP k NNEW and RP k NNDST, is better than that of a KNN under all different dimension.Figure 6
Precision versus dimension.


### 7.3. Precision versusk

Figure7 displays the precision of the above approaches (including a KNN, RP k NNEW, and RP k NNDST) under different k. The results prove that the precision of RP k NNEW and RP k NNDST is higher than that of the existing method a KNN. The precision of RP k NNEW is higher than that of RP k NNDST; the reason is that RP k NNEW adopted the equal width partition strategy; while the projected values are skewed, several partitions will contain more data points; the precision will be higher accordingly. The precision of a KNN and RP k NNDST is basically stable under different k value, while the precision of RP k NNEW is a little more sensitive to the different k value.Figure 7
Precision versusk.


### 7.4. Precision Distribution

Figure8 displays the precision distribution of a KNN, RP k NNEW, and RP k NNDST. It can be found that the precision of some data points is very low (less than 5%), and the precision of some data points is very high (more than 80%) by using RP k NNEW. The average precision of RP k NNEW is higher than that of a KNN and RP k NNDST; the percentage of the data points whose precision is more than 80% is 20.6%, 0.05%, and 0.57%, respectively, for RP k NNEW, a KNN, and RP k NNDST. The main reason is that RP k NNEW adopts the equal width partition strategy, which cannot deal with the skewed projected values effectively; however, RP k NNDST adopts distance split tree-based partition strategy, which can distribute all the data points into different partitions more evenly.Figure 8
The distribution of the precision: (a) dim = 512, data size = 30000, and k = 30; (b) dim = 512, data size = 30000, and k = 30; (c) dim = 512, data size = 30000, and k = 30; (d) dim = 1024, data size = 30000, and k = 30.
(a)(b)(c)(d)


### 7.5. Performance versus Data Size

Figure9 displays the performance of BNLJ, a KNN, RP k NNEW, and RP k NNDST on the datasets with different size. The run time of a KNN, RP k NNEW, and RP k NNDST is much less than that of the BNLJ method; the run time of BNLJ increases exponentially with the size of the datasets; however, the run time of a KNN, RP k NNEW, and RP k NNDST increases linearly with the size of the datasets. The run time of RP k NNEW is a little bit more than that of a KNN and RP k NNDST. While we can find that RP k NNEW has the best precision among all the methods based on the above precision analysis, we can choose the RP k NNEW method when the performance requirements are not very strict; otherwise, RP k NNDST will be the most appropriate choice, because the precision of RP k NNDST is higher than that of a KNN, while its run time is less than that of RP k NNEW.Figure 9
Performance versus data size.


### 7.6. Performance versus Dimension

Figure10 displays the performance of our proposed methods and the existing methods for different dimensions, which are 128, 256, 512, and 1024, respectively. The time of all algorithms grows with the increase of the dimension, and the reason is the bigger the dimension, the higher the time complexity. The performance of RP k NNEW is the best when the dimension is less than 512, while the run time of RP k NNEW will be slightly higher than that of a KNN when the dimension exceeds 512. The run time of RP k NNEW is higher than that of a KNN and RP k NNEW, while Figure 6 shows that RP k NNEW has the best precision in all cases.Figure 10
Performance versus dimension.


### 7.7. Performance versusk

The performance of BNLJ,a KNN, RP k NNEW, and RP k NNDST with different k (data size = 30000; dim = 512) is displayed in Figure 11. The run time of all the above algorithms changes little with the different value of k. The run time of RP k NNDST is very close to that of a KNN, and the reason has been explained in Section 6; however, the precision of RP k NNDST is better than that of a KNN according to Figure 7. The run time of RP k NNDST and a KNN is less than that of RP k NNEW.Figure 11
Performance versusk.


### 7.8. Preprocessing Time

Figure12 displays the preprocessing time required by the construction of the distance split tree (DST) in RP k NNDST approach for different dataset. The preprocessing time increases almost linearly with the size of the dataset. Given a dataset with a fixed size, the preprocessing time increases exponentially with the growth of the dimension. Overall, the proportion of preprocessing time in the total time is low and relative stable. The benefit of the distance split tree (DST) can make up for the additional overhead caused by the construction of DST and can make the total run time of RP k NNDST less than that of RP k NNEW.Figure 12
Preprocessing time.


## 7.1. Precision versus Data Size

It can be concluded that RPk NNEW has the best precision among the above three approaches, including a KNN, RP k NNEW, and RP k NNDST; in some cases, the precision of RP k NNEW is more than 50%. However, Figure 5 shows that the precision of a KNN, RP k NNEW, and RP k NNDST is not very stable for different data size, and the precision of RP k NNDST is between that of a KNN and RP k NNEW.Figure 5
Precision versus data size.


## 7.2. Precision versus Dimension

Figure6 displays the precision of a KNN, RP k NNEW, and RP k NNDST under different dimension. The proposed method RP k NNEW has the best precision; although the precision of RP k NNEW varies under different dimension, it is always higher than 40% under all conditions. The precision of RP k NNDST is relatively stable under different dimension, and it is lower than that of RP k NNEW. Because RP k NNDST adopts the distance tree-based partition strategy and all the data points will be distributed into different partitions more evenly, every partition will not contain much more data points, so its precision will decrease to some extent compared with RP k NNEW. The precision of our proposed methods, including RP k NNEW and RP k NNDST, is better than that of a KNN under all different dimension.Figure 6
Precision versus dimension.


## 7.3. Precision versusk

Figure7 displays the precision of the above approaches (including a KNN, RP k NNEW, and RP k NNDST) under different k. The results prove that the precision of RP k NNEW and RP k NNDST is higher than that of the existing method a KNN. The precision of RP k NNEW is higher than that of RP k NNDST; the reason is that RP k NNEW adopted the equal width partition strategy; while the projected values are skewed, several partitions will contain more data points; the precision will be higher accordingly. The precision of a KNN and RP k NNDST is basically stable under different k value, while the precision of RP k NNEW is a little more sensitive to the different k value.Figure 7
Precision versusk.


## 7.4. Precision Distribution

Figure8 displays the precision distribution of a KNN, RP k NNEW, and RP k NNDST. It can be found that the precision of some data points is very low (less than 5%), and the precision of some data points is very high (more than 80%) by using RP k NNEW. The average precision of RP k NNEW is higher than that of a KNN and RP k NNDST; the percentage of the data points whose precision is more than 80% is 20.6%, 0.05%, and 0.57%, respectively, for RP k NNEW, a KNN, and RP k NNDST. The main reason is that RP k NNEW adopts the equal width partition strategy, which cannot deal with the skewed projected values effectively; however, RP k NNDST adopts distance split tree-based partition strategy, which can distribute all the data points into different partitions more evenly.Figure 8
The distribution of the precision: (a) dim = 512, data size = 30000, and k = 30; (b) dim = 512, data size = 30000, and k = 30; (c) dim = 512, data size = 30000, and k = 30; (d) dim = 1024, data size = 30000, and k = 30.
(a)(b)(c)(d)


## 7.5. Performance versus Data Size

Figure9 displays the performance of BNLJ, a KNN, RP k NNEW, and RP k NNDST on the datasets with different size. The run time of a KNN, RP k NNEW, and RP k NNDST is much less than that of the BNLJ method; the run time of BNLJ increases exponentially with the size of the datasets; however, the run time of a KNN, RP k NNEW, and RP k NNDST increases linearly with the size of the datasets. The run time of RP k NNEW is a little bit more than that of a KNN and RP k NNDST. While we can find that RP k NNEW has the best precision among all the methods based on the above precision analysis, we can choose the RP k NNEW method when the performance requirements are not very strict; otherwise, RP k NNDST will be the most appropriate choice, because the precision of RP k NNDST is higher than that of a KNN, while its run time is less than that of RP k NNEW.Figure 9
Performance versus data size.


## 7.6. Performance versus Dimension

Figure10 displays the performance of our proposed methods and the existing methods for different dimensions, which are 128, 256, 512, and 1024, respectively. The time of all algorithms grows with the increase of the dimension, and the reason is the bigger the dimension, the higher the time complexity. The performance of RP k NNEW is the best when the dimension is less than 512, while the run time of RP k NNEW will be slightly higher than that of a KNN when the dimension exceeds 512. The run time of RP k NNEW is higher than that of a KNN and RP k NNEW, while Figure 6 shows that RP k NNEW has the best precision in all cases.Figure 10
Performance versus dimension.


## 7.7. Performance versusk

The performance of BNLJ,a KNN, RP k NNEW, and RP k NNDST with different k (data size = 30000; dim = 512) is displayed in Figure 11. The run time of all the above algorithms changes little with the different value of k. The run time of RP k NNDST is very close to that of a KNN, and the reason has been explained in Section 6; however, the precision of RP k NNDST is better than that of a KNN according to Figure 7. The run time of RP k NNDST and a KNN is less than that of RP k NNEW.Figure 11
Performance versusk.


## 7.8. Preprocessing Time

Figure12 displays the preprocessing time required by the construction of the distance split tree (DST) in RP k NNDST approach for different dataset. The preprocessing time increases almost linearly with the size of the dataset. Given a dataset with a fixed size, the preprocessing time increases exponentially with the growth of the dimension. Overall, the proportion of preprocessing time in the total time is low and relative stable. The benefit of the distance split tree (DST) can make up for the additional overhead caused by the construction of DST and can make the total run time of RP k NNDST less than that of RP k NNEW.Figure 12
Preprocessing time.


## 8. Conclusions

In the above sections, we mainly studied thek nearest neighbor similarity join problem on high-dimensional data. We proposed k nearest neighbor join algorithm using random projection with equal width partition strategy (RP k NNEW) and k nearest neighbor join algorithm using random projection with distance split tree-based partition strategy (RP k NNDST), which can filter out many unnecessary comparisons and ensure the required precision. We also conducted several experiments to test the effectiveness and performance of our proposed approaches, and the test results show that the proposed approaches in this paper have better effectiveness and performance. However, the proposed approaches in this paper have some limitations, and they can only work with the Euclidean distance. In future research works, we are planning to further study the k NN similarity join approaches, which can deal with other similarity measures, other more effective dimension reduction techniques, and the distributed k nearest neighbor similarity join algorithms.



---

*Source: 1249393-2022-04-26.xml*