高效前缀约简的三维Hilbert空间填充曲线编解码算法

3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性。为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率。理论上证明:当编码或解码一个k阶的窗体(窗体内总共含有2k×2k×2k个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法,编解码时间复杂度从O(k)降低到了O(1)。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。

顾及多级空间索引结构的矢量地图局部加密方法

随着地理信息产业的蓬勃发展,地图与各类生活服务深度融合,地图从专业化应用逐步走向大众化应用。大数据时代的到来,为地图数据的分发、共享、获取与动态更新等提供了极大便利,但伴随而来的是地图数据传输过程中面临的信息泄露、窃取等安全隐患问题也日益严峻。现有的矢量地图加密方法大多是在经典密码学算法基础上扩展而来,虽然已有加密方法考虑到矢量地图的特征,但是现有方法大多仍以整个地图或图层为加密单元,在用户需要访问某个局部的感兴趣区域时需要对整个地图文件或图层进行解密,对于矢量地图的按需局部加密仍未提出有效方案,还难以满足大数据时代地图按需用图、众包地图数据采集与云端更新等应用场景对矢量地图局部加密的应用需求。为此,本文从矢量地图的数据结构特点出发,提出了一种顾及多级空间索引的矢量地图局部加密方法。通过点、线、面不同矢量地图数据的加密试验分析,结果表明:①本文方法可以有效实现矢量地图的局部加解密;②相比于现有加密方法,本文方法采用局部加密策略,且支持多级分块并行加密,具有更高的加密效率;③本文针对不同加密单元采用不同加密参数,显著提高了加密算法的抗攻击能力。

基于Hilbert曲线的轨迹大数据分布式存储与索引方法

针对具有时空特征的轨迹大数据快速增长的趋势及对其快速查询的需求,传统的关系型数据库对海量轨迹数据的存储和特定的查询需求具有一定局限性,而非关系型数据库又难以满足海量数据的高效索引需求,轨迹数据的存储和索引效率仍亟待提高。本文设计并实现了一种基于HBase数据库的存储和检索的框架,以应对时空轨迹数据的高效管理。首先,构建了一种新颖的Rowkey结构,结合时空索引工具构建了GeoMesa-HBase底层存储模型;然后,融合了基于Hilbert曲线的编码技术构建空间索引,提高了轨迹数据的存储和检索效率;最后,为了评估所提方法的有效性,将其存储和查询性能与传统存储数据库(HBase和MySQL)和Geohash索引进行比较。试验结果表明,本文方案能够有效提升轨迹数据的存储和检索效率,这对于应对轨迹大数据管理领域面临的多项挑战具有重要现实意义。

基于改进的K-means聚类分区均匀化空间学习索引

传统空间索引的体量随数据量的增加而膨胀,查询效率较低。学习索引的体量不随数据量的增加而膨胀,同时避免了层级比较查询,性能优异。将学习索引应用于空间索引存在2个难点:一是选取合适的降维方法实现空间数据的排序;二是对降维后数据序列进行有效的简化分布计算,使其易于拟合。基于此,提出了一种网格混合聚类分区学习索引(grid-ml),用z曲线进行降维,用双层网格结构优化查询策略,用改进的K-means聚类算法进行数据分区,实现数据分布均匀化。对比实验发现,grid-ml构建速度快、存储空间小、查询效率高,较传统空间索引优势显著。

加权Hilbert型空间中超齐次核离散算子的最佳搭配参数及范数计算

引入超齐次核概念,利用权系数方法,讨论具有超齐次核离散算子在加权Hilbert型空间中的有界性及算子范数,得到该类算子最佳搭配参数的充分必要条件和算子范数的计算公式,统一了齐次核,广义齐次核及若干非齐次核情形的相关结果.

空间索引技术及其GIS应用综述

空间索引技术可提供高效的空间数据组织与管理方式,以支撑海量空间数据的挖掘与分析。针对当前空间索引存在的知识体系不明晰、选择难等问题,该文通过文献调查法和CiteSpace工具,依据空间划分及映射方法将空间索引划分为基于树结构、格网、空间填充曲线和地址编码的空间索引四大类,并综述其原理、空间结构、适用范围及在GIS领域的应用,最后对空间索引在数据组织、高效计算、可视化、可靠性等方面的研究进行展望。结论如下:基于树结构的空间索引最具普适性且可以处理多维度及多层次的数据,查询性能依赖于树结构的平衡性及数据的分布;基于格网的空间索引可以均匀划分空间以便于高效范围查询,却不适用于非结构化或动态数据集;基于空间填充曲线的空间索引可以在实现维度压缩的同时保持局部邻近性,但插入或删除数据可能导致整个曲线的重构难以频繁更新;基于地址编码的空间索引将语义地址信息转化为编码信息,便于高效检索,然而语义地址匹配仍存在较大误差和不确定性。研究结果可为空间数据组织和结构设计提供参考。

基于Hilbert空间向量赋权的网络选择算法

为了提升海上异构无线网络中移动节点业务完成率和网络资源配置效率,针对现有网络选择算法与业务需求匹配性较差、动态环境下业务完成率不高的问题,该文提出一种基于Hilbert空间向量赋权的网络接入选择算法。该算法采用基于Hilbert空间的网络-业务匹配模型,将网络特征与业务需求映射至同一空间,在同一坐标系内衡量网络是否满足业务需求;同时,采用基于优劣解距离法的预切换网络选择算法,引入网络-业务匹配权重对优劣解距离法标准化矩阵进行修正,确保所选网络与业务需求相匹配,克服传统网络选择中业务需求考虑较少、网络特征与业务需求难以进行统一衡量的问题。此外,采用基于空间距离的网络切换控制算法,将匹配权重、空间距离引入网络切换控制,保证业务传输连续性,提高动态环境下的业务完成率。仿真结果表明,相较于对比算法,该算法的业务平均完成率提高6.81%以上,有效提升了网络的业务传输能力和通畅度,间接实现了网络资源的有效配置。

Hilbert空间中Riesz-型框架的刻画

研究了Hilbert空间中Riesz-型框架的一些性质,给出了连续框架成为Riesz-型框架的一些等价条件,证明Hilbert空间中任意两个Riesz-型Parseval连续框架酉等价,进而证明了Hilbert空间中任意两个Riesz-型框架相似,最后通过引入由两连续Bessel序列诱导的有界线性算子进一步刻画了Riesz-型框架的等价性。

一种基于Hilbert排列码的GIS空间索引方法

分析了基于栅格格网的索引数据结构在空间查询中的重要地位 ,讨论了基于多维数据一维映射的空间排列的优点 ,对 Morton码、Gray码、Hilbert码和 Sierpinsky码的空间聚类特征进行了分析和比较 ,得出了 Hilbert码在空间查询中效率最高的结论 .考虑到基于特征的 GIS数据模型的特点 ,兼顾内存索引与磁盘索引 ,提出了基于Hilbert空间排列的点特征二叉平衡排序树动态索引结构和基于角点回溯的线特征索引结构 ,并对其在 GIS空间查询中的应用方法进行了论述 .

基于聚类的Hilbert R-树空间索引算法

R-树适合于动态索引,但空间重叠大,而Hilbert R-树也不能有效降低节点覆盖和交叠,直接影响R-树的查询效率。为适应大量的GIS查询应用需要,提出对Hilbert R-树节点进行聚类的索引算法,较好地解决相邻数据的聚类存放,使叶节点MBR面积减小,内部节点交叠降低,并对该算法进行实验测试和性能分析,结果表明该算法具有较高的查询效率。

基于多层索引及缓存的空间数据管理系统

为充分利用空间数据对象的位置信息,提升存储结构化程度及查询效率,基于多层索引及缓存建立空间数据管理系统。首先基于不同粒度建立用于渲染和查询的两层索引框架,同时为索引及空间数据建立内存缓冲队列。在查询过程中通过区域范围及索引多级筛选空间数据对象,在空间数据变更时增量修改索引及数据记录,在渲染时通过内存缓冲队列及渲染区域对应索引读取数据。结合实例,验证了索引及内存缓冲的效果,为高效空间数据存储及查询提供了技术支持。

集合空间关键字内聚组查询方法

给定一个道路网络和社交网络,集合空间关键字查询的目的是找到一组兴趣点,该组兴趣点的文本信息包含所有查询关键字,与查询的位置较近且彼此之间的距离较小。内聚组查询的目的是找到在地理位置和社交关系上紧密联系的一组用户;而集合空间关键字内聚组查询的目的是找到满足查询要求的一对最佳匹配的兴趣点集合和用户集合。针对这一问题,提出一种新的集合空间关键字内聚组查询处理模式。首先通过快速贪心查询过程获得候选兴趣点集合,然后使用core-tree结构存储(k,c)-core核心分解的结果,从而提高内聚组查询效率,并且保证查询结果能够同时满足用户之间的社会关系约束和兴趣点之间的空间位置约束。通过在真实数据集上开展实验,结果表明提出的方法比枚举方法的查询效率快1~2个数量级,并且具有较高查询准确性。

基于空间网格和Hilbert R-tree的二级R-tree空间索引

针对分布式海量空间数据库管理要求,提出了一种基于空间划分网格、Hilbert R-tree和普通R-tree的二级空间索引结构,该结构被命名为H2R-tree。然后,详细讨论了该结构的优点,并给出了实现算法。实际算例表明,H2R-tree具有多方面的优良性能,是一种值得推广的二级索引技术。

双层索引驱动的隧洞海量点云高效管理方法

针对隧洞表观性态监测,三维激光扫描获取的点云具有数据量巨大、非结构化以及狭长线状非均匀分布等特点,给隧洞点云数据处理极大的压力,也制约了隧洞工程点云监测应用的发展。为此,本文结合隧洞工程空间分布特点,提出一种基于双层索引结构的隧洞海量点云管理方法。该方法设计了一种基于Hough变换的隧洞水平中线粗提取方法,指导隧洞点云数据沿水平中线进行点云自动分段;而后利用“自下而上”的归并构建策略建立分段点云八叉树索引。在此基础上,利用非冗余的多层次细节(LOD)建模方法和内外存动态调度技术实现海量点云数据快速可视化。实验结果显示,本文方法有效提高了隧洞点云水平轴线提取效率,基于双层索引结构的隧洞点云管理在点云检索、海量点云数据可视化等方面表现出优异性能。

四元数Hilbert空间中Riesz基的刻画

四元数Hilbert空间在应用物理科学特别是量子物理中占有重要地位.本文讨论四元数Hilbert空间的框架理论,在四元数Hilbert空间中引入了Riesz基的概念,在此基础上刻画了Riesz基,给出了它们的一些等价条件;特别地,得到了四元数Hilbert空间中的一个序列是Riesz基的充要条件是它是一个具有双正交序列的完备Bessel序列,且它的双正交序列也是一个完备Bessel序列;并进一步证明了双正交序列中一个序列的完备性可以从特征刻画中去除.文中举例说明了双正交性、完备性和Bessel性质之间的关系.

基于多层Voronoi图索引的非点型空间对象区域查询方法研究

区域查询技术是面向城市地理空间大数据GIS系统的一个重要组成部分。在面对多中心、非均匀分布的城市地理空间数据时,相较于传统树形结构的R-tree索引,MVD索引通过多层网络结构有效避免了节点重叠带来的空间查询算法效率低下问题,然而原生MVD索引无法直接支持非点型空间对象的区域查询。针对该问题,首先根据点—质心—对象整体的映射关系设计一种基于MVD索引的非点型空间数据管理方案,并基于该方案利用空间对象最小外包圆的边界扩展技术实现了一种可靠的空间区域查询算法MVD-Polygon;然后根据空间对象尺度分布特征提出一种用于提高区域查询算法效率的的分级索引构建策略;最后在MVD索引的基础上形成了一套面向城市地理空间非点型数据的高性能区域查询技术框架MVD-Polygon-Grade。实验结果表明,与基于R-tree索引的主流区域查询算法Multi-step相比,MVD-Polygon-Grade在城市地理空间查询场景中具有更高的运行效率,充分证明了所提技术框架的可行性与实用性。

Hilbert空间中的算子非紧性测度

该文利用经典的Hausdorff非紧性测度理论研究了Banach空间中(特殊地,Hilbert空间中)的算子非紧性测度:具体地,先给出Banach空间中算子非紧性测度的表示问题,及其在全空间与子空间上的限制测度的等价问题;最后研究了Hilbert空间之间的有界算子序列的几个半范数相互等价的关系性质,特别地,其中包括了一种由Hausdorff测度生成的算子半范数.

一类加权序列空间中广义齐次核的Hilbert型离散不等式和序列算子的有界性

引入以指数函数为权函数的加权序列空间l_(r)^(φ(m))(Z),通过权系数方法,得到加权序列空间中具有广义齐次核的Hilbert型离散不等式,利用所得不等式讨论加权序列空间中序列算子的有界性及算子范数估计,并给出若干特例.

Hilbert空间中的K-R-融合框架

给出了Hilbert空间中K-R-融合框架和紧K-R-融合框架一些新的刻画,并利用框架理论和算子理论的方法和技术给出了K-R-融合框架的几个性质。最后,讨论了Hilbert空间中的K-R-融合框架的冗余性。

RPA:一种内存高效的度量空间recall@R近似最近邻搜索索引

现有的度量空间的近似最近邻搜索(approximate nearest neighbor search, ANNS)方法通常依赖于预选择的支撑点构成的序列,序列中的支撑点按照到数据元素的距离升序排列.然而,大多数现有的度量空间ANNS方法由于索引结构复杂、支撑点过多或者未能充分利用距离信息导致搜索时内存开销巨大.为此,提出精简排列阵(reduced permutation array, RPA)的度量空间recall@R近似最近邻搜索方法.对于全体数据元素,RPA预先选择k个支撑点,对每个数据元素仅存储离该数据元素最近的l个(l<<k),并将所有元素的支撑点序列构建为一个数组结构.在搜索过程中,利用一种得分函数,该函数基于查询对象到各个支撑点的距离来近似计算数据元素到查询对象的距离.同时,维护一个有界最小堆,以保存R个候选结果数据元素.RPA具有结构简单、内存效率高和可扩展性强等特点.实验结果表明,在相同召回率的情况下,与排列索引(permutation-based index, P-index)相比,RPA平均具有高达3倍的内存压缩比.研究结果可在内存资源有限的单机环境下提供一种有效的针对海量数据的ANNS方法.