{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:44:16Z","timestamp":1725479056835},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,29]]},"abstract":"<jats:p>\n            We present SPARSI, a novel theoretical framework for partitioning sensitive data across multiple non-colluding adversaries. Most work in privacy-aware data sharing has considered disclosing summaries where the aggregate information about the data is preserved, but sensitive user information is protected. Nonetheless, there are applications, including online advertising, cloud computing and crowdsourcing markets, where detailed and fine-grained user data must be disclosed. We consider a new data sharing paradigm and introduce the problem of privacy-aware data partitioning, where a sensitive dataset must be partitioned among\n            <jats:italic>k<\/jats:italic>\n            untrusted parties (adversaries). The goal is to maximize the utility derived by partitioning and distributing the dataset, while minimizing the total amount of sensitive information disclosed. The data should be distributed so that an adversary, without colluding with other adversaries, cannot draw additional inferences about the private information, by linking together multiple pieces of information released to her. The assumption of no collusion is both reasonable and necessary in the above application domains that require release of private user information. SPARSI enables us to formally define privacy-aware data partitioning using the notion of sensitive properties for modeling private information and a hypergraph representation for describing the interdependencies between data entries and private information. We show that solving privacy-aware partitioning is, in general, NP-hard, but for specific information disclosure functions, good approximate solutions can be found using relaxation techniques. Finally, we present a local search algorithm applicable to generic information disclosure functions. We conduct a rigorous performance evaluation with real-world and synthetic datasets that illustrates the effectiveness of SPARSI at partitioning sensitive data while minimizing disclosure.\n          <\/jats:p>","DOI":"10.14778\/2536258.2536270","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1594-1605","source":"Crossref","is-referenced-by-count":13,"title":["SPARSI"],"prefix":"10.14778","volume":"6","author":[{"given":"Theodoros","family":"Rekatsinas","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amol","family":"Deshpande","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Brightkite: A location based social network. http:\/\/en.wikipedia.org\/wiki\/Brightkite.  Brightkite: A location based social network. http:\/\/en.wikipedia.org\/wiki\/Brightkite."},{"key":"e_1_2_1_2_1","unstructured":"Gowalla: A location based social network. http:\/\/en.wikipedia.org\/wiki\/Gowalla.  Gowalla: A location based social network. http:\/\/en.wikipedia.org\/wiki\/Gowalla."},{"issue":"1","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/1900000008","article-title":"Privacy-preserving data publishing","volume":"2","author":"Chen B.-C.","year":"2009","unstructured":"B.-C. Chen , D. Kifer , K. Lefevre , and A. Machanavajjhala . Privacy-preserving data publishing . Foundations and Trends in Databases , 2 ( 1-2 ): 1 - 167 , 2009 . B.-C. Chen, D. Kifer, K. Lefevre, and A. Machanavajjhala. Privacy-preserving data publishing. Foundations and Trends in Databases, 2(1-2):1-167, 2009.","journal-title":"Foundations and Trends in Databases"},{"key":"e_1_2_1_4_1","first-page":"1082","volume-title":"KDD","author":"Cho E.","year":"2011","unstructured":"E. Cho , S. A. Myers , and J. Leskovec . Friendship and mobility: user movement in location-based social networks . In KDD , pages 1082 - 1090 , 2011 . E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in location-based social networks. In KDD, pages 1082-1090, 2011."},{"key":"e_1_2_1_5_1","volume-title":"Assessing privacy risk in outsourcing","author":"Davino M.","year":"2004","unstructured":"M. Davino . Assessing privacy risk in outsourcing . American Health Information Management Association , vol. 75 , 2004 . M. Davino. Assessing privacy risk in outsourcing. American Health Information Management Association, vol. 75, 2004."},{"key":"e_1_2_1_6_1","volume-title":"SEA","author":"Doerr B.","year":"2010","unstructured":"B. Doerr , M. K\u00fcnnemann , and M. Wahlstr\u00f6m . Randomized rounding for routing and covering problems: experiments and improvements . In SEA , 2010 . B. Doerr, M. K\u00fcnnemann, and M. Wahlstr\u00f6m. Randomized rounding for routing and covering problems: experiments and improvements. In SEA, 2010."},{"key":"e_1_2_1_7_1","first-page":"14","volume-title":"Proceedings of the 19th USENIX Security Symposium","author":"Duan Y.","year":"2010","unstructured":"Y. Duan , N. Youdao , J. Canny , and J. Zhan . P4p: Practical large-scale privacy-preserving distributed computation robust against malicious users abstract . In Proceedings of the 19th USENIX Security Symposium , page 14 , 2010 . Y. Duan, N. Youdao, J. Canny, and J. Zhan. P4p: Practical large-scale privacy-preserving distributed computation robust against malicious users abstract. In Proceedings of the 19th USENIX Security Symposium, page 14, 2010."},{"key":"e_1_2_1_8_1","first-page":"1","volume-title":"TAMC","author":"Dwork C.","year":"2008","unstructured":"C. Dwork . Differential privacy : A survey of results . In TAMC , pages 1 - 19 , 2008 . C. Dwork. Differential privacy: A survey of results. In TAMC, pages 1-19, 2008."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","article-title":"Greedy randomized adaptive search procedures","volume":"6","author":"Feo T. A.","year":"1995","unstructured":"T. A. Feo and M. G. Resende . Greedy randomized adaptive search procedures . Journal of Global Optimization , 6 : 109 - 133 , 1995 . T. A. Feo and M. G. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109-133, 1995.","journal-title":"Journal of Global Optimization"},{"key":"e_1_2_1_10_1","volume-title":"Submodular functions and optimization. Annals of Discrete Mathematics","author":"Fijishige S.","year":"2005","unstructured":"S. Fijishige . Submodular functions and optimization. Annals of Discrete Mathematics . Elsevier , 2005 . S. Fijishige. Submodular functions and optimization. Annals of Discrete Mathematics. Elsevier, 2005."},{"issue":"3","key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1147954.1147956","article-title":"Dependent rounding and its applications to approximation algorithms","volume":"53","author":"Gandhi R.","year":"2006","unstructured":"R. Gandhi , S. Khuller , S. Parthasarathy , and A. Srinivasan . Dependent rounding and its applications to approximation algorithms . J. ACM , 53 ( 3 ): 324 - 360 , 2006 . R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324-360, 2006.","journal-title":"J. ACM"},{"issue":"6","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans M. X.","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson . Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming . J. ACM , 42 ( 6 ): 1115 - 1145 , 1995 . M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995.","journal-title":"J. ACM"},{"key":"e_1_2_1_13_1","volume-title":"CMU","author":"Golovin D.","year":"2005","unstructured":"D. Golovin . Max-min fair allocation of indivisible goods. Technical report , CMU , 2005 . D. Golovin. Max-min fair allocation of indivisible goods. Technical report, CMU, 2005."},{"key":"e_1_2_1_14_1","volume-title":"NSDI, page 13","author":"Guha S.","year":"2011","unstructured":"S. Guha , B. Cheng , and P. Francis . Privad: practical privacy in online advertising . In NSDI, page 13 , 2011 . S. Guha, B. Cheng, and P. Francis. Privad: practical privacy in online advertising. In NSDI, page 13, 2011."},{"key":"e_1_2_1_15_1","volume-title":"CoRR","author":"Hardt M.","year":"2010","unstructured":"M. Hardt , K. Ligett , and F. McSherry . A simple and practical algorithm for differentially private data release . CoRR , 2010 . M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. CoRR, 2010."},{"key":"e_1_2_1_16_1","first-page":"4","article-title":"Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays","author":"Homer N.","year":"2008","unstructured":"N. Homer , S. Szelinger , M. Redman , D. Duggan , W. Tembe , J. Muehling , J. V. Pearson , D. A. Stephan , S. F. Nelson , and D. W. Craig . Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays . PLoS Genet , 4 , 2008 . N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS Genet, 4, 2008.","journal-title":"PLoS Genet"},{"key":"e_1_2_1_17_1","volume-title":"APPROX\/RANDOM","author":"Khot S.","year":"2007","unstructured":"S. Khot and A. K. Ponnuswami . Approximation algorithms for the max-min allocation problem . In APPROX\/RANDOM , 2007 . S. Khot and A. K. Ponnuswami. Approximation algorithms for the max-min allocation problem. In APPROX\/RANDOM, 2007."},{"key":"e_1_2_1_18_1","first-page":"1181","volume-title":"AAAI","author":"Krause A.","year":"2008","unstructured":"A. Krause and E. Horvitz . A utility-theoretic approach to privacy and personalization . In AAAI , pages 1181 - 1188 , 2008 . A. Krause and E. Horvitz. A utility-theoretic approach to privacy and personalization. In AAAI, pages 1181-1188, 2008."},{"key":"e_1_2_1_19_1","first-page":"545","volume-title":"SODA","author":"Kulik A.","year":"2009","unstructured":"A. Kulik , H. Shachnai , and T. Tamir . Maximizing submodular set functions subject to multiple linear constraints . In SODA , pages 545 - 554 , 2009 . A. Kulik, H. Shachnai, and T. Tamir. Maximizing submodular set functions subject to multiple linear constraints. In SODA, pages 545-554, 2009."},{"key":"e_1_2_1_20_1","first-page":"323","volume-title":"STOC","author":"Lee J.","year":"2009","unstructured":"J. Lee , V. S. Mirrokni , V. Nagarajan , and M. Sviridenko . Non-monotone submodular maximization under matroid and knapsack constraints . In STOC , pages 323 - 332 , 2009 . J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In STOC, pages 323-332, 2009."},{"key":"e_1_2_1_21_1","first-page":"446","volume-title":"ICDE","author":"Li T.","year":"2008","unstructured":"T. Li and N. Li . Injector: Mining background knowledge for data anonymization . In ICDE , pages 446 - 455 , 2008 . T. Li and N. Li. Injector: Mining background knowledge for data anonymization. In ICDE, pages 446-455, 2008."},{"key":"e_1_2_1_22_1","volume-title":"ICDE, page 24","author":"Machanavajjhala A.","year":"2006","unstructured":"A. Machanavajjhala , J. Gehrke , D. Kifer , and M. Venkitasubramaniam . `l-diversity: Privacy beyond k-anonymity . In ICDE, page 24 , 2006 . A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. `l-diversity: Privacy beyond k-anonymity. In ICDE, page 24, 2006."},{"key":"e_1_2_1_23_1","unstructured":"A. Marshall. Principles of Economics. 1890.  A. Marshall. Principles of Economics . 1890."},{"issue":"4","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","article-title":"Randomized rounding: A technique for provably good algorithms and algorithmic proofs","volume":"7","author":"Raghavan P.","year":"1987","unstructured":"P. Raghavan and C. Tompson . Randomized rounding: A technique for provably good algorithms and algorithmic proofs . Combinatorica , 7 ( 4 ): 365 - 374 , 1987 . P. Raghavan and C. Tompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987.","journal-title":"Combinatorica"},{"issue":"5","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1142\/S0218488502001648","article-title":"a model for protecting privacy. International Journal on Uncertainty","volume":"10","author":"Sweeney L.","year":"2002","unstructured":"L. Sweeney . k-anonymity : a model for protecting privacy. International Journal on Uncertainty , Fuzziness and Knowledge-based Systems , 10 ( 5 ): 557 - 570 , 2002 . L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):557-570, 2002.","journal-title":"Fuzziness and Knowledge-based Systems"},{"key":"e_1_2_1_26_1","volume-title":"NDSS","author":"Toubiana V.","year":"2010","unstructured":"V. Toubiana , A. Narayanan , D. Boneh , H. Nissenbaum , and S. Barocas . Adnostic: Privacy preserving targeted advertising . In NDSS , 2010 . V. Toubiana, A. Narayanan, D. Boneh, H. Nissenbaum, and S. Barocas. Adnostic: Privacy preserving targeted advertising. In NDSS, 2010."},{"key":"e_1_2_1_27_1","first-page":"515","volume-title":"CCS","author":"Zhang K.","year":"2011","unstructured":"K. Zhang , X. Zhou , Y. Chen , X. Wang , and Y. Ruan . Sedic: privacy-aware data intensive computing on hybrid clouds . In CCS , pages 515 - 526 , 2011 . K. Zhang, X. Zhou, Y. Chen, X. Wang, and Y. Ruan. Sedic: privacy-aware data intensive computing on hybrid clouds. In CCS, pages 515-526, 2011."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536258.2536270","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:37:29Z","timestamp":1672223849000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536258.2536270"}},"subtitle":["partitioning sensitive data amongst multiple adversaries"],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":27,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,8,29]]}},"alternative-id":["10.14778\/2536258.2536270"],"URL":"https:\/\/doi.org\/10.14778\/2536258.2536270","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}