图是一种描述对象以及对象之间关系的表示模型,学术界和工业界产生的结构关系数据和非结构化关系数据都可以直接或间接地用图模型进行描述。图相似性查询旨在从两个图数据集合中找出所有两两相似的图对或从单个图数据集合中找出与查询图相似的所有图。前者称之为图相似性连接查询,后者称之为图相似性搜索查询。图分类的目的是通过从训练图集中学习分类模型,以此预测无标签图的类标签。图相似性查询和图分类技术在许多领域都有重要的实际应用价值,如化学领域、生命科学领域和社交网络领域。虽然图相似性查询和图分类技术具有重要的实用价值,但是,目前这两种技术的研究面临着两个严峻的挑战:(1)多图复杂特性引起的挑战。多图是一种描述对象和其组件之间的组合关系的表示模型,是由多个图组成的一个集合。虽然多图相似性查询和多图分类技术很重要,但是由于多图结构复杂,因此解决多图相似性查询和多图分类问题很困难。(2)大规模特性引起的挑战。目前,现有大规模图数据处理技术主要面向单个自身规模很大的图,这些技术不适合直接用于处理自身规模不大但数量庞大的图和多图。海量的图和多图的相似性查询和分类需要分布式处理,也面临许多技术挑战。本文从学术界和工业界的实际需求出发,分析了图和多图相似性查询和分类技术面临的挑战,针对自身规模不大但数量庞大的图和多图的相似性查询和分类问题进行了深入的研究,提出了一些高效的解决方法,满足学术界和工业界的实际需求。本文的贡献点总结如下:(1)针对大规模图相似性连接查询问题,提出了相应的解决方案,具体内容包括:提出了可扩展的前缀过滤技术,该过滤技术适用于大q-gram字母表;提出一种基于可扩展前缀过滤技术和MapReduce框架的并行的MR-GSimJoin算法,解决大规模图的相似性连接查询问题;使用多个技术对MR-GSimJoin算法进行优化,包括:压缩技术、两轮数据访问技术和复合键技术。最后,通过一系列的实验验证了所提出算法的有效性和高效性。(2)针对大规模多图相似性搜索查询问题,提出了相应的解决方案,具体内容包括:提出了一种多图距离定义,并优化了计算多图距离的KM算法;提出了增量式的多层倒排索引和多个下界剪枝策略;提出了一种基于多图距离、增量式多层倒排索引和多个下界剪枝策略的MGSS算法,解决小规模多图相似性搜索查询问题;提出了一种基于MGSS算法和MapReduce框架的并行的MR-MGSS算法,解决大规模多图相似性搜索查询问题;并使用局部化策略对MR-MGSS算法进行了优化,不仅减少了通信代价,而且在一定程度上解决了 map task负载不均衡问题,从而提高了 MR-MGSS的效率。最后,通过一系列的实验验证了MGSS和MR-MGSS算法的有效性和高效性。(3)针对有监督大规模多图分类问题,提出了相应的解决方案,具体内容包括:提出了一种基于MapReduce框架的并行的ME-MGC算法,解决有监督大规模多图分类问题;使用倒排索引技术和复用技术提高ME-MGC算法的效率;使用超限学习机方法(ELM)提高ME-MGC算法的分类性能,并研究了 ELM算法隐藏节点数目对ME-MGC算法分类性能的影响。最后,通过一系列的实验验证了 ME-MGC算法的有效性和高效性。(4)针对半监督大规模多图分类问题,提出了相应的解决方案,具体内容包括:提出了一种评价特征子图价值的打分函数;该打分函数既考虑有标签多图和无标签多图,又考虑多图的两层标签约束特性,有利于选择出质量更好的特征子图;提出了一种基于打分函数的MGSSL算法,解决半监督小规模多图分类问题;提出了一种上界剪枝策略,提高MGSSL算法的效率;提出了一种基于MGSSL和MapReduce框架的MR-MGSSL算法,解决半监督大规模多图分类问题;并使用复用技术和局部化策略对MR-MGSSL算法进行了优化。最后,通过一系列的实验验证了 MGSSL算法和MR-MGSSL算法的有效性和高效性。总之,本文研究了大规模图的相似性连接查询问题、大规模多图的相似性搜索查询问题、半监督大规模多图分类问题和有监督大规模多图分类问题,提出了高效的解决方案。实验结果表明,本文提出的方法的查询性能和分类精度均优于之前最好的方法。