Server-side cache replacement algorithm based on spatiotemporal aging model for tiles

doi:10.3785/j.issn.1008-9497.2022.02.010

Journal of Zhejiang University (Science Edition)

2022, Vol. 49

Issue (2): 210-218 DOI: 10.3785/j.issn.1008-9497.2022.02.010

Earth Science

Server-side cache replacement algorithm based on spatiotemporal aging model for tiles

Qiuyi TANG^1,²,Chao WANG^1,²,Zhenhong DU^1,²(

),Feng ZHANG^1,²,Renyi LIU^1,²

^1.Zhejiang Provincial Key Lab of GIS，Zhejiang University，Hangzhou 310028，China
^2.Department of Geographic Information Science，Zhejiang University，Hangzhou 310027，China

Download:

HTML( 6 )

PDF(882KB)
Export: BibTeX | EndNote (RIS)

Abstract

As network geographic information service (NGIS) is developing towards cloud services, the client-side tiles cache architecture has already demonstrated its limitations in applications. To improve the efficiency of tile service, this paper designs a server-side cache replacement algorithm based on spatiotemporal aging model for tiles (SSAT). The SSAT algorithm is based on the aging algorithm and comprehensively analysis on the long-term and short-term popularity of tile access pattern as well as the characteristics of tile size. A series of Google global base map tiles and access logs of tiles are used for simulation experiment. The experimental results show that the SSAT algorithm outperforms traditional algorithms when using different cache sizes. With the increasing of cache size, the SSAT algorithm can increase the request hit rate by 0.24% and the byte hit rate by 0.23% for every additional 1 MB of cache. When the cache space is 500 MB, SSAT algorithm can achieve 73% cache hit rate and 76% byte hit rate, and reduce the average access time by more than 35%. In summary, the SSAT algorithm considers both performance and resource consumption, and has high efficiency and scalability.

Key words： NGIS tile service tile cache replacement algorithm aging algorithm spatiotemporal aging model

Received: 21 January 2021 Published: 22 March 2022

CLC:

P 208

Corresponding Authors: Zhenhong DU E-mail: duzhenhong@zju.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Qiuyi TANG
	Chao WANG
	Zhenhong DU
	Feng ZHANG
	Renyi LIU

Cite this article:

Qiuyi TANG,Chao WANG,Zhenhong DU,Feng ZHANG,Renyi LIU. Server-side cache replacement algorithm based on spatiotemporal aging model for tiles. Journal of Zhejiang University (Science Edition), 2022, 49(2): 210-218.

URL:

https://www.zjujournals.com/sci/EN/Y2022/V49/I2/210

基于时空老化模型的服务端瓦片缓存置换算法

随着网络地理信息服务（network geographic information service，NGIS）向云服务演进，客户端瓦片缓存架构的应用局限性逐渐体现。为提升瓦片服务的性能，在老化算法的基础上，综合分析了瓦片访问长短期流行度和瓦片大小特征，设计了基于时空老化模型的服务端瓦片缓存置换算法（server-side cache replacement algorithm based on spatiotemporal aging model for tiles，SSAT），并利用谷歌全球底图瓦片和瓦片访问日志进行了仿真实验。结果表明，在不同缓存空间下，SSAT的缓存命中率均高于传统算法，缓存空间每增加1 MB，最多可以提高0.24%的请求命中率和0.23%的字节命中率；当缓存空间为500 MB时，SSAT能达到73%的请求命中率和76%的字节命中率，平均访问时长可缩短35%以上。SSAT能兼顾性能与资源消耗，具备高效性和扩展性。

关键词： 网络地理信息服务, 瓦片服务, 瓦片缓存置换算法, 老化算法, 时空老化模型

Fig.1 Aging algorithm workflow

Fig.2 Tile horizontal neighborhood and vertical neighborhood

Fig.3 Server-side tile cache index structure

Fig.4 Impact of T and vol on cache hit ratio of SSAT

Fig.5 Changes of request hit ratio and byte hit ratio of SAAT with cache space under three conditions

Fig.6 Changes of tile request hit ratio， tile byte hit ratio and their growth of four algorithms with cache space

Fig.7 Change of average visit time and save ratio of average visit time of four algorithms with cache space

Fig.8 CPU usage ratio and sum usage ratio of four algorithms


[1]	BREUNIG M， BRADLEY P E， JAHN M， et al. Geospatial data management research： Progress and future directions［J］. ISPRS International Journal of Geo-Information， 2020， 9（2）： 95-115. DOI：10.3390/ijgi9020095 doi: 10.3390/ijgi9020095

[2]	GOMES V C F， QUEIROZ G R， FERREIRA K R. An overview of platforms for big earth observation data management and analysis［J］. Remote Sensing， 2020， 12（8）： 1253. DOI：10.3390/rs12081253 doi: 10.3390/rs12081253

[3]	GUO H D. Big earth data： A new frontier in earth and information sciences［J］. Big Earth Data， 2017， 1（1/2）： 4-20. DOI：10.1080/20964471.2017.1403062 doi: 10.1080/20964471.2017.1403062

[4]	陆晔，张伟，李飞，等. 一种基于主题时空价值的服务器端瓦片缓存算法［J］. 浙江大学学报（理学版）， 2020， 47（1）： 12-19. DOI：10.3785/j.issn.1008-9497.2020.01.002 LU Y， ZHANG W， LI F， et al. A server-side tile caching algorithm based on theme temporal and spatial value［J］. Journal of Zhejiang University（Science Edition）， 2020， 47（1）： 12-19. DOI：10.3785/j.issn.1008-9497.2020.01.002 doi: 10.3785/j.issn.1008-9497.2020.01.002

[5]	GUO D D， ZOU Y J， WANG S. An Effective tile caching mechanism of UAV remote sensing map based on hilbert coding index［C］// 2019 IEEE 11th International Conference on Communication Software and Networks （ICCSN）. Piscataway： IEEE， 2019： 535-541. DOI：10.1109/ICCSN.2019. 8905357 doi: 10.1109/ICCSN.2019. 8905357

[6]	周扬发. Web代理服务器的缓存技术研究［D］. 北京：北京邮电大学， 2014. ZHOU Y F. Research on Caching Technology of Web Proxy Server［D］. Beijing： Beijing University of Posts and Telecommunications， 2014.

[7]	LI R， FAN J P， WANG X X， et al. Distributed cache replacement method for geospatial data using spatiotemporal locality-based sequence［J］. Geospatial Information Science， 2015， 18（4）： 171-182. DOI：10.1080/10095020.2015.1123427 doi: 10.1080/10095020.2015.1123427

[8]	LI R， FENG W， WU H Y， et al. A replication strategy for a distributed high-speed caching system based on spatiotemporal access patterns of geospatial data［J］. Computers， Environment and Urban Systems， 2017， 61（B）： 163-171. DOI：10.1016/j.compenvurbsys.2014.02.009 doi: 10.1016/j.compenvurbsys.2014.02.009

[9]	CHENG Y Y， ZHOU K F， WANG J L， et al. Big earth observation data integration in remote sensing based on a distributed spatial framework［J］. Remote Sensing， 2020， 12（6）： 972-988. DOI：10.3390/rs12060972 doi: 10.3390/rs12060972

[10]	KANG Y K， KIM K C， KIM Y S. Probability-based tile pre-fetching and cache replacement algorithms for web geographical information systems［C］// East European Conference on Advances in Databases and Information Systems. Berlin： Springer， 2001： 127-140. DOI：10.1007/3-540-44803-9_11 doi: 10.1007/3-540-44803-9_11

[11]	王浩，喻占武，曾武，等. 网络地理信息服务中的空间数据缓存算法研究［J］. 测绘学报， 2009， 38（4）： 348-355. DOI：10.3321/j.issn：1001-1595.2009.04.011 WANG H， YU Z W， ZENG W， et al. The research on the algorithm of spatial data cache in network geographic information service［J］. Acta Geodaetica et Cartographica Sinica， 2009， 38（4）： 348-355. DOI：10.3321/j.issn：1001-1595.2009.04.011 doi: 10.3321/j.issn：1001-1595.2009.04.011

[12]	王浩，潘少明，彭敏，等. 数字地球中影像数据的Zipf-like访问分布及应用分析［J］. 武汉大学学报（信息科学版）， 2010， 35（3）： 356-359. doi:10.3724/SP.J.1084.2010.00199 WANG H， PAN S M， PENG M， et al. Zipf-like distribution and its application to image data tile request in digital earth［J］. Geomatics and Information Science of Wuhan University， 2010， 35（3）： 356-359. doi:10.3724/SP.J.1084.2010.00199 doi: 10.3724/SP.J.1084.2010.00199

[13]	LI R， WANG X X， WANG J J， et al. Simulation and Analysis of Cluster-Based Caching Replacement Based on Temporal and Spatial Locality of Tiles Access［M］. Boston： Springer， 2013： 169-181. DOI：10.1007/978-1-4614-8745-6_13 doi: 10.1007/978-1-4614-8745-6_13

[14]	王浩，喻占武，曾武，等. 基于瓦片寿命和访问热度的海量空间数据缓存置换策略［J］. 武汉大学学报（信息科学版）， 2009， 34（6）： 667-670. doi:10.1109/itcs.2009.114 WANG H， YU Z W， ZENG W， et al. Massive spatial data cache replacement policy based on tile lifetime and popularity［J］. Geomatics and Information Science of Wuhan University， 2009， 34（6）： 667-670. doi:10.1109/itcs.2009.114 doi: 10.1109/itcs.2009.114

[15]	刘佳星，陈飞翔，陈星涵. 一种基于地理单元热度的瓦片缓存策略［J］. 计算机工程与应用， 2017， 53（5）： 90-96. DOI：10.3778/j.issn.1002-331.1608-0530 LIU J X， CHEN F X， CHEN X H. Tile cache strategy based on geographic unit heat［J］. Computer Engineering and Applications， 2017， 53（5）： 90-96. DOI：10.3778/j.issn.1002-8331.1608-0530 doi: 10.3778/j.issn.1002-8331.1608-0530

[16]	CAO P， IRANI S. Cost-aware WWW proxy caching algorithms［C］// Proceedings of the USENIX Symposium on Internet Technologies and Systems. Monterey， CA： USENIX， 1997： 193-206.

[17]	LEE D H， KIM J S， KIM S D， et al. Adaptation of a neighbor selection markov chain for prefetching tiled web GIS data［C］// International Conference on Advances in Information Systems. Heidelberg： Springer， 2002： 213-222. doi:10.1007/3-540-36077-8_21 doi: 10.1007/3-540-36077-8_21

[18]	涂振发，孟令奎，张文，等. 面向网络GIS的最小价值空间数据缓存替换算法研究［J］. 华中师范大学学报（自然科学版）， 2012， 46（2）： 230-234. DOI：10. 3969/j.issn.1000-1190.2012.02.023 TU Z F， MENG L K， ZHANG W， et al. Research on the lowest-value cache replacement algorithm of geospatial data in network GIS［J］. Journal of Central China Normal University （Natural Sciences）， 2012， 46（2）： 230-234. DOI：10.3969/j.issn.1000-1190.2012.02.023 doi: 10.3969/j.issn.1000-1190.2012.02.023

[19]	ULUAT M F， ??LER V. Ensemble adaptive tile prefetching using fuzzy logic［J］. International Journal of Geographical Information Science， 2016， 30（6）： 1117-1136. DOI：10.1080/13658816. 2015.1108420 doi: 10.1080/13658816. 2015.1108420

[20]	LI R， FAN J P， JIANG J， et al. Spatiotemporal correlation in WebGIS group-user intensive access patterns［J］. International Journal of Geographical Information Science， 2017， 31（1）： 36-55. DOI：10. 1080/13658816.2016.1170133 doi: 10. 1080/13658816.2016.1170133

[21]	SAXENA A. A study of page replacement algorithms［J］. International Journal of Engineering Research and General Science， 2014， 2（4）： 385-388.

[22]	刘敏，房至一，王红斌，等. 基于老化算法的分布式文件缓存算法［J］. 吉林大学学报（理学版）， 2011， 49（5）： 895-900. doi:10.1007/978-3-642-26001-8_69 LIU M， FANG Z Y， WANG H B， et al. Distributed file caching algorithm based on aging algorithm［J］. Journal of Jilin University （Science Edition）， 2011， 49（5）： 895-900. doi:10.1007/978-3-642-26001-8_69 doi: 10.1007/978-3-642-26001-8_69

[23]	FAROOQUI M Z， SHOAIB M， KHAN M Z. A comprehensive survey of page replacement algorithms［J］. International Journal of Advanced Research in Computer Engineering & Technology， 2014， 3（1）： 52-58. doi:10.7763/ijet.2011.v3.218 doi: 10.7763/ijet.2011.v3.218

[1]	Yueyi LI,Feng ZHANG,Zhenhong DU,Renyi LIU. Distributed scheduling and storage scheme based on LSM-OCTree for spatiotemporal stream[J]. Journal of Zhejiang University (Science Edition), 2023, 50(2): 204-212.

[2]	Yuwen WANG,Zhenhong DU,Zhen DAI,Renyi LIU,Feng ZHANG. Multivariate water quality parameter prediction model based on hybrid neural network[J]. Journal of Zhejiang University (Science Edition), 2022, 49(3): 354-362.

Viewed

Full text

Abstract

Cited

Shared

Discussed