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