大规模图数据可达性索引技术的应用

2017-12-28冯浩然长沙市实验中学

数码世界 2017年11期

冯浩然长沙市实验中学

大规模图数据可达性索引技术的应用

冯浩然长沙市实验中学

我们进入大数据时代后，数据的数量与规模明显增加，而很多数据的结构较为复杂，需用数据模型展示，由此，大规模图数据可达性索引技术开始大范围应用，让数据索引更加精准，展示数据，提高了索引的效率。本文先论述了技术的应用，随后阐述了可达性索引的研究现状。

可达性索引生物信息网社交网络

当下，大数据已经成为我们经常提及的词汇，其具有的特点是，数据种类具有多样性、结构更加复杂，针对这一情况，我们可以采用大规模图数据可达性索引技术，完成数据的收集，并用较短的时间匹配数据。但该技术仍有很多问题需要完善。

1 大规模图数据可达性索引技术的应用

现在，可达性索引已经在多个计算机领域广泛应用，包括软件工程、编程语言等，而它的应用，也可以强化其他应用算法的效果。比如Kijkstra等。

1.1 语义网

建立语义网的目标是，机器可以理解在Web上发布的信息，转化数据存储的形式，让其从原有的数据转化为RDF、XML，其中XML是用文档的方式存在，整体结构为树状，如果所有数据中存在ID/IDF关系，需用图表示，而RDF具有的关系为三元关系，也需要用图表示。同时，RDF、XML也有各自的查询语言，这两种查询语言都需要分析相应的路径，可达性查询在其中起到的作用是，找到合适的路径并进行匹配。

1.2 本体

本体的定义是概念的集合，具有概念属性，在同一个范畴内不同的概念有相互关系，本体会根据关系的范围，在特定的范畴内完成推理。本体推理出来的内容可在语义网中应用。语义网内，推理引擎会搜集所有推理后的结论，并把这些结论放到RDF数据中，加快推理的过程，比如，若是类C1为类C2的子类，C2又是C3的子类，由此推出，C1为C3的子类，简化了原有的推理过程。

1.3 生物信息网

随着数据获取技术的发展，用高吞吐量获取数据的方式已经广泛应用，生物学家用这一方式可以搜集到大量的数据，而很多数据都需要用异构图显示，比如代谢路径分析、信号传播网络数据等。生物学家把这些数据集中到一起后，会用顶点或边表示数据内的结构，即顶点可以代表蛋白质、化合物等，而边会连接不同的顶点，用于表示两个顶点之间的关系。比如基因控制网络数据，提出用基因A是否可以控制基因B，是直接控制还是间接控制，这恰巧对应可达性查询的内容。

1.4 社交网络

任意一个社交网络中，每个用户都是一个顶点，如果这两个用户之间可以建立联系，顶点间会用一边连接，而用户之间的关系存在明显的差异，包括父子、兄妹、姐妹等，需在边的上方标记两个用户之间的关系。同时，在整个社交网络中，大部分查询都需要先判断两个节点是否真正存在关系，而这一查询方式即为可达性查询。比如，我们想知道用户A与B是否是远亲关系，需探查两点连接的路径，分析周围不同边代表的关系，由此判断A和B之间的关系。

此外，其在社交网络的查询中，会运用子图查询，即子图查询是选择一个图数据库与一个需要查询的查询图，待查询后把所有结果输出，但因为查询图的结构是随机的，所以在查询的过程中，要在所有数据库中找到同构图，完成子图匹配。其使用的算法是统计启发式算法，具体的操作方式是，运用信息熵，发挥信息上的度量作用，并让其作为两个图是否匹配的依据，避免两个相邻的点过度匹配，提高查询效率。其体现的思想是：在查询中加入信息熵，并建立一个动态模型与评价标准，随后，根据动态模型提出匹配的算法，最终对比不同的实验结果，分析结果的有效性。

1.5 复杂查询处理

对于复杂查询处理，可以通过可达性索引加快匹配算法的操作，通过最短的路径查询到相关信息，并完成子图的匹配工作。

2 可达性索引的研究现状

基于上述五方面可达性索引的应用，可以总结出以下内容：

从可达性索引发展至今，为扩大其应用范围，很多索引方法被推出，而所有方法的选择，都是为了让时间、规模及模型构建达到平衡，并可以分成不同的类型。从数据规模的角度来看，可以分为三类，包括小型、中型、大型数据规模，每个规模的数据都有不同的等级，依次为万级以下、百万以下、百万以上，可以使用的查询方式是有无约束查询、动态与静态查询。而以最大图数据规模作为划分标准，可以把索引方式分三种，分别是小规模、中规模、大规模的索引，若是把图数据类型作为分类标准，可以使用静态与动态两种索引方式。其中，所有查询与索引的方式中，静态与动态是较为常用的方式，前者可以用于大型、中型、小型数据图非限制的索引，以及中小型数据土受限的索引，后者因为数据结构较为复杂，不易动态维护，所以运用较少，其分类与静态索引相同，但不可以用于中小型数据类型受限的索引。