计算机科学 ›› 2017, Vol. 44 ›› Issue (3): 220-225.doi: 10.11896/j.issn.1002-137X.2017.03.046

• 软件与数据库技术 • 上一篇    下一篇

基于位置信息的移动SNS数据动态划分复制算法

王青芸,程春玲   

  1. 南京邮电大学计算机学院 南京210003,南京邮电大学计算机学院 南京210003
  • 出版日期:2018-11-13 发布日期:2018-11-13

Mobile SNS Data Dynamic Partitioning and Replication Algorithm Based on Location Information

WANG Qing-yun and CHENG Chun-ling   

  • Online:2018-11-13 Published:2018-11-13

摘要: 现有社交网络数据划分算法大多关注于好友关系和交互关系,忽略了位置信息,造成基于位置查询的响应时间较长。针对该问题,设计了一种移动社交网络双层社交图模型,该模型考虑了移动社交网络中用户交互行为的位置依赖性特点;并在此基础上提出了一种基于位置信息的移动社交网络数据动态划分复制算法MSDPR,该算法采用改进的K-Means算法对位置信息进行聚类,再根据聚类结果对数据进行划分,并利用社交关系进行数据的复制。实验结果表明:MSDPR算法在移动社交网络环境下能够有效地提高本地访问率,降低访问延迟,并且在动态加入数据时具有较好的适应性。

关键词: 移动社交网,分布式存储,动态划分复制,位置信息,用户交互

Abstract: The existing social network data partitioning algorithms focus on the social relationship and interaction,without considering location information,which results in the long response time of location-based queries.To solve this problem,we designed a two-layer graph model of mobile social network which takes the location dependency of the user interaction behavior into account.We proposed a mobile SNS data dynamic partitioning and replication algorithm based on location information--MSDPR.MSDPR divides data based on the clustered results generated by an improved K-Means clustering algorithm,and then replicates data by using the social relationships.Experiments reveal that MSDPR can effectively improve the efficiency of the local access and reduce the latency of access in the mobile social network.Moreover,it also has better adaptability when adding data dynamically.

Key words: Mobile social network,Distributed storage,Dynamic partitioning and replication,Location information,User interaction

[1] 中国互联网络信息中心.第36次中国互联网络发展状况统计报告[EB/OL].[2015-07-22].http://www.cnnic.cn/hlwfzyj/ hlwxzbg/hlwtjbg/201507/ P020150723549500667087.pdf.
[2] TalkingData移动数据研究中心.2015移动社交应用行业报告[EB/OL].[2015-07-09].http://www.talkingdata.com/index/files/2015-07/1436432039347.pdf.
[3] HOFFT .Friendster lost lead because of a failure to scale.[EB/OL].(2007-11-13)[2015-11-9].http://highscalability.com/blog/2007/11/13/friendster-lost-lead-because-of-a-failure-to-scale.html.
[4] TAMER M,PATRICK V.Principles of distributed databasesystems(Third Edition)[M].New York:Springer,2011.
[5] JIN H S,KIM M H.An adaptable vertical partitioning method in distributed systems[J].Journal of Systems & Software,2004,73(3):551-561.
[6] LAKSHMAN A,MALIK P.Cassandra:a decentralized struc-tured storage system [J].ACM SIGOPS Operating Systems Review,2010,44(2):35-40.
[7] YU G,GU Y,BAO Y B,et al.Large Scale Graph Data Proces-sing on Cloud Computing Environments[J].Chinese Journal of Computers,2011,34(10):1753-1767.(in Chinese) 于戈,谷峪,鲍玉斌,等.云计算环境下的大规模图数据处理技术[J].计算机学报,2011,4(10):1753-1767.
[8] PJUOL J M,ERRAMILLI V,et al.The little engine(s) that could:scaling online social networks [J].IEEE/ACM Transactions on Networking (TON),2012,20(4):1162-1175.
[9] HUANG Y,DENG Q,ZHU Y.Differentiating your friends for scaling online social networks[C]∥Proceedings of the 2012 IEEE International Conference on Cluster Computing.IEEE,2012:411-419.
[10] NASIR M,RAHIMIAN F,GIRDZIJAUSKAS S.Gossip-basedpartitioning and replication for Online Social Networks[C]∥Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).IEEE,2014:33-42.
[11] BROCHELER M,PUGLIESE A,S UBRAHMANIAN V S.Cosi:Cloud oriented subgraph identification in massive social networks[C]∥Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining (ASONAM).IEEE,2010:248-255.
[12] YU B,PAN J.Location-aware associated data placement forgeo-distributed data-intensive applications[C]∥2015 IEEE Conference on Computer Communications (INFOCOM).IEEE,2015:603-611.
[13] KUMAR K,QUAMAR A,D ESHPANDE A,et al.SWORD:workload-aware data placement and replica selection for cloud data management systems [J].The VLDB Journal-The International Journal on Very Large Data Bases,2014,23(6):845-870.
[14] TURK A,SELVITOPI O,FERHATOSMANOGLU H,et al.Temporal workload-aware replicated partitioning for social networks [J].IEEE Transactions on Knowledge and Data Engineering,2014,26(11):2832-2845.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!