(K, P)-SHORTEST PATH ALGORITHM IN THE CLOUD MAINTAINING NEIGHBORHOOD PRIVACY
Keywords:
privacy preservation, k-neighborhood privacy, sensitive path privacy, shortest path, k-skipAbstract
Privacy-preserving computation has recently attracted much attention in areas of transaction, social networking, location-based, and mobile services. The inexpensive storage and efficient computation of cloud computing technology is expected to further escalate these services to a higher and wider level, without compromising the breaches of sensitive information. In this work, we study the shortest path distance computing in the cloud while preserving two types of privacy in the same time: k-neighborhood privacy and sensitive path privacy. We propose a new privacy model called (k, p)-shortest path neighborhood privacy, which is an extension of [19] and more flexible than 1-neighborhood-d-radius model [6]. We also develop an efficient four-step shortest distance computation scheme to achieve (k, p)- shortest path neighborhood privacy on p outsourced servers in the cloud, which combines the construction of k-skip shortest path sub-graphs, sensitive vertex adjustment, vertex hierarchy labeling and bottom-up partitioning techniques. Numerical experiments show that the proposed approach is more efficient than prior model of constructing the 1-neighborhood privacy graph and also requires less querying time.
Downloads
References
I. Abraham, A. Fiat, A.V. Goldberg, and R.F.F. Werneck, “Highway dimension, shortest paths,
and provably efficient algorithms,” In Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), 782–793, 2010.
D. Agrawal, A. El Abbadi, S. Antony, and S. Das, “Data management challenges in cloud
computing infrastructures,” In Proceedings of the 6th international conference on Databases in
Networked Information Systems, Berlin, Heidelberg, 1–10, 2010.
K.M. Chandy ad J. Misra, “Distributed computation on graphs: shortest path algorithm,” In
Communications of ACM, Vol. 25, No. 11, 833-857, 1982.
S. Das, O. Egecioglu, and A. El Abbadi, “Anonymizing weighted social network graphs,” In 2010
IEEE 26th International Conference on Data Engineering (ICDE), 904–907, 2010.
A. W.-C. Fu, H. Wu, J. Cheng, S. Chu, and R. C.-W. Wong, “IS-LABEL: an independent-set
based labeling scheme for point-to-point distance querying on large graphs,” arXiv:1211.2367,
Nov. 2012.
J. Gao, J. X. Yu, R. Jin, J. Zhou, T. Wang, and D. Yang, “Neighborhood-privacy protected
shortest distance computing in cloud,” In Proceedings of the 2011 ACM SIGMOD International
Conference on Management of Data, New York, NY, USA, 409–420, 2011.
H. Hacigümüs, B.R. Iyer, and S. Mehrotra. “Providing database as a service,” In ICDE, pages 29–
, 2002.
M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis, “Resisting structural re-identification in
anonymized social networks,” In Proc Vldb Endow, vol. 1, no. 1, 102–114, 2008.
IPython.parallel, http://ipython.org/ipython-doc/dev/parallel
S. Kanchi, D. Vineyard, “An optimal distributed algorithm for all pairs shortest path,” In
International Journal of Information Theories and Applications, Vol. 11, 141-146, 2004.
L. Liu, J. Liu, J. Zhang, “Privacy preservation of affinities in social networks”, In Proceedings of
the International conference on Information Systems, 372-376, 2010.
K. Liu and E. Terzi, “Towards identity anonymization on graphs,” In Proceedings of the 2008
ACM SIGMOD international conference on Management of data, New York, USA, 93–106, 2008.
L. Liu, J. Wang, J. Liu, J. Zhang, “Privacy preservation in social networks with sensitive edge
weights,” In SDM, 954-965, 2009.
S. Nath, H. Yu, and H. Chan. “Secure outsourced aggregation via one-way chain,” In SIGMOD,
pages 31–44, 2009.
Networkx, http://networkx.github.io/
P. Sanders and D. Schultes. “Engineering highway hierarchies,” In Proceedings of European
Symposium on Algorithms (ESA), 804–816, 2006.
Y. Tao, C. Sheng, and J. Pei, “On k-skip shortest paths,” In Proceedings of the 2011 ACM
SIGMOD International Conference on Management of data, New York, USA, 421-432, 2011.
VirtualBox, https://www.virtualbox.org/
S.L. Wang, J.W. Chen, H.H. Ting, and T.P. Hong, “Sensitive and neighborhood privacy on
shortest paths in the cloud”, In Proceedings of the 15th International Conference on Information
Integration and Web-based Applications & Services, Vienna, Austria, 555-559, 2013.
S.L. Wang, C.C. Shih, H.H. Ting, and T.P. Hong, “Degree anonymization for K-shortest-path
privacy”, In 2013 IEEE International Conference on SMC, Manchester, UK, October, 2013.
S.L. Wang, Z.Z. Tsai, T.P. Hong, and H.H. Ting, “Anonymizing shortest paths on social network
graphs”, In Proceedings of the The Third Asian Conference on Intelligent Information and
Database Systems (ACIIDS), Daegu, Korea April, 2011.
M.L. Yiu, Y.Lin, and K.Mouratidis. “Efficient verification of shortest path search via authenticated
hints,” In ICDE, 237–248, 2010.
M. Yuan, L. Chen, and P. S. Yu, “Personalized privacy protection in social networks,” In Proc
VLDB Endow, vol. 4, no. 2, 141–150, 2010.
B. Zhou and J. Pei, “Preserving privacy in social networks against neighborhood attacks,” In
Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, Washington,
DC, USA, 506–515, 2008.
L. Zou, L. Chen, and M. T. Özsu, “Distance-join: pattern match query in a large graph database,”
In Proc Vldb Endow, vol. 2, no. 1, pp. 886–897, Aug. 2009.
