一种基于路网的多源聚合距离Skyline查询算法

基于路网距离的多源Skyline查询在地图服务中广泛使用,但现有的Skyline查询方法对于复杂的路网距离计算效率低下,并且随着查询点数量的增加查询结果集变得过于庞大,无法为用户提供精简有效的查询结果。为了提高查询结果的有效性和查询效率,提出一种基于最小聚合距离的倒排索引Skyline查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。     

障碍空间中基于R+树的空间Skyline查询方法

为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题,提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点,缩小查询范围,提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选,最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明,该算法在处理障碍空间中的空间Skyline查询问题时具有优势。     

不确定移动对象概率Skyline集的查询更新

Skyline查询的研究已从传统的静态Skyline操作延伸到动态的、不确定数据集上的Skyline查询和计算上。研究了移动环境下,查询点位置固定、目标点处于运动状态并且位置不确定情况下的连续概率Skyline计算问题。这个过程中,移动对象与查询对象之间的距离随时间不断变化。移动对象由于其运动状态导致位置无法精确定位,因此移动对象之间的支配关系只能采用概率形式表示,且随时间不断变化。给出了移动对象间的支配概率的定义,以及移动对象Skyline概率的定义,并定义了触发事件来记录对象支配概率发生变化的时刻,实现概率Skyline计算的连续跟踪和动态更新。提出了基于事件触发的连续概率Skyline查询算法(event triggered continuous probabilistic Skyline query for uncertain moving object,U-ECPS),对移动环境下的Skyline集进行连续查询和更新。大量的实验结果验证了U-ECPS算法的有效性。     

基于事件的位置不确定移动对象连续概率Skyline查询

Skyline查询是基于位置服务(Location based service, LBS)的一项重要操作,其目的是发现数据集中不被其他点支配的点的集合.移动对象在运动过 程中,其位置信息具有不确定性,导致各数据点间的支配关系不稳定,从而影响Skyline操作.本文针对以位置不确定移动对象为查 询点的Skyline查询进行研究,首先,定义了查询点移动时各对象间支配概率,提出了支配概率和Skyline概率的微元计算方法.在此基 础上,提出一种面向不确定移动对象进行连续概率Skyline查询的有效算法U_CPSC.该算法首先快速计算初始时刻的p-Skyline集合; 然后,定义了两类可能引起p-Skyline变动的事件,通过对这些事件的跟踪计算快速更新p-Skyline集合,无需在移动对象的每一运动 时刻去遍历整个数据集,实现了对p-Skyline的连续更新操作,大大减少了算法的查找和计算开销,提高了运算效率;最后,提出一 种静态算法U_SPSC,与U_CPSC进行了对比试验,实验结果证明了算法的有效性.     

Skyline代表点的选择*

Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.     

面向服务环境中的NServiceBus服务总线应用研究

反Skyline查询现在已经被广泛用于商业规划、环境监测及其它领域。当前的研究多集中在目标对象静止条件下的反Skyline计算。对移动环境下的目标对象不断运动变化并且位置不确定情况下的连续概率反Skyline计算进行了研究。在对移动对象间反支配关系进行细致分析的基础上,定义了反支配概率和反Skyline概率以及导致反Skyline集变化的process,提出了一种基于过程事件的算法来处理位置不确定移动对象的连续概率反Skyline查询算法,以通过计算、跟踪、更新这些process来快速找出p-RSky集合,并提出两个剪枝规则进行优化,避免了大量的无效计算。大量的实验证实了该算法的有效性。     

RDF数据的Skyline优化查询

为解决海量RDF数据的Skyline查询问题,通过分析现有Skyline查询算法的优缺点,提出一种针对海量RDF数据的查询机制。对RDF数据的存储结构进行分析,根据RDF数据垂直存储结构,设计一种候选Skyline点筛选策略,提前修剪部分非Skyline元组,减少Skyline支配点计算的数据量;在筛选的基础上,给出基于MapReduce的Skyline并行化查询算法。实验结果表明,提前筛选能有效减小查询的数据集,并行化算法能够有效提高查询的效率。     

非完整数据库Skyline-join查询*

传统的Skyline-join查询仅适用于完整数据库,随着新的应用需要的出现,实际应用中考虑到非完整数据库中的Skyline-join查询。概率Skyline利用概率值表示非完整数据项之间的支配关系,有效地避免了传统非完整数据库Skyline查询存在的支配性丢失问题。在分析概率Skyline无法有效处理多关系查询的基础上,对概率Skyline定义进行了扩充,使其适用于多关系查询,并提出了基于多层次分组的PSkyline-join算法。该算法首先基于连接键值及缺失位图对各个关系进行多层次分组,再计算各组数据项的局部Skyline概率上界,然后连接数据项并更新数据项的全局Skyline概率上界,最后利用全局Skyline概率上界与全局Skyline概率下界设计了两种剪枝策略,高效地计算全局概率Skyline结果集。在模拟数据集上验证了PSkyline-join算法效率相较传统算法有着几十倍的提升。     

一种网格化高并发Skyline查询处理方法

为减少冗余支配测试对Skyline查询性能的影响并提高Skyline查询处理的效率，本文将测试单位扩大为网格，并设计了一种基于网格分层划分的Skyline查询方法.通过不断缩小Skyline点集所在网格的方式，使网格之间的支配关系与点支配关系重合，从而避免了点与点之间大量无效的支配测试，提升了Skyline查询处理的效率.方法中同一层的网格可并行计算，且层次计算过程可达到任意精度，适用于计算能力有限但对结果精度要求不高的场合.实验结果表明，方法与现有Skyline查询处理方式相比具有数据吞吐量大、响应速度快等特点，在拥有高性能GPU或多核CPU等高并发环境下其优势更为明显.     

路网中位置不确定的二元反kNN查询

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询（PBRkNN）,旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率。最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

路网中基于Voronoi图的反向最近邻查询方法

针对已有的在路网中的反向最近邻(Reverse Nearest Neighbor,RNN)查询方法存在的不足,提出了利用网络Voronoi图(Network Voronoi Diagram,NVD)的NVD-RNN算法,该算法具有较好的效果,它把路网划分成小的Voronoi区域,并且采用了两个过程:过滤过程和精炼过程。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。并且进一步给出了处理新增加点的ADDNVD-RNN算法和处理删除点的DENVD-RNN算法。实验表明,该算法在处理路网中的反向最近邻问题时有明显的优势。     

路网中基于地理位置和区域封闭性的最短路径的查询算法

针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。     

基于Flink的k-支配skyline体并行求解算法

k-支配skyline算法弱化了数据点之间的支配关系,更适合高维数据。k-支配skyline体适应于多名用户使用k-支配skyline算法查询,而现有的求解算法在时间效率和代码扩展性方面都有待提高。因此,提出了面向多用户的k-支配skyline体求解优化算法MKSSOA,该算法对每名用户的候选集和中间集分别进行存储,同时在k-支配检查过程中利用2集合中数据点出现的先后次序将候选集中的非k-支配skyline点存储到对应用户的中间集中,以便下一名用户筛选使用,这样可以减少数据点之间的比较次数,避免重复计算,从而提升查询效率。同时,提出了面向多用户的k-支配skyline体并行求解算法MKSPSA,通过Apache Flink并行处理框架有效减少了数据点的比较时间。理论研究和实验结果显示,提出的算法具有较高的效率,能很好地处理多用户k-支配skyline问题。     

基于不确定理论的不确定性数据Top-k查询计算

在不确定性数据集中,基于参数化排名函数的Top-k查询研究近年来备受关注。给出了一种新的解决方法,该方法将不确定性数据集中的元组建模为不确定网络,将有序元组的Top-k查询等价转化为相应样本图中边的不确定测度关系,并对样本图依据所包含边的排序位置进行分类,从而 将不确定性数据中基于参数化排名函数的Top-k查询等价转换为依Top-k值不同的有限查询。本算法避免了计算所有元组在样本图中的排名不确定测度值,提高了不确定图的Top-k查询计算效率。 理论分析和实验结果表明,提出的Top-k查询算法能够从非确定角度解决不确定性数据的Top-k查询计算问题。     

时间依赖路网上的移动对象K近邻查询算法

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。     

基于HBase的路网移动对象时空索引方法

在处理路网移动对象时,由于HBase只能采用key查询,不适用于移动对象的多维查询,导致HBase存在存储索引与查询效率不高的问题。针对此问题,在HBase存储结构的基础上设计并实现了一种高效的路网移动对象HBase索引框架（RM-HBase）。首先,对原生HBase索引框架的上层HMaster和下层HRegionServer进行改进,解决分布式集群数据的热点分布问题,提高空间数据的查询效率;其次,提出路网移动索引——RN-tree,解决空间划分中的"死空间"问题,同时提高空间中路段的查询效率;然后,基于上述对HBase的索引改进,分别设计了时空范围查询、时空K最近邻（KNN）查询和移动对象轨迹查询的查询算法;最后,实验选用了同样是基于HBase分布式数据库而提出的时空HBase索引（STEHIX）框架作为对比对象,分别从索引框架的性能和算法的查询效率两个方面对RM-HBase的性能进行分析。实验结果表明,所提的RM-HBase在数据的均衡分布性能和时空查询算法的查询性能方面都优于STEHIX框架,有助于提升海量路网移动对象数据的时空索引效率。     

基于深度语义信息的查询扩展

随着互联网时代的到来，搜索引擎开始被普遍使用。在针对冷门数据时，由于用户的搜索词范围过小，搜索引擎无法检索出需要的数据，此时查询扩展系统可以有效辅助搜索引擎来提供可靠服务。基于全局文档分析的查询扩展方法，提出结合神经网络模型与包含语义信息的语料的语义相关模型，来更深层地提取词语间的语义信息。这些深层语义信息可以为查询扩展系统提供更加全面有效的特征支持，从而分析词语间的可扩展关系。在近义词林、语言知识库“HowNet”义原标注信息等语义数据中抽取局部可扩展词分布，利用神经网络模型的深度挖掘能力将语料空间中每一个词语的局部可扩展词分布拟合成全局可扩展词分布。在与分别基于语言模型和近义词林的查询扩展方法对比实验中，使用基于语义相关模型的查询扩展方法拥有较高的查询扩展效率；尤其针对冷门搜索数据时，语义相关模型的查全率比对比方法分别提高了11.1个百分点与5.29个百分点。