基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.     

基于路网的移动对象动态双层索引结构

为了支持对大规模不确定性移动对象当前及将来位置的查询,亟需设计更加有效和高效的索引结构.当前索引算法主要考虑索引建立和维护的效率问题或关注基于索引进行查询时的准确性,对索引建立维护以及查询时性能综合考虑的研究较少.针对已有方法的不足,提出基于路网的移动对象动态双层索引结构DISC-tree,对静态路网信息采用R~*-tree索引,对实时更新的移动对象运动轨迹采用结点更新代价较小的R-tree进行索引,设计哈希表和双向链表辅助结构对索引协同管理.成都市真实地图数据集上的实验结果表明:相比于经典的NDTRtree,DISC-tree在索引建立和维护方面时间代价平均减少39.1%,移动对象轨迹查询时间代价平均减少24.1%;相比于FNR-tree,DISC-tree的范围查询准确率平均提高约31.6%.     

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

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

方向感知的路网移动对象范围查询算法

路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。     

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

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

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率.这类索引通常以同一线路为单位来组织轨迹数据的存储.索引通常采用两层的R-tree索引结构,上层的2D R-tree用于索引在某个区域内的线路,下层的2D R-tree用于索引某个时间段内在这些区域的移动对象.这类索引在处理轨迹信息的时间维度的时候,仅仅是把时间维度等同于空间的维度来进行R树维度的扩展.由于R树算法不能有效地降低最小限定矩形的空间堆叠问题,尤其是在数据量较大、数据维数增加时表现得更为明显.所以,为了提高路网中移动对象时空信息的存储以及查询的效率,本文则将轨迹信息中的时间数据和空间数据整合起来,提出了一种移动对象数据索引PM-tree(Phase-point Moving Object Tree).首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维"时空相点",并讨论了时空相点之间的偏序关系,建立了基于相点偏序划分的相点序分枝结构,为索引的建立提供了理论支撑.接着论文以MON-tree索引为基础,以相点序分枝结构来改进其下层索引结构,提出了时空相点移动对象数据索引,该索引能完成运动轨迹时空的一体化查询,能避免类R-tree索引中最小限定矩形堆叠导致的效率低下的问题,有效地缩小搜索空间.最后论文实现了索引的增量式动态更新管理.通过实验的对比分析,表明PM-tree索引不但能有效提高储存空间的利用率,"一次一集合"的查询模式还提高了查询性能.     

一种移动对象数据库全时态区域查询处理方法

全时态区域查询方法是可以同时支持对于移动对象过去、现在以及预测性未来信息区域查询处理的方法,是移动对象数据管理的一个重要方面.在移动对象数据库领域,大量技术被提出以支持历史信息查询或未来信息预测,但是缺乏对于全时态区域查询方法的研究.提出一个可以支持精确区域查询的移动对象全时态查询方法,并支持对于历史信息的轨迹查询.为提高查询效率,提出索引结构PPF-index.在PPF-index中,首先在移动对象信息到达时,利用提出的TB_TPR-tree结构来索引移动对象现在以及预测性未来信息;其次,历史轨迹信息经过轨迹切分后利用3D R-tree进行索引;最后,提出基于PPF-index索引结构的全时态区域查询算法.全时态区域查询算法中的时间范围不同,需要访问的索引结构也不同.实验结果表明,PPF-index可以高效支持全时态查询,并具有很高的更新效率.     

路网中高吞吐量移动对象实时查询算法

随着无线通信技术、空间定位技术和移动计算技术的快速发展,基于位置的查询成为数据库领域的一个重要研究问题。研究了路网中移动对象的KNN查询,一系列的算法被提出用于解决移动对象的KNN查询问题。然而,这些算法关注于查询的快速响应问题或者专注于解决移动对象的快速更新问题。随着移动对象数量的不断增加,当查询和更新大量涌入时,吞吐量成为一个更重要的问题。针对移动对象的更新数据流和查询数据流,提出了一种基于内存的高吞吐量移动对象KNN查询算法——DSRNKNN算法,用于处理路网中移动对象的KNN查询。DSRNKNN算法采用了基于快照的模式。在每个快照中,DSRNKNN算法通过重新构建索引的方式避免了复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,充分利用查询内和查询间的并行,增加了数据的局部性,提高了算法的效率。在基于实际路网生成的数据集上对算法进行了测试,实验验证了DSRNKNN算法具有很好的性能表现。     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

分布式环境下大规模移动对象范围查询算法

移动对象的连续范围查询是许多基于位置的服务的核心问题。针对该问题,提出一种面向大规模移动对象并发范围查询的分布式搜索方法。首先,设计了一种由全局网格索引（GGI）和局部弹性四叉树构成的移动对象分布式动态索引（DDI）结构。其次,提出了一种基于DDI结构的分布式查询算法（DSA）,该算法首先引入了一种在移动对象和查询点的位置连续变化的情况下的查询结果增量更新策略;然后,在增量更新过程中引入一种面向多并发查询的共享计算优化策略,该策略能够根据已有计算结果对移动对象范围查询结果进行增量搜索。最后,基于德国路网模拟了3个具有不同空间分布的移动对象数据集,将DSA与NS(Naive Search)、GI(Grid Index)和分布式混合索引（DHI）进行对比。实验结果表明,与性能最好的对比算法DHI相比,DSA的初始查询时间减少了22.7%,增量查询时间减少了15.2%,性能优于对比算法。     

k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks

Recent development of wireless communication technologies and the popularity of smart phones are making location-based services (LBS) popular. However, requesting queries to LBS servers with users’ exact locations may threat the privacy of users. Therefore, there have been many researches on generating a cloaked query region for user privacy protection. Consequently, an effcient query processing algorithm for a query region is required. So, in this paper, we propose k-nearest neighbor query (k-NN) processing algorithms for a query region in road networks. To effciently retrieve k-NN points of interest (POIs), we make use of the Island index. We also propose a method that generates an adaptive Island index to improve the query processing performance and storage usage. Finally, we show by our performance analysis that our k-NN query processing algorithms outperform the existing k-Range Nearest Neighbor (kRNN) algorithm in terms of network expansion cost and query processing time.     

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

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

Countering overlapping rectangle privacy attack for moving kNN queries

An important class of LBSs is supported by the moving k nearest neighbor (MkNN) query, which continuously returns the k nearest data objects for a moving user. For example, a tourist may want to observe the five nearest restaurants continuously while exploring a city so that she can drop in to one of them anytime. Using this kind of services requires the user to disclose her location continuously and therefore may cause privacy leaks derived from the user's locations. A common approach to protecting a user's location privacy is the use of imprecise locations (e.g., regions) instead of exact positions when requesting LBSs. However, simply updating a user's imprecise location to a location-based service provider (LSP) cannot ensure a user's privacy for an MkNN query: continuous disclosure of regions enable LSPs to refine more precise location of the user. We formulate this type of attack to a user's location privacy that arises from overlapping consecutive regions, and provide the first solution to counter this attack. Specifically, we develop algorithms which can process an MkNN query while protecting the user's privacy from the above attack. Extensive experiments validate the effectiveness of our privacy protection technique and the efficiency of our algorithm.     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

基于连续查询的用户轨迹k-匿名隐私保护算法

随着移动服务和移动网络的持续发展,基于LBS的连续查询服务被广泛应用。基于单点的K-匿名位置隐私保护算法已经不能满足连续查询下用户位置隐私需求。针对用户轨迹隐私保护提出新的保护方法,该方法采用不可信第三方中心匿名器,用户获取自己的真实位置后首先在客户端进行模糊处理,然后提交给第三方匿名器,第三方匿名器根据用户的隐私需求结合用户某时刻的真实位置信息生成虚假用户,然后根据历史数据生成虚假轨迹。为了进一步提高虚假轨迹与用户真实轨迹的相似性,该算法提出了虚假轨迹生成的两个约束条件：虚假轨迹距用户真实轨迹的距离约束和相似性约束。经大量实验证明,该算法与传统的不同时刻K-匿名算法相比,不仅可以满足连续查询的用户轨迹隐私保护而且可以满足基于快照的LBS用户位置隐私保护。     

轨迹大数据:数据处理关键技术研究综述

大数据时代下移动互联网发展与移动终端的普及形成了海量移动对象轨迹数据.轨迹数据含有丰富的时空特征信息,通过轨迹数据处理技术可以挖掘人类活动规律与行为特征、城市车辆移动特征、大气环境变化规律等信息.海量的轨迹数据也潜在性地暴露移动对象行为特征、兴趣爱好和社会习惯等隐私信息,攻击者可以根据轨迹数据挖掘出移动对象的活动场景、位置等属性信息.另外,量子计算因其强大的存储和计算能力成为大数据挖掘重要的理论研究方向,用量子计算技术处理轨迹大数据可以使一些复杂的问题得到解决并实现更高的效率.本文对轨迹大数据中数据处理关键技术进行综述.首先,介绍轨迹数据概念和特征,并且总结了轨迹数据预处理方法包括噪声滤波、轨迹压缩等.其次,归纳轨迹索引与查询技术,以及轨迹数据挖掘已有的研究成果包括模式挖掘、轨迹分类等.总结了轨迹数据隐私保护技术基本原理和特点,介绍了轨迹大数据支撑技术如处理框架、数据可视化.本文也讨论了轨迹数据处理中应用量子计算的可能方式,并且介绍了目前轨迹数据处理中所使用的核心算法所对应的量子算法实现.最后,对轨迹数据处理面临的挑战与未来研究方向进行了总结与展望.     

面向连续查询的敏感语义位置隐私保护方案

针对连续查询位置服务中构造匿名区域未考虑语义位置信息导致敏感隐私泄露问题，通过设计[(K,θ)]-隐私模型，提出一种路网环境下面向连续查询的敏感语义位置隐私保护方案。该方案利用Voronoi图将城市路网预先划分为独立的Voronoi单元，依据用户的移动路径和移动速度，选择具有相似特性的其他[K-1]个用户，构建匿名用户集；利用匿名用户集用户设定的敏感语义位置类型和语义安全阈值，以及用户所处语义位置的Voronoi单元，构建满足[(K,θ)]-隐私模型的语义安全匿名区域，可以同时防止连续查询追踪攻击和语义推断攻击。实验结果表明，与SCPA算法相比，该方案在隐私保护程度上提升约15%，系统开销上降低约20%。     

多用户连续k近邻查询多线程处理技术研究

针对面向移动对象集的多用户连续k近邻查询处理,提出了基于多线程的多用户连续查询处理(MPMCQ)框架,采用流水线处理策略,将连续查询处理过程分解为可同时作业的查询预处理、查询执行以及查询结果分发三个执行阶段,利用多线程技术来提高多用户连续查询处理的并行性;基于MPMCQ框架和移动对象内存格网索引,提出了基于多线程的连续k近邻查询处理(MCkNN)算法。实验结果与分析表明,基于MPMCQ框架的MCkNN算法在多核平台上优于CPM、YPK-CNN等现有算法。     

基于分解和加密的外包数据库隐私保护

目前基于全部数据加密的外包数据库服务不能有效平衡数据处理性能与数据隐私保护之间的关系。针对该不足,提出一种基于单个外包数据库服务器的隐私保护方法,通过加密和分解关联隐私约束规则最大限度地减少加密属性,实现最小加密属性分解的近似算法,并给出基于元数据的查询分解方法,实现查询处理。理论分析表明,该方法能实现外包数据的隐私保护,又能较好地改善外包数据的查询性能。     

Towards practical private processing of database queries over public data

Privacy is a major concern when users query public online data services. The privacy of millions of people has been jeopardized in numerous user data leakage incidents in many popular online applications. To address the critical problem of personal data leakage through queries, we enable private querying on public data services so that the contents of user queries and any user data are hidden and therefore not revealed to the online service providers. We propose two protocols for private processing of database queries, namely BHE and HHE. The two protocols provide strong query privacy by using Paillier’s homomorphic encryption, and support common database queries such as range and join queries by relying on the bucketization of public data. In contrast to traditional Private Information Retrieval proposals, BHE and HHE only incur one round of client server communication for processing a single query. BHE is a basic private query processing protocol that provides complete query privacy but still incurs expensive computation and communication costs. Built upon BHE, HHE is a hybrid protocol that applies ciphertext computation and communication on a subset of the data, such that this subset not only covers the actual requested data but also resembles some frequent query patterns of common users, thus achieving practical query performance while ensuring adequate privacy levels. By using frequent query patterns and data specific privacy protection, HHE is not vulnerable to the traditional attacks on k-Anonymity that exploit data similarity and skewness. Moreover, HHE consistently protects user query privacy for a sequence of queries in a single query session.