• SHYUE-LIANG WANG National University of Kaohsiung, Taiwan
  • JIA-WEI CHEN National University of Kaohsiung, Taiwan
  • I-HSIEN TING National University of Kaohsiung, Taiwan
  • TZUNG-PEI HONG National University of Kaohsiung, Taiwan


privacy preservation, k-neighborhood privacy, sensitive path privacy, shortest path, k-skip


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.



Download data is not yet available.


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.