面向带约束分析对象的联机分析模型和算法研究

随着计算机应用的日趋深入，产生了大量的社会网络、生物网络和化合物结构等图数据以及XML数据，如何对这类数据进行多角度多层面的分析，掌握其内在规律，有着重要的意义。本项目将此类数据抽象为分析对象的集合和集合上的约束加以研究。针对传统的联机分析不能处理分析对象之间约束的现状，研究使用语义网提高多维数据模型的建模能力。针对新应用对新型分组方式的需求，研究基于多值属性、基于属性和约束的两类分组操作，采用查询重写和图变换技术，将其转换为传统的分组操作和图划分问题。针对由于新型分组操作具有重复分组的特点而造成Data Cube失效的问题，研究通过统计分析，在分组间合理的分配被重复分组的分析对象并进行补偿的查询重写机制。针对同构的XML数据，研究判定多个元素是否在指定层上有共同祖先的问题，以此为基础，实现封闭的XCube，达到压缩存储空间的目的。研究关键字查询在联机分析中的应用，提高联机分析普适化程度。

基于相似性的分组操作是项目的一个主要的研究内容。项目提出了一个计算XML文档之间的语义和结构相似度的算法XMLSim，它采用节点标记对之间的语义相似度和编辑距离计算节点标记对之间的相似度。在分析了路径上节点具有的偏序关系之后，将路径之间相似度问题抽象为最大相似子序列(MSS，Maximal Similar Subsequence)问题，并利用动态规划MS问题求解得到路径相似度NpathSim。XML文档之间的相似度通过路径集合之间的最大NPathSim的平均值得到。. 项目设计了一个图像分析系统，包括图像特征提取、对图像的抽象内容进行表达和描述、计算图像之间相似度，并进行检索、聚类和分类。主要的创新点： （1）图像特征降维，将图像转换成特征点集，对所有图像的特征点集进行聚类，可以得到k（k=1,2...n)个类中心。计算图像特征点在k个类中的分布,同时对分布向量归一化处理；（2）“图像|特征”模式设计，计算图像特征点集中每个特征点对应的类中心，统计k个类中心在每幅图像特征点集中出现的次数即词频，通过训练获得n主题，根据词频计算每幅图像在不同主题中的概率对图像进行分类。. 项目针对XML等树形数据结构，提出了一个CUBE算法，该算法可以计算完整的CUBE，也可以计算任意一个节点下的CUBE，同时，可以去除CUBE中的冗余数据。项目针对K-SNAP算法存在的问题在按照对象的属性初始划分、按照对象之间关系再次划分的基础上，提出了借助CANAL的思想，对数值型属性进行了预处理，以减少无用分组的数目，引入了Q函数理论，在根据对象之间的关系进行划分时，将分组中节点之间的联系密度作为一个衡量标准，使得分组更有实际意义。. 项目还对社交网络的社区结构的挖掘和Drill Down操作进行了研究。