基于热点区域簇群的林区地图瓦片缓存策略

柴龙成,高文灵,尹俊飞,陈星涵,陈飞翔



基于热点区域簇群的林区地图瓦片缓存策略

柴龙成,高文灵,尹俊飞,陈星涵,陈飞翔*

北京林业大学信息学院, 北京 100083

为了提升林区瓦片地图的运行与服务效率，本文针对瓦片的特点以及用户操作习惯，提出一种基于区域簇群（Regional Cluster）的瓦片缓存策略。该策略从林区地图的区域性出发，根据瓦片记录信息，首先通过全局空间自相关分析确定聚类类型，再通过局部空间自相关分析出热点区域。策略结合瓦片地图的塔状结构特点，对传统的LFU算法进行改进，保留热点区域瓦片金字塔内的瓦片数据群，提高瓦片缓存命中率。实验表明，该策略能够提高瓦片缓存命中率，加快林区瓦片地图的访问速度。

瓦片地图; 缓存策略; 区域簇群; 空间自相关

Web GIS（网络地理信息系统）是一种基于Web端的地理信息系统，它拥有采集、传输、存储、管理、处理、分析、表达和使用地理空间数据等功能[1]，其跨平台快速部署的特点得到了用户的广泛认可。在传统的Web GIS中，都是由客户端向服务器发送所需区域范围请求，服务器根据范围来实时生成图片并返回，时间长、效率低、出图慢的缺点很明显[2]。为了满足Web GIS对于地图显示、切换、浏览速度的需求，Google提出了瓦片地图（Map Tile）的概念，利用提前生成的静态图片，快速响应地图请求[3]。瓦片地图依照一定的切割规则，将地图在不同的比例尺下分层，每层切割成相同大小的瓦片地图，根据用户所需空间范围返回瓦片数据，达到局部地图快速访问的目的[4]。在此基础上，又增加了瓦片缓存机制，通过本地数据与远程服务器数据的共同协作，大大提高了用户浏览地图的速度。

在瓦片缓存策略改进方面，国内外许多专家学者做了大量研究，并相应提出了面向网络GIS的最小价值空间数据缓存替换算法GDLVF[5]、用户行为选择参与的缓存替换策略UPBA[6]、基于瓦片寿命与访问热度的缓存置换策略TCLEPR[7]等。这些文献设计的瓦片缓存策略对瓦片地图更新效率有所提升，但都是根据单个瓦片粒度计算出的价值来判断需要替换哪些瓦片，却忽略了瓦片本身的区域性、连续性、层级性等特性，并且林区地图本身也有很强的区域特性。通过分析用户的移动行为特征以及操作习惯，每个用户有其特有的经常访问的地点[8]，并且会在对同一个林场区域进行较频繁的缩放、移动操作，在切换到另一个林场地图区域后，又会出现类似的行为。用户在高频度的缩放、移动、切换地图时，脱离瓦片特性的缓存策略往往会遇到缓存命中率低、缓存频繁置换占用大量系统资源的情况。

针对传统瓦片缓存策略的不足，本文提出了基于区域簇群（Regional Cluster，简称RC）的瓦片缓存策略，将瓦片缓存根据其位置、层级特点，再结合林区区域性特点，以簇群的方式进行管理。如图1所示。

1 瓦片缓存区域簇群管理策略设计

瓦片缓存区域簇群管理策略通过对用户历史数据以及在线实时统计数据空间自相关分析得到访问频度高的范围区域，根据各个高频区域范围，建立多区域金字塔数据存储结构，对瓦片数据进行簇群管理，再在LFU缓存策略的基础上进行改进，将簇群数据与离散数据统一管理，对于长时间最少访问的离散数据与簇群数据分别进行单独置换与集体置换。

1.1 区域金字塔索引设计

1.1.1 统计单位瓦片访问频度瓦片金字塔一般采用的是四叉树模型，是由二维瓦片图像数据的特性决定的[9]。一个二维的图像可以被均分为四个部分：东北、东南、西北、西南，四叉树结构可以很好地表示图像数据的分割。如图2所示，四叉树在每层级上的节点数为4n个，第0层的唯一节点为根节点代表整个区域地图，第1层存在4个节点分别显示整个区域的1/4，第2层存在16个节点分别显示整个区域的1/16，以此类推[10-13]。

图1 瓦片缓存策略的区别

图2 四叉树示意图

其中D为分辨率，为地图层级，则该层地图被分割为2的2次幂的瓦片块。该层每一块瓦片可以由二维坐标(,)唯一索引，再加入瓦片的层级确定的索引，组成瓦片的唯一索引值Tile ID= (,,)。

地图窗口在滑动、缩放时，每次请求的数据范围皆为矩形区域。矩形的左下角(min,min)与右上角(max,max)就可以确定窗口矩形的范围与位置。再将各层每次被访问的区域都投影到瓦片塔的最底层(图3)。把每次投影到底层的对应区域内的瓦片被访问频数相应增加1，最终可以得到最底层地理单元瓦片块被访问频数灰度图。该灰度图反映了用户的地图访问特点以及各区域之间瓦片的需求差异。经常访问的林区以及对同一区域放缩地图查看的瓦片区域会拥有较高的命中次数。

1.1.2 瓦片区域金字塔的设计为了实现区域簇群瓦片缓存管理，提高瓦片命中率，本研究设计了多区域金字塔结构。通过构建对于高频瓦片的区域瓦片金字塔，来保证高频瓦片数据在缓存内的优势。根据历史数据以及在线实时请求数据，热点区域划分得到访问频度高的区域，分别建立多个瓦片缓存金字塔，对区域数据进行统一管理。在高频度访问的地区，移动、缩放地图所请求的瓦片索引都落在该区域的瓦片金字塔内，通过保留区域瓦片金字塔内的数据，可以提高瓦片缓存的命中率。设最底层的瓦片为最小瓦片单元，每个最小瓦片单元包括了最小的地理元素以及最详细的地图信息。多区域瓦片金字塔结构如图4所示，根据四叉树原则，从瓦片地图最底层向上收缩，直至收缩到单块能囊括该高频区域的瓦片为止。该瓦片即为区域瓦片金字塔的塔顶，金字塔每层对应的瓦片构成了区域金字塔的主体。为方便计算，区域瓦片金字塔将该区域最底层的瓦片索引范围作为唯一标识。

图3 瓦片金字塔

图4 区域瓦片金字塔示意图

1.2 获取瓦片热点区域

1.2.1 瓦片空间分布模式分析根据用户的行为习惯可知，这些被命中区域瓦片之间有高度的空间自相关性。空间自相关是空间依赖性的重要形式，也是后续开展空间数据探索性空间分析（Exploratory spatial data analysis, ESDA），以及划分热点区域的充分条件[14-16]。本文将一名随机林业工作人员的用户地图访问记录，包括底层瓦片命中数据以及其命中次数（未访问的瓦片次数记为0），通过Globlal Moran’s统计方法公式（2）来评估这组数据的区域空间自相关性，其中自相关性分为三种：聚类模式、离散模式、随机模式。

将分子通过方差进行归一化，指数值在[-1.0，+1.0]区间之内。如果指数值为正，代表瓦片的命中次数分布具有正相关性，即随着空间分布位置（距离）的聚集，相关性就越发显著。若指数为负，则代表具有负相关性。还可以根据式（4）来计算得分值来判断瓦片的命中次数在统计学上的显著性。

图5为对瓦片访问数据进行Globlal Moran’s空间计算分析的结果。

图5 瓦片数据空间自相关分析结果

Fig.5 Results of spatial autocorrelation analysis of tile data

从图5可知，值是标准差的5.489079倍，远超过2.58，从而可以判断该组数据在99%的置信度情况下拒绝零假设，说明其在空间自相关性中表现出聚类特征。因此可以对该组数据进行热点区域聚类分析，划分热点区域范围。

1.2.2 热点区域划分在确定数据的全局自相关特性后，采用局部空间自相关来分析局部空间数据分布特征，如非典型局部区域、空间聚集区、异常值等。本文以Anselin Local Moran’s方法式（5）来判定拥有相似访问频数的瓦片数据[17,18]。

式子中的参数定义与Globlal Moran’s公式的参数定义相同。Anselin Local Moran’s方法的得分显著性检验计算公式（6）。

Anselin Local Moran’s方法根据Local Moran’s分析得到莫兰指数值、值、值，来对瓦片访问数据进行分类。若大于1.96，表示临近范围的瓦片访问数据具有95%置信度的相似度，为高值聚类（HH）或者低值聚类（LL）；若小于-1.96，表示其数据为95%置信度下的空间异常值；其他的数据为不具有统计显著性的瓦片数据。

通过分析得到高值聚类的瓦片数据位置83个，可以将其视为用户访问的热点位置。为进一步确认瓦片热点区域范围，以热点位置为中心，根据瓦片位置以及瓦片命中次数构造标准差椭圆。椭圆中心为高值聚类瓦片区域的加权平均中心，椭圆的长轴与短轴分别由、方向的标准距离确定，式（7）所示。

由公式（8）得到椭圆的倾斜角度：

为方便瓦片金字塔的构建，本文以标准差椭圆的水平最小外切矩形（向外取整）范围作为热点范围，如图6所示。将统计得到的热点范围作为区域金字塔范围，对各个热点区域金字塔内的瓦片数据进行统一管理。

1.3 瓦片缓存管理策略

为提高缓存命中率，本文设计了服务于热点区域瓦片数据、离散数据与簇群数据整合管理的缓存管理策略，缓存中的数据结构如图7，分别是RC缓存列队，四叉树缓存区和空间对象区域。

图6 部分热点区域划分结果

图7 缓存数据结构

首先从空间分析得到各个热点区域，由左下顶点（0,0）与右上顶点（1,1）唯一确定，两个顶点的水平距离为1-0,垂直距离记为1-0，分别记为D、D，并且再给每个区域一个Area ID值，即热点区域可记作（Area ID,，，D，D）。统计所有热点区域左下顶点的0值得到中位数x。构造以x值为根节点，以所有0值为子节点的排序二叉树。每个节点存储有热点区域信息，以及用于存储瓦片金字塔簇群的瓦片表。排序二叉树的构造目的是便于判定用户请求的瓦片是否位于热点区域瓦片金字塔范围内。具体流程如下：

（1）假设用户请求的瓦片索引对应最底层瓦片索引为（X,Y），将X与二叉树的节点进行比较，得到所有满足X大于X且X-X小于节点D值的节点；

（2）将得到的节点中在轴方向进一步筛选。若存在Y–Y小于Dy值的节点，则表示该请求的瓦片在该热点区域瓦片金字塔范围内，进入第3步。否则该瓦片没有落在热点区域范围内，直接返回；

（3）将该瓦片的Tile ID以及对应的瓦片存储内存地址放入该节点下的瓦片表内。

瓦片区域查询的过程由子线程完成，不影响主线程瓦片缓存的访问与载入，所有瓦片缓存地址都储存在同一张缓存哈希表内供地图进程调取。

为了提高瓦片的利用率，以及实现区域瓦片簇群管理，本文在LFU缓存策略基础上进行了改进，将热点区域Area ID与离散瓦片Tile ID放入同一个LFU队列当中。当离散瓦片被访问时，它的Tile ID对应的访问频次就会增加；当热点区域的瓦片被访问时，该区域的Area ID对应的访问频次也会增加。由于热点区域瓦片表的瓦片数量大，被访问的概率高，因此不容易被离散瓦片淘汰，提高了高频数据的缓存寿命。只有用户长时间很少访问该热点区域，该热点区域对应的瓦片金字塔内的数据才会被淘汰。

1.4 瓦片缓存管理策略流程

客户端请求瓦片的缩放等级为以及平面坐标（,)，地图数据在该层级上被切割了2的2次幂个地图瓦片，在二维坐标范围计算瓦片的坐标值(,)即可获取瓦片的唯一坐标值(,,)，随后向服务端请求瓦片。瓦片数据具有唯一的Tile ID，Tile ID是由层级、行号、列号组合变换而成的字符串，可以确定唯一的瓦片地图块：Tile ID=(,,) (9)

其中，表示瓦片层级，表示该瓦片在层级的行序号，表示该瓦片在层级的列序号，Tile ID=(,,)表示层级为，行序号为，列序号为的编码，定位到的索引项采用哈希存储。设缓存瓦片索引表的索引项为ind，则Tile ID为索引项的关键字，用来标识索引项ind。设Index为缓存中存放数据的索引集：∀ind ϵ Index, ind=(Tile ID, Tile Heat, Size, Fre) (10)

ind(Tile ID) ϵ Index表示索引集Index中关键字为Tile ID的索引项，Tile Heat表示该瓦片的热度值，Size表示该瓦片大小，Fre表示该瓦片被请求的次数。

当用户放缩、移动地图，不断有新的瓦片请求以及瓦片缓存产生，区域簇群瓦片管理策略具体流程为：

（1）策略初始化，首先读取历史记录进行空间分析，若符合空间聚类特点，则对数据进行热点分析，得到瓦片请求高频区域，将高频区域存入排序二叉树。主进程根据索引请求查询判断缓存哈希表内是否存在相应的瓦片数据，若存在则直接将数据返回，否则通知线程池下载对应的瓦片数据，下载完成后通知主线程，并将数据存入缓存哈希表；

（2）子线程根据瓦片的请求索引，在热点区域排序二叉树内进行查询。如果该索引落在某个热点区域内，则将该瓦片的Tile ID以及对应的数据地址存入该区域的瓦片表内，同时将该区域的Area ID在LFU中的频数加1。如果瓦片未落在任何一块热点区域内，则直接将该瓦片的Tile ID在LFU中的频数加1。当向LFU队列插入数据且队列饱和时，将队列中访问频数最少的数据弹出。若弹出的是Tile ID，将缓存哈希表中对应的瓦片数据删除；若弹出的是Area ID，则将Area ID对应的热点区域节点从二叉树中删除，同时删除该区域瓦片表内的记录及对应缓存哈希表内的数据；

（3）当队列中的有Area ID被弹出，则对现有的离散瓦片数据进行空间分析，若符合空间聚类特点，就通过热点区域分析将得到新的区域插入到二叉树中。如此往复。

RC瓦片缓存管理策略结合了瓦片自身区域性的特点，结合并改进传统LFU算法的改进与结合，将簇群瓦片与离散瓦片统一管理，提高了林区瓦片地图浏览速度。

2 实验评价

2.1 实验环境

实验通过Wire shark采集客户端多个用户的瓦片请求日志，以及用户对应的历史数据日志，共计1120485条记录。实验环境CPU为双核i5，主频2.70 GHz，内存16 G。根据用户的瓦片请求日志，可以获得瓦片的层级、行列号、大小、请求时间s等数据，以此来模拟用户的客户端行为。实验在RC瓦片缓存管理策略的基础上模拟用户的客户端行为，统计瓦片缓存命中率。

2.2 实验结果与分析

将统计得到的用户的瓦片请求分别在LFU、LRU、FIFO、RC缓存策略基础上进行瓦片模拟调度。对相应的瓦片缓存命中率在不同缓存容量大小下进行比较,得出各缓存策略瓦片缓存命中率实验数据统计表（下表仅展示实验中10%、20%、30%、40%、50%相对缓存大小下的数据）和实验结果（如图8所示）。

图8 瓦片缓存命中率

表1 各缓存策略瓦片缓存命中率实验数据统计表

实验表明瓦片四种算法的缓存命中率（瓦片命中率以及字节命中率）都随着缓存容量增加而增加，增加的速率逐渐降低，曲线趋于平稳。在四种算法中，FIFO缓存策略效率最低，远低于其他几种策略。LRU缓存策略表现要优于FIFO，对数据淘汰队列有更好的优化。LFU缓存策略避免了LRU因为偶然性或者周期性的状况而产生缓存命中率下滑的影响，在实验结果中的表现要优于LRU缓存策略。实验结果中RC缓存策略的缓存命中率要高于其他缓存策略，是由于RC缓存策略是在LFU缓存策略的基础上，利用用户的历史数据，结合瓦片区域性、层级性特点，大程度地提高了瓦片缓存命中率。因此，从实验结果来看，RC缓存策略在瓦片缓存数据管理上有其独特的优势，RC缓存策略在不同的缓存容量大小下都表现出了最好的结果。

3 结语

本文分析了现有瓦片缓存策略的不足之处，针对林区瓦片地图的特点，设计了基于区域簇群的林区地图瓦片管理策略（RC缓存策略）。构造区域瓦片金字塔，将经常被访问的热点区域的瓦片数据进行统一调度。RC缓存策略在LFU原有基础上进行改进，既吸收了LFU缓存策略的优点，又满足了瓦片缓存数据区域性调度的需求。

实验结果显示，RC缓存管理策略在不同的缓存容量大小情况下，都优于FIFO、LRU、LFU缓存策略的瓦片缓存命中率。

由于RC缓存策略涉及到空间相关分析，虽然在瓦片缓存命中率上有很大优势，但是在时间效率上要低于其他缓存策略。在接下来的研究中，将着重改进RC缓存策略，使其在合理的瓦片数据密度下进行空间分析，降低时间开销，释放线程资源，提高林区瓦片地图效率。

[1] 刘佳星,陈飞翔,陈星涵.一种基于地理单元热度的瓦片缓存策略[J].计算机工程与应用,2017,53(5):90-96

[2] 苏旭明,谭建成.Web GIS中瓦片地图关键技术研究[J].北京测绘,2012(2):9-12

[3] 陈桦,李艳明,朱美正.一种支持大量并发用户的瓦片缓存方案研究[J].计算机工程与科学,2012,34(12):144-149

[4] 朱秀丽,周治武,李静,等.网络矢量地图瓦片技术研究[J].测绘通报,2016(11):106-109,117

[5] 涂振发,孟令奎,张文,等.面向网络GIS的最小价值空间数据缓存替换算法研究[J].华中师范大学学报:自科 版,2012,46(2):230-234

[6] 褚信,蔡阳军,杜震洪,等.用户行为选择参与的五层十五级瓦片缓存置换策略研究[J].浙江大学学报:理学 版,2016,43(4):452-457

[7] 王浩,喻占武,曾武,等.基于瓦片寿命和访问热度的海量空间数据缓存置换策略[J].武汉大学学报:信息科学 版,2009,34(6):667-670

[8] Lu X, Wetter E, Bharti N,. Approaching the limit of predictability in human mobility[J]. Scientific reports, 2013(3):2923

[9] 杨莹.瓦片四叉树和填充曲线实现海量地形数据管理[J].计算机工程与应用,2016,52(14):192-196

[10] 李东军,曾国荪.一种基于四叉树的空间数据缓存策略[J].计算机工程与应用,2008,44(22):162-165

[11] 路东林,智广玉.地图发布平台下瓦片金字塔技术研究[J].数字技术与用,2013(3):99,101

[12] Gao F, Jiang P, Li X,. A massive tile data organization and management strategy based on file tree[C]//IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, 2015

[13] 李鹤元,陈刚.基于改进Web墨卡托投影的瓦片地图服务设计与实现[J].测绘工程,2016,25(2):11-16

[14] Getis A. Spatial Autocorrelation[J]. Trends in Ecology & Evolution, 1973,14(5):196

[15] Anselin L. Interactive techniques & exploratory spatial data analysis[J].1999,47(2):415-421

[16] Getis A, Ord JK. The Analysis of Spatial Association by Use of Distance Statistics[J]. Geographical Analysis, 1992,24(3):189-206

[17] 季斌,周涛发,袁峰,等.地球化学异常信息的空间自相关提取方法[J].测绘科学,2017(8):1-6

[18] Anselin L. Local Indicators of Spatial Associa- tion-LISA[J]. Geographical Analysis, 1995,27(2):93-115

Forest Map Tile Cache Strategy Based on Hot Area Regional Cluster

CHAI Long-cheng, GAO Wen-ling, YIN Jun-fei, CHEN Xing-han, CHEN Fei-xiang*

100083,

To improve the operation and service efficiency of tile map, this paper proposes a tile caching strategy based on Regional Cluster according to the characteristics of tile and user operation habits. Based on the regional map of forest region and tile record information, this strategy firstly determines the clustering type through global spatial autocorrelation analysis, and then identifies hot spots through local spatial autocorrelation analysis. According to the tower structure characteristics of tile map, the traditional LFU algorithm is improved to preserve the tile data group in tile pyramid of hot spot area and improve the hit rate of tile cache.Experiments demonstrate that the strategy can improve the tile cache hit rate and accelerate the tile map access speed.

Tile map; cache strategy; regional cluster; spatial autocorrelation

TP391

A

1000-2324(2019)02-0328-07

10.3969/j.issn.1000-2324.2019.02.033

2018-06-21

2018-09-12

中央高校基本科研业务费专项资金资助(TD2014-02)

柴龙成(1993-),男,硕士研究生,研究领域为空间信息技术. E-mail:1005583751@qq.com

Author for correspondence.E-mail:fxchen@126.com