多用户偏好的 Top-k 查询处理算法研究磁

传统的 Top-k 查询处理都是利用单用户偏好来计算评分函数,这种方法有极大的局限性。针对基于多用户偏好的 Top-k 查询处理问题进行研究,为了提高查询效率,首先提出了预处理算法 PA 与 PVA ,生成一些具有代表性的系统用户偏好,并据此将初始数据集进行全排序,保存在物化视图中,以便利用它们进行 Top-k 查询。然后,提出了处理 Top-k 查询的 VBA 算法且进行了正确性与完备性论证。最后,实验结果表明,该算法比直接在原数据集中查询的效率有极大的提高。     

支持OR语义的高效受限Top-k空间关键字查询技术

近些年,随着定位系统和移动设备的普及,空间文本对象的数量日益庞大,基于位置的地理信息服务在人们的生活中发挥着越来越重要的作用.对于空间关键字查询搜索的研究亦如火如荼.然而,现有许多研究工作只适用于AND语义,支持OR语义的搜索研究相对较少.当用户放松对关键字匹配的要求时,支持OR语义的搜索技术显得尤为重要.针对这一问题,在聚集线性四分树的基础上,利用线性四分树上物理存储的Morton码与逻辑空间位置的对应性,提出了基于虚拟网格的VGrid算法.该算法可同时支持OR语义和AND语义.最后,通过在真实数据集上进行大量实验,验证了所提算法的有效性和高效性.     

一种障碍空间中的反k最近邻查询方法

随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象(RkNN)的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种...     

基于Voronoi图的最近邻查询的研究

移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型.基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间.但在以往的研究中基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及.本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树.进而给出了基于VR树索引结构的1NN查询算法.     

障碍空间中基于Voronoi图的k最近邻查询

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。     

空间数据库中全局最近邻查询处理方法

空间数据库中基于层次化索引结构的全局最近邻(all-nearest-neighbor, All-NN)计算采用单节点展开策略的嵌套循环技术来降低计算开销.在同一数据集合的全局最近邻计算中,基于索引结构带来的对象空间位置临近性特点,抛弃传统理论距离裁剪规则和嵌套循环技术来减少计算和索引节点访问开销.提出了采用局部计算和完备计算两阶段的计算模型来获得全局最近邻结果.首先以叶节点为单位,采用扫描线算法获得节点内部所有对象的局部最近邻结果,然后根据计算结果得到启发式裁剪距离.在第2阶段采用层次化过滤的范围查询算法来获取外部的(可能的)最近邻对象.实验与分析表明该方法可以很好地支持不同种类、大小、分布的数据集合All-NN查询处理,具有良好的实用价值.     

基于R树及其变种的最近邻查询研究

最近邻查询是空间数据查询领域中最重要的查询技术之一.最近邻查询根据所查询的目标对象的运动特性分为静态最近邻查询和动态最近邻查询.静态最近邻查询的关键在于运用最小距离和最小最大距离作为查询条件,对索引树的节点进行排序和剪枝进而查找目标对象 通过对现有最近邻查询算法的分析研究,比较这些现有算法的优缺点     

基于阈值的快速启动Top-k查询处理算法

Top-k查询是搜索引擎领域广泛应用的技术之一,该算法从海量数据中返回最符合用户需求的前k 个结果,在执行时能避免对大部分无关文档的打分处理。Top-k 查询虽然极大提升了查询性能,但其存在的慢启动问题并未得到有效解决。为此,该文首先提取倒排索引的静态Top-k信息,再动态计算针对具体查询词项的初始阈值,在此基础上,结合MaxScore和WAND算法,提出了快速启动的Top-k查询处理算法。实验结果表明,该方法能够有效解决上述问题,具有良好的性能。     

障碍空间中基于Voronoi图的组反k最近邻查询研究

为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

支持偏好调控的路网隐私保护k近邻查询方法

随着人们对个体隐私的日益关注,位置服务中的隐私保护问题成为数据库领域新兴的研究热点.针对面向路网的隐私保护k近邻查询中,保护位置隐私引发的难以兼顾查询质量问题及查询者对查询效率与准确性间偏好调控需求问题,引入PoI(Points of Interest)概率分布概念,通过分析服务器端PoI邻接关系,生成PoI概率分布.将服务器端查找k近邻PoI过程分解为路网扩张查询阶段和迭代替换阶段,为迭代替换阶段构建基于PoI概率分布的可替换PoI概率预测机制.基于所构建概率预测机制,提出支持用户偏好调控的保护位置隐私k近邻查询方法AdPriQuery(Adjustable Privacy-preserving k nearest neighbor Query),查询者通过调节筛选概率阈值,在兼顾位置隐私安全的同时,实现对查询效率与准确性的偏好调控.所提调控机制对已有的基于空间混淆的路网环境保护位置隐私近邻查询方法具有良好的兼容性.理论分析和实验结果表明,所提方法在兼顾保护位置隐私的同时,能有效提高服务器端查询效率,同时支持查询结果准确性与查询效率的偏好调控要求.     

保护位置隐私近邻查询中隐私偏好问题研究

近年来,位置服务中的隐私保护问题得到了研究者的持续关注,特别是近邻查询中位置隐私保护问题更是得到了广泛的研究.已有工作缺少对查询者个性化隐私偏好约束的系统研究,位置隐私与查询服务质量的兼顾,在隐私偏好约束下尤为困难:(1)偏好强调个性与隐私模型侧重共性存在矛盾;(2)偏好对查询中间结果动态可控依赖与查询简化中间结果的思想相抵触;(3)连续查询中,支持隐私偏好存在基于候选解集攻击的风险.结合上述问题,提出保护位置隐私近邻查询中的隐私偏好问题,从位置隐藏原理及近邻查询性能与保护位置隐私内在制约机理的角度,对已有的位置隐藏与查询处理方法的性能及其对隐私偏好支持能力进行论述分析.进一步地,对支持隐私偏好与保护位置隐私查询内在制约机理进行了剖析,分析保护位置隐私近邻查询中支持隐私偏好需解决的主要问题,并对所归纳问题的可能解决方法进行了展望.     

基于新型索引结构的反最近邻查询

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义,提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree),该索引结构运用了R-树中分割空间数据的思想,将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance),利用多种序关系对原始点集进行划分,从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析,给出了MBDNN-树的性质.在此基础上,给出了MBDNN-树进行反最近邻查询的剪枝规则,进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性,有效地减少了结点的访问数量,从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明：基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.     

基于差分隐私的LBS群组最近邻查询

针对当前基于位置服务(LBS)的群组最近邻查询中出现的隐私保护问题,提出了一种新的基于差分隐私保护的LBS群组最近邻查询方法,该方法满足了差分隐私性质并引入了“区域不可区分”这一新的理念。基于分类及聚类给出了LBS群组构建方法并提供了群组隐私预算分配机制。提出了LBS群组用户位置扰乱算法(GPOL),将群组最近邻查询转换为群组质心的最近邻查询,并将其应用到整个隐私保护框架中。实验结果表明该方法能够有效地抵御现有的交叉攻击和组合攻击。     

基于Voronoi图的线段反向最近邻查询

提出一种基于平面线段的反向最近邻查询方法,用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性,给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明,反向最近邻方法易于找到相交的线段,具有较高的查询效率。     

一种新的面向集合的空间关键字查询方法

面向集合的空间关键字查询处理是数据库领域近年来的热点研究课题.针对已有查询的不足,定义一种新的描述集合质量的Cost函数,提出一种新的面向集合的空间关键字查询方法,并证明基于该Cost函数的查询问题是NP完全问题.对于给定的对象数据集D={o1,o2,…,on},q为包含位置信息和关键字集合的查询点,查询返回的是在对象数据集D中,既满足查询点q的全部关键字,又能成为q的近邻且较紧凑的对象集合.为处理该查询,利用最小圆覆盖包含全部关键字的对象集合,并采用有效的裁剪策略分别实现了该查询的近似查询算法和精确查询算法.最后通过实验验证了所提算法的有效性.     

数据集中单纯型连续近邻链查询方法

为解决数据集中的单纯型连续近邻链查询问题,提出一种基于Voronoi图的查询方法。给出单纯型连续近邻链查询的定义,利用Voronoi图的性质对大量数据点进行精减,设计可准确查询出数据集中单纯型连续近邻链的查询算法。实验结果表明,随着待查连续近邻链所含数据点规模的增大,该方法的效率比传统基于R树方法更高。     

基于空间近邻查询的移动医疗呼叫算法

随着大数据时代的到来，传统的计算机因为单机资源有限、运行速度慢、分布式处理支持差，已满足不了现行的医疗体系中的大数据处理需求，基于时空数据的移动医疗呼叫系统方法可以很好地解决这些问题。在移动云计算环境下研究[k]最近邻查询算法是当前一个热点问题，支持可扩展和分布式的空间数据索引对于kNN查询的效率影响很大，目前已有的查询算法不适合并行化或者会导致内容冗余。将MapReduce分布式处理技术与空间kNN查询方法相结合，设计可以快速检索到满足用户查询需求的医生位置信息的移动医疗呼叫算法。提出并构建了一个新的分布式空间数据索引方法：倒排Voronoi图索引，它将倒排索引和Voronoi图索引进行结合；提出了一种基于MapReduce的利用Voronoi图来处理kNN查询的高效算法，其在分布式环境下可以有效提高查询效率；用真实的和仿真的数据集来进行大量实验评估，实验结果表明所提出的方法具有良好的高效性和可扩展性。