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

• 作者: 张永新 贾世杰 马友忠
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 相似性连接查询 高维数据 卡方分布 p-稳态分布 召回率
• 年，卷（期）: 2016,（7）
• 所属期刊栏目: 大数据
• 页码范围: 1993-1997,2037
• 页数: 6页
• 分类号: TP311.13
• 字数: 5791字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2016.07.1993

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张永新	洛阳师范学院信息技术学院	15	62	4.0	7.0
2	马友忠	洛阳师范学院信息技术学院	5	92	3.0	5.0
6	贾世杰	洛阳师范学院信息技术学院	2	5	1.0	2.0