[00347359]非结构化数据管理与挖掘关键技术及应用

该成果隶属于计算机科学与技术学科。非结构化数据的存储与挖掘是国际上的学科前沿热点，涉及数据库、数据挖掘、机器学习等研究领域，具有重要科学意义和应用前景。相较于针对结构化数据的关系型数据库和相关的数据仓库及挖掘技术而言，非结构化数据的存储和挖掘还极不成熟，存在着诸多挑战。网络空间中的非结构化数据主要存在高维向量(如图像、音频、文本)、图(如社交网络和万维网)、序列(如DNA、IoT信号)等多种模态，根据其模态不同，相应的存储与管理方法、挖掘与分析方法面临诸多挑战，具体包括四个方面的瓶颈：大规模复杂数据间的关联性表达缺失造成组织存储困难和检索性能低下、网络环境中网络攻击频发造成云端复杂数据的隐私泄露风险、面向复杂数据的分析方法存在计算复杂度高(指数级计算复杂度)的弊端、复杂数据挖掘方法的竞争环境适应性差。上述问题制约了复杂数据的存储与挖掘在实际生产生活中的应用，其解决对非结构化数据的管理具有重要科学意义和应用前景，也完美契合于国家大数据和人工智能发展的战略需求。 在国家自然科学基金的支持下，针对上述挑战，项目组进行了接近五年时间的研究工作，取得了以下三个发现点： 发现点一：海量复杂数据有效组织和高效检索方法。针对高维数据近似查询中距离难以计算、数据无法有效索引的问题，提出了高维数据局部敏感哈希映射下的线序表征模型，使得高维数据通过哈希函数簇进行降维后不仅保持间距特征而且形成了线序集，并在理论上给出了该降维映射和线序集下原数据间的距离损失上限。在该线序集模型基础上，进一步提出了基于B+树的局部敏感哈希值索引结构，在国际上首次实现了传统关系型数据索引结构在高维数据上的有效应用，大幅降低了高维数据近似最近邻查询中的I/O操作量，相对于现有最新方案在査询响应时间上减少了一个数量级。针对云环境下复杂数据检索的隐私泄露问题，利用半同态加密算法、对称加密算法、多功能加密算法等，实现了公有云环境下安全的图像数据近似查询系统，在利用云平台实现高效图像査询功能的同时保障了数据拥有者的隐私。 发现点二：低计算复杂度的复杂数据高效分析关键基础算法。针对SIGKDD’2007会议上Xu等提出的基于密度的网络聚类算法SCAN，解决该算法的聚类结果对于密度阈值参数过于敏感的问题。提出的方法通过将网络投射到其核连通最大生成树上，然后采用凝聚树聚类和相似模块度指标，既克服了基于密度聚类方法的参数敏感问题，又能够有效抽取网络中的层次聚类结构。针对路径规划中典型的组合爆炸问题，采用一种新的动态规划策略，通过从线路终点向起点后向生长的最优序列搜索和剪枝，能够从组合爆炸的节点组合中高效搜索最优线路。针对多序列最长公共子串线性时间解法的瓶颈，项目组提出了多序列无冗余的公共子序列图，提出了高效的多序列最长公共子串求解算法，在该问题提出40年后首次给出了对应的线性时间解法。 发现点三：竞争环境下大规模复杂数据高效挖掘方法。针对图结构中关键节点发现及其信息传播规模在多项式时间不可预测的问题，在关键节点发现方面，项目组基于社会心理学的接受力概念首次提出了大规模社交网络中节点信息接受力的量化模型，并提出了针对此量化模型的迭代计算机制；在信息传播规模预测方面，项目组在国际上首次提出了单一社交网络中多信息竞争传播理论，在此基础上设计了基于混合纳什均衡和马尔可夫随机场的传播范围近似估计算法，解决了多信息传播环境下各竞争体传播范围最大化的问题。针对动态竞争环境下的位置选择问题，项目组首次将目标的移动性与概率结合，提出了Prime-LS位置选择算法。引入有效的剪枝策略设计了高效的PINOCCHIO算法和两个剪枝策略，进一步降低了算法的计算量。此外，为了解决信息传播估计问题，项目组还提出了一种最少资源无参数神经网络(MRNN)求解方法，在仿真数据和大规模美国城市数据上与传统方法，相较于传统的Dijkstra方法，该算法在全局最优解査找过程中实现了50倍的效率提升，在解的质量和求解的速度上都具有绝对优势。 该成果的代表性论文发表在数据库和数据挖掘领域国际顶级刊物和会议上，产生了较大的国际学术影响力。特别是，项目组是西部地区首次在SIGMOD和VLDB数据管理领域顶级会议上进行论文发表和口头报告的科研团队(2014年图灵奖得主Michael Stonebraker教授在公开场合多次表示SIGMOD和VLDB是其衡量数据库领域团队成员学术成果的唯一指标)；所取得的研究成果全面涵盖计算机学会推荐A类国际会议列表中数据库领域三大会议(包括SIGMOD、VLDB和ICDE)；所提出的多信息竞争传播理论及最大化算法被ACM Fellow高度认可，并被提名SIGMOD最佳论文奖，这是中国学者首次获该奖项提名；相关工作持续并广泛的被众多ACM Fellows、IEEE Fellows，数据库领域ACM/EEE顶级汇刊主编或副主编、院士(美国科学院、欧洲科学院等)等国际权威学者的正面评价、引用及专著收录。项目组的8篇代表性论文被SCI他引共计72次，Google学术网引用约230次，项目成果解决了制约非结构化数据管理的四大主要瓶颈问题，促进了该领域研究的进一步发展和相关成果的实际应用。