基于倒排索引的正则路径查询算法

对于图数据上的正则路径查询(regular path query, RPQ)问题,其使用正则表达式定义图中两个节点之间的约束。针对现有的RPQ在图上遍历匹配方法效率低下这一问题,提出一种基于倒排索引的RPQ算法,在图上构建标签的倒排索引,匹配过程中快速检索标签的相应倒排列表。设计的IRPQ算法将查询转化为面向倒排列表的查询计划树,经过优化以减少冗余列表合并操作。在真实数据集上进行了实验,其结果表明,IRPQ及其优化算法相比现有方法显著提高了查询性能。

结构化加密图的最短路径查询

随着云计算的快速发展,数据用户将大量图数据外包给云以节约存储和管理成本。然而,外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的,为保护敏感信息的隐私安全,数据拥有者希望在将图数据外包给云服务器之前对其加密,同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径,是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案,以支持加密图上近似或精确最短距离查询、约束最短距离查询和top-k最近关键字查询,但支持最短路径查询的方案较少,且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中,我们基于2-Hop标签技术构造支持有向图上最短路径查询的标签索引并加密,然后将加密的标签外包给云服务器。利用改进的保序编码算法编码距离值,实现加法运算和值的比较,提高最短路径查询的效率。在查询阶段,通过递归式地计算两节点间最短路径上的第一条边和最后一条边,最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的,能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。

多重背景下的top-k路径序列查询

随着路网信息的逐渐完善以及人们出行需求的增长,路网属性和路径查询方式正在不断地丰富,传统路网上的路径查询正在转变为时间依赖路网上的路径查询.查询需求的增加使得在某些情境中时间依赖路网上的路径查询结果并非最佳(如某些时刻部分道路禁止通行带来不同道路通行时间的差异、在极端天气情况下道路的通行时间与平时不同等).对时间依赖路网进行了拓展,在考虑时间背景的基础上,引入道路属性及天气因素,以此得到当前查询背景下的最优路径.为了有效地解决当前背景下的top-k路径序列查询问题,对候选路径建立了支配关系用来进行合理路径剪枝,使其在多条件下的时间依赖路网中能根据特殊点策略序列(例如<饭店→加油站→电影院>)得到旅行时间最短的前k条路径.

隐私保护最短路径距离查询综述

随着云计算技术的快速发展,越来越多的用户选择将图数据上传至云端,以节约本地的计算和存储资源。最短路径距离查询是经典问题,由于云计算存在数据泄露的风险,大量隐私保护的最短距离查询方案被提出,但在存储开销、查询效率、安全性等方面仍然存在进步的空间。为了促进对该项工作的深入研究,介绍了该项工作的基本系统模型、基本密码原语、功能分类、索引技术及安全模型,并提出了目前研究工作存在的缺陷,指明了未来的研究方向。

正确性可验证的密文图数据最短路径外包计算方案

地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%~23.19%,12.91%~30.89%和1.13%~18.62%。

顾及轨迹压缩的车辆路径查询算法

基于位置服务技术的迅猛发展,产生了巨量车辆轨迹数据。为了有效压缩并查询大规模车辆轨迹数据,本文提出一种面向压缩车辆轨迹的路径空间查询算法。本文算法基于Stroke道路层次结构压缩轨迹空间数据,提取关键变速点压缩轨迹时间数据,并构建了一种用于建立轨迹空间和时间数据之间联系的哈希编码,从而实现车辆轨迹的时空数据集成压缩。利用后缀数组对车辆轨迹的基于Stroke路段的压缩编码构建空间索引结构,再以此为基础,设计了车辆轨迹所对应路径的点信息查询算法、相同子路径查询算法和相似路径查询算法。试验结果表明,针对原始轨迹点空间数据,本文的压缩编码方法压缩比可以达到97∶1,与常规的基于路段编码方式相比,本文压缩编码在车辆轨迹的点信息路径查询方面,查询效率可以提升约2倍;在车辆轨迹的相同子路径查询方面,查询效率可以提升约8倍;在车辆轨迹的相似路径查询方面,查询耗时增长率减少了50%。本文算法对于大规模车辆轨迹的数据管理具有十分重要的基础性作用。

面向图数据的结构化正则路径查询方法

正则路径查询是一种应用正则表达式在图数据上进行查询的技术,通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列,未能充分保留图的结构,为了解决这一问题,提出了一种面向图数据的结构化正则路径查询方法,通过在不同的序列间加以结构化约束,使得查询结果由路径转变为子图。为了实现这一目的,首先定义了一种结构化的正则路径查询语言,并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析,验证了网络规模对查询速度的影响,并设置了对照实验。实验结果表明,提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。

基于Map-Reduce的向量空间约束连接路径查询方法

随着交通路网、社交网络等与空间位置有关的新型服务逐渐增多,向量空间数据规模正以极快速度增长和累积,传统数据处理技术在大规模向量空间数据上的执行效率及结果集优化等方面面临着巨大的挑战.本文提出一种基于Map-Reduce的向量空间约束连接路径查询算法,首先,算法在向量空间上进行等边距网格划分,以距离为阈值进行约束连接;其次,利用MapReduce框架,通过节点到单元格的筛选、节点所在约束区域的筛选、单向边集合的筛选以及节点到节点的距离筛选的四阶段筛选策略找到满足约束条件的全部备选路径,从而减少大量的文本复制和路径计算过程.实验表明,本文提出的算法具有较高的执行效率和较低的误差率.

最佳路径的层次编码及查询算法

有效的路径查询处理是地理信息系统、导航系统及计算机网络等高级应用中的一个关键需求 .文中研究如交通网络和通信网络等节点数很大的网络中的最佳路径查询算法 .为了保证最佳路径查询的响应时间 ,采用实例化最佳路径视图的策略 ,即预先计算和存储最佳路径 .文中提出了 HEPV (Hierarchical Encoded Path View )结构 ,证明了在 HEPV上进行路径查询的最佳性 ,同时给出了相应的最佳路径查询算法 .

自适应蚁群优化的云数据库动态路径查询

蚁群算法对于解决动态最优路径查询问题具有很强的优势,但蚁群算法中的信息素挥发因子的静态设置容易带来收敛速度不稳定和陷入局部最优解的问题,在云数据库中更是明显。融合了蚁群算法和云数据库,并提出了信息素挥发因子自适应的算法,该算法能够在云中快速、合理地找到所需访问的数据库,减少了云数据库数路由的动态负荷,从而很大程度上提高云计算的效率。

基于最短路径查询的城市公交网络拓扑建模研究

最短路径分析是地理信息系统 (GIS)中网络分析的一项重要功能 ,等价于图论中的节点间求解最短路径问题。对地理网络进行地理分析和建模 ,以实现最短路径搜索已经有大量论文讨论 ,但是专门针对城市公交网络的建模和路径寻优 ,则少鲜有研究 ,而且已有的一些网络模型也不能直接应用到公交网络寻优中。本文应用图论理论 ,讨论公共交通网络的拓扑建模 。

多维代价图模型上最优路径查询问题的研究

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性.

动态网络中多规则的最短路径查询算法

最佳排序路径查询,是智能交通中的热点问题.在实际的应用中,由于最佳排序路径查询有许多限制条件,现有的算法不能有效地解决动态网络中受限制的路径查询问题.为了解决动态网络中最佳排序路径查询问题,用规则表示每个限制条件,提出了一种新的最佳排序路径查询形式,即多规则的最短路径查询.提供了统一的框架,该框架包含了路径集合查询和最短路径查询.在路径集合查询部分,为了高效地查询出满足多规则的路径集合,在广义规则树的基础上,提出一种新的树的遍历方式,即树的继承全遍历;并基于树的继承全遍历思想,提出一种剪枝技术,对路径集合进行删减,最后求得候选路径集合.在最短路径查询部分,提出一种基于动态阈值的最短路径搜索方法.通过两个真实的动态道路网络的实验验证,所提出的算法能够高效地解决多规则的最短路径查询问题.

一种高效的XML路径查询索引

XML文档的查询索引是当前研究的热点。提出一种高效的XML路径查询索引KDXI,首先对XML文档进行编码,然后建立结构索引并对结构索引进行编码。研究了基于KDXI索引结构的半结构连接算法和路径查询处理过程。通过KDXI索引机制,可以有效执行一般的路径查询语句,并避免冗余的结构连接操作。实验证明了KDXI索引机制的优越性。

XML查询路径分解结构连接优化算法研究

XML查询语言将树型路径查询作为其核心。以XML树形结构进行的导航式遍历的查询,其时间复杂度较高。提出了1种执行效率高的路径分解结构连接策略,对策略中的连接算法进行了深入分析。事实证明,该算法在降低时间复杂度,减少冗余连接等方面有优良的性能。

一种XML多分支路径索引查询算法

为高效地实现XML多分支路径查询,提出了基于索引的XML多分支路径查询算法depthjoin.首先对XML文档进行编码并创建索引,然后对查询树进行查询匹配.采用栈存储多分支路径中的单路径,对多分支结点采用索引信息判定其子结点是否具有共同的祖先结点或父结点.与现有的XML分支查询算法相比,算法depthjoin充分利用索引,不需要进行单路径的连接操作,实验表明其查询效率比现有的查询算法高.

一种基于XML前缀编码的路径查询

为了解决XML文档树子结点过多时前缀编码长度增加的问题,提出一种改进的XML前缀编码——IPE编码.基于IPE编码,结合倒排索引表,给出XPath路径查询算法,可以有效地提高XML文档的查询速度.

XML查询优化的面向路径可扩展模型

通过XQuery中的路径表达式的处理提出了一种更为完整和灵活的查询优化模型 ,称之为POEM (面向路径的可扩展模型 ) .与现有的解决方案不同 ,模型先给出路径表达式的形式化描述———查询路径图 ,并根据路径表达式查询中影响性能的关键因素———结构连接建立了POEM查询优化模型 .

移动对象的连续k最优有序路径查询

针对最优有序路径查询问题,提出了移动对象的连续k最优有序路径查询问题,并针对移动查询对象和静态数据对象的情况,通过引入加权相对距离函数的概念提出了SCkOSR算法和DCkOSR算法。SCkOSR算法利用加权相对距离函数确定数据点与移动查询对象的相对关系。DCkOSR算法进一步通过搜索区域的限制减少了计算加权相对距离函数的点的数量。实验表明,动态局部算法具有相对较好的性能。

一种高效的XML多分支路径查询算法

目前XML单路径查询和简单的分支路径查询已经得到了较好的解决,但如何高效地实现XML多分支路径查询还没有很好的方法。提出一种高效的XML多分支查询算法MBPQ。算法MBPQ首先对XML文档和被查询的多分支路径结点分别按照各自不同的方式进行编码,并将被查询的多分支路径拆分成单路径,最后将单路径查询匹配成多分支查询结果。在单路径查询结果匹配过程中,算法MBPQ利用栈控制匹配过程,按照查询树从左到右、自底向上的顺序匹配具有共同祖先结点的单路径查询结果,从而提高匹配效率。实验表明,与现有的XML多分支查询一般算法相比,算法MBPQ的查询效率高。