{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T02:03:36Z","timestamp":1783476216902,"version":"3.55.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Union's Seventh Framework Programme (FP7\/2007-2013)\/ERC","award":["259569"],"award-info":[{"award-number":["259569"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2015,4,13]]},"abstract":"<jats:p>The emergence of cloud-based storage services is opening up new avenues in data exchange and data dissemination. This has amplified the interest in right-protection mechanisms to establish ownership in the event of data leakage. Current right-protection technologies, however, rarely provide strong guarantees on dataset utility after the protection process. This work presents techniques that explicitly address this topic and provably preserve the outcome of certain mining operations. In particular, we take special care to guarantee that the outcome of hierarchical clustering operations remains the same before and after right protection. Our approach considers all prevalent hierarchical clustering variants: single-, complete-, and average-linkage. We imprint the ownership in a dataset using watermarking principles, and we derive tight bounds on the expansion\/contraction of distances incurred by the process. We leverage our analysis to design fast algorithms for right protection without exhaustively searching the vast design space. Finally, because the right-protection process introduces a user-tunable distortion on the dataset, we explore the possibility of using this mechanism for data obfuscation. We quantify the tradeoff between obfuscation and utility for spatiotemporal datasets and discover very favorable characteristics of the process. An additional advantage is that when one is interested in both right-protecting and obfuscating the original data values, the proposed mechanism can accomplish both tasks simultaneously.<\/jats:p>","DOI":"10.1145\/2700403","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T20:29:44Z","timestamp":1428092984000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On Data Publishing with Clustering Preservation"],"prefix":"10.1145","volume":"9","author":[{"given":"Michail","family":"Vlachos","sequence":"first","affiliation":[{"name":"IBM Research - Zurich, R\u00e4schlikon, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"Schneider","sequence":"additional","affiliation":[{"name":"ABB Corporate Research - Baden, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vassilios G.","family":"Vassiliadis","sequence":"additional","affiliation":[{"name":"IBM Research - Zurich, R\u00e4schlikon, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497446"},{"key":"e_1_2_1_2_1","volume-title":"Yu","author":"Aggarwal Charu C.","year":"2004","unstructured":"Charu C. Aggarwal and Philip S . Yu . 2004 . A condensation approach to privacy preserving data mining. In Advances in Database Technology - EDBT 2004, Elisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens B\u00f6hm, and Elena Ferrari (Eds.). Lecture Notes in Computer Science, Vol. 2992 . Springer , Berlin, 183--199. Charu C. Aggarwal and Philip S. Yu. 2004. A condensation approach to privacy preserving data mining. In Advances in Database Technology - EDBT 2004, Elisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens B\u00f6hm, and Elena Ferrari (Eds.). Lecture Notes in Computer Science, Vol. 2992. Springer, Berlin, 183--199."},{"key":"e_1_2_1_3_1","volume-title":"Yu","author":"Aggarwal Charu C.","year":"2008","unstructured":"Charu C. Aggarwal and Philip S . Yu . 2008 . A general survey of privacy-preserving data mining models and algorithms. In Privacy-Preserving Data Mining, Charu C. Aggarwal and Philip S. Yu (Eds.). Advances in Database Systems, Vol. 34 . Springer , 11--52. Charu C. Aggarwal and Philip S. Yu. 2008. A general survey of privacy-preserving data mining models and algorithms. In Privacy-Preserving Data Mining, Charu C. Aggarwal and Philip S. Yu (Eds.). Advances in Database Systems, Vol. 34. Springer, 11--52."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287384"},{"key":"e_1_2_1_5_1","volume-title":"Sabrina De Capitani di Vimercati, and Pierangela Samarati","author":"Ardagna Claudio Agostino","year":"2007","unstructured":"Claudio Agostino Ardagna , Marco Cremonini , Ernesto Damiani , Sabrina De Capitani di Vimercati, and Pierangela Samarati . 2007 . Location privacy protection through obfuscation-based techniques. In Data and Applications Security XXI, Steve Barker and Gail-Joon Ahn (Eds.). Lecture Notes in Computer Science, Vol. 4602 . Springer , Berlin, 47--60. Claudio Agostino Ardagna, Marco Cremonini, Ernesto Damiani, Sabrina De Capitani di Vimercati, and Pierangela Samarati. 2007. Location privacy protection through obfuscation-based techniques. In Data and Applications Security XXI, Steve Barker and Gail-Joon Ahn (Eds.). Lecture Notes in Computer Science, Vol. 4602. Springer, Berlin, 47--60."},{"key":"e_1_2_1_6_1","first-page":"19","article-title":"Digital rights protection","volume":"27","author":"Atallah Mikhail J.","year":"2004","unstructured":"Mikhail J. Atallah , Sunil Prabhakar , Keith B. Frikken , and Radu Sion . 2004 . Digital rights protection . IEEE Data Engineering Bulletin 27 , 1 (2004), 19 -- 25 . Mikhail J. Atallah, Sunil Prabhakar, Keith B. Frikken, and Radu Sion. 2004. Digital rights protection. IEEE Data Engineering Bulletin 27, 1 (2004), 19--25.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/6046.923822"},{"key":"e_1_2_1_8_1","volume-title":"Retrieved","author":"Borgatti Steve","year":"2007","unstructured":"Steve Borgatti . 2007 . Distance and Correlation. (2007) . Retrieved March 30, 2014 from http:\/\/www.analytictech.com\/mb876\/handouts\/distance_and_correlation.htm. Steve Borgatti. 2007. Distance and Correlation. (2007). Retrieved March 30, 2014 from http:\/\/www.analytictech.com\/mb876\/handouts\/distance_and_correlation.htm."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.121"},{"key":"e_1_2_1_10_1","volume-title":"Desai","author":"Chen Rui","year":"2011","unstructured":"Rui Chen , Benjamin C. M. Fung , and Bipin C . Desai . 2011 . Differentially private trajectory data publication. CoRR abs\/1112.2020 (2011). Rui Chen, Benjamin C. M. Fung, and Bipin C. Desai. 2011. Differentially private trajectory data publication. CoRR abs\/1112.2020 (2011)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEMBS.2011.6092021"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.21314\/JOP.2008.052"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.650120"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.4.364"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00132-V"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.929851"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2218\/ijdc.v6i1.172"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1983.10478008"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1749603.1749605"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.12.001"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2009 Conference on Hot Topics in Cloud Computing (HotCloud\u201909)","author":"Geambasu Roxana","unstructured":"Roxana Geambasu , Steven D. Gribble , and Henry M. Levy . 2009. CloudViews: Communal data sharing in public clouds . In Proceedings of the 2009 Conference on Hot Topics in Cloud Computing (HotCloud\u201909) . USENIX Association, Article 14. Roxana Geambasu, Steven D. Gribble, and Henry M. Levy. 2009. CloudViews: Communal data sharing in public clouds. In Proceedings of the 2009 Conference on Hot Topics in Cloud Computing (HotCloud\u201909). USENIX Association, Article 14."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538909.1538911"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01516-8_26"},{"key":"e_1_2_1_24_1","unstructured":"HGP 2013. All About The Human Genome Project. Retrieved from http:\/\/www.genome.gov\/10001772.  HGP 2013. All About The Human Genome Project. Retrieved from http:\/\/www.genome.gov\/10001772."},{"key":"e_1_2_1_25_1","volume-title":"Wright","author":"Jagannathan Geetha","year":"2006","unstructured":"Geetha Jagannathan , Krishnan Pillaipakkamnatt , and Rebecca N . Wright . 2006 . A new privacy-preserving distributed k-clustering algorithm. In Proceedings of the 2006 SIAM International Conference on Data Mining. 494--498. Geetha Jagannathan, Krishnan Pillaipakkamnatt, and Rebecca N. Wright. 2006. A new privacy-preserving distributed k-clustering algorithm. In Proceedings of the 2006 SIAM International Conference on Data Mining. 494--498."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484846"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952160"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557079"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2006.155"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0178-6"},{"key":"e_1_2_1_31_1","volume-title":"Overview: A phylogenetic backbone and taxonomic framework for procaryotic systematics. In Bergey","author":"Ludwig Wolfgang","year":"2001","unstructured":"Wolfgang Ludwig and Hans-Peter Klenk . 2001 . Overview: A phylogenetic backbone and taxonomic framework for procaryotic systematics. In Bergey \u2019 s Manual of Systematic Bacteriology. Springer , 49--65. Wolfgang Ludwig and Hans-Peter Klenk. 2001. Overview: A phylogenetic backbone and taxonomic framework for procaryotic systematics. In Bergey\u2019 s Manual of Systematic Bacteriology. Springer, 49--65."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646140"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2000.899542"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0010-5"},{"key":"e_1_2_1_36_1","first-page":"101","article-title":"Complexities of hierarchic clustering algorithms: State of the art","volume":"1","author":"Murtagh Fionn","year":"1984","unstructured":"Fionn Murtagh . 1984 . Complexities of hierarchic clustering algorithms: State of the art . Computational Statistics Quarterly 1 , 2 (1984), 101 -- 113 . Fionn Murtagh. 1984. Complexities of hierarchic clustering algorithms: State of the art. Computational Statistics Quarterly 1, 2 (1984), 101--113.","journal-title":"Computational Statistics Quarterly"},{"key":"e_1_2_1_37_1","first-page":"1","article-title":"Towards trajectory anonymization: A generalization-based approach","volume":"2","author":"Nergiz Mehmet Ercan","year":"2009","unstructured":"Mehmet Ercan Nergiz , Maurizio Atzori , Y\u00fccel Saygin , and Baris G\u00fc\u00e7 . 2009 . Towards trajectory anonymization: A generalization-based approach . Transactions on Data Privacy 2 , 1 (April 2009), 47--75. Mehmet Ercan Nergiz, Maurizio Atzori, Y\u00fccel Saygin, and Baris G\u00fc\u00e7. 2009. Towards trajectory anonymization: A generalization-based approach. Transactions on Data Privacy 2, 1 (April 2009), 47--75.","journal-title":"Transactions on Data Privacy"},{"key":"e_1_2_1_38_1","first-page":"37","article-title":"Privacy preserving clustering by data transformation","volume":"1","author":"Oliveira Stanley R. M.","year":"2010","unstructured":"Stanley R. M. Oliveira and Osmar R. Za\u00efane . 2010 . Privacy preserving clustering by data transformation . Journal of Information and Data Management 1 , 1 (2010), 37 -- 52 . Stanley R. M. Oliveira and Osmar R. Za\u00efane. 2010. Privacy preserving clustering by data transformation. Journal of Information and Data Management 1, 1 (2010), 37--52.","journal-title":"Journal of Information and Data Management"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2005 IEEE International Conference on Data Mining. 18--25","author":"Parameswaran Rupa","unstructured":"Rupa Parameswaran and D. Blough . 2005. A robust data obfuscation approach for privacy preservation of clustered data . In Proceedings of the 2005 IEEE International Conference on Data Mining. 18--25 . Rupa Parameswaran and D. Blough. 2005. A robust data obfuscation approach for privacy preservation of clustered data. In Proceedings of the 2005 IEEE International Conference on Data Mining. 18--25."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501656"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1702135.1702171"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968151"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/16.1.30"},{"key":"e_1_2_1_44_1","volume-title":"Using mean similarity dendrograms to evaluate classifications. Journal of Agricultural, Biological, and Environmental Statistics","author":"Sickle John Van","year":"1997","unstructured":"John Van Sickle . 1997. Using mean similarity dendrograms to evaluate classifications. Journal of Agricultural, Biological, and Environmental Statistics ( 1997 ), 370--388. John Van Sickle. 1997. Using mean similarity dendrograms to evaluate classifications. Journal of Agricultural, Biological, and Environmental Statistics (1997), 370--388."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the IEEE International Conference on Multimedia and Expo","volume":"1","author":"Simitopoulos Dimitrios","unstructured":"Dimitrios Simitopoulos , Sotirios A. Tsaftaris , Nikolaos V. Boulgouris , and Michael G. Strintzis . 2002. Compressed-domain video watermarking of MPEG streams . In Proceedings of the IEEE International Conference on Multimedia and Expo , Vol. 1 . IEEE, 569--572. Dimitrios Simitopoulos, Sotirios A. Tsaftaris, Nikolaos V. Boulgouris, and Michael G. Strintzis. 2002. Compressed-domain video watermarking of MPEG streams. In Proceedings of the IEEE International Conference on Multimedia and Expo, Vol. 1. IEEE, 569--572."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.94"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.82"},{"key":"e_1_2_1_48_1","volume-title":"Limits of predictability in human mobility. Science 327, 5968","author":"Song Chaoming","year":"2010","unstructured":"Chaoming Song , Zehui Qu , Nicholas Blumm , and Albert-Lszl Barabsi . 2010. Limits of predictability in human mobility. Science 327, 5968 ( 2010 ), 1018--1021. Chaoming Song, Zehui Qu, Nicholas Blumm, and Albert-Lszl Barabsi. 2010. Limits of predictability in human mobility. Science 327, 5968 (2010), 1018--1021."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1684(98)00014-0"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2008.29"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69497-7_8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956776"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956777"},{"key":"e_1_2_1_54_1","volume-title":"Developments in Applied Statistics, Anu\u0161ka Ferligoj and Andrej Mrvar (Eds.). metodolo\u0161ki zvezki - Advances in Methodology and Statistics","author":"\u017diberna Ale\u0161","unstructured":"Ale\u0161 \u017diberna and Vesna \u017dabkar . 2003. Application of end-users market segmentation using statistical methods . In Developments in Applied Statistics, Anu\u0161ka Ferligoj and Andrej Mrvar (Eds.). metodolo\u0161ki zvezki - Advances in Methodology and Statistics , Vol. 19 . 243--263. Ale\u0161 \u017diberna and Vesna \u017dabkar. 2003. Application of end-users market segmentation using statistical methods. In Developments in Applied Statistics, Anu\u0161ka Ferligoj and Andrej Mrvar (Eds.). metodolo\u0161ki zvezki - Advances in Methodology and Statistics, Vol. 19. 243--263."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2240236.2240255"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993077.1993080"},{"key":"e_1_2_1_57_1","first-page":"1301","article-title":"A survey of digital vector map watermarking","volume":"2","author":"Xiamu Niu Xiaotong Wang","year":"2006","unstructured":"Xiaotong Wang Xiamu Niu , Chengyong Shao . 2006 . A survey of digital vector map watermarking . International Journal of Innovative Computing, Information and Control 2 , 6 (2006), 1301 -- 1316 . Xiaotong Wang Xiamu Niu, Chengyong Shao. 2006. A survey of digital vector map watermarking. International Journal of Innovative Computing, Information and Control 2, 6 (2006), 1301--1316.","journal-title":"International Journal of Innovative Computing, Information and Control"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536274.2536275"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063945"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141277.1141415"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_74"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/76.767121"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.90"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:44Z","timestamp":1750223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4,13]]}},"alternative-id":["10.1145\/2700403"],"URL":"https:\/\/doi.org\/10.1145\/2700403","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}