计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 96-102.doi: 10.11896/jsjkx.200800215
郦睿翔, 毛莺池, 郝帅
LI Rui-xiang, MAO Ying-chi, HAO Shuai
摘要: 针对终端用户产生大量相同或相似计算请求的情况,可以通过近似匹配在边缘服务器缓存空间中查找相似数据,选取可复用的计算结果。现有算法大多未考虑数据分布不均的问题,导致计算量和时间开销较大,对此文中提出基于动态局部敏感哈希算法与加权k近邻算法的缓存数据选择策略(Cache Selection Strategy based on Dynamic-LSH algorithm and Weighted-KNN algorithm,CSS-DLWK)。其中,Dynamic-LSH算法能够针对数据分布不均的问题,根据数据分布的变化动态调整哈希桶粒度,从缓存空间中选出与输入数据相似的数据集合;Weighted-KNN算法以距离和样本数为权重,对由Dynamic-LSH算法获取的相似数据集合进行数据再选取,得到与输入数据最相似的数据,获取相应的计算结果以供复用。仿真实验结果表明,在CIFAR-10数据集中,与基于A-LSH算法与H-KNN算法的缓存选取策略相比,CSS-DLWK策略的平均选取准确率提高了4.1%;与传统的LSH算法相比,其平均选取准确率提高了16.8%。CSS-DLWK策略能够在可接受的数据选取时间开销内,有效地提高可复用数据选取的准确率,从而减少边缘服务器的重复计算。
中图分类号:
[1] SHI W,CAO J,ZHANG Q,et al.Edge computing:Vision and challenges[J].IEEE Internet of Things Journal,2016,3(5):637-646. [2] GUO Y,LIU F,CAI Z,et al.Edge-based efficient search over encrypted data mobile cloud storage[J].Sensors,2018,18(4):1189. [3] MASTORAKIS S,MTIBAA A,LEE J,et al.ICedge:WhenEdge Computing Meets Information-Centric Networking[J].IEEE Internet of Things Journal,2020,7(5):4203-4217. [4] SANADHYA S,SIVAKUMAR R,KIM K H,et al.Asymmetric caching:improved network deduplication for mobile devices[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:161-172. [5] GUO Y,LIU F,CAI Z,et al.Edge-based efficient search over encrypted data mobile cloud storage[J].Sensors,2018,18(4):1189. [6] SUN S Y,YAO W B,LI X Y.DARS:A dynamic adaptive replica strategy under high load Cloud-P2P[J].Future Generation Computer Systems,2018,78:31-40. [7] ANDONI A,INDYK P.Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[C]//2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06).IEEE,2006:459-468. [8] BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.The R*-tree:An Efficient and Robust Access Method for Points and Rectangles[C]//Proceedings of the ACM SIGMOD Confe-rence on Management of Data.1990:322-331. [9] SAMET H.The design and analysis of spatial data structures[M].Reading,MA:Addison-Wesley,1990. [10] YIANILOS P N.Data structures and algorithms for nearestneighbor search in general metric spaces[C]//Soda.1993:311-321. [11] SANADHYA S,SIVAKUMAR R,KIM K H,et al.Asymmetric caching:improved network deduplication for mobile devices[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:161-172. [12] DUBOIS L,AMALDAS M,SHEPPARD E.Key considerations as deduplication evolves into primary storage[J].White Paper,2011,223310. [13] KANNAN K,BHATTACHARYA S,RAJ K,et al.Seesaw-similarity exploiting storage for accelerating analytics workflows[C]//8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage'16).2016. [14] TANG Y,YANG J.Secure deduplication of general computa-tions[C]//2015 USENIX Conference on Annual Technical Conference.2015:319-331. [15] ZHANG Z,TAO M.Accelerated Deep Reinforcement Learning for Wireless Coded Caching[C]//2019 IEEE/CIC International Conference on Communications in China (ICCC).IEEE,2019:249-254. [16] ZHU H,CAO Y,WANG W,et al.Deep reinforcement learning for mobile edge caching:Review,new features,and open issues[J].IEEE Network,2018,32(6):50-57. [17] ZHONG C,GURSOY M C,VELIPASALAR S.A deep reinforcement learning-based framework for content caching[C]//2018 52nd Annual Conference on Information Sciences and Systems (CISS).IEEE,2018:1-6. [18] GUO P,HU B,LI R,et al.Foggycache:Cross-device approximate computation reuse[C]//Proceedings of the 24th Annual International Conference on Mobile Computing and Networking.ACM,2018:19-34. [19] GUO P,HU W.Potluck:Cross-application approximate deduplication for computation-intensive mobile applications[C]//Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems.2018:271-284. [20] LI Y,CHENG B.An improved k-nearest neighbor algorithm and its application to high resolution remote sensing image classification.[C]//2009 17th International Conference on Geoinforma-tics.IEEE,2009:1-4. [21] PEREZ S.Lets smartphone cameras understand what they see[EB/OL].https://techcrunch.com/2017/05/17/google-lens/. [22] LOWE D G.Distinctive Image Features from Scale-InvariantKeypoints[J].International Journal of Computer Vision,2004,60(2):91-110. [23] ANDONI A,INDYK P.E2LSH:Exact euclidean locality-sensitive hashing[EB/OL].http://web.mit.edu/andoni/www/LSH/. [24] COVER T,HART P.Nearest Neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1):21-27. [25] SHAH J,SMOLENSKI B,YANTORNO R,et al.Sequentialknearest neighbor pattern recognition for usable speech classification[C]//2004 12th European Signal Processing Conference.Vienna,2004:741-744. [26] RUSSAKOVSKY O,DENG J,SU H,et al.ImageNet Large Scale Visual Recognition Challenge[J].International Journal of Computer Vision,2015,115(3):211-252. [27] KRIZHEVSKY A,HINTON G.Learning Multiple Layers of Features from Tiny Images[R].University of Toronto,2009. |
[1] | 梁俊斌, 田凤森, 蒋婵, 王天舒. 物联网中多设备多服务器的移动边缘计算任务卸载技术综述[J]. 计算机科学, 2021, 48(1): 16-25. |
[2] | 于天琪, 胡剑凌, 金炯, 羊箭锋. 基于移动边缘计算的车载CAN网络入侵检测方法[J]. 计算机科学, 2021, 48(1): 34-39. |
[3] | 毛莺池, 周彤, 刘鹏飞. 基于延迟接受的多用户任务卸载策略[J]. 计算机科学, 2021, 48(1): 49-57. |
[4] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法[J]. 计算机科学, 2021, 48(1): 103-110. |
[5] | 胡锦天, 王高才, 徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略[J]. 计算机科学, 2020, 47(6): 260-265. |
[6] | 田贤忠, 姚超, 赵晨, 丁军. 一种面向5G网络的移动边缘计算卸载策略[J]. 计算机科学, 2020, 47(11A): 286-290. |
[7] | 刘伟, 孙童心, 杜薇. 面向访问模式的混合内存缓存替换策略[J]. 计算机科学, 2020, 47(10): 130-135. |
[8] | 谷晓会,章国安. SDN在车载网中的应用综述[J]. 计算机科学, 2020, 47(1): 237-244. |
[9] | 殷佳, 管昕洁, 白光伟. 基于移动边缘计算的任务迁移和协作式负载均衡机制[J]. 计算机科学, 2019, 46(12): 126-131. |
[10] | 董思岐, 李海龙, 屈毓锛, 张钊, 胡磊. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学, 2019, 46(11): 32-40. |
[11] | 杨冬菊,冯凯. 基于缓存的分布式统一身份认证优化机制研究[J]. 计算机科学, 2018, 45(3): 300-304. |
[12] | 田铭,邬江兴,兰巨龙. 信息中心网络中基于局部内容活跃度的自适应缓存算法[J]. 计算机科学, 2016, 43(11): 164-171. |
[13] | 叶剑虹,叶 双. 基于混合模式的流媒体缓存调度算法[J]. 计算机科学, 2013, 40(2): 61-64. |
[14] | 黄敏 蔡志刚. 缓存替换算法研究综述[J]. 计算机科学, 2006, 33(B12): 191-193. |
[15] | 佘堃 牛新征 周明天. 证书系统缓存替换算法的研究[J]. 计算机科学, 2004, 31(2): 89-92. |
|