一种基于单调链和Geohash索引的公共边裂缝处理算法

在分析矢量数据压缩时产生公共边裂缝的原因以及解决该问题的常用方法的优缺点的基础上,提出一种基于单调链和Geohash的公共边裂缝处理算法.首先,算法采用单调链扫描线算法从图形集中为每一个矢量图形快速确定可与之相交的图形子集;其次,利用Geohash索引快速查找相交图形的公共点,继而提取出公共边和非公共边;然后,设计一个索引结构存储公共边的压缩信息,用于公共边只压缩一次的前提下保证图形集的完整性;最后,从有效性和时间效率2个方面对算法进行分析和评价.实验结果表明,算法对图形进行逻辑分段保证了公共边在相邻图形中化简结果的一致,与目前比较优秀的同类算法相比,在可行性以及在时间效率上都具有一定的优越性.

面向海量交通数据的HBase时空索引

针对HBase无法直接建立时空索引所带来的交通数据查询性能问题,基于HBase行键设计了面向海量交通数据的HBase时空索引。首先利用Geohash降维方法将二维空间位置数据转化为一维编码,再与时间维度进行组合;然后根据组合顺序的不同,提出了四种结构模型,分别讨论了模型的具体构成以及交通数据查询中的适应面;最后提出了相应的时空索引管理算法及基于Hbase时空索引的交通数据查询方法。通过实验验证了提出的HBase时空索引结构能有效提升海量交通数据的区域查询性能,并比较了四种时空索引结构在不同数据规模、不同查询半径以及不同时间范围的查询性能,量化验证了不同索引结构在交通数据查询中的适应场景。

一种基于HBase的空间关键字查询算法

针对传统关系数据库处理海量空间文本数据的不足,基于HBase数据库提出了一种结合Geohash编码与分词技术的空间文本索引方案,并基于该空间文本索引提出了一种多边形区域内的空间关键字查询算法。通过与传统经纬度索引方案的实验比较,验证了算法的高效性和可扩展性。

一种面向相似查询的轨迹索引方法

轨迹数据具有重要的应用价值,轨迹索引技术得到广泛的研究与关注。传统索引方法存在节点重叠、缺乏动态划分空间能力和丢失大量原始信息等问题,为此提出一种面向相似查询的轨迹索引方法GeoSAX。该方法将原始轨迹分成若干等长子段并采用基于Geohash的空间编码;对编码后的整条轨迹设计了基于HBase存储的索引架构;实现相似轨迹查询。GeoSAX不仅节点间没有重叠,还能依据数据量的大小对空间动态划分,同时保留指定精度的轨迹信息。在真实的航运和出租车数据集上进行的对比实验表明,与传统方法相比GeoSAX具有更好的轨迹查询性能。

基于实时数据和历史查询分布的时空索引新方法

在大数据时代,数据具有体量大、时空复杂性明显、对实时性要求较高等特点,而传统基于树形结构对大规模时空数据进行索引的方法存在存储空间浪费和查询效率较低的问题。为了解决该问题,提出了一种基于数据和历史查询记录分布建立时空索引的新方法 HDL-index。该算法一方面根据数据在空间上的分布,通过空间划分的思想建立索引网格;另一方面考虑到查询在时间上的延续性,对查询记录对象进行密度聚类后抽象出查询代表模型,然后根据模型的坐标位置和其查询粒度对整体查询区域进行分割。两部分所得到的索引网格都采用Geohash编码,最终合并得到最优的索引编码。HDL-index在考虑数据分布的同时充分考虑用户查询行为,使得频繁查询区域上的索引更加细化。在真实航空数据集上与同类方法进行比较测试的结果表明,其创建索引的效率提高了50%;同时在数据均匀分布的情况下对热点区域的查询效率可提高75%以上。

一种基于受限网络的移动对象索引结构

为了提高受限网络中移动对象索引效率和满足近邻查询需求,基于FNR-Tree索引结构和Geohash编码算法,提出一种能够满足近邻查询的移动对象索引结构RNR(restricted network R-Tree)。通过添加哈希表、链表等辅助索引结构来提升索引结构操作效率,融合Geohash编码和相关算法来使得索引结构能高效满足近邻查询的需求。通过将指定区域按一定规则划分,可使得索引结构具备在不规则范围查询的能力。使用旧金山市地理数据和移动对象数据对索引结构性能进行了测试,结果表明RNR具有较高索引结构操作效率,并且能够高效地提供窗口查询和近邻查询的功能。

结合否定关键词的空间关键词查询

面向个性化约束的空间关键词查询是数据库查询领域的热点问题,其中快速性和匹配性是衡量此类查询优劣的核心问题.传统空间关键词范围查询无法匹配除地理位置和关键词信息以外的带有个性化约束条件下的查询,且大多数二维空间下的索引结构的构建更新速度和查询效率较低.针对上述问题,提出了一种带否定关键词约束(即用户不喜欢的关键词)的查询模式.采用Geohash字符串表示兴趣点对象,对字符串排序后构建B+树作为二叉树的叶节点,通过二叉树过滤带否定关键词的对象,构建了基于Geohash的混合索引结构BGIB-Tree.在此基础上,依靠Geohash编码的递归性,设计了前缀匹配搜索算法.以区域编码和对象编码前缀匹配为剪枝策略,快速找到满足空间约束的兴趣点,最后在倒排索引中双向搜索即可完成查询.通过与IR-Tree和BIR-Tree对比,在真实数据集上对BGIB-Tree的构建时间与相关参数对查询算法的影响做出验证,实验证明结果表明在索引构建时间上减少30%,算法查询效率提高29%.

辽东山区红松人工林空间分布格局研究

为提高人工红松林经营效果,研究红松人工林的林分空间结构数量分布特征和质量分布特征,以辽东山区红松人工林为研究对象,采用geohash的Peano曲线填充算法索引4株相邻木,利用剔除边界木的方法设置缓冲区,排除边界木对分析结果的影响,根据空间结构参数(角尺度)分析林分空间结构数量分布特征,结合角尺度和胸径分析林木空间结构质量分布特征。结果表明:红松人工林平均角尺度为0.65,角尺度为0.75的林木居多,相对频数为49.61%,林分整体呈聚集分布;角尺度为0.25、0.5、0.75和1的红松胸径之间差异不显著(P>0.05)。林木单体获得足够的生长空间,聚集分布特征未对质量特征造成影响,人为经营干扰有利于提高森林生长质量;剔除边界木法分析的结果与实际样地情况相符,剔除边界木法或可能为新的缓冲区设置方法研究林分空间结构分布。

Geohash-Trees:一种用于组织大规模轨迹的自适应索引

蕴含着挖掘价值的轨迹数据分布在世界各地,且规模庞大。如何在全球范围内组织轨迹数据并支持高效范围查询成为难题。一种自适应索引组织框架被提出来管理查询全球范围大规模轨迹数据集,其基本思想为:针对不同轨迹数据集,根据Geohash编码,生成层数最深的Geohash格网覆盖住整个轨迹数据集范围;以格网作为根节点,生成Geohash-Trees;为了加快查询定位到对应索引,根据编码前缀相同的特点设计了字典查询树。Geohash-Trees是一种基于格网划分的空间索引,它能够根据轨迹密度自适应使用多种剖分策略划分空间,提高范围查询效率。为了支持索引动态更新,设计了增量插入和更新算法。同时,该索引被移植到商用数据库Oracle中,利用数据库性能高效管理查询轨迹数据。实验结果表明,该方法在范围查询以及占用空间等方面明显优于Oracle内置的R树索引。