在现实世界中,绝大多数图数据都在随时间发生动态演化。近年来,随着大规模“动态图”数据的不断涌现,面向大规模动态图数据的查询处理逐渐成为图数据管理中非常重要的一类任务。其中,面向大规模图上的位置查询处理是一个十分重要的研究方向,该方向主要包括两类图数据上基础的查询问题:顶点可达性查询与k-近邻查询。对于动态图上的可达性查询问题,我们重点关注结构变化动态图上基于历史区间的可达性查询,即:给定动态图的拓扑结构会随时间发生变化,且对于变化过程中的一段历史区间,判断顶点u和v在此历史区间内是否可达。当前仅有极少数工作涉及针对该方向的研究,且其大都侧重于利用增量式更新策略快速重建任意时刻图快照,进而在重建图快照上完成可达性查询。然而,重建大规模动态图的快照需要昂贵的代价,这在现实应用场景下是难以接受的。仅有少量工作考虑通过构建查询索引的方式来回答用户给定查询,然而其构建的查询索引大都包含各类约束条件,进而限制了查询的性能。对于动态图上的k-近邻查询,我们更关注于内容变化的动态图,即:图中边上的权重会随着时间发生改变。在该问题中,用户给定出发时刻,查询需要返回在该时刻出发时距离查询点q最近邻的k个对象。基于内容变化的动态图的特点往往被刻画成时间依赖图模型,这也导致现有的大量基于构建静态查询索引的k-近邻查询算法无法适用于该时间依赖图模型。本文对上述两个问题分别设计了相应的高效查询算法,具体的工作如下:1.该课题中,我们设计了一种兼具合理时空开销和查询可用性的全新可达性查询索引架构,并基于图着色问题给出了相应的优化策略,使其能够有效地解决结构变化动态图上两类基于历史区间可达性的查询问题。2.针对内容变化的动态图上的k-近邻查询,我们在原有索引框架的基础上提出了一种全新的二级索引架构,进一步提高了查询效率。本文主要研究面向大规模图上的位置查询处理,并围绕顶点可达性查询与k-近邻查询两类图数据上基础的查询问题分别设计了相应的高效查询算法,并通过在多个真实数据集上进行大量实验验证了其有效性及高效性。