基于卡方分布的高维数据相似性连接查询算法

Chi-square distribution based similarity join query algorithm on high-dimensional data

为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题,基于p-稳态分布,将高维数据映射到低维空间。根据卡方分布的性质,证明了如果低维空间的距离大于kε,则原始空间距离大于ε的概率具有一定的下界,从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上,提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率,提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验,实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能,但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法;反之,可以采用基于卡方分布的相似性连接查询算法。

To deal with the curse of dimensionality and costly computation problems existed in high-dimensional similarity join query, the high-dimensional data were mapped to low-dimensional space based on p-stable distribution. According the definition of chi-square distribution, a theorem was proved： if the distance of two points in low-dimensional space is greater than kε, the probability that the distance of two points in original space is greater than ε has a lower bound. So the effective filtering can be performed at relative low cost in the mapped space. A novel chi-square distribution-based similarity join query algorithm on high-dimensional data was proposed. In order to further improve the query efficiency, another similarity join query algorithm based on double filtering was also proposed. Comprehensive experiments were performed. The experimental results show that the proposed approaches have good performance. The recall of the chi-square distribution-based similarity join query algorithm is larger than 90%. The double filtering based similarity join query algorithm can further improve the efficiency, but it will lose some recall rate. Chi-square distribution based similarity join query algorithm is suitable for the query tasks which are critical of the query performance but not critical of the recall; otherwise, the similarity join query algorithm based on double filtering is favorable.