{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:38Z","timestamp":1750220918446,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2019,11,5]]},"abstract":"<jats:p>The adoption of differential privacy is growing but the complexity of designing private, efficient and accurate algorithms is still high. We propose a novel programming framework and system, \u2208ktelo, for implementing both existing and new privacy algorithms. For the task of answering linear counting queries, we show that nearly all existing algorithms can be composed from operators, each conforming to one of a small number of operator classes. While past programming frameworks have helped to ensure the privacy of programs, the novelty of our framework is its significant support for authoring accurate and efficient (as well as private) programs.<\/jats:p>\n          <jats:p>We describe the design and architecture of the \u2208ktelo system and show that \u2208ktelo is expressive enough to describe many algorithms from the privacy literature. \u2208ktelo allows for safer implementations through code reuse and allows both privacy novices and experts to more easily design new algorithms. We demonstrate the use of \u2208ktelo by designing new algorithms offering state-of-the-art accuracy and runtime.<\/jats:p>","DOI":"10.1145\/3371316.3371321","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T18:56:07Z","timestamp":1572980167000},"page":"15-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["#8712;"],"prefix":"10.1145","volume":"48","author":[{"given":"Dan","family":"Zhang","sequence":"first","affiliation":[{"name":"U. of Massachusetts Amherst, Amherst, MA, USA"}]},{"given":"Ryan","family":"McKenna","sequence":"additional","affiliation":[{"name":"U. of Massachusetts Amherst, Amherst, MA, USA"}]},{"given":"Ios","family":"Kotsogiannis","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}]},{"given":"George","family":"Bissias","sequence":"additional","affiliation":[{"name":"U. of Massachusetts Amherst, Amherst, MA, USA"}]},{"given":"Michael","family":"Hay","sequence":"additional","affiliation":[{"name":"Colgate University, Hamilton, NY, USA"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}]},{"given":"Gerome","family":"Miklau","sequence":"additional","affiliation":[{"name":"U. of Massachusetts Amherst, Amherst, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/onthemap.ces.census.gov\/ 2010.  https:\/\/onthemap.ces.census.gov\/ 2010."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/github.com\/dpcomp-org\/dpcomp_core 2016.  https:\/\/github.com\/dpcomp-org\/dpcomp_core 2016."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.80"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158146"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978371"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"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":"Foundations and Trends in Theoretical Computer Science","author":"Dwork C.","year":"2014","unstructured":"C. Dwork and A. Roth . The Algorithmic Foundations of Differential Privacy . Foundations and Trends in Theoretical Computer Science , 2014 . C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 2014."},{"key":"e_1_2_1_10_1","volume-title":"Featherweight pinq. JPC, 7(2)","author":"Ebadi H.","year":"2017","unstructured":"H. Ebadi and D. Sands . Featherweight pinq. JPC, 7(2) , 2017 . H. Ebadi and D. Sands. Featherweight pinq. JPC, 7(2), 2017."},{"key":"e_1_2_1_11_1","volume-title":"CCS","author":"Pihur V.","year":"2014","unstructured":"\u00da. Erlingsson, V. Pihur , and A. Korolova . Rappor: Randomized aggregatable privacy-preserving ordinal response . In CCS , 2014 . \u00da. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In CCS, 2014."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/10079687X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429113"},{"key":"e_1_2_1_14_1","volume-title":"USENIX Conference on Security","author":"Haeberlen A.","year":"2011","unstructured":"A. Haeberlen , B. C. Pierce , and A. Narayan . Differential privacy under fire . In USENIX Conference on Security , 2011 . A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In USENIX Conference on Security, 2011."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035940"},{"key":"e_1_2_1_16_1","volume-title":"NIPS","author":"Hardt M.","year":"2012","unstructured":"M. Hardt , K. Ligett , and F. McSherry . A simple and practical algorithm for differentially private data release . In NIPS , 2012 . M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. In NIPS, 2012."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882931"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_19_1","volume-title":"Differentially private histograms for range-sum queries: A modular approach. arXiv","author":"Kellaris G.","year":"2015","unstructured":"G. Kellaris , S. Papadopoulos , and D. Papadias . Differentially private histograms for range-sum queries: A modular approach. arXiv , 2015 . G. Kellaris, S. Papadopoulos, and D. Papadias. Differentially private histograms for range-sum queries: A modular approach. arXiv, 2015."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035945"},{"key":"e_1_2_1_21_1","volume-title":"Conf. on Innovative Data Systems Research (CIDR)","author":"Kotsogiannis I.","year":"2019","unstructured":"I. Kotsogiannis , Y. Tao , A. Machanavajjhala , G. Miklau , and M. Hay . Architecting a differentially private SQL engine . In Conf. on Innovative Data Systems Research (CIDR) , 2019 . I. Kotsogiannis, Y. Tao, A. Machanavajjhala, G. Miklau, and M. Hay. Architecting a differentially private SQL engine. In Conf. on Innovative Data Systems Research (CIDR), 2019."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783366"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732271"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_26_1","volume-title":"Private selection from private candidates. CoRR, abs\/1811.07971","author":"Liu J.","year":"2018","unstructured":"J. Liu and K. Talwar . Private selection from private candidates. CoRR, abs\/1811.07971 , 2018 . J. Liu and K. Talwar. Private selection from private candidates. CoRR, abs\/1811.07971, 2018."},{"key":"e_1_2_1_27_1","volume-title":"Optimizing error of high-dimensional statistical queries under differential privacy. PVLDB, 11(10)","author":"McKenna R.","year":"2018","unstructured":"R. McKenna , G. Miklau , M. Hay , and A. Machanavajjhala . Optimizing error of high-dimensional statistical queries under differential privacy. PVLDB, 11(10) , 2018 . R. McKenna, G. Miklau, M. Hay, and A. Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. PVLDB, 11(10), 2018."},{"key":"e_1_2_1_28_1","volume-title":"ICML","author":"McKenna R.","year":"2019","unstructured":"R. McKenna , D. Sheldon , and G. Miklau . Graphical-model based estimation and inference for differential privacy . In ICML , 2019 . R. McKenna, D. Sheldon, and G. Miklau. Graphical-model based estimation and inference for differential privacy. In ICML, 2019."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382264"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342549.2342553"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544872"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_35_1","volume-title":"NSDI","author":"Roy I.","year":"2010","unstructured":"I. Roy , S. T. V. Setty , A. Kilzer , V. Shmatikov , and E. Witchel . Airavat: Security and privacy for mapreduce . In NSDI , 2010 . I. Roy, S. T. V. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for mapreduce. In NSDI, 2010."},{"key":"e_1_2_1_36_1","first-page":"2451","volume-title":"NIPS","author":"Williams O.","year":"2010","unstructured":"O. Williams and F. McSherry . Probabilistic Inference and Differential Privacy . NIPS , pages 2451 -- 2459 , 2010 . O. Williams and F. McSherry. Probabilistic Inference and Differential Privacy. NIPS, pages 2451--2459, 2010."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447831"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009884"},{"key":"e_1_2_1_39_1","unstructured":"D. Zhang R. McKenna I. Kotsogiannis G. Bissias M. Hay A. Machanavajjhala and G. Miklau. Ektelo: A framework for defining differentially-private computations. https:\/\/arxiv.org\/abs\/1808.03555v3.  D. Zhang R. McKenna I. Kotsogiannis G. Bissias M. Hay A. Machanavajjhala and G. Miklau. Ektelo: A framework for defining differentially-private computations. https:\/\/arxiv.org\/abs\/1808.03555v3."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196921"},{"key":"e_1_2_1_41_1","first-page":"42","article-title":"PrivBayes: Private data release via Bayesian networks","author":"Zhang J.","year":"2017","unstructured":"J. Zhang , G. Cormode , C. M. Procopiuc , D. Srivastava , and X. Xiao . PrivBayes: Private data release via Bayesian networks . TODS , 42 , 2017 . J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao. PrivBayes: Private data release via Bayesian networks. TODS, 42, 2017.","journal-title":"TODS"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882928"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.68"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371316.3371321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:05Z","timestamp":1750204385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371321"}},"subtitle":["A Framework for Defining Differentially-Private Computations"],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,11,5]]}},"alternative-id":["10.1145\/3371316.3371321"],"URL":"https:\/\/doi.org\/10.1145\/3371316.3371321","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"2019-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}