异构信息网查询和分析研究

发布时间：2017-12-11 00:22

  本文关键词：异构信息网查询和分析研究

  更多相关文章： 异构信息网 元路径 可达性 聚集图 立方体 冰山立方体

【摘要】：信息网络表示现实世界中实体以及实体之间的联系。随着科技的进步和互联网的普及,信息网络应用广泛,如社交网络、生物网络、交通网络等。信息网络可以用图数据模型进行建模,包含顶点和边两个元素,其中顶点对应现实世界中的实体对象,边对应实体之间的联系。按照信息网络中顶点和关系的类型的数量,信息网络被划分为两类:同构信息网和异构信息网。同构信息网中顶点和边的类型都只有一种,如朋友网、作者合作网等。异构信息网包含多种类型的顶点和边。大多数真实世界的信息网络都是异构的,如知识图谱、社交网络、物联网等。异构信息网络强大的表达能力使其蕴含大量有价值的信息,使异构信息网络查询和分析研究具有重要的现实意义。本文运用算法学、数据分析和计算复杂性的相关技术,结合异构信息网信息丰富和结构复杂的特点,对异构信息网络查询和分析问题进行深入研究,主要研究成果概括如下:1.本文研究了异构信息网上可达性查询问题。可达性查询是查询两个顶点之间是否存在路径连接,是信息网络中的基本查询。研究两个顶点的关系时,首先考虑的查询也是两点的可达性。然而,信息网络上的可达性查询不涉及顶点的类型和边的类型,且都是建立在有向无环图的基础上。在异构信息网中环路是经常存在的,把异构信息网中强连通组件压缩成一个顶点会丢失不同类型顶点之间的路径信息,现有的信息网络上可达性研究都无法解决异构信息网上基于不同关系的可达性查询。本文形式化的定义了异构信息网上可达性查询问题,并证明该问题的时间复杂性是PTIME的。随着网络规模的爆炸式增长,每个查询都需要遍历一遍网络的时间开销是不能容忍的。因此,本文提出MP索引结构用于快速响应查询。通过将网络的元路径按照长度进行分层,构建元路径的偏序图。在偏序图上选择一部分元路径,并预计算元路径上顶点的可达信息,使多个查询可以共享相同元路径中顶点可达信息。在真实和人工数据集上实验验证了本文算法可以快速响应查询。2.本文研究了异构信息网上聚集算法。聚集操作允许用户从特定的维度上观察数据的视图,是多维分析的基础。然而,信息网络上的聚集操作只基于同构信息网上顶点的属性维度,与顶点的类型、边的类型、以及网络的结构无关。异构信息网不仅包含多种类型的顶点,还包含多种类型的关系,聚集的维度不应该仅限于顶点的属性,而忽略丰富的结构信息。因此信息网络上现有的聚集工作无法用于异构信息网。本文提出了基于多种类型顶点和多种类型边的聚集操作,聚集的维度包括:顶点的类型、顶点的属性和边的类型。定义了异构信息网上基于图熵的度量函数,该函数能够很好的刻画异构信息网中顶点在不同关系上的相似度。本文证明了异构信息网上的聚集问题是NP难的,并提出了线性时间和空间的高效近似聚集算法。聚集算法包括两个过程:信息维聚集和结构维聚集。本文进一步证明了算法的近似比。最后在真实数据集上的实验结果显示异构信息网上的聚集算法能够在特定的维度上对异构信息网进行深入的分析,并具有较好的可扩展性。3.本文研究了异构信息网上立方体计算问题。立方体计算允许用户从不同的维度观察数据对象的概括,是多维数据分析的核心。由于信息网络上聚集操作的维度定义的局限制,也导致其立方体物化技术只基于顶点的属性维度,通过属性子集合之间的包含关系,选择部分立方体进行物化。异构信息网上维度概念的复杂化,使得传统立方体物化技术并不适用于异构信息网。本文提出了异构信息网上立方体概念,从多个维度分析网络:顶点属性、顶点类型和元路径。本文研究了异构信息网上的部分立方体物化问题,证明了该问题是NP难的。为了解决部分立方体物化问题,本文提出了异构信息网上聚集图之间两种依赖关系:属性依赖和路径依赖,利用这两种依赖关系建立代价模型和构建方体格。本文为解决部分立方体物化问题提出了贪心算法,证明了该算法的近似比。在真实数据集上的实验结果显示异构信息网立方体可以从多个维度上对网络进行有效的分析,部分立方体物化算法可以提高查询效率。4.本文研究了异构信息网上近似冰山立方体问题。冰山立方体问题是计算聚集值大于阈值的立方体,是多维数据分析中的重要操作。然而,现有信息网络上冰山立方体也是基于同构信息网中顶点的属性维度。显然,这并不适用于异构信息网。对于具有多种类型顶点和边的异构信息网来说,冰山立方体需要涉及顶点的属性维度、类型维度,以及结构维度,聚集函数也更加复杂。因此,需要一种新的冰山立方体定义,刻画异构信息网复杂的语义和结构。本文形式化的定义了异构信息网上冰山立方体,证明了该问题是NP难的。为了快速求解问题,本文设计了基于随机游走的近似算法,并证明了基于随机游走计算顶点相似性的相对误差界。本文设计了两种剪枝策略。当聚集函数满足单调性时,可以提前结束方体计算或直接对方体进行剪枝。在真实和人工数据集上进行了大量实验,结果显示冰山立方体可以帮助用户发现感兴趣的聚集结果,近似算法和剪枝策略算法大大缩短查询时间。
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP391.3

【相似文献】

中国期刊全文数据库 前10条

1 魏震方;宋正德;;云计算环境下异构信息的发现机制与管理方法研究[J];商场现代化;2011年23期

2 王乐,强晓远,孙莉;基于本体模型异构信息交互的研究[J];微型机与应用;2005年01期

3 董明哲,张同军;基于信息语义的异构信息集成方法[J];计算机工程;2005年02期

4 李艾丹;薛中玉;李春梅;;异构信息知识挖掘与可视化分析系统架构模型解析[J];中国科技论坛;2012年10期

5 李剑;宋靖宇;钟华;;基于本体的异构信息集成查询划分及转换[J];软件学报;2007年10期

6 李艾丹;薛中玉;李春梅;;异构信息知识挖掘与可视化系统处理流程解析[J];图书馆学研究;2012年14期

7 康文杰;郑倩冰;陈侃;;基于社会网络分析的学术合作关系研究[J];计算机技术与发展;2014年05期

8 史达;杨洋;;一种面向多层次异构信息平台的数据访问链路识别算法[J];信息与控制;2014年01期

9 刘钰峰;李仁发;;基于查询—文档异构信息网络的半监督学习[J];通信学报;2014年08期

10 徐寿芳;嵇美华;曾益坤;;基于本体的异构电子商务信息集成探析[J];绍兴文理学院学报(自然科学版);2008年01期

中国重要报纸全文数据库 前2条

1 陈友梅;DB2信息集成提速异构信息管理[N];中国计算机报;2003年

2 齐向真;我市两项目获科技部863计划批复[N];太原日报;2012年

中国博士学位论文全文数据库 前5条

1 黄冬;面向网络金融知识服务的模型与方法研究[D];哈尔滨工业大学;2015年

2 尹丹;异构信息网查询和分析研究[D];哈尔滨工业大学;2016年

3 刘钰峰;异构信息网络检索技术研究[D];湖南大学;2014年

4 李朋;异构信息网络分析模型及其应用研究[D];重庆大学;2013年

5 王小刚;异构信息集成环境中基于语义的查询研究[D];华中科技大学;2006年

中国硕士学位论文全文数据库 前10条

1 朱敏;极性异构信息网络相关性搜索技术研究[D];山东大学;2015年

2 童浩;异构信息网络进化协同聚类算法的研究[D];福州大学;2014年

3 罗琛;异构信息网络上半监督机器学习算法研究[D];吉林大学;2015年

4 王倩;异构信息网络上的主题建模研究[D];山东大学;2014年

5 吴晶;面向异构信息集成的数据服务通道的设计与实现[D];电子科技大学;2013年

6 李立;基于元路径选择和融合的异构信息网络社区挖掘算法研究[D];西安电子科技大学;2014年

7 肖颖;面向信息集成的异构信息描述方法研究[D];国防科学技术大学;2003年

8 贾伟;云环境下异构信息交换模板的研究与设计[D];北京邮电大学;2012年

9 潘丽;极性异构信息网络的联系预测技术研究[D];山东大学;2014年

10 豆荣刚;基于异构信息的债券知识服务的研究与实现[D];哈尔滨工业大学;2013年

，

本文编号：1276471