{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:07:13Z","timestamp":1755839233626,"version":"3.37.3"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1636205","U1636205"],"award-info":[{"award-number":["U1636205","U1636205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1636205","61572413"],"award-info":[{"award-number":["U1636205","61572413"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Grants Council, Hong Kong SAR, China","award":["15238116, 15238118,15218919,C1008-16G"],"award-info":[{"award-number":["15238116, 15238118,15218919,C1008-16G"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP200103650"],"award-info":[{"award-number":["DP200103650"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00778-021-00706-0","type":"journal-article","created":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T13:02:19Z","timestamp":1636635739000},"page":"581-602","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Privacy and efficiency guaranteed social subgraph matching"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9857-654X","authenticated-orcid":false,"given":"Kai","family":"Huang","sequence":"first","affiliation":[]},{"given":"Haibo","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Shuigeng","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Jihong","family":"Guan","sequence":"additional","affiliation":[]},{"given":"Qingqing","family":"Ye","sequence":"additional","affiliation":[]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,11]]},"reference":[{"key":"706_CR1","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In: SIGMOD, pp. 1199\u20131214 (2016)","DOI":"10.1145\/2882903.2915236"},{"key":"706_CR2","unstructured":"Low, Y., Gonzalez, J.E., Kyrola, A., Bickson, D., Guestrin, C.E., Hellerstein, J.: Graphlab: a new framework for parallel machine learning. arXiv preprint arXiv:1408.2041 (2014)"},{"key":"706_CR3","doi-asserted-by":"crossref","unstructured":"Chang, Z., Zou, L., Li, F.: Privacy preserving subgraph matching on large graphs in cloud. In: SIGMOD, pp. 199\u2013213 (2016)","DOI":"10.1145\/2882903.2882956"},{"key":"706_CR4","doi-asserted-by":"crossref","unstructured":"Cao, N., Yang, Z., Wang, C., Ren, K., Lou, W.: Privacy-preserving query over encrypted graph-structured data in cloud computing. In: ICDCS, pp. 393\u2013402 (2011)","DOI":"10.1109\/ICDCS.2011.84"},{"key":"706_CR5","doi-asserted-by":"crossref","unstructured":"Hu, H., Xu, J., Chen, Q. et al.: Authenticating location-based services without compromising location privacy. In: SIGMOD, pp. 301\u2013312 (2012)","DOI":"10.1145\/2213836.2213871"},{"key":"706_CR6","doi-asserted-by":"crossref","unstructured":"Xu, J., Yi, P., Choi, B. et al.: Privacy-preserving reachability query services for massive networks. In: CIKM, pp. 145\u2013154 (2016)","DOI":"10.1145\/2983323.2983799"},{"key":"706_CR7","unstructured":"Available at: https:\/\/www.oracle.com\/a\/tech\/docs\/sg-oow2019-using-graph-analysis-and-fraud-detection-in-fintech-industry.pdf"},{"issue":"05","key":"706_CR8","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0218488502001648","volume":"10","author":"L Sweeney","year":"2002","unstructured":"Sweeney, L.: k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(05), 557\u2013570 (2002)","journal-title":"Int. J. Uncertain. Fuzziness Knowl. Based Syst."},{"key":"706_CR9","doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: l-diversity: privacy beyond k-anonymity. In: ICDE, pp. 24 (2006)","DOI":"10.1109\/ICDE.2006.1"},{"key":"706_CR10","doi-asserted-by":"crossref","unstructured":"Li, N., Li, T., Venkatasubramanian, S.: t-closeness: privacy beyond k-anonymity and l-diversity. In: ICDE, pp. 106\u2013115 (2007)","DOI":"10.1109\/ICDE.2007.367856"},{"key":"706_CR11","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: TCC, pp. 265\u2013284 (2006)","DOI":"10.1007\/11681878_14"},{"issue":"3","key":"706_CR12","first-page":"633","volume":"25","author":"M Yuan","year":"2013","unstructured":"Yuan, M., Chen, L., Philip, S.Y., Yu, T.: Protecting sensitive labels in social network data anonymization. TKDE 25(3), 633\u2013647 (2013)","journal-title":"TKDE"},{"key":"706_CR13","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: SIGMOD, pp. 93\u2013106 (2008)","DOI":"10.1145\/1376616.1376629"},{"issue":"3","key":"706_CR14","first-page":"635","volume":"26","author":"C-H Tai","year":"2014","unstructured":"Tai, C.-H., Tseng, P.-J., Philip, S.Y., Chen, M.-S.: Identity protection in sequential releases of dynamic networks. TKDE 26(3), 635\u2013651 (2014)","journal-title":"TKDE"},{"key":"706_CR15","doi-asserted-by":"crossref","unstructured":"Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: ICDE, pp. 506\u2013515 (2008)","DOI":"10.1109\/ICDE.2008.4497459"},{"issue":"1","key":"706_CR16","first-page":"102","volume":"1","author":"M Hay","year":"2008","unstructured":"Hay, M., Miklau, G., Jensen, D., Towsley, D., Weis, P.: Resisting structural re-identification in anonymized social networks. PVLDB 1(1), 102\u2013114 (2008)","journal-title":"PVLDB"},{"issue":"1","key":"706_CR17","first-page":"946","volume":"2","author":"L Zou","year":"2009","unstructured":"Zou, L., Chen, L., \u00d6zsu, M.T.: K-automorphism: a general framework for privacy preserving network publication. PVLDB 2(1), 946\u2013957 (2009)","journal-title":"PVLDB"},{"key":"706_CR18","doi-asserted-by":"crossref","unstructured":"Cheng, J., Fu, A.W.-c., Liu, J.: K-isomorphism: privacy preserving network publication against structural attacks. In: SIGMOD, pp. 459\u2013470 (2010)","DOI":"10.1145\/1807167.1807218"},{"key":"706_CR19","doi-asserted-by":"crossref","unstructured":"Wu, W., Xiao, Y., Wang, W., He, Z., Wang, Z.: K-symmetry model for identity anonymization in social networks. In: EDBT, pp. 111\u2013122 (2010)","DOI":"10.1145\/1739041.1739058"},{"key":"706_CR20","doi-asserted-by":"crossref","unstructured":"Gao, J., et al.: A privacy-preserving framework for subgraph pattern matching in cloud. In: DASFAA, pp. 307\u2013322 (2018)","DOI":"10.1007\/978-3-319-91452-7_20"},{"issue":"3","key":"706_CR21","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316\u2013329 (1998)","journal-title":"Oper. Res."},{"key":"706_CR22","doi-asserted-by":"crossref","unstructured":"Li, X.-Y., Zhang, C., Jung, T., Qian, J., Chen, L.: Graph-based privacy-preserving data publication. In: INFOCOM, pp. 1\u20139 (2016)","DOI":"10.1109\/INFOCOM.2016.7524584"},{"issue":"5\u20136","key":"706_CR23","first-page":"1158","volume":"28","author":"S Hajian","year":"2014","unstructured":"Hajian, S., Domingo-Ferrer, J., Farr\u00e0s, O.: Generalization-based privacy preservation and discrimination prevention in data publishing and mining. DMKD 28(5\u20136), 1158\u20131188 (2014)","journal-title":"DMKD"},{"key":"706_CR24","doi-asserted-by":"crossref","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover\u2019s distance as a metric for image retrieval. IJCV 40(2), 99\u2013121 (2000)","DOI":"10.1023\/A:1026543900054"},{"key":"706_CR25","doi-asserted-by":"crossref","unstructured":"Karypis, G., Kumar, V.: Analysis of multilevel graph partitioning. In: ICS, p.\u00a029 (1995)","DOI":"10.1145\/224170.224229"},{"key":"706_CR26","doi-asserted-by":"crossref","unstructured":"He, H., Singh, A.K.: Graphs-at-a-time: query language and access methods for graph databases. In: SIGMOD, pp. 405\u2013418 (2008)","DOI":"10.1145\/1376616.1376660"},{"issue":"4","key":"706_CR27","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"EL Lawler","year":"1966","unstructured":"Lawler, E.L., Wood, D.E.: Branch-and-bound methods: a survey. Oper. Res. 14(4), 699\u2013719 (1966)","journal-title":"Oper. Res."},{"key":"706_CR28","unstructured":"ILOG, I.: Cplex optimizer. https:\/\/www.ibm.com\/cn-zh\/marketplace\/ibm-ilog-cplex (2012)"},{"key":"706_CR29","doi-asserted-by":"crossref","unstructured":"Du, B., Zhang, S., Cao, N., Tong, H.: First: fast interactive attributed subgraph matching. In: SIGKDD. ACM, pp. 1447\u20131456 (2017)","DOI":"10.1145\/3097983.3098040"},{"issue":"2","key":"706_CR30","first-page":"176","volume":"11","author":"M Qiao","year":"2017","unstructured":"Qiao, M., Zhang, H., Cheng, H.: Subgraph matching: on compression and computation. PVLDB 11(2), 176\u2013188 (2017)","journal-title":"PVLDB"},{"key":"706_CR31","doi-asserted-by":"crossref","unstructured":"Yang, Z., Fu, A.W.-C., Liu, R.: Diversified top-k subgraph querying in a large graph. In: SIGMOD, pp. 1167\u20131182 (2016)","DOI":"10.1145\/2882903.2915216"},{"key":"706_CR32","unstructured":"Han, W.-S., Lee, J., Lee, J.-H.: Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD, pp. 337\u2013348 (2013)"},{"key":"706_CR33","doi-asserted-by":"crossref","unstructured":"Zhu, G., Lin, X., Zhu, K., Zhang, W., Yu, J.X.: Treespan: efficiently computing similarity all-matching. In: SIGMOD, pp. 529\u2013540 (2012)","DOI":"10.1145\/2213836.2213896"},{"key":"706_CR34","doi-asserted-by":"crossref","unstructured":"Hay, M., Li, C., Miklau, G., Jensen, D.: Accurate estimation of the degree distribution of private networks. In: ICDM, pp. 169\u2013178 (2009)","DOI":"10.1109\/ICDM.2009.11"},{"issue":"11","key":"706_CR35","first-page":"1146","volume":"4","author":"V Karwa","year":"2011","unstructured":"Karwa, V., Raskhodnikova, S., Smith, A., Yaroslavtsev, G.: Private analysis of graph structure. PVLDB 4(11), 1146\u20131157 (2011)","journal-title":"PVLDB"},{"key":"706_CR36","doi-asserted-by":"crossref","unstructured":"Zhang, J., Cormode, G., Procopiuc, C.M., Srivastava, D., Xiao, X.: Private release of graph statistics using ladder functions. In: SIGMOD, pp. 731\u2013745 (2015)","DOI":"10.1145\/2723372.2737785"},{"key":"706_CR37","doi-asserted-by":"publisher","unstructured":"Ye, Q., Hu, H., Au, M.H., Meng, X., Xiao, X.: LF-GDPR:Graph metric estimation with local differential privacy. In: TKDE (2020). https:\/\/doi.org\/10.1109\/TKDE.2020.3047124","DOI":"10.1109\/TKDE.2020.3047124"},{"key":"706_CR38","doi-asserted-by":"crossref","unstructured":"Jiang, H., Pei, J., Yu, D. et al.: Applications of differential privacy in social network analysis: a survey. TKDE (2021)","DOI":"10.1109\/TKDE.2021.3073062"},{"key":"706_CR39","unstructured":"Ding, X., Sheng, S., Zhou, S. et al.: Differentially Private Triangle Counting in Large Graphs. TKDE (2021)"},{"key":"706_CR40","doi-asserted-by":"crossref","unstructured":"Chen, S., Zhou, S.: Recursive mechanism: Towards node differential privacy and unrestricted joins. In: SIGMOD, pp. 653\u2013664 (2013)","DOI":"10.1145\/2463676.2465304"},{"key":"706_CR41","doi-asserted-by":"crossref","unstructured":"Kasiviswanathan, S.P., Nissim, K., Raskhodnikova, S., Smith, A.: Analyzing graphs with node differential privacy. In: TCC, pp. 457\u2013476 (2013)","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"706_CR42","doi-asserted-by":"crossref","unstructured":"Day, W.Y., Li, N., Lyu, M.: Publishing graph degree distribution with node differential privacy. In: SIGMOD, pp. 123\u2013138 (2016)","DOI":"10.1145\/2882903.2926745"},{"issue":"4","key":"706_CR43","first-page":"591","volume":"15","author":"Q Wang","year":"2016","unstructured":"Wang, Q., Zhang, Y., Lu, X., et al.: Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy. TDSC 15(4), 591\u2013606 (2016)","journal-title":"TDSC"},{"key":"706_CR44","doi-asserted-by":"crossref","unstructured":"Jorgensen, Z., Yu, T., Cormode, G.: Publishing attributed social graphs with formal privacy guarantees. In: SIGMOD, pp. 107\u2013122 (2016)","DOI":"10.1145\/2882903.2915215"},{"key":"706_CR45","doi-asserted-by":"crossref","unstructured":"Zheleva, E., Getoor, L.: Preserving the privacy of sensitive relationships in graph data. In: International Workshop on Privacy, Security, and Trust in KDD, pp. 153\u2013171 (2007)","DOI":"10.1007\/978-3-540-78478-4_9"},{"key":"706_CR46","doi-asserted-by":"crossref","unstructured":"Campan, A., Truta, T.M.: Data and structural k-anonymity in social networks. In: International Workshop on Privacy, Security, and Trust in KDD, pp. 33\u201354 (2008)","DOI":"10.1007\/978-3-642-01718-6_4"},{"issue":"1","key":"706_CR47","first-page":"766","volume":"2","author":"S Bhagat","year":"2009","unstructured":"Bhagat, S., Cormode, G., Krishnamurthy, B., Srivastava, D.: Class-based graph anonymization for social network data. PVLDB 2(1), 766\u2013777 (2009)","journal-title":"PVLDB"},{"key":"706_CR48","doi-asserted-by":"crossref","unstructured":"Fan, Z., Choi, B., Xu, J., Bhowmick, S.S.: Asymmetric structure-preserving subgraph queries for large graphs. In: ICDE, pp. 339\u2013350 (2015)","DOI":"10.1109\/ICDE.2015.7113296"},{"key":"706_CR49","doi-asserted-by":"crossref","unstructured":"Gao, J., Yu, J.X., Jin, R., Zhou, J., Wang, T., Yang, D.: Neighborhood-privacy protected shortest distance computing in cloud. In: SIGMOD, pp. 409\u2013420 (2011)","DOI":"10.1145\/1989323.1989367"},{"key":"706_CR50","doi-asserted-by":"crossref","unstructured":"Xie, D., Li, G., Yao, B., Wei, X., Xiao, X., Gao, Y., Guo, M.: Practical private shortest path computation based on oblivious storage. In: ICDE, pp. 361\u2013372 (2016)","DOI":"10.1109\/ICDE.2016.7498254"},{"issue":"10","key":"706_CR51","first-page":"1999","volume":"30","author":"J Ma","year":"2018","unstructured":"Ma, J., Yao, B., Gao, X., et al.: Top-k critical vertices query on shortest path. TKDE 30(10), 1999\u20132012 (2018)","journal-title":"TKDE"},{"issue":"4","key":"706_CR52","first-page":"940","volume":"13","author":"M Shen","year":"2017","unstructured":"Shen, M., Ma, B., Zhu, L., et al.: Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection. TIFS 13(4), 940\u2013953 (2017)","journal-title":"TIFS"},{"issue":"2","key":"706_CR53","first-page":"331","volume":"33","author":"X Ding","year":"2019","unstructured":"Ding, X., Wang, C., Choo, K.K.R., et al.: A novel privacy preserving framework for large scale graph data publishing. TKDE 33(2), 331\u2013343 (2019)","journal-title":"TKDE"},{"key":"706_CR54","doi-asserted-by":"crossref","unstructured":"Jiang, J., Yi, P., Choi, B., et al.: Privacy-preserving reachability query services for massive networks. In: CIKM, pp. 145\u2013154 (2016)","DOI":"10.1145\/2983323.2983799"},{"key":"706_CR55","first-page":"25","volume":"134","author":"S Yang","year":"2019","unstructured":"Yang, S., Tang, S., Zhang, X.: Privacy-preserving k nearest neighbor query with authentication on road networks. JPDC 134, 25\u201336 (2019)","journal-title":"JPDC"},{"key":"706_CR56","doi-asserted-by":"crossref","unstructured":"Liang, H., Yuan, H.: On the complexity of t-closeness anonymization and related problems. In: DASFAA, pp. 331\u2013345 (2013)","DOI":"10.1007\/978-3-642-37487-6_26"},{"issue":"1","key":"706_CR57","first-page":"364","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB 1(1), 364\u2013375 (2008)","journal-title":"PVLDB"},{"key":"706_CR58","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman San Francisco, vol. 174 (1979)"},{"issue":"9\u201310","key":"706_CR59","doi-asserted-by":"publisher","first-page":"2306","DOI":"10.1016\/j.mcm.2011.05.039","volume":"54","author":"S Schrenk","year":"2011","unstructured":"Schrenk, S., Finke, G., Cung, V.-D.: Two classical transportation problems revisited: pure constant fixed charges and the paradox. Math. Comput. Model. 54(9\u201310), 2306\u20132315 (2011)","journal-title":"Math. Comput. Model."},{"issue":"1","key":"706_CR60","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jlst-2015-0006","volume":"6","author":"J \u017derovnik","year":"2015","unstructured":"\u017derovnik, J.: Heuristics for np-hard optimization problems-simpler is better!? Logist. Sustain. Transp. 6(1), 1\u201310 (2015)","journal-title":"Logist. Sustain. Transp."},{"key":"706_CR61","doi-asserted-by":"crossref","unstructured":"Nayak, K., Wang, X.S., Ioannidis, S., Weinsberg, U., Taft, N., Shi, E.: Graphsc: Parallel secure computation made easy. In: S&P, pp. 377\u2013394 (2015)","DOI":"10.1109\/SP.2015.30"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00706-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00706-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00706-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T23:18:25Z","timestamp":1726096705000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00706-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,11]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["706"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00706-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2021,11,11]]},"assertion":[{"value":"12 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}