目前,随着网络中数据量的剧增,基于集中式的查询处理与计算技术已经不能满足对真实数据分析的能力,因此适合于各应用的并行模型系统受到更加广泛的关注与研究。其中,s-t最短路径距离查询是常见的一类图查询应用,而已有的技术在集中式环境下对该查询提出了高效的策略实现,但在并行环境下这些技.术并不完全适用,需要根据自身的并行特征进行改进与优化设计。因此,本文提出基于并行框架下广泛实用的BSP模型,面向大图数据的s-t最短距离近似查询处理技术展开研究,并针对有向图与无向图的两大类拓扑结构的不同特点,分别提出了不同的优化策略。一方面,面向广泛被研究的无向图近似查询,提出基于局部顶点覆盖的索引技术对大图进行有效地压缩,获取由参考点集与边界点集构成的压缩小图,从而剩余顶点根据其出入边与压缩图中顶点的连接情况进行有效存储,保证整体查询的准确性;查询阶段,根据双向bsp迭代比较机制进行最短距离结果的查询;最终,在理论上,对查询结果进行误差分析,并通过实验验证了算法的有效性。另一方面,面对已有研究涉及较少但在应用中广泛存在的有向图查询,提出了全新的层次图构建策略,最终在压缩小图上获得具有精度保证的结果,首先,采用局部betweenness的算法获取第一层压缩图,有效存储原图顶点信息;然后,在此基础上,根据被松弛顶点不同的出入边信息选择特定的松弛操作,进而对图中顶点进行删除或重新组建,由此构建不同层次的压缩小图;接下来,根据给定的查询源顶点与目的顶点所属的最高层次图,进行回溯找到在最高层次压缩图上的相关顶点,从而在最小的压缩图上快速得到最短距离值;最后,对基于bsp迭代的基本查询过程进行了优化,提出基于跳数的提前终止策略,一种通过统计数据准确限定,另一种基于当前距离值分布近似限定,同时可以获得理论上的概率保证,在实验中验证了该概率保证的有效性。本文提出的两种框架和相应的优化方法为大规模图数据的最短路径查询和基于该类查询的复杂分析提供了有效的解决途径。理论分析和大量真实图数据上的实验测试,展现了算法可以在保证查询精度的前提下,获得很大的性能提升。提出的方法对其他分布式环境下的图数据近似处理技术也具有借鉴意义。