适用于矢量瓦片缓存替换的视点相关预测区域算法

王治铭，范光鹏，陈飞翔,2，崔晓晖,2*

(1.北京林业大学信息学院，北京 100083；2.国家林业草原林业智能信息处理工程技术研究中心，北京 100083)

0 引言

随着地球空间数据获取技术和网络服务技术日趋成熟，获取的空间数据呈现出海量特征，空间数据的实时获取和可视化应用是WebGIS的重点[1,2]。瓦片技术的出现提升了空间数据服务的可用性[3]，然而传统的栅格瓦片数据体量巨大，且存在浏览性能瓶颈。矢量瓦片凭借其占用带宽小和交互性强的优势，受到更多关注[4-7]，对比矢量数据的渐进传输方式，使用矢量瓦片更加高效[8]。矢量瓦片同样依据四叉树模型生成多分辨率瓦片金字塔，并通过瓦片层级和X、Y方向序号建立唯一索引[9]；同时在客户端建立良好的缓存机制，能够进一步提高数据的传输效率，更好地满足空间数据应用的实时性需求[10,11]。

研究缓存的管理和分配，需考虑如何放置和替换存储内容，缓存的命中率直接影响获取存储内容的延迟或响应时间[12]。当缓存已满且请求的新数据不在其中时，需要通过其他途径获取，并使用一定的策略对缓存进行数据更新[13]。目前，在瓦片缓存替换方面的相关研究有：王浩等提出一种瓦片访问平均时间间隔最长的缓存算法[10]，该算法结合最近最少使用(LRU)策略的特征，考虑了瓦片在一定时期内的流行度，将超出平均缓存寿命最长且访问热度最低的瓦片置换出内存；涂振发等提出最小空间数据价值缓存置换算法[14]，在考虑数据访问时间和频率的基础上，引入瓦片空间位置和可视区域面积等因子评估瓦片缓存价值；刘佳星等融合瓦片金字塔的结构特性，提出基于地理单元热度的缓存策略[15]，并应用热度挥发机制对该策略进行优化；柴龙成等提出基于热点区域簇群的瓦片缓存策略[16]，考虑了瓦片访问的空间局部性特征，并结合空间数据的空间自相关特性计算瓦片缓存价值；吴家皋等考虑图层对数据缓存价值的影响，将缓存更新抽象成0/1背包问题进行求解[17]。上述缓存方法主要将空间数据的访问时间作为替换的重要因素，未充分考虑数据的空间特征，并且缓存策略未结合矢量瓦片的特性，无法获得较高的缓存效率。

基于预测区域的缓存算法[18]是一种用于缓存位置相关数据的方法，预测区域实质是指客户端活动范围，算法依据缓存数据与预测区域的位置关系更新缓存，充分考虑了数据访问的空间特征。本文在此基础上提出了一种适用于矢量瓦片缓存替换的视点相关预测区域算法：首先根据瓦片金字塔结构，将空间划分为若干个大小相同的位置相关数据单元，并引入空间单元热度，基于访问热度高的空间单元构建预测区域；通过分析预测区域获得数据单元缓存价值，进而得到瓦片缓存价值，最后进行缓存置换。

1 适用于矢量瓦片缓存替换的视点相关预测区域算法

1.1 视点相关预测区域算法流程

视点相关预测区域算法具体流程(图1)为： 1)客户端记录用户地图操作的类型和视点的当前位置，并请求瓦片数据；2)判断所请求的瓦片是否命中缓存，是则直接返回缓存中的数据，执行步骤4)，否则下载瓦片数据，执行步骤3)；3)判断缓存空间是否已满，是则不断淘汰队尾的瓦片，直到缓存能够容纳请求的瓦片，否则执行步骤4)；4)更新客户端的矢量要素缓存，计算瓦片访问热度(取决于其所包含的要素的热度平均值)，并根据金字塔结构计算位置相关数据单元的访问热度(与覆盖瓦片的热度相关)；5)选择高访问热度的数据单元，用以构建预测区域,判断数据单元是否在预测区域内，是则通过视点移动速度和方向计算视点的预估位置，进而计算数据单元到视点预估位置的距离并将其作为距离因子，否则直接用数据单元到视点当前位置的距离作为距离因子；6)结合距离因子、访问概率和访问热度计算位置相关数据单元的价值；7)获取瓦片的缓存价值，对缓存中的瓦片队列重新排序。

图1 视点相关预测区域算法流程Fig.1 Flow chart of the proposed predicted region algorithm

1.2 矢量要素的瓦片访问热度计算

目前计算瓦片访问热度的方法可分为基于特征统计的方法和基于智能预算的方法[19],这两类方法均以单个瓦片为最小单元评估瓦片的访问热度。而矢量数据包含属性数据和位置数据，前者以瓦片为单位进行组织且与要素类型相关，后者则以矢量要素为单位进行组织[20,21]，故本文引入矢量要素类型和组织结构的影响因素，提出一种融合矢量瓦片特性的瓦片访问热度计算方法。

设任意瓦片T对应一个矢量要素列表EList，其中包含该瓦片地理范围内的所有矢量要素。将客户端内存中已经缓存的瓦片集合记为C，用户执行一次地图操作所请求的瓦片数据集合记为R。在客户端需要维护一个缓存矢量要素CElei(其存储结构见式(1))的列表CeList，其中记录着客户端曾经访问过的矢量要素。

CElei=(EleIndexi,ElePop(EleIndexi))

(1)

式中：EleIndexi为缓存矢量要素CElei的索引;ElePop为要素的访问热度。

初始时CeList中要素数量为0，随着用户移动、缩放地图，产生瓦片请求集合，不断有新的数据进入缓存，其更新方式如下：

CeList=CeList∪EList

(2)

ElePop(EleIndexi)=ElePop(EleIndexi)+Inci

(3)

Inci=s/SpanNum(i,z)

(4)

式中：Inci为缓存矢量要素CElei的访问热度增量；s为矢量要素访问热度增量标准因子;SpanNum(i,z)表示在第z层级、索引为EleIndexi的矢量要素所跨越的瓦片数量，考虑到点要素不会出现跨越瓦片的情况，为避免点类型的途径要素热度增幅过大，令SpanNum≥2。

根据用户不同的地图操作行为和矢量要素类型，将客户端的缓存矢量要素分为途径矢量要素、观察矢量要素和贬值矢量要素3类。1)如果某要素为用户请求瓦片的要素，且该要素不在客户端的矢量要素列表中，或该要素已在客户端建立缓存，但访问热度为0，则认为该要素为首次加载，可能是用户切换观察点时的途径要素；另外，如果瓦片是地图缩小操作过程中请求的数据，则不再考虑前一个条件，而认为其包含的所有矢量要素都是途径要素。途径要素不是用户观察的重点，其访问热度增量(计算方式见式(4))虽为正值，但绝对值较小。2)如果某要素是客户端的缓存矢量要素且其访问热度大于0，则认为该要素是用户在局部区域内浏览的细节，属于观察要素；观察要素是用户关注的矢量要素，应保持较高的访问热度，故直接用热度增量标准因子(s)表征其热度增量。3)如果要素不是所请求瓦片的矢量要素，即用户本次地图操作并未访问该要素，则认为其是贬值矢量要素；贬值矢量要素的访问热度持续衰减，考虑到其未来有可能成为观察要素，要素的访问热度不应减少过快，应采用与途径要素热度增量类似的计算方法(式(4))，但值为负。

瓦片T存储在客户端缓存中，其矢量要素列表含有n个矢量要素，则其访问热度可表示为：

(5)

1.3 预测区域构建及矢量瓦片替换

瓦片作为一种地理空间数据，其访问模式同时具有时间和空间局部性特征[22,23]:当用户访问特定区域内的某瓦片时，该瓦片周围的瓦片在下一时刻被访问的可能性也很高[24]。充分考虑这种空间局部性特征，本文在预测区域缓存算法的基础上，提出适用于矢量瓦片缓存替换的视点相关预测区域算法：首先将空间划分为位置相关数据单元，并根据瓦片热度和金字塔结构计算空间单元热度；结合空间自相关性和单元热度，在数据单元维度上构建预测区域，考虑到该预测区域为视点位置范围，数据单元和预测区域的位置关系将直接影响缓存价值的求解，故在缓存价值计算中引入缓存项和视点位置的距离因子，结合其访问概率和访问热度，可得空间单元缓存价值；最后根据瓦片的层级和覆盖的空间单元价值计算瓦片缓存价值，进行缓存替换。

矢量瓦片的金字塔结构使不同层级的瓦片存在地理范围上的重叠，且上层瓦片涵盖的地理范围很大，不宜直接进行预测区域分析，故用瓦片金字塔最底层的网格对地理空间进行规则划分，将分割得到的空间数据单元称为位置相关数据单元(图2)。

图2 位置相关数据单元划分Fig.2 Division of location-dependent data units

预测区域算法[18]是一种位置感知方法，算法的关键是对客户端近期活动范围进行合理预测。本文算法基于位置相关数据单元构建视点相关的预测区域。在传统方法中，计算当前视点位置与移动地图后视点位置之间的距离，将其作为预测区域的半径[25]，但当视点移动距离很小时，大部分数据单元会落在预测区域外，所有数据缓存项的缓存价值都极低，被替换出缓存的概率较高。本文算法计算数据缓存项有效范围参考点到视点当前位置的均方根距离，用来估计预测区域半径[18]。当位置相关数据单元的数量较大且分布均匀时，该方法计算效率低且估算的预测区域半径过大，因此，根据瓦片热度估算位置相关数据单元的访问热度，结合空间数据的空间自相关性进一步优化：选取访问热度大于均值的数据单元作为有效单元，计算其到视点的均方根距离Hdp(式(6))，将其作为预测区域半径，图3为预测区域构建示意图。

图3 预测区域构建Fig.3 Construction of predicted region

(6)

式中：N为有效单元的数量；(xi,yi)为第i个有效单元的坐标；(xc,yc)为当前视点命中的数据单元坐标，计算结果向上取整。

构建预测区域及计算缓存价值均需使用空间单元热度。考虑到瓦片的金字塔结构特征，位置相关数据单元的访问热度应由瓦片访问热度和金字塔层级决定，初始时热度均为0。对于瓦片T地理范围内的数据单元Ui，其访问热度计算公式如下：

Popu(Ui)=Popu(Ui)+Pop(T)/22(L-z)

(7)

式中：L表示金字塔的最高层级；z表示命中数据单元Ui的瓦片T的层级。

对位置相关数据单元进行预测区域分析时，由于位置相关单元的有效范围大小相同且都是正方形，容易选取有效范围的参考点，在计算缓存价值时也去除了有效范围面积的影响因素。本文引入单元访问热度参与缓存价值计算，并结合访问概率和表示缓存项[26]与预测区域位置关系的距离因子，设计位置相关数据单元Ui的缓存价值Valu(Ui)计算公式如下：

(8)

式中：Pi为位置相关数据单元Ui的访问概率，本文采用指数老化方法计算，Pi=α/(tc-tl)+(1-α)×Pi(tc为系统当前时间，tl、α分别为位置相关数据单元最近一次访问时间和重要性权值)，初始时所有位置相关数据单元的Pi均设为0;D(Ui)表示预测区域PR内Ui的预测位置与当前位置的距离(式(9))；D′(Ui)表示当Ui不属于预测区域PR时，预测区域中心与Ui间的距离(式(10))。

(9)

(10)

式中：(xp，yp)为视点预估位置，(xc，yc)为视点当前位置；β为UnitDir(位置相关数据单元相对于预测区域中心的方向向量)与数据单元坐标系X轴正方向的夹角;Lm为预测的视点移动距离，θ为视点移动方向向量Dir与UnitDir的夹角(图4)，vc为视点移动的速度(与客户端显示地图的当前分辨率有关，地图移动的最大距离不会超过显示地图对角线覆盖的数据单元长度)，rand为0～1范围内的随机数，xs、ys分别为显示地图覆盖范围X、Y方向上的位置相关数据单元数量。

如果随着地图操作，视点与数据单元的距离越来越小，其缓存价值应越来越大，故采用θ的负余弦函数参与距离因子运算。图4展示了不同方向的数据单元处理方法，此时视点移动方向为水平方向，θ与β相同。

图4 不同方向的数据单元处理方法Fig.4 Processing of data units at different locations

使用上述算法计算出位置相关数据单元的缓存价值，依据瓦片金字塔结构特征，量化位置相关数据单元缓存价值对涵盖它的相应层级瓦片缓存价值的影响；同时考虑不同瓦片的数据量大小，得到矢量瓦片T的缓存价值Value(T)为：

(11)

式中：Size(T)表示矢量瓦片T的数据量；M为T包含的位置相关数据单元数量。

对客户端缓存中的矢量瓦片按照缓存价值大小排序。当需要进行缓存置换时，总是将缓存价值最小的瓦片替换出缓存，直到缓存剩余空间能够置入最新请求的瓦片数据为止。

2 实验数据与结果分析

本文实验数据为从OpenStreetMap下载的中国区域数据，包含7 552 860个要素(759 462个点要素、4 046 059个线要素和2 747 339个面要素)。在无本地缓存的情况下，实验(测试环境：型号ThinkPad E531，CPU为i5双核，主频2.60 GHz，内存容量 8 GB)采集不同用户进行地图操作时客户端所产生的矢量瓦片请求日志共386 243条，根据其中的瓦片层级、序号解析瓦片索引，同时记录瓦片的数据大小及用户操作的相隔时间，还原用户浏览过程。将采集的日志结果随机划分为4组瓦片请求集合，分别采用传统的先进先出(FIFO)、最近最少使用(LRU)、最不经常使用(LFU)策略以及本文提出的缓存策略进行测试，客户端用sqlite数据库文件作为本地缓存，并计算4组数据集合的平均瓦片命中率(从客户端缓存中直接获取的请求瓦片数量占总请求数量的百分比，与客户端的响应时间相关)、平均字节命中率(从客户端缓存中直接获取的瓦片字节量占总请求字节量的百分比，与带宽紧密相关)和平均瓦片请求耗时作为评估指标。针对本文使用的缓存策略，还应记录每次数据请求时的地图操作类型和视域范围。实验中的矢量瓦片统一使用MBTiles存储格式，客户端请求的瓦片数据均来源于本地文件而非网络，从而减少网速慢等因素的影响。

2.1 不同缓存策略下命中率对比

应用本文所提出的策略时，需要指定算法中矢量要素的访问热度标准增量s以及位置相关数据单元的最近访问重要性权值α。经测试，s=3、α=0.6时，本策略在各组实验中瓦片请求效率均为最高。实验设置客户端的缓存空间最大为200 MB，将用户请求数据分为不同的数据集合，分别模拟不同相对缓存下客户端的缓存执行流程，计算4种缓存策略下所有数据集合的平均瓦片命中率(图5a)和平均字节命中率(图5b)。实验结果表明，随着相对缓存的增大，不同的缓存策略均表现出更高的缓存效率。其中，FIFO算法缓存效率最低，LFU算法比LRU算法缓存命中率更高；本文视点相关预测区域算法在不同数据集和不同缓存大小情况下缓存命中率都最高，约为FIFO算法的1.5倍、LRU算法的1.2倍，相比缓存效率不错的LFU算法也有明显优势，主要原因是本文算法基于预测区域对用户行为进行合理预测，计算的缓存价值排序更符合实际浏览时对象替换出内存的正确顺序。

图5 不同缓存策略下平均瓦片命中率和平均字节命中率对比Fig.5 Comparison of average tile hit rate and average byte hit rate under different cache strategies

2.2 不同缓存策略下的请求耗时对比

当相对缓存为100%，即客户端缓存空间可容纳200 MB矢量瓦片数据时，统计4种策略下瓦片请求的平均响应时间(图6)。结果表明，对于相同的数据源，在客户端缓存空间大小相同的情况下，本文视点相关预测区域算法的平均瓦片请求耗时更低。在请求瓦片集合为256 MB时，4种方法的平均瓦片请求耗时差距不大，可能是设置了客户端缓存空间大小为200 MB，能够容纳请求过程中的大部分瓦片，导致4种方法下客户端执行缓存置换的次数大致相同，命中率相差不大，平均瓦片请求耗时也基本持平。而最好情况下本文算法比FIFO耗时缩短约50%，比LRU耗时缩短约30%，相比LFU也略有优势。算法耗时主要由划分的位置相关数据单元数量决定，对于高分辨率的大规模瓦片数据，缓存价值计算的耗时更多。应用本文算法时，客户端还需为矢量要素和位置相关数据单元建立额外缓存，前者可以忽略，故额外缓存也与位置相关数据单元数量有关。对于最高分辨率为213×213的瓦片数据，额外缓存约为200 MB。因此，本文算法的总体性能优于其他缓存策略，更适用于中小型数据量矢量瓦片的缓存管理。

图6 不同缓存策略下平均瓦片请求耗时对比Fig.6 Comparison of average request time of tiles under different cache strategies

3 结语

本文结合矢量瓦片的数据组织结构及瓦片访问的空间局部性特征，提出一种适用于矢量瓦片缓存替换的视点相关预测区域算法。该算法考虑了矢量瓦片存储信息按矢量要素组织的特征，根据不同的地图操作更新矢量要素的热度，通过矢量要素访问热度反映瓦片热度；结合瓦片访问的空间局部性特征，提高矢量瓦片的访问效率；基于位置相关数据单元构建预测区域，评估瓦片的缓存价值，辅助客户端缓存管理。实验结果表明，针对不同数据集，本文策略相比传统的缓存置换策略瓦片命中率和字节命中率更高，耗时更短，更适用于中小型数据量矢量瓦片的缓存替换。然而，本文算法需要额外的空间缓存矢量要素热度和空间数据单元热度，如何减小缓存空间将是下一步的研究重点；还需进一步从历史访问数据中提取更多的信息参与决策，以提升矢量瓦片的可视化速度。