高维大数据相似性连接查询关键技术研究

Existing big high-dimensional data similarity join query mechanism has some shortcomings: high computational cost, long query time and poor scalability, it is hard to meet the requirements for efficient query and analysis on the huge and growing of high-dimensional data. This project aims to study the theory and application of the key techniques of big high-dimensional data similarity join query: In order to deal with the "curse of dimensionality" problem, we construct the PAA-based multiple filtering mechanism, the random projection based dynamic filtering mechanism and the similarity join query hybrid filtering mechanism to reduce the candidate set size; In order to deal with the scalability problem, we construct the similarity calculation load evaluation model and load balancing strategy, propose the scalable similarity join query strategy; In order to deal with the similarity join on multiple high-dimensional data sets, we design multi-source similarity join order selection strategy, propose the multiple data sets similarity join algorithm based on double data sets similarity join, the direct similarity join algorithm for multiple high-dimensional data sets. The results of this project will provide a certain technical support and theoretical accumulation for big data integration. It is of great significance to improve the efficiency of big data analysis, to enhance the competitiveness of enterprises and our country, to promote rapid development of China's big data applications and big data industry.

现有高维大数据相似性连接查询机制存在计算代价高、查询时间长、可扩展性差等不足，难以满足对海量且持续增长的高维数据的高效查询与分析需求。本项目针对高维大数据相似性连接查询关键技术开展理论与应用研究：针对高维数据相似性连接查询中存在的“维度灾难”问题，构建基于PAA的多重过滤机制、基于随机映射的动态过滤机制和相似性连接查询混合过滤机制，减少候选集合规模；针对高维大数据相似性连接查询面临的扩展性问题，构建相似度计算负载评估模型和负载均衡策略，设计可扩展的高维大数据相似性连接查询策略 ；针对多源高维大数据相似性连接查询代价高的问题，设计多源相似性连接顺序选择策略，提出基于双源连接的多源相似性连接查询算法和多源高维大数据直接相似性连接查询算法。本项目研究成果将为大数据集成奠定理论基础和技术积累，对提高大数据分析能力、利用大数据提升企业和国家竞争力、促进我国大数据应用及产业快速发展，具有重要意义。

大数据集成与大数据融合是进行大数据处理与分析的前提，也是实现大数据价值最大化的关键。相似性连接查询是大数据集成的重要研究内容，其理论和方法的研究已经成为国内外学术界的研究热点之一。同时，相似性连接查询作为大数据分析的一种重要操作，可以提高相似性检索和数据挖掘的效率，在很多领域得到了广泛应用，如相似网页检测、个性化推荐、恶意广告屏蔽、相似图像检索、轨迹聚类等。现有高维大数据相似性连接查询机制存在计算代价高、查询时间长、可扩展性差等不足，难以满足对海量且持续增长的高维数据的高效查询与分析需求。. 本项目主要研究研究内容包括：高维数据相似性连接查询过滤模型构建、可扩展的高维数据相似性连接查询方法和多源高维数据相似性连接查询策略。. 对大数据相似性连接查询技术研究进展进行了综述，分析了现有研究工作的优点与不足，并指出了未来主要研究方向；设计了基于PAA的多重过滤机制、基于随机映射的动态过滤机制和相似性连接查询混合过滤机制，大大减少了候选对规模，有效解决了高维数据相似性连接查询中存在的“维度灾难”问题；设计了相似度计算负载评估模型和负载均衡策略，提出了可扩展的高维大数据相似性连接查询算法，有效解决高维大数据相似性连接查询面临的扩展性问题；设计了基于距离划分树的相似性连接查询算法，既可以提高过滤效果，又可以有效应对数据倾斜问题；设计了基于分层采样方法的相似度分布直方图构建方法，并在此基础上提出了基于阈值估计的Top-k相似性连接查询算法，大量实验结果表明，提出的算法具有较好的性能和扩展性。. 随着大规模高维数据分析处理需求的急剧增长，高维数据相似性连接查询在未来会有较大的发展和广阔的应用前景。本项目研究成果将为大数据集成奠定一定的理论基础和技术积累，对提高大数据分析能力、充分挖掘大数据价值、利用大数据提升企业和国家竞争力、促进我国大数据应用及产业快速发展，具有重要意义。