Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (1): 96-102.doi: 10.11896/jsjkx.200800215

Special Issue: Intelligent Edge Computing

• Intelligent Edge Computing • Previous Articles     Next Articles

Cache Management Method in Mobile Edge Computing Based on Approximate Matching

LI Rui-xiang, MAO Ying-chi, HAO Shuai   

  1. School of Computer and Information,Hohai University,Nanjing 211100,China
  • Received:2020-08-30 Revised:2020-11-07 Online:2021-01-15 Published:2021-01-15
  • About author:LI Rui-xiang,born in 1996,master candidate,is a student member of China Computer Federation.His main research interests include edge computing,and federated learning.
    MAO Ying-chi,born in 1976,Ph.D,professor,is a senior member of China Computer Federation.Her main research interests include cloud computing and edge computing,mobile sen-sing systems and internet of things.
  • Supported by:
    National Key R&D Program of China(2018YFC0407105),Key Project of National Nature Science Foundation of China(61832005) and Key Technology Project of China Huaneng Group (HNKJ17-21).

PDF (PC)

764

Abstract: For the case of massive identical or similar computing requests from end users,a search of similar data in the cache space of the edge server by approximate match can be applied to select computing results that can be reused.Most of the existing algorithms do not consider the uneven distribution of data,resulting in a large amount of calculation and time overhead.In this paper,a cache selection strategy based on dynamic-locality sensitive hashing (LSH) algorithm and Weighted-k nearest neighbor (KNN) algorithm(CSS-DLWK) is proposed.The Dynamic-LSH algorithm can deal with uneven data distribution by dynamically adjusting the hash bucket size accordingly,thereby selecting data sets that are similar to the input data from the cache space.Then,regarding distance and sample size as weights,the weighted-KNN algorithm re-selects the data in the similar data sets acquired by the dynamic-LSH algorithm.From this approach,the data most similar to the input data are obtained,and the corresponding computing result is acquired for reuse.As demonstrated by simulation experiments,in the CIFAR-10 dataset,CSS-DLWK increases the ave-rage selection accuracy by 4.1% compared to the cache selection strategy based on A-LSH and H-KNN algorithms.The improvement is 16.8% compared to traditional LSH algorithms.Overall,with acceptable time costs in data selection,the proposed strategy can effectively improve the selection accuracy of reusable data,thereby reducing repetitive computation in the edge server.

Key words: Approximate matching, Cache replacement, Data reuse, Locality sensitive hashing algorithm, Mobile edge computing

CLC Number: 

  • TP399
[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] YU Bin, LI Xue-hua, PAN Chun-yu, LI Na. Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning [J]. Computer Science, 2022, 49(7): 248-253.
[2] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[3] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[4] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[5] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
[6] ZHANG Hai-bo, ZHANG Yi-feng, LIU Kai-jian. Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC [J]. Computer Science, 2022, 49(2): 304-311.
[7] LIANG Jun-bin, ZHANG Hai-han, JIANG Chan, WANG Tian-shu. Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing [J]. Computer Science, 2021, 48(7): 316-323.
[8] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[9] FAN Yan-fang, YUAN Shuang, CAI Ying, CHEN Ruo-yu. Deep Reinforcement Learning-based Collaborative Computation Offloading Scheme in VehicularEdge Computing [J]. Computer Science, 2021, 48(5): 270-276.
[10] LI Zhen-jiang, ZHANG Xing-lin. Resource Allocation and Offloading Decision of Edge Computing for Reducing Core Network Congestion [J]. Computer Science, 2021, 48(3): 281-288.
[11] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[12] XU Xu, QIAN Li-ping, WU Yuan. Computation Resource Allocation and Revenue Sharing Based on Mobile Edge Computing for Blockchain [J]. Computer Science, 2021, 48(11): 124-132.
[13] LIANG Jun-bin, TIAN Feng-sen, JIANG Chan, WANG Tian-shu. Survey on Task Offloading Techniques for Mobile Edge Computing with Multi-devices and Multi-servers in Internet of Things [J]. Computer Science, 2021, 48(1): 16-25.
[14] YU Tian-qi, HU Jian-ling, JIN Jiong, YANG Jian-feng. Mobile Edge Computing Based In-vehicle CAN Network Intrusion Detection Method [J]. Computer Science, 2021, 48(1): 34-39.
[15] MAO Ying-chi, ZHOU Tong, LIU Peng-fei. Multi-user Task Offloading Based on Delayed Acceptance [J]. Computer Science, 2021, 48(1): 49-57.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.