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

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