{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:07:04Z","timestamp":1770289624302,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T00:00:00Z","timestamp":1581120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1253327, 1408982, 1409125, 1443014, 1421325, and 1409143"],"award-info":[{"award-number":["1253327, 1408982, 1409125, 1443014, 1421325, and 1409143"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["N66001-15-C-4067"],"award-info":[{"award-number":["N66001-15-C-4067"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>\n            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, \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            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.\n          <\/jats:p>\n          <jats:p>\n            After describing the design and architecture of the \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            system, we show that \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            is expressive, allows for safer implementations through code reuse, and allows both privacy novices and experts to easily design algorithms. We provide a number of novel implementation techniques to support the generality and scalability of \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            operators. These include methods to automatically compute lossless reductions of the data representation, implicit matrices that avoid materialized state but still support computations, and iterative inference implementations that generalize techniques from the privacy literature.\n          <\/jats:p>\n          <jats:p>\n            We demonstrate the utility of \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            by designing several new state-of-the-art algorithms, most of which result from simple re-combinations of operators defined in the framework. We study the accuracy and scalability of \u03f5\n            <jats:sc>KTELO<\/jats:sc>\n            plans in a thorough empirical evaluation.\n          <\/jats:p>","DOI":"10.1145\/3362032","type":"journal-article","created":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T09:03:56Z","timestamp":1581152636000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["\u03f5\n            <scp>KTELO<\/scp>"],"prefix":"10.1145","volume":"45","author":[{"given":"Dan","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}]},{"given":"Ryan","family":"McKenna","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}]},{"given":"Ios","family":"Kotsogiannis","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"George","family":"Bissias","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}]},{"given":"Michael","family":"Hay","sequence":"additional","affiliation":[{"name":"Colgate University, Hamilton, NY"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Gerome","family":"Miklau","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}]}],"member":"320","published-online":{"date-parts":[[2020,2,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2010. Apache Hive. Retrieved from https:\/\/hive.apache.org.  2010. Apache Hive. Retrieved from https:\/\/hive.apache.org."},{"key":"e_1_2_1_2_1","unstructured":"2010. OnTheMap. Retrieved from https:\/\/onthemap.ces.census.gov\/.  2010. OnTheMap. Retrieved from https:\/\/onthemap.ces.census.gov\/."},{"key":"e_1_2_1_3_1","unstructured":"2012. Apache Accumulo. Retrieved from https:\/\/accumulo.apache.org.  2012. Apache Accumulo. Retrieved from https:\/\/accumulo.apache.org."},{"key":"e_1_2_1_4_1","unstructured":"2014. Apache Spark. Retrieved from https:\/\/spark.apache.org.  2014. Apache Spark. Retrieved from https:\/\/spark.apache.org."},{"key":"e_1_2_1_5_1","unstructured":"2018. 2018 Differential Privacy Synthetic Data Challenge. Retrieved from https:\/\/www.nist.gov\/communications-technology-laboratory\/pscr\/funding-opportunities\/open-innovation-prize-challenges-1.  2018. 2018 Differential Privacy Synthetic Data Challenge. Retrieved from https:\/\/www.nist.gov\/communications-technology-laboratory\/pscr\/funding-opportunities\/open-innovation-prize-challenges-1."},{"key":"e_1_2_1_6_1","unstructured":"2018. Ektelo source code. Retrieved from https:\/\/github.com\/ektelo\/ektelo.  2018. Ektelo source code. Retrieved from https:\/\/github.com\/ektelo\/ektelo."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.80"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978371"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916069"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020598"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science.  Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science.","DOI":"10.1561\/9781601988195"},{"key":"e_1_2_1_15_1","first-page":"159","article-title":"Featherweight PINQ","volume":"7","author":"Ebadi Hamid","year":"2016","unstructured":"Hamid Ebadi and David Sands . 2016 . Featherweight PINQ . Journal of Privacy and Confidentiality 7 , 2 (2016), 159 \u2013 164 . Hamid Ebadi and David Sands. 2016. Featherweight PINQ. Journal of Privacy and Confidentiality 7, 2 (2016), 159\u2013164.","journal-title":"Journal of Privacy and Confidentiality"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)","author":"Elgamal Tarek","year":"2017","unstructured":"Tarek Elgamal , Shangyu Luo , Matthias Boehm , Alexandre V. Evfimievski , Shirish Tatikonda , Berthold Reinwald , and Prithviraj Sen . 2017 . SPOOF: Sum-product optimization and operator fusion for large-scale machine learning . In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917) . Tarek Elgamal, Shangyu Luo, Matthias Boehm, Alexandre V. Evfimievski, Shirish Tatikonda, Berthold Reinwald, and Prithviraj Sen. 2017. SPOOF: Sum-product optimization and operator fusion for large-scale machine learning. In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_18_1","first-page":"5","article-title":"LSMR: An iterative algorithm for sparse least-squares problems","volume":"33","author":"Chin-Lung Fong David","year":"2011","unstructured":"David Chin-Lung Fong and Michael Saunders . 2011 . LSMR: An iterative algorithm for sparse least-squares problems . SIAM J. Sci. Comput. 33 , 5 (Oct. 2011), 2950--2971. David Chin-Lung Fong and Michael Saunders. 2011. LSMR: An iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33, 5 (Oct. 2011), 2950--2971.","journal-title":"SIAM J. Sci. Comput."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL\u201913)","author":"Gaboardi Marco","unstructured":"Marco Gaboardi , Andreas Haeberlen , Justin Hsu , Arjun Narayan , and Benjamin C. Pierce . 2013. Linear dependent types for differential privacy . In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL\u201913) . 357--370. Marco Gaboardi, Andreas Haeberlen, Justin Hsu, Arjun Narayan, and Benjamin C. Pierce. 2013. Linear dependent types for differential privacy. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL\u201913). 357--370."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035940"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201912)","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt , Katrina Ligett , and Frank McSherry . 2012 . A simple and practical algorithm for differentially private data release . In Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201912) . Moritz Hardt, Katrina Ligett, and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. In Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201912)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882931"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070607.3070608"},{"key":"e_1_2_1_25_1","volume-title":"Differentially private histograms for range-sum queries: A modular approach. arXiv","author":"Kellaris Georgios","year":"2015","unstructured":"Georgios Kellaris , Stavros Papadopoulos , and Dimitris Papadias . 2015. Differentially private histograms for range-sum queries: A modular approach. arXiv ( 2015 ). Georgios Kellaris, Stavros Papadopoulos, and Dimitris Papadias. 2015. Differentially private histograms for range-sum queries: A modular approach. arXiv (2015)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035945"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201919)","author":"Kotsogiannis Ios","year":"2019","unstructured":"Ios Kotsogiannis , Yuchao Tao , Ashwin Machanavajjhala , Gerome Miklau , and Michael Hay . 2019 . Architecting a differentially private SQL engine . In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201919) . Ios Kotsogiannis, Yuchao Tao, Ashwin Machanavajjhala, Gerome Miklau, and Michael Hay. 2019. Architecting a differentially private SQL engine. In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201919)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783366"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732271"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231769"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201919)","author":"McKenna Ryan","year":"2019","unstructured":"Ryan McKenna , Daniel Sheldon , and Gerome Miklau . 2019 . Graphical-model based estimation and inference for differential privacy . In Proceedings of the International Conference on Machine Learning (ICML\u201919) . Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019. Graphical-model based estimation and inference for differential privacy. In Proceedings of the International Conference on Machine Learning (ICML\u201919)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382264"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115419"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)","author":"Palkar Shoumik","year":"2017","unstructured":"Shoumik Palkar , James J. Thomas , Anil Shanbhag , Deepak Narayanan , Holger Pirk , Malte Schwarzkopf , Saman Amarasinghe , and Matei Zaharia . 2017 . Weld: A common runtime for high performance data analytics . In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917) . Shoumik Palkar, James J. Thomas, Anil Shanbhag, Deepak Narayanan, Holger Pirk, Malte Schwarzkopf, Saman Amarasinghe, and Matei Zaharia. 2017. Weld: A common runtime for high performance data analytics. In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064013"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100030929"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342549.2342553"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544872"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588575"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201910)","author":"Roy Indrajit","year":"2010","unstructured":"Indrajit Roy , Srinath T. V. Setty , Ann Kilzer , Vitaly Shmatikov , and Emmett Witchel . 2010 . Airavat: Security and privacy for MapReduce . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201910) . Indrajit Roy, Srinath T. V. Setty, Ann Kilzer, Vitaly Shmatikov, and Emmett Witchel. 2010. Airavat: Security and privacy for MapReduce. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201910)."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Neural Information Processing Systems (NeurIPS\u201916)","author":"Schelter Sebastian","year":"2016","unstructured":"Sebastian Schelter , Andrew Palumbo , Shannon Quinn , Suneel Marthi , and Andrew Musselman . 2016 . Samsara: Declarative machine learning on distributed dataflow systems . In Proceedings of the Neural Information Processing Systems (NeurIPS\u201916) . Sebastian Schelter, Andrew Palumbo, Shannon Quinn, Suneel Marthi, and Andrew Musselman. 2016. Samsara: Declarative machine learning on distributed dataflow systems. In Proceedings of the Neural Information Processing Systems (NeurIPS\u201916)."},{"key":"e_1_2_1_48_1","volume-title":"Morrison","author":"Sherman Jack","year":"1950","unstructured":"Jack Sherman and Winifred J . Morrison . 1950 . Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Stat . 21, 1 (3 1950), 124--127. DOI:https:\/\/doi.org\/10.1214\/aoms\/1177729893 10.1214\/aoms Jack Sherman and Winifred J. Morrison. 1950. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Stat. 21, 1 (3 1950), 124--127. DOI:https:\/\/doi.org\/10.1214\/aoms\/1177729893"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 2013 IEEE\/WIC\/ACM International Joint Conferences on Web Intelligence (WI\u201913) and Intelligent Agent Technologies (IAT\u201913)","volume":"1","author":"Vaidya J.","year":"2013","unstructured":"J. Vaidya , B. Shafiq , A. Basu , and Y. Hong . 2013. Differentially private naive bayes classification . In Proceedings of the 2013 IEEE\/WIC\/ACM International Joint Conferences on Web Intelligence (WI\u201913) and Intelligent Agent Technologies (IAT\u201913) , Vol. 1 . 571--576. DOI:https:\/\/doi.org\/10.1109\/WI-IAT. 2013 .80 10.1109\/WI-IAT.2013.80 J. Vaidya, B. Shafiq, A. Basu, and Y. Hong. 2013. Differentially private naive bayes classification. In Proceedings of the 2013 IEEE\/WIC\/ACM International Joint Conferences on Web Intelligence (WI\u201913) and Intelligent Agent Technologies (IAT\u201913), Vol. 1. 571--576. DOI:https:\/\/doi.org\/10.1109\/WI-IAT.2013.80"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201910)","author":"Williams Oliver","year":"2010","unstructured":"Oliver Williams and Frank McSherry . 2010 . Probabilistic inference and differential privacy . Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201910) . 2451--2459. Oliver Williams and Frank McSherry. 2010. Probabilistic inference and differential privacy. Proceedings of the Conference on Neural Information Processing Systems (NIPS\u201910). 2451--2459."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447831"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2007.12.020"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009884"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196921"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882928"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.68"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3362032","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3362032","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3362032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:53Z","timestamp":1750203893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3362032"}},"subtitle":["A Framework for Defining Differentially Private Computations"],"short-title":[],"issued":{"date-parts":[[2020,2,8]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3362032"],"URL":"https:\/\/doi.org\/10.1145\/3362032","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,8]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}