随着图数据的广泛应用,图数据规模也在飞速增长。目前的图数据规模可以轻松地超越GB,达到TB、EB级别。使用内存图分析算法处理大规模图数据时具有高昂的内存空间代价,而使用外存图分析算法需要保证在计算设备内存空间较小时算法的可运行性,难以满足大规模图分析的效率要求。与此同时,图数据不断增长的规模也考验着基于索引的图分析算法。例如,一些子图查询算法需要在内存中存储与输入图规模基本相同的内存索引,部分可达性查询算法的外存索引的规模随着输入图规模呈指数级增长。本文讨论了以深度优先搜索、强连通分量计算、子图查询和可达性查询为代表的传统图分析问题在存储资源受限情况下的研究难点。由于子图查询和可达性查询常与特殊图模型相关,且知识图谱是一种典型的图模型,因此本文选择知识图谱作为二者的具体应用场景。具体地说,本文的主要研究内容和研究成果如下。首先,本文为大规模图在有限内存中的深度优先搜索问题,提出了一个高效的半外存深度优先搜索算法EP-DFS。不同于传统外存环境,半外存环境为计算设备内存空间大小设置了一个下限。具体地说,现有的半外存深度优先搜索算法在内存中为维护了一棵生成树,并不断地重构直至是的一棵深度优先搜索树。本文通过分析发现,由于在的重构过程中其节点的深度优先搜索顺序的变化具有不可预测性,因此传统算法需要扫描很多次,或引入复杂的CPU计算操作,或需使用大量的随机磁盘寻道操作。为了解决这一问题,EP-DFS采用了一个特殊的重构方式,并能够在算法运行的早期固定上大部分节点的深度优先搜索顺序,从而降低查询所需I/O代价、CPU操作难度和随机磁盘寻道操作数目。真实和合成数据集上的实验结果表明,EP-DFS的CPU代价和I/O代价均比传统算法降低了一个数量级。其次,本文也为在有限内存空间中的强连通分量计算问题,提出了半外存强连通分量计算算法EP-SCC。本文通过分析发现,由于传统半外存强连通分量计算算法为了降低内存空间使用量,仅在内存中为上的每个节点维护两个属性值,导致其难以在（1）时间内计算上两节点之间的可达性关系,并在查询过程中不得不引入一些复杂的优化函数,具有较高的CPU和I/O代价。故此,在EP-SCC中,本文提出了一个新颖的内存处理函数EP-Reduction。基于该函数,EP-SCC可在仅为中每个节点维护两个属性值的前提下,在（1）时间内计算上两节点之间的可达性关系,从而独立于任何优化算法。本文在真实和合成数据集上测试了EP-SCC和传统算法的性能差距,其中数据集WDC-2014拥有超过17亿个节点,数据集eu-2015拥有超过910亿条边。实验结果表明,EP-SCC的性能显著地超越了传统算法。此外,本文为知识图谱应用场景下的子图查询问题,提出了一个有限内存空间中的知识图谱代表性子图查询算法LKAQ。本文通过分析发现,随着图数据规模的飞速增长,传统算法为知识图谱构建的索引已经很难被存储于内存中,并且目前知识图谱上的子图查询算法仍以返回给定查询在上的结果全集为目标。但是,上的子图查询的结果全集中可能包含着海量的的子图,这对后续的分析工作提出了不小的挑战。因此,相比于,部分实际应用更加希望获得中的一部分具有代表性的结果。故此,为了实现在有限内存空间中高效地处理上的子图查询并为给定查询返回代表性结果集,本文设计了两个知识图谱上的轻量级索引I-Index和M-Index。基于这两个索引,LKAQ能够在查询过程中实现效率、内存空间代价和返回代表性结果数目之间的自动平衡。真实和合成数据集上的实验结果表明,在内存受限情况下LKAQ比传统知识图谱上的子图查询算法具有更好的性能,并且LKAQ在可用内存空间与的体积差异显著时依旧具有较好的性能。最后,本文为知识图谱应用场景下的可达性查询问题,提出了一个有限外存空间中有标签和子结构约束的可达性LSCR查询算法INSK。一方面,随着图数据规模的增长,传统可达性查询算法的外存索引体积庞大,已经难以被现有的外存存储设备所负担。另一方面,大规模图上的推理也不再局限于传统无约束的可达性查询或有标签约束的可达性LCR查询,其常与LSCR查询相关。本文通过分析发现,目前知识图谱上LSCR查询的解决方案均需要依赖在线搜索算法,并且搜索方向固定难以实现高效的查询。故此,本文为INSK设计了一个轻量级索引L-Index,并且基于该索引设计了一个复杂的启发式评估函数,从而令INSK能够打破传统无信息搜索算法的固定搜索方向,实现高效的查询。本文的理论分析和实验结果同时证明了,L-Index的外存空间代价远小于传统LCR算法的外存空间代价。与此同时,实验结果也表明INSK在真实和合成数据集上的查询代价较LSCR查询现有解决方案的优化算法低了一个数量级。