空间对象数据库的网格索引机制

本文提出了针对空间对象的一种新的索引机制，称为网格索引（Ｌｄｅｘ）．Ｌｄｅｘ基于空间对象的位置及其分布，是一种高效实用的空间索引方法．文章全面地讨论了它的查找、插入、删除和修改算法及实现技术．

空间数据库网格索引机制的最优划分

该文证明了当空间对象的分布特征小于0.2929时,一级网格索引机制才有效,并获得了最佳网格划分条件.通过分析二级网格的最优划分,证明了二级网格检索机制比一级网格索引机制有效,可以减少存储桶的个数.

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.

一种基于网格索引的空间连接查询处理优化算法

针对云环境下的空间数据连接查询处理问题,提出一种基于MapReduce框架的高效空间连接查询处理优化算法.该算法采用网格划分方法将数据空间划分成大小相同的网格单元,并将其中一类数据集中的每个空间对象,按照其中心点的位置划分到所在的网格单元中,从而避免了连接对象的复制,网格单元之间根据其所包含数据对象的交叠关系构建网格索引;对另一类数据集中的对象,仅将其复制到与网格单元中数据有交叠的网格单元,从而过滤掉不可能有连接结果的数据对象,大大减少了后续的连接计算代价.合成数据和真实数据集上的大量实验表明,本文提出的空间数据连接查询处理优化算法在性能上明显优于原有SJMR查询处理算法.

利用层次网格索引提高WebGIS性能

层次网格索引是在传统网格索引的基础上 ,进一步改进 ,减少了传统网格索引的冗余和索引的大小。在层次网格索引的基础上 ,利用客户端和服务器端的双缓冲机制 ,可以减轻网络传输和服务器的负担 ,提高WebGIS应用的整体性能。

一种改进的网格索引生成方法

分析了网格索引的优缺点以及Bresenham等方法用于线状目标网格索引生成存在的问题,在此基础上提出了一种改进的网格索引生成方法,此方法避免了在生成网格索引时遗漏目标覆盖的网格格子,并可提高选择目标的精度。

基于轨道约束的空间目标球面网格索引及区域查询应用

针对海量、高速运动的空间目标检索查询效率低的问题,提出一种基于轨道约束的空间目标球面网格索引构建方法。该方法利用地球惯性系下空间目标轨道相对稳定的特性,通过维护球面剖分网格内途经的空间目标列表,实现了对高速运动目标的稳定索引。在此基础上,提出基于目标球面网格索引的区域查询应用方案,首先,依据一定步长离散查询时段;然后,计算查询区域在惯性空间的边界点坐标并确定交叉网格;其次,提取网格中的空间目标,计算并判断目标与区域的位置关系;最后,递归查询整个时段,实现空间目标过境查询分析。仿真实验中,传统逐目标查询方法耗时与目标数量线性正相关而与区域大小无关,单目标平均耗时0.09 ms;与之相比,所提方法用时随区域面积减小呈线性递减,区域格网数小于2 750时,时间效率高于对比方法,且能够维持相当的准确率。实验结果表明,该方法在实际区域应用中可以有效提升查询的效率。

基于网格索引的Top-k偏好查询算法

目的设计基于网格索引的Top-k偏好查询算法,提高Top-k偏好查询问题的解决效率.方法利用网格索引,采用概念划分的方法,实现基于范围查询和NN查询两种方式的Top-k偏好查询算法.结果通过真实数据集测试结果表明算法能够结合网格索引的优点,与基于R树索引的传统算法相比,在k值不断增加的情况下,查询效率提高了50%,能适应多种空间特征数据对象集合.结论网格索引可以有效处理Top-k偏好查询.

Spark环境下基于网格索引的轨迹k近邻查询方法

移动对象轨迹的k近邻(k nearest neighbor trajectories,kNNT)查询是一种重要的空间信息服务,主要用于寻找与给定轨迹最近邻的k条轨迹,被广泛地应用于智能交通、信息推荐等领域。随着轨迹数据量的快速增长,由于单机计算资源的限制,传统集中式环境下的kNNT查询效率和可扩展性无法满足实际要求。为了解决这个问题,设计了轨迹数据的分布式网格索引结构,该索引在Spark环境下将轨迹切分并映射到网格中,并引入轨迹还原表以保留查询时候选子轨迹段间的连续性。基于此索引,提出了Spark环境下的轨迹k近邻查询方法kNNT-Grid。实验结果表明,kNNT-Grid方法在分布式环境下实现了良好的查询效率和可扩展性,能够应对海量轨迹数据的k近邻查询需求。

基于凸包和网格索引技术的快速TIN生成算法及应用

在原有凸包推进算法的基础上,提出了一种针对散乱点集的快速生成TIN的算法。通过在三角形外接圆的最小网格覆盖中查找点扩展三角形,使得每次查找的点的个数与且只与散乱点的分布有关,而与散乱点集的大小无关;同时利用有向凸包和动态修正前沿圈等技术避免生成重复三角形,从而大大提高了建网的速度。实践证明,该算法具有可操作性和较强的实用性。该算法实现了两类基于不规则三角网数字地面模型的分析应用。

基于网格索引的高速网络数据流偏好查询方法

为增大高速网络中被唤醒信息节点的数量值水平,使得网络主机能够准确掌握数据流偏好,从而实现对网络数据的精准查询,提出基于网格索引的高速网络数据流偏好查询方法。根据网格索引原则,建立完整的空间方向定义标准,再分别从点目标匹配、线目标匹配两个角度,完成基于网格索引的高速网络数据指标度量。在此基础上,按照信息表建立条件,描述既定的数据流偏好,再通过计算分发查询向量的处理方式,实现对高速网络数据流偏好的精准查询。实验结果表明,在网格索引原则的作用下,随着网络报文发送数量的增大,被唤醒信息节点的数量值水平也在不断提升,对于高速网络主机而言,能够准确掌握数据流偏好,满足精准查询网络数据的实际应用需求。

基于层次网格索引的大批监控车辆显示模型

车辆定位和监控应用越来越多,但是大批车辆显示存在速度慢、车辆覆盖率低等问题。针对以上问题,提出了基于层次网格索引的大批监控车辆显示模型,为车辆建立多层网格索引,结合地图显示比例尺动态聚合重叠显示的车辆,实现了车辆监控的全覆盖,降低了数据传输量,提高了车辆显示速度。最后通过广东省重点车辆监控系统实现了该模型,验证了模型的有效性。

基于网格索引结构的TNN查询算法

目的应用网格索引结构实现TNN查询算法,提高查询效率.方法将首次查询到的TNN路径长设为探测距离,利用它缩小有效查询区域,随着查询的进行,不断更新探测距离,直至终止条件到达查询结束.结果实验表明,在同等条件下,利用网格索引比利用R-tree索引结构进行查询的效率至少高一倍,而且随着目标点个数的增加,优势更加明显.结论运用网格索引并选择合适的网格粒度实现TNN查询优于运用R-tree索引实现的算法.

基于网格索引的时空轨迹伴随模式挖掘算法

时空轨迹伴随模式是数据挖掘领域的一项重要研究内容。CMC(Coherent Moving Cluster)算法是一种经典的时空轨迹伴随模式挖掘算法,该算法引入了DBSCAN算法以挖掘出任意形状的簇。但是,DBSCAN聚类算法极耗时,导致CMC算法的时间效率较低。因此提出了一种基于网格索引的时空轨迹伴随模式挖掘算法MAP-G(Mining Adjoint Pattern of spatial-temporal trajectory based on the Grid index)。实验表明,MAP-G算法不仅比CMC算法具有更高的时间效率,而且能够过滤掉部分不正确的结果,因此结果也更加准确。

基于道路网格索引的无线通信基站定位与实现

为了促使无线通信基站定位技术进一步用于解决用户定位信息与空间地图信息匹配的问题,该文提出了一种基于话单的道路定位算法:针对移动场景,在基站定位过程中结合话单定位参数信息和空间道路信息,实现了将用户直接定位到道路上的目标;对矢量道路进行解析并采用网格索引技术建立索引,设计过滤条件对算法进行优 化,提高了定位的求解速度。以实际话单进行测试,得到了合适的网格化步长参数,通过对定位精度进行分析,证明了该算法的可行性和有效性。该算法可进一步提高基站定位技术的应用范围,对5G及物 联网技术也将有重要意义。

基于MapReduce和双层倒排网格索引的kNN算法

随着卫星定位技术和移动互联网技术的飞速发展,地理空间数据来源变得更加多源异构.面对海量地理空间数据,如何快速有效地找到目标周围的兴趣点变得异常重要.依据空间k近邻(kNN)查询算法,提高效率的关键在数据索引和数据块存储结构设计,通过引入云计算的MapReduce编程模型,设计了一种面向MapReduce的地理空间数据双层倒排网格索引,利用CircularTrip算法实现了目标点近邻查询计算,最终获得距离目标点最邻近的数据点集.实验结果表明,该索引方法较单层倒排网格索引下的kNN查询效率有明显提高,且数据量越大效率提升越明显,此法适合大规模并行计算.

一种基于网格索引的数据聚类算法

为了提高基于密度聚类算法的效率,避免算法在执行过程中的多余搜索,提出了一种基于DBSCAN算法的改进的空间数据聚类算法。该算法采用对象邻域空间进行划分的方法,将网格索引结构应用于该算法。在核心对象的邻域内选择八个方向上未标记且距离核心对象最边缘的对象来扩展种子对象,减少查询次数,降低聚类的时间复杂度。在实验中,利用海量数据集对算法进行测试,测试结果证明新算法在保证聚类精度的情况下时间效率显著高于DBSCAN算法。

基于网格索引的云海大数据模糊聚类方法仿真

针对云海大数据聚类问题,以及当前数据聚类方法中的不足之处,提出基于网格索引的云海大数据模糊聚类方法。通过云海大数据网格划分,建立云海大数据网格索引机制,用于识别与描述空间内数据的分布与定位信息,应用过程中需要根据实际需求选择适当的网格划分级别来保证网格索引效果;根据空间索引机制中各网格内数据的分布情况,将近邻的高密度数据网格进行合并与边界柔化处理,实现数据簇更新及边界调整,结合隶属度函数获取数据聚类信息,完成云海大数据模糊聚类。实验结果表明,基于网格索引的云海大数据模糊聚类方法的聚类迭代次数少于实验对比方法,能够有效辨识数据集的实际类簇数,聚类过程的运行时间更短,即使对于含噪数据集也具备较好的鲁棒性。

空间对象多级网格索引有效性的数学证明

传统的实验验证方式是不完全归纳的方式,理论说服力存在不足,通过严密的数学理论论证能够实现完备的证明。阐述了空间对象网格索引机制的原理,重点对多级网格索引做了详细介绍,尤其针对空间对象多级网格索引机制的优越性进行了完备的数学证明,从理论上论证了多级网格索引的有效性。

基于分布式运算的多网格索引人脸识别方法研究

针对当前人脸识别技术在大型人脸图形数据库研究应用存在的两大问题,一是批量处理人脸图像数据效率低;二是一种算法只对某一类人脸图像库有较好的处理效果,没有一种通用的处理算法,提出了基于分布式运算的多网格索引人脸识别方法,介绍了其模型结构、核心算法以及优点特色,对于人脸识别方法的研究和应用具有一定的借鉴价值。