空间查询处理技术综述

空中索引是依据空间对象的位置和形状或空间对象间的某种关系,按照一定顺序排列的一种数据结构。不同方式组织起来的索引结构需采用不同的检索方法,因此空中索引在一定程度上决定了空间查询处理的效率。回顾了常用的空间查询处理方法,并对现有的空中索引结构及空间查询处理技术进行了系统分类,分别对欧式空间、道路网络及无线广播环境下用于空间查询处理的空中索引及查询算法进行了详细描述。     

用户偏好约束的空间关键词范围查询处理方法

随着基于地理位置的个性化服务的广泛应用,用户偏好约束的空间关键词范围查询成为了研究热点。现有面向空间关键词范围查询的索引没有考虑用户偏好属性,导致剪枝性能和查询效率较低。为了解决该问题,提出了一种支持用户偏好属性、空间位置、关键词协同剪枝的混合索引BRPQ;并在此基础上,提出了高效的用户偏好约束的空间关键词范围查询处理算法。实验结果表明,相比现有索引,BRPQ索引的构建时间平均减少了13%,查询效率平均提升了20%。     

无线数据广播环境下路网最近邻居节点的查询

针对大规模用户数量,首次提出结合无线数据广播技术,在路网环境中进行最近邻居节点查询.该方法使用基于Voronoi图的算法转化路网信息,将处理后的路网信息作为广播数据,不仅提高了用户的查询效率,还减少广播数据中的冗余信息.在数据调度上,采用Hilbert曲线对数据排序,从而保持广播数据的空间临近性.实验表明,上述方法在为用户提供高效查询的情况下有效减少了访问时间.     

能量高效的无线传感器网络空间范围查询处理算法

现有无线传感器网络空间范围查询处理算法能量消耗大且当节点失效时查询处理过程易被中断,无法返回查询结果.文中提出了一种能量高效的算法ESA(Energy-efficient Spatial window query processing Algorithm).它将查询区域划分为若干个网格,每个网格中有一个簇头节点负责收集...     

链路感知的传感器网络空间范围查询处理算法

在无线传感器网络环境中,用户经常提交空间范围查询以获取网络某局部区域的统计信息,如最大温度、平均湿度等。现有的基于路线的空间范围查询处理算法假设节点通信模型为理想的圆盘模型,而实际的网络并不满足该假设,导致其能量消耗大且查询结果质量差。提出了一种链路感知的空间范围查询处理算法LSA,它根据网络拓扑和链路质量动态地将查询区域划分为若干个网格,依次收集各网格中节点的感知数据,以生成最终的查询结果。LSA算法通过遍历查询区域内的所有网格,保证了算法查询结果的质量。提出了启发式的网格划分方法以降低节点间数据通信的丢包率,给出链路感知的数据收集算法,以减少算法的能量消耗,提高查询结果的质量。通过仿真实验系统地分析和比较了LSA算法和现有的IWQE算法的能量消耗及查询结果质量,结果表明,在绝大多数情况下,LSA算法优于IWQE算法。     

数据广播环境下实时查询处理

现有的实时数据广播研究中,只考虑了具有截止期约束的单个数据请求的调度问题,而支持实时查询处理的数据广播技术尚未得到足够的关注。该文研究在on-demand数据广播环境下,如何有效地处理实时查询问题,提出一种新的数据调度算法(QSA)。通过仿真实验与目前最为有效的数据请求调度算法SIN进行了比较,结果显示QSA具有更低的错过截止期比率,在最好的情况下,QSA比SIN降低了17.45%。     

关于范围查询的动态轮廓计算方法

考虑关于范围查询的动态轮廓计算问题。基于范围查询将数据集中的点利用点与查询之间的距离特性进行转换,转换后的点可视为是一个以查询点为坐标原点的新空间中的数据点,利用现有的轮廓计算方法对转换后的数据集进行计算得到轮廓集合,以此为基础设计相应的算法来实现针对范围查询的动态轮廓的计算。利用网格索引和Z曲线结构设计多个剪枝策略降低算法的空间与时间复杂度。实验结果验证了算法的有效性以及在时间和空间上的效率。     

空间网络环境下的移动范围查询技术的研究

随着无线通信技术、移动定位技术和互联网的不断发展,在智能交通系统、自助旅游服务、数字化战场等应用中,时空数据管理,特别是对时空查询的处理受到了广泛关注.此领域中的已有研究工作涉及的范围很广,然而大部分技术都是针对欧式空间以及精确位置提出的.但在实际的情况下,对象的移动方向和轨迹通常是受(河流、公路等)限制的.本文定义了两种空间网络环境下的移动范围查询.针对这两种范围查询,提出基于“有效区间”概念的增量处理方法.并采用真实的路网数据集和模拟的对象集合分布,验证了算法的高效性.     

基于本地差分隐私的空间范围查询方法

基于本地差分隐私的用户数据收集与分析得到了研究者的广泛关注.用户数据的值域大小、编码机制以及扰动机制直接制约着空间范围查询的精度.针对现有编码机制与扰动机制难以有效响应空间范围查询的不足,提出了一种基于网格分割与四分树索引的空间范围查询响应方法GT-R(grid-based quadtree range query),该方法利用网格对用户数据的值域进行均匀分割,产生大小均等的单元格区域.同时利用四分树结构对所有单元格区域进行索引.每个用户结合服务器共享的四分树副本,对所拥有的数据进行编码.借助于编码后的四分树进行层次随机采样,并利用优化随机应答机制对所采层次中的结点进行本地扰动处理.服务器利用每个用户的报告值重构四分树索引结构,并响应空间范围查询.GT-R与现有的编码机制与扰动机制在真实的大规模空间数据集上实验结果表明,其分割精度以及响应范围查询效果优于同类算法.     

抗窃听攻击的传感器网络空间范围聚集查询处理算法

现有传感器网络聚集查询隐私保护方法采用加解密的形式保护节点感知数据,且需要网络中的所有节点参与查询处理。过多加解密操作会大量消耗节点能量,且用户可能只对其中部分区域的聚集结果感兴趣。针对这些问题,提出一种抗窃听攻击的传感器网络空间范围聚集查询处理算法PCPDA。该算法沿着既定路线,一边查询一边聚集,使得算法不依赖于预先构造好的拓扑结构,适用于网络拓扑结构动态变化的传感器网络,节省了维护拓扑结构的开销。该算法在未采用任何加密措施情况下保证了节点感知数据的隐私性。理论分析和仿真结果表明,PCPDA在能量损耗和隐私保护方面都优于现有算法。     

An efficient nonuniform index in the wireless broadcast environments

Data broadcast is an efficient dissemination method to deliver information to mobile clients through the wireless channel. It allows a huge number of the mobile clients simultaneously access data in the wireless environments. In real-life applications, more popular data may be frequently accessed by clients than less popular ones. Under such scenarios, Acharya et al.’s Broadcast Disks algorithm (BD) allocates more popular data appeared more times in a broadcast period than less popular ones, i.e., the nonuniform broadcast, and provides a good performance on reducing client waiting time. However, mobile devices should constantly tune in to the wireless broadcast channel to examine data, consuming a lot of energy. Using index technologies on the broadcast file can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. In this paper, we propose an efficient nonuniform index called the skewed index, SI, over BD. The proposed algorithm builds an index tree according to skewed access patterns of clients, and allocates index nodes for the popular data more times than those for the less popular ones in a broadcast cycle. From our experimental study, we have shown that our proposed algorithm outperforms the flexible index and the flexible distributed index.     

空间区域聚集查询方法研究

为了提高空间数据仓库中区域聚集查询的响应性能,通过使用R_tree对空间维进行分层后,采用物化视图存储空间对象及R_tree中间结点的聚集信息,能够有效地支持空间维和非空间维上的区域聚集查询。     

移动环境下多数据项请求的广播策略研究*

提出了一种移动环境下的多信道试探广播策略MCHM（multiple channel heuristic method）。该广播策略在多信道广播中采用高效的数据调度算法,在不重复广播的情况下,消除了多信道广播中多数据请求的访问冲突,大大减少了移动客户机的访问时间,提高了数据广播的性能。     

无线传感器网络空间查询算法 IWQE 优化研究

针对当前流行的窗口路线查询处理 IWQE 算法,若查询路线上节点选择不当(节点剩余能耗过低或节点相距偏远)而导致通信传输中断、查询结果丢失的问题,提出了相应的优化算法 EIWQE。算法以剩余能耗为节点选择基础,采用基于位置的路由协议 GPSR 构建多边形,通过增加中继节点保证查询路线的连通性,并根据最大剩余能耗选择邻居节点分担信息收集与处理任务,以进一步降低查询路线上节点的能耗。给出了 EIWQE的详细实现流程,并在 OMNET ＋＋平台上用仿真方法从查询成功率、查询遍及率、节点能耗的均匀度等方面验证了 EIWQE 算法的优越性。     

非结构化P2P网络下的空间范围查询

目前空间数据已被应用于很多领域,最典型的例子就是GIS（地理信息系统）。然而,随着空间数据爆炸式的增长以及用户应用需求的不断增加,传统的集中式的GIS逐渐显现出其可伸缩性差,容易形成性能瓶颈等缺陷。针对空间数据的范围查询是GIS中最典型的应用之一,提出一种基于非结构化的分组式P2P网络结构下的空间范围查询方法,使得系统具有更高的查询效率以及负载均衡特性和可伸缩性。最后通过仿真证明了该方法的有效性。     

移动环境中基于Huffman索引树的广播数据组织

移动计算环境中无线网络通信的非对称性和伸缩性要求 ,使得数据广播成为移动环境中数据发布和获取的重要手段 .为使移动客户有效地从广播中获取数据 ,该文提出了一种基于 Huffm an树的索引模型 ,给出 Huffman索引树的构造方法和基于 Huffman索引树的广播数据组织方式 .同时 ,该文还对比 B 树 ,对基于 Huffman索引树的数据组织方式从空间开销、调谐时间、存取时间等方面进行了性能分析与比较 ,表明该广播组织方式能提高移动数据广播的性能     

移动对象的反向k近邻查询算法的研究

传统的反向k近邻查询的研究主要集中在k=1时的单色移动对象的反向最近邻查询上,单色和双色的反向k近邻查询问题还没有解决。利用网格索引结构结合60°平面修剪策略,提出了一种解决单色和双色的移动对象的连续反向k近邻查询方法。最后实验结果验证了算法的有效性。     

一种支持多维区间查询的云对等网络索引架构*

针对用户在大规模云对等网络环境下多维区间查询问题,将基于m叉平衡树的索引架构引入到云对等网络环境下,在该架构上实现集中式环境下支持多维数据索引的层次化树结构,例如R树,QR树等。多维区间查询算法保证查询从树的任意位置开始,避免了根节点引起的系统性能瓶颈问题。通过计算和实验验证,对于N个节点的网络,多维区间查询效率为O(logmN)(m>2)(m表示扇出),由此可见,查询效率和维数d无关,查询效率不会随着维数d的增加而降低。最后建立基于扇出m的代价模型,并且计算出了最优的m值。