一种空间数据访问规律动态统计及信息压缩的方法及系统

摘要

本发明针对空间数据访问规律统计信息具有的离散性、无结构性，设计了一种空间数据访问规律动态统计及信息压缩的方法及系统，通过空间数据访问规律统计信息的点云表达、聚类梯度计算与聚类区域提取，实现偶发性访问的无效空间数据访问规律统计信息剔除，减少信息基量；通过对每个聚类点云集区域，按照点云差数和访问次数的点云序列用1个字节编码形成最终压缩统计数据输出，减少信息总量。本发明相对于现有技术，解决了由于全局动态统计带来的不可承载的网络流量问题，实现了实时动态跟踪空间数据访问全局分布规律，大大改善了空间数据系统公众服务能力。

说明书

技术领域

本发明属于大规模分布式环境下空间地理信息系统技术领域，尤其涉及海量空间信息存 储、访问、缓存和控制应用技术领域，具体涉及一种云计算环境下空间数据访问规律动态统 计及信息压缩的方法及系统。

背景技术

随着高精度遥感影像技术的提高，对空间数据（DOM/DEM/DLG/DRG）的开发和利用， 已经被广泛重视并应用到众多领域。数字地球中的空间信息服务质量问题，即如何支持大规 模、高强度的并发用户访问以提供高可靠、高可用的空间信息服务以及如何最快速地将空间 数据传输并显示在数字地球的客户端，成为工业界和学术界的关注热点。随着互联网络技术 的发展和宽带网络的普及，空间数据的服务形式从桌面转变到分布式网络环境中，新的服务 形式迫切需要将空间数据服务和网络通信技术融合到一起，从而在分布式网络环境下为用户 各种空间数据浏览、分析、查询、漫游等服务提供高效的平台支持。空间信息服务的质量， 对于加速推广和普及空间信息服务和提升数字地球用户的服务体验，具有重要意义，相关的 研究也就成为热点。

空间数据访问规律的动态统计，可有效的为空间数据的存储组织、副本数量及其存储分 布提供依据，而动态统计所产生的海量空间数据访问规律统计信息将带来不可承载的网络流 量，既而有算法研究如何通过P2P的方式，减少统计信息融合的副本数量。但由于统计信 息基本量巨大，简单的代理分发和融合依然难以满足要求。

研究表明，空间用户访问统计信息存在由于用户兴趣、地区热点等引发的用户访问特 征行为，也存在用户随意访问等偶发性行为。针对用户特征访问行为，其对应瓦片被再次访 问的可能性大，而对偶发性访问行为，其行为准则难以判断，对应瓦片被再次访问的可能性 不可预测。针对偶发性访问而进行空间数据瓦片的存储组织调整，将变得非常频繁和低效， 不但很难有效提高空间信息服务系统的性能，相反，这种频繁的无序调整还将额外增加系统 的计算和传输开销因此，如何减少偶发性访问形成的空间数据访问规律信息，成为问题的关 键之一。

针对空间数据的压缩有很多研究，包括删格数据的压缩、矢量数据的压缩等。将空间数 据映射成空间点云进行数据压缩处理的研究相对较少。纯粹的基于点云处理的研究包括边界 提取、表面重建以及模型简化处理等，而点云去噪是基于点云测量和处理的重要过程之一， 应用领域较广，包括地形测量，如利用地面三维激光扫描进行地形测量数据去噪，三维重构 和曲面拟合等。

不同应用目的，点去噪算法也存在差异，对于有序或者部分有序的点云来说，可以采用 的去噪算法有很多，如基于最小二乘估计的维纳滤波、卡尔曼滤波等。针对无序点云，一般 是先利用相关规则建立其相互之间的拓扑关系，如八叉树法、k-d tree法以及空间单元格法 等。海量空间统计数据点云规模巨大，数据映射到点云后，其点云基本是无序的，相互之间 没有拓扑关系或很难确定其拓扑关系，针对这种无序海量点云，目前的研究算法较少。

所以，解决由于海量空间数据访问规律统计信息传输带来的不可承载的网络流量问题， 从而实现能实时动态跟踪空间数据访问全局分布规律、大大改善空间数据系统公众服务能力 的方法及系统，是目前该领域的重要研究方向。

发明内容

本发明目的在于解决现有技术不足，提供一种能解决由于海量空间数据访问规律统计信 息传输带来的不可承载的网络流量问题、能实时动态跟踪空间数据访问全局分布规律、大大 改善空间数据系统公众服务能力的空间数据访问规律动态统计及信息压缩的方法及系统。

本发明的方法所采用的技术方案是：一种空间数据访问规律动态统计及信息压缩的方法， 其特征在于，包括以下步骤：

步骤1：空间数据访问规律统计信息点云输出：将空间数据访问规律信息按照每块瓦片数据 的空间位置及其被访问下载次数，形成空间数据访问规律统计信息点云输出；

步骤2：空间数据访问规律统计信息聚类计算：根据获取的聚类计算半径参数计算空间数据 访问规律统计信息点云聚类梯度，根据计算得到的聚类梯度剔除偶发性的离散访问点云，保 留有效特征访问点云，减少空间数据访问规律统计信息基量；

步骤3：空间数据访问规律统计信息区域提取：根据获取的聚类区域提取扩散半径、聚类区 域内点云差数量参数计算聚类内点云欧式距离，将特征访问点云进行聚类分组，形成聚类点 云集，对空间数据访问规律统计信息进行聚类区域划分和分类提取；

步骤4：空间数据访问规律统计信息聚类压缩：根据每个聚类点云集区域，计算聚类区域内 点云差，按照点云差数和访问次数的点云序列用1个字节编码形成最终压缩统计数据输出。

作为优选，所述的空间数据按照金子塔瓦片的形式存储，每块瓦片的被访问次数为空间 数据访问规律统计信息；空间数据访问规律统计信息包括空间数据的位置坐标和访问次数。

作为优选，所述的空间数据访问规律统计信息空间坐标范围、空间数据块数量参数通过 系统计算自动获取；聚类梯度计算参数、聚类区域提取扩散半径、聚类区域内点云差数量通 过配置参数设置。

本发明的系统所采用的技术方案是：一种空间数据访问规律动态统计及信息压缩的系统， 其特征在于，包括：空间数据访问规律统计信息表达单元、空间数据访问规律统计信息聚类 计算单元、空间数据访问规律统计信息区域提取单元和空间数据访问规律统计信息聚类压缩 单元；

所述的空间数据访问规律统计信息表达单元用于将空间数据访问规律信息按照每块瓦片数 据的空间位置及其被访问下载次数，形成空间数据访问规律统计信息点云表达；

所述的空间数据访问规律统计信息聚类计算单元用于根据获取的聚类计算半径参数计算空 间数据访问规律统计信息点云聚类梯度，剔除偶发性的离散访问点云，保留有效特征访问点 云，减少空间数据访问规律统计信息基量；

所述的空间数据访问规律统计信息区域提取单元用于根据获取的聚类区域提取扩散半径、聚 类区域内点云差数量参数计算聚类内点云欧式距离，将特征访问点云进行聚类分组，形成聚 类点云集，达到对空间数据访问规律统计信息进行聚类区域划分和提取；

所述的空间数据访问规律统计信息聚类压缩单元用于对提取的每个聚类点云集区域，按照点 云差数和访问次数的点云序列用1个字节编码形成最终压缩统计数据输出。

作为优选，所述的空间数据访问规律统计信息表达单元包括空间参数获取模块、点云表 达调节因子计算模块和空间点云输出模块；

所述的空间参数获取模块用于获取空间数据访问规律统计信息空间坐标范围、空间数据块数 量、空间数据被访问或下载最大次数参数；

所述的点云表达调节因子计算模块用于计算空间数据访问规律统计信息中空间数据点云输 出调节因子；

所述的空间点云输出模块用于根据空间数据位置和调节因子输出将空间数据访问规律输出 成空间点云。

作为优选，所述的空间数据访问规律统计信息聚类计算单元包括：聚类梯度计算参数输 入模块和聚类梯度计算模块；

所述的聚类梯度计算参数输入模块用于控制聚类计算半径；

所述的聚类梯度计算模块用于区域内聚类梯度计算。

作为优选，所述的空间数据访问规律统计信息区域提取单元包括聚类区域提取参数输入 模块和聚类区域提取模块；

所述的聚类区域提取参数输入模块用于限制聚类区域提取扩散半径、限制聚类区域内点云差 数量；

所述的聚类区域提取模块用于提取聚类区域。

作为优选，所述的空间数据访问规律统计信息聚类压缩单元包括聚类区域点云差计算模 块、点云序列组织模块和点云序列游程编码压缩模块；

所述的聚类区域点云差计算模块用于计算聚类区域内点云差；

所述的点云序列组织模块用于将聚类区域按照坐标顺序和点云差数量依序组织；

所述的点云序列游程编码压缩模块用于按照游程编码规则，将按序组织的点云序列进行编码 压缩。

本发明具有的有益效果是：空间数据访问规律统计信息存在由于用户兴趣、地区热点等 引发的用户访问特征行为，也存在用户随意访问等偶发性行为；针对用户特征访问行为，其 对应空间数据瓦片被再次访问的可能性大，而对偶发性访问行为，其行为准则难以判断，对 应瓦片被再次访问的可能性不可预测；本发明能在空间数据访问规律统计信息中，剔除偶发 性访问形成的统计信息，并对点云数据根据欧式距离形成聚类集后压缩编码，形成最终统计 信息输出，大大减少实际需要传输分发的空间数据访问规律统计信息总量；解决了由于海量 空间数据访问规律统计信息传输带来的不可承载的网络流量问题，能实时动态跟踪空间数据 访问全局分布规律，大大改善空间数据系统公众服务能力。

附图说明

附图1：是本发明的方法流程图。

附图2：是本发明实施例中系统的结构示意图。

附图3：是本发明实施例中空间数据访问规律统计信息表达单元的功能模块图。

附图4：是本发明实施例中空间数据访问规律统计信息聚类计算单元的功能模块图。

附图5：是本发明实施例中空间数据访问规律统计信息区域提取单元的功能模块图。

附图6：是本发明实施例中空间数据访问规律统计信息聚类压缩单元的功能模块图。

具体实施方式

以下结合附图和具体实施方式对本发明做进一步的阐述，本实施例主要以地理信息系统 作为载体进行具体说明。

针对空间数据访问分布规律，微软研究院通过Hotmap模型得到数字地球系统中的影像 瓦片请求符合幂律(Power-law)访问分布，但这种局部、静态的访问分布规律，不能真正实时、 动态的反映访问分布规律的全局信息，从而制约了系统服务能力的提高。一方面，由于存在 地形区域的差异（海洋、沙漠、城市）、时事热点的差异（海湾战争、朝韩冲突、台海问题） 等，针对空间数据的访问是高度分布不均的，而且国际时事风云变幻，热点区域经常转移， 导致空间数据的访问规律也动态变化；另一方面，分布式空间信息服务环境下的异构服务器 也存在更新替换、性能老化，导致这种分布不均和设备性能差异（处理能力的差异（内存、 CPU）、存储能力的差异（存储聚合速度、存储容量、容错能力）、有效传输带宽的差异）是 经常变化的；因此需要对这些要素信息进行动态统计和分发，以便跟踪这些变化，及时调整 地形数据的存储组织策略和预取、缓存策略。

通过简单的同步、复制机制进行异构服务器的全局、动态统计和获取空间数据访问分布 规律，将带来的不可承载的网络流量。以SRTM90地形数据为例，共3538890块瓦片，若 每个字节表示一个瓦片的访问次数，则每个字节可以代表最大255次访问，可以计算，当服 务器数量达到1000个时，一次统计分发，由于没有信息压缩，每个服务器产生的数据都将 分发999次，总共将分发3292.55GB的总数据量，通过这种方式实时、动态统计将持续产 生大量的统计流量，从而挤占用户服务带宽，影响服务体验。因此，如何有效的减少空间数 据访问规律动态统计信息总量成为关键。

请见图1、图2、图4、图5和图6，本发明的方法所采用的技术方案是：一种空间数据 访问规律动态统计及信息压缩的方法，包括以下步骤：

步骤1：空间数据访问规律统计信息点云输出：将空间数据访问规律信息按照每块瓦片 数据的空间位置及其被访问下载次数，形成空间数据访问规律统计信息点云输出；

步骤2：空间数据访问规律统计信息聚类计算：根据获取的聚类计算半径参数计算空间 数据访问规律统计信息点云聚类梯度，根据计算得到的聚类梯度剔除偶发性的离散访问点云， 保留有效特征访问点云，减少空间数据访问规律统计信息基量；

步骤3：空间数据访问规律统计信息区域提取：根据获取的聚类区域提取扩散半径、聚 类区域内点云差数量参数计算聚类内点云欧式距离，将特征访问点云进行聚类分组，形成聚 类点云集，对空间数据访问规律统计信息进行聚类区域划分和分类提取；

步骤4：空间数据访问规律统计信息聚类压缩：根据每个聚类点云集区域，计算聚类区 域内点云差，按照点云差数和访问次数的点云序列用1个字节编码形成最终压缩统计数据输 出。

其中，空间数据按照金子塔瓦片的形式存储，每块瓦片的被访问次数为空间数据访问规 律统计信息；空间数据访问规律统计信息包括空间数据的位置坐标和访问次数；空间数据访 问规律统计信息空间坐标范围、空间数据块数量参数通过系统计算自动获取；聚类梯度计算 参数、聚类区域提取扩散半径、聚类区域内点云差数量通过配置参数设置。

请见图2、本发明的系统所采用的技术方案是：一种空间数据访问规律动态统计及信息 压缩的系统，包括：空间数据访问规律统计信息表达单元100、空间数据访问规律统计信息 聚类计算单元200、空间数据访问规律统计信息区域提取单元300和空间数据访问规律统计 信息聚类压缩单元400；空间数据访问规律统计信息表达单元100用于将空间数据访问规律 信息按照每块瓦片数据的空间位置及其被访问下载次数，形成空间数据访问规律统计信息点 云表达；空间数据访问规律统计信息聚类计算单元200用于根据获取的聚类计算半径参数计 算空间数据访问规律统计信息点云聚类梯度，剔除偶发性的离散访问点云，保留有效特征访 问点云，减少空间数据访问规律统计信息基量；空间数据访问规律统计信息区域提取单元 300用于根据获取的聚类区域提取扩散半径、聚类区域内点云差数量参数计算聚类内点云欧 式距离，将特征访问点云进行聚类分组，形成聚类点云集，达到对空间数据访问规律统计信 息进行聚类区域划分和提取；空间数据访问规律统计信息聚类压缩单元400用于对提取的每 个聚类点云集区域，按照点云差数和访问次数的点云序列用1个字节编码形成最终压缩统计 数据输出。

空间数据访问规律统计信息表达单元100包括空间参数获取模块101、点云表达调节因子计 算模块102和空间点云输出模块103；空间参数获取模块101用于获取空间数据访问规律统 计信息空间坐标范围、空间数据块数量、空间数据被访问或下载最大次数参数；点云表达调 节因子计算模块102用于计算空间数据访问规律统计信息中空间数据点云输出调节因子；

空间点云输出模块103用于根据空间数据位置和调节因子输出将空间数据访问规律输出成 空间点云。

其中，空间数据访问规律统计信息聚类计算单元200包括：聚类梯度计算参数输入模块 201和聚类梯度计算模块202；聚类梯度计算参数输入模块201用于控制聚类计算半径；聚 类梯度计算模块202用于区域内聚类梯度计算。空间数据访问规律统计信息区域提取单元 300包括聚类区域提取参数输入模块301和聚类区域提取模块302；聚类区域提取参数输入 模块301用于限制聚类区域提取扩散半径、限制聚类区域内点云差数量；聚类区域提取模块 302用于提取聚类区域。空间数据访问规律统计信息聚类压缩单元400包括聚类区域点云差 计算模块401、点云序列组织模块402和点云序列游程编码压缩模块403；聚类区域点云差 计算模块401用于计算聚类区域内点云差；点云序列组织模块402用于将聚类区域按照坐标 顺序和点云差数量依序组织；点云序列游程编码压缩模块403用于按照游程编码规则，将按 序组织的点云序列进行编码压缩。

本系统实际工作时的具体流程为：

（1）空间数据访问规律统计信息点云输出：通过所述空间数据访问规律统计信息表达 单元100将空间数据访问规律信息按照每块瓦片数据的空间位置及其被访问下载次数，形成 空间数据访问规律统计信息点云输出；在这一过程，包括以下方面：

①利用所述的空间参数获取模块101获取空间数据访问规律统计信息空间坐标范围、空 间数据块数量、空间数据被访问或下载最大次数参数；

空间数据访问规律统计信息的空间坐标范围根据所有统计的空间数据坐标，分别选择最 大坐标和最小坐标作为空间坐标范围；

空间数据块数量N依据空间坐标范围计算面积可得，即连续空间坐标范围内，每个点 代表一块空间数据；

空间数据被访问或下载最大次数参数只需要依次获取每块空间数据块i的被访问或下载 次数ki，取最大值即可。

②利用所述的点云表达调节因子计算模块102计算空间数据访问规律统计信息中空间 数据点云输出调节因子；

若空间瓦片总个数为N，每个瓦片的访问次数分别为k_i,则调节因子α要求满足式（1） 限制；

α≤255-max(k_i),i=1,2,…,N   （1）

其中255表示最大访问次数必须不大于255，对于大于255的空间数据，通过拆分成多 份数据进行压缩处理，最大访问次数必须小于255的限制，是为了满足后续处理中游程编码 运算效率要求。

③利用所述的空间点云输出模块103将空间数据访问规律信息根据空间数据位置和调 节因子输出成空间点云；

首先将地理信息系统的每个瓦片看成一个点，所有瓦片形成一个空间连续点集，没有被 访问的空间瓦片称为“虚点”，被访问的瓦片称“实点”；

同时，“虚点”以颜色RGB（255，255，255）表示，实点i根据其访次数，分别按照 颜色RGB（ki+α，0，0）表示，其中ki为空间数据实点i被访问或下载次数，最大不超过 255次；

最后，按照“虚点”、“实点”的相对坐标，将空间数据访问映射成空间点云，其中“实 点”代表被访问的瓦片，点云颜色深浅表示被访问的次数。

（2）空间数据访问规律统计信息聚类计算：通过所述空间数据访问规律统计信息聚类 计算单元200，根据获取的聚类计算半径参数计算空间数据访问规律统计信息点云聚类梯度， 根据计算得到的聚类梯度剔除偶发性的离散访问点云，保留有效特征访问点云，减少空间数 据访问规律统计信息基量；在这一过程，包括以下方面：

①利用所述的聚类梯度计算参数输入模块201获取用于控制聚类计算半径参数；

控制聚类计算半径参数r和空间访问聚类梯度阀值T通过配置管理输入。

②利用所述的聚类梯度计算模块202进行区域内聚类梯度计算；

考察一段时间t，设某瓦片“实点”p_i的访问次数为k_i，以p_i为中心，边长r的区域 内，其ni个邻居“实点”瓦片p′_i,j(j=1,2,…,n_i)的访问次数分别为k′_i,j(j=1,2,…,n_i)， 访问聚类梯度表示某“实点”瓦片被访问的聚集程度，聚集程度越低，是偶发性访问的可能 性越大，定义瓦片p_i的访问聚类梯度为T(p_i)，则有：

$T\left(p_i\right)=\underset{j}{\overset{N_i}{\Sigma }}\frac{k_i\times k_{i,j}^{\prime }\times r}{f_d(p_i,p_{i,j}^{\prime })\times k_{\mathrm{av}}^2}$

其中，k_i×k′_i,j表示瓦片的被访问次数，次数越大，访问聚类梯度越大，被再次访问的 可能性越大；函数f_d(p_i,p′_i,j)表示两点之间的欧式距离，通过瓦片坐标可以计算，距离越 大，“实点”瓦片越离散，偶发性访问的可能性越大，被再次访问的概率越小，k_av表示统 计范围内所有“实点”的平均访问次数；参数r和k_av为平衡系数，使访问聚类梯度T(p_i)的 值落入1附近；

瓦片的访问梯度为T(p_i)越大，表示该瓦片更聚集，该瓦片下次被再次访问的概率相对 更高，需要统计融合传输，相反，则更离散，被再次访问的概率相对更小；

选择一个合适的空间访问聚类梯度阀值T，过滤掉不需要统计的访问瓦片，将大大减少 空间访问统计数据的瓦片数量。同样，选择一个足够大的T，将包含全部“实点”瓦片。

（3）空间数据访问规律统计信息区域提取：通过所述的空间数据访问规律统计信息区 域提取单元300，根据获取的聚类区域提取扩散半径、聚类区域内点云差数量参数计算聚类 内点云欧式距离，将特征访问点云进行聚类分组，形成聚类点云集，对空间数据访问规律统 计信息进行聚类区域划分和分类提取；在这一过程，包括以下方面：

①利用所述的聚类区域提取参数输入模块301获取限制聚类区域提取扩散半径、限制聚 类区域内点云差数量参数；

聚类区域提取扩散半径参数E_d和限制聚类区域内点云差数量参数K_c通过配置管理输 入。

②利用所述的聚类区域提取模块302提取聚类区域；

经过偶发性离散点剔除后的点云数据，存在明显的分块聚集性，聚类区域提取是将散乱 点剔除后的点云，根据其空间临近性和颜色临近性进行分组。空间临近性依据其相互之间的 欧式距离，颜色临近性根据其访问次数差；

定义1：聚类CL是满足下列等式的点的集合：

$\mathrm{CL}=\left\{p_i\right|\left(\begin{array}{c}\sqrt{(p_i-p_j){(p_i-p_j)}^T}\le E_d\\ |k_i-k_j|\le K_c\end{array}\right),p_j\in \mathrm{CL}\}---\left(2\right)$

其中E_d为欧式距离调节因子，用于限制聚类大小和扩散半径；K_c为访问次数（点云颜 色）调节因子，用于限制聚类点云之间的访问频率差。基于以上分析，E_d和K_c最大为127。

式（2）表明，聚类内点云之间的距离和色差必须满足条件，通过调整调节因子，可组 成不同的聚类组合，且聚类组合内的点云相互之间点云差小于127，可以用1个字节表示。

（4）空间数据访问规律统计信息聚类压缩：通过所述的空间数据访问规律统计信息聚 类压缩单元400，根据每个聚类点云集区域，计算聚类区域内点云差，按照点云差数和访问 次数的点云序列用1个字节编码形成最终压缩统计数据输出；在这一过程，包括以下方面：

①利用所述的聚类区域点云差计算模块401计算聚类区域内点云差；

设空间数据块i的被访问或下载次数ki，空间数据块j的被访问或下载次数kj，则空间 数据块j的聚类区域内点云差KDj=kj-ki。

②利用所述的点云序列组织模块402将聚类区域按照坐标顺序和点云差数量依序组织 成点云序列；

对每个聚类点云集，按照如下形似组织形成点云序列：定义瓦片点云p_i由三元组<x_i， y_i，k_i>描述，其中x_i，y_i为点云坐标，k_i为访问次数，针对四维空间点云，只需扩展为 四元组，为简单起见，以某层平面瓦片点云为例。聚类内所有点云根据顺序，按照<x₁,x₂- x₁,…, x_n-x_n-1>、<y₁,y₂-y₁,…, y_n-y_n-1>和<k₁,KD2,…, KDn>的形式组织，形成三个点 云差序列。

③利用所述的点云序列游程编码压缩模块403将组织的点云序列按照游程编码规则进 行编码压缩输出；

将坐标点云差序列的第一个数用2个字节表示，其余点云差数和访问次数点云序列用1 个字节表示，并对每个序列按照游程编码进行压缩，最终形成空间访问统计聚类压缩编码数 据输出。

本发明针对空间数据访问规律统计信息具有的离散性、无结构性，设计一种云计算环境 下空间数据访问规律动态统计信息压缩方法，通过空间数据访问规律统计信息的点云表达、 聚类梯度计算与聚类区域提取，实现偶发性访问的无效空间数据访问规律统计信息剔除，减 少信息基量；通过对每个聚类点云集区域，按照点云差数和访问次数的点云序列用1个字节 编码形成最终压缩统计数据输出，减少信息总量。解决由于全局动态统计带来的不可承载的 网络流量问题，能实时动态跟踪空间数据访问全局分布规律，大大改善空间数据系统公众服 务能力。

本发明可应用于大规模分布式环境下空间地理信息系统技术领域，特别是涉及海量空间 信息存储、访问、缓存和控制应用技术领域。

以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围，因此，凡在本发 明的精神和原则之内所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之 内。