{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T22:17:55Z","timestamp":1779920275627,"version":"3.53.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>\n            <jats:italic>Differential privacy<\/jats:italic>\n            is the state-of-the-art formal definition for data release under strong privacy guarantees. A variety of mechanisms have been proposed in the literature for releasing the noisy output of numeric queries (e.g., using the Laplace mechanism), based on the notions of global sensitivity and local sensitivity. However, although there has been some work on generic mechanisms for releasing the output of non-numeric queries using global sensitivity (e.g., the Exponential mechanism), the literature lacks generic mechanisms for releasing the output of non-numeric queries using local sensitivity to reduce the noise in the query output.\n          <\/jats:p>\n          <jats:p>\n            In this work, we remedy this shortcoming and present the\n            <jats:italic>local dampening mechanism.<\/jats:italic>\n            We adapt the notion of local sensitivity for the non-numeric setting and leverage it to design a generic non-numeric mechanism. We illustrate the effectiveness of the local dampening mechanism by applying it to two diverse problems: (i) Influential node analysis. Given an influence metric, we release the top-k most influential nodes while preserving the privacy of the relationship between nodes in the network; (ii) Decision tree induction. We provide a private adaptation to the ID3 algorithm to build decision trees from a given tabular dataset. Experimental results show that we could reduce the use of privacy budget by 3 to 4 orders of magnitude for Influential node analysis and increase accuracy up to 12% for Decision tree induction when compared to global sensitivity based approaches.\n          <\/jats:p>","DOI":"10.14778\/3436905.3436912","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T17:23:50Z","timestamp":1614014630000},"page":"521-533","source":"Crossref","is-referenced-by-count":8,"title":["Local dampening"],"prefix":"10.14778","volume":"14","author":[{"given":"Victor A. E.","family":"Farias","sequence":"first","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felipe T.","family":"Brito","sequence":"additional","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cheryl","family":"Flynn","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javam C.","family":"Machado","sequence":"additional","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhabrata","family":"Majumdar","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Catherine L Blake and Christopher J Merz. 1998. UCI repository of machine learning databases.  Catherine L Blake and Christopher J Merz. 1998. UCI repository of machine learning databases."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_4_1","volume-title":"Classification and regression trees","author":"Breiman Leo","unstructured":"Leo Breiman , Jerome Friedman , Charles J Stone , and Richard A Olshen . 1984. Classification and regression trees . CRC press . Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. 1984. Classification and regression trees. CRC press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_6_1","volume-title":"Differential privacy. Encyclopedia of Cryptography and Security","author":"Dwork Cynthia","year":"2011","unstructured":"Cynthia Dwork . 2011. Differential privacy. Encyclopedia of Cryptography and Security ( 2011 ), 338--340. Cynthia Dwork. 2011. Differential privacy. Encyclopedia of Cryptography and Security (2011), 338--340."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_9_1","volume-title":"Ego network betweenness. Social networks 27, 1","author":"Everett Martin","year":"2005","unstructured":"Martin Everett and Stephen P Borgatti . 2005. Ego network betweenness. Social networks 27, 1 ( 2005 ), 31--38. Martin Everett and Stephen P Borgatti. 2005. Ego network betweenness. Social networks 27, 1 (2005), 31--38."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436912"},{"key":"e_1_2_1_11_1","first-page":"99","article-title":"A Differentially Private Decision Forest","volume":"15","author":"Fletcher Sam","year":"2015","unstructured":"Sam Fletcher and Md Zahidul Islam . 2015 . A Differentially Private Decision Forest . AusDM 15 (2015), 99 -- 108 . Sam Fletcher and Md Zahidul Islam. 2015. A Differentially Private Decision Forest. AusDM 15 (2015), 99--108.","journal-title":"AusDM"},{"key":"e_1_2_1_12_1","volume-title":"Australasian joint conference on artificial intelligence","author":"Fletcher Sam","unstructured":"Sam Fletcher and Md Zahidul Islam . 2015. A differentially private random decision forest using reliable signal-to-noise ratios . In Australasian joint conference on artificial intelligence . Springer , 192--203. Sam Fletcher and Md Zahidul Islam. 2015. A differentially private random decision forest using reliable signal-to-noise ratios. In Australasian joint conference on artificial intelligence. Springer, 192--203."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.01.034"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337064"},{"key":"e_1_2_1_15_1","volume-title":"Centrality in social networks conceptual clarification. Social networks 1, 3","author":"Freeman Linton C","year":"1978","unstructured":"Linton C Freeman . 1978. Centrality in social networks conceptual clarification. Social networks 1, 3 ( 1978 ), 215--239. Linton C Freeman. 1978. Centrality in social networks conceptual clarification. Social networks 1, 3 (1978), 215--239."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835868"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2425831"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875258"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999325.2999396"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2009.93"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1566770.1566773"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623683"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458115"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054779"},{"key":"e_1_2_1_31_1","volume-title":"National Long-Term Care Survey","author":"Manton Kenneth G","year":"1982","unstructured":"Kenneth G Manton . 2010. National Long-Term Care Survey : 1982 , 1984, 1989, 1994, 1999, and 2004. Inter-university Consortium for Political and Social Research ( 2010). Kenneth G Manton. 2010. National Long-Term Care Survey: 1982, 1984, 1989, 1994, 1999, and 2004. Inter-university Consortium for Political and Social Research (2010)."},{"key":"e_1_2_1_32_1","volume-title":"Egocentric and sociocentric measures of network centrality. Social networks 24, 4","author":"Marsden Peter V","year":"2002","unstructured":"Peter V Marsden . 2002. Egocentric and sociocentric measures of network centrality. Social networks 24, 4 ( 2002 ), 407--422. Peter V Marsden. 2002. Egocentric and sociocentric measures of network centrality. Social networks 24, 4 (2002), 407--422."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICACCI.2014.6968348"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022643204877"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.76"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/152181"},{"key":"e_1_2_1_40_1","unstructured":"Integrated Public Use Microdata Series. 2015. Version 6.0. Minneapolis: University of (2015).  Integrated Public Use Microdata Series. 2015. Version 6.0. Minneapolis: University of (2015)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3436905.3436912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:24:24Z","timestamp":1672223064000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3436905.3436912"}},"subtitle":["differential privacy for non-numeric queries via local sensitivity"],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.14778\/3436905.3436912"],"URL":"https:\/\/doi.org\/10.14778\/3436905.3436912","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}