泛数据双向包容连接查询处理关键技术研究

Join and Similarity Join are basic but important research problems of the data management field. Researchers have conducted a lot of research works on the similarity joins on various data types, including relations, vectors, strings, trees, graphs. Especially, the problem of similarity joins on massive heterogeneous socialized data attracts attention of more and more people. However, research results in this field are far from satisfying people's needs for real applications. This project aims to propose and study concepts, techniques and methods of bi-containment join queries for universal data. 1) Design an extended relational algebra supporting bi-containment queries for universal data. 2) Propose bi-domain-indices-based query processing algorithms on bi-containment join processing for universal data, which include both expectation domain and fact domain. 3) Propose approximate-bi-containment join query processing algorithms for universal data based on the divide-and-conquer policy, and that based on the normalizing policy. 4) Establish the automatic data mapping model for universal data, and propose effective approximate-bi-containment join query processing algorithms for massive universal data based on MapReduce. It is the problem of bi-containment joins that has important theoretical significance and practical value. The research results of this project are expected to be widely used in key areas of social production and life, such as friend making, house leases, and jobs & recruitment.

连接及相似连接是数据管理领域的一个基础而重要的研究问题，学者们已在关系、向量、字符串、树及图等众多类型数据的相似连接方面做了大量研究工作。尤其随着大数据时代的来临，海量异构社会化数据的相似连接问题吸引着越来越多人的关注。然而，该方向已有研究成果还远不能满足现实中的应用需求。本项目旨在提出并研究泛数据双向包容连接查询的概念、技术和方法。设计支持泛数据双向包容连接查询的扩展关系代数；提出基于期望域和事实域双域索引的泛数据双向包容连接查询处理算法；基于分治策略的泛数据近似双向包容连接查询处理技术，以及基于归一策略的泛数据近似双向包容连接查询处理技术；建立泛数据的自动数据映射模型，提出基于MapReduce的大规模泛数据近似双向包容连接的有效查询处理算法。泛数据双向包容连接问题具有重要的理论研究意义和实际应用价值,本项目的研究成果有望广泛应用于交友推荐、房屋租赁、求职招聘等社会生产生活关键领域。

本项目旨在提出并研究泛数据双向包容连接查询处理问题。通过4年的研究工作，课题组在IEEE TKDE、IEEE TIP、IEEE TSIPN、PVLDB、AAAI、IJCAI、《软件学报》等国内外期刊和会议上发表论文35篇。这些论文包括SCI论文6篇、EI论文15篇、CCF A类长文12篇，申请国家发明专利6项、软件著作权2项，获得国内外最佳会议论文奖2项。.课题组深入分析交友、求职等类型的多维复杂数据的匹配问题，通过引入定义在多种数据类型上的满足操作符和每条数据的独立阈值，将研究问题凝练形成一种新的相似连接概念——泛化双向相似连接，扩展了相似连接的应用范围。这种新的连接支持泛化数据类型(包括数值、数值范围、枚举、布尔、字符串等)的事实属性与对应期望属性的交叉比较；通过为每个比较对象设置独立阈值，使得连接结果更加符合用户客观需求。针对泛化双向相似连接查询处理问题，提出子连接集算法和映射-过滤-验证算法。对于映射-过滤-验证算法，还提出了 3 种映射方法，包括单射方法、等步长映射方法和启发式映射方法。其中，启发式映射方法在性能上优于单射和等步长映射，能进一步提高算法效率。.在深入分析交友等应用场景的过程中，课题组尝试针对用户以及社区进行深入的建模与分析。针对偏好的非传递性，提出了用户的多标准偏好模型，使用多个潜在特征向量表示同一个用户，以及该模型的若干种变体，如潜在特征模型、内容特征模型和混合特征模型，适用于不同的应用场景。针对完全非平衡标签信息下的网络表示学习问题，提出了一种新的半监督网络表示学习方法RSDNE，一方面考虑了网络的结构特性，另一方面通过近似地保证特征空间中类内相似性与类间差异性来合理利用完全非平衡的标注信息。针对天际线群组问题，提出了最小支配图结构，包含且仅包含所有的候选点，进而提出两种不同的深度优先搜索技术和一种基于组合的优化技术，快速找出所有的天际线群组。针对社区发现结果精度较低的问题，提出一种基于深度稀疏自动编码器的社区发现算法，能够基于已知网络拓扑结构，提高使用现有经典方法进行社区发现的准确性。针对拓扑不完备情况下的社区发现问题，提出了两种在非连通图上进行社区发现的新方法。针对社区搜索问题，提出了一种结合网络的拓扑结构和节点属性信息的图优化方法。