现实生活中的很多应用可以抽象为图里面的问题,比如基因网络中的疾病进展跟踪,可以抽象为图里面的路径查询问题;城市建设的规划,可以抽象为图里面的k个最近邻节点对查询问题;蛋白质交互网络的分析比较,可以抽象为图匹配问题等等。本文的研究主要涉及前两个问题,即路径查询和k个最近邻节点对的查询。现有的路径查询和k个最近邻节点对查询的工作中,主要存在以下两个问题:(1)现有的研究大多数是基于静态图,也有一些研究涉及到动态图上的路径查询问题,但是目前还没有动态图上的k个最近邻节点对的相关研究;(2)现有的研究没有考虑图的边上可能会有属性信息,也没有考虑用户在进行查询的时候会对时间以及边上的属性有特定的需求。本文主要考虑了以上这两点,从而提出了模型来贴切地描述现实生活中的网络,也提出了查询方法来更好地满足用户的查询需求。本文的主要贡献如下:(1)提出了属性时序图的概念,并在属性时序图上提出了多约束下的最早到达路径、最晚出发路径以及多约束下的k个最近邻节点对的查询问题;(2)提出了一组近似算法,称为两次扫描算法。第一次扫描中定义了一个时序目标函数,它由多个约束和不断变化的属性值组成,指示时序路径是否可行。第二次扫描对时序图进行搜索以找到满足用户所提约束的的路径;(3)提出了网格分解技术,与分治法相结合,加速了时序图中k个最近邻节点对的查询。其中,任意两个节点之间的多约束下的最短路径的查询算法是对两次扫描算法进行修改得到的;(4)本文在Enron、Openflights和Arxiv等多个真实数据集上对上述方法进行了评测,同时与目前最新的方法进行了比较。实验证明了本文提出的时序图中多约束下的时序路径查询方法和k个最近邻节点对查询方法的高效性和有效性。