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

来源：计算机应用杂志2016年第7期北京时间：

作者：马友忠, 贾世杰, 张永新

单位：1. 洛阳师范学院 信息技术学院, 河南 洛阳 471022;2. 中原经济区智慧旅游河南省协同创新中心, 河南 洛阳 471022

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

关键词：相似性连接查询,高维数据,卡方分布,p-稳态分布,召回率

基金资助：国家自然科学基金资助项目（61501216，61272015）；河南省科技攻关计划项目（152102210332，152102210331）；中原经济区智慧旅游河南省协同创新中心2015年度开放课题（2015-ZHLV-009）。