{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:35:13Z","timestamp":1780054513557,"version":"3.54.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>\n            Counting the fraction of a population having an input within a specified interval i.e. a\n            <jats:italic>range query,<\/jats:italic>\n            is a fundamental data analysis primitive. Range queries can also be used to compute other core statistics such as\n            <jats:italic>quantiles,<\/jats:italic>\n            and to build prediction models. However, frequently the data is subject to privacy concerns when it is drawn from individuals, and relates for example to their financial, health, religious or political status. In this paper, we introduce and analyze methods to support range queries under the local variant of differential privacy [23], an emerging standard for privacy-preserving data analysis.\n          <\/jats:p>\n          <jats:p>The local model requires that each user releases a noisy view of her private data under a privacy guarantee. While many works address the problem of range queries in the trusted aggregator setting, this problem has not been addressed specifically under untrusted aggregation (local DP) model even though many primitives have been developed recently for estimating a discrete distribution. We describe and analyze two classes of approaches for range queries, based on hierarchical histograms and the Haar wavelet transform. We show that both have strong theoretical accuracy guarantees on variance. In practice, both methods are fast and require minimal computation and communication resources. Our experiments show that the wavelet approach is most accurate in high privacy settings, while the hierarchical approach dominates for weaker privacy requirements.<\/jats:p>","DOI":"10.14778\/3339490.3339496","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1126-1138","source":"Crossref","is-referenced-by-count":78,"title":["Answering range queries under local differential privacy"],"prefix":"10.14778","volume":"12","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"University Of Warwick"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tejas","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"University Of Warwick"}],"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":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"trip record data","author":"NYC","year":"2017","unstructured":"NYC taxi and limousine commission , trip record data , 2017 . NYC taxi and limousine commission, trip record data, 2017."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/en.wikipedia.org\/wiki\/Geohash.  https:\/\/en.wikipedia.org\/wiki\/Geohash."},{"key":"e_1_2_1_3_1","first-page":"2285","volume-title":"NIPS","author":"Bassily R.","year":"2017","unstructured":"R. Bassily , K. Nissim , U. Stemmer , and A. G. Thakurta . Practical locally private heavy hitters . In NIPS , pages 2285 -- 2293 , 2017 . R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta. Practical locally private heavy hitters. In NIPS, pages 2285--2293, 2017."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_2_1_5_1","volume-title":"IEEE Security and Privacy Symposium","author":"Chang J. C.-N.","year":"2018","unstructured":"J. C.-N. Chang and A. G. Thakurta . Autocompletion with local differential privacy . In IEEE Security and Privacy Symposium , 2018 . J. C.-N. Chang and A. G. Thakurta. Autocompletion with local differential privacy. In IEEE Security and Privacy Symposium, 2018."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_10_1","volume-title":"Apple Machine Learning Journal","author":"Team Differential Privacy","year":"2017","unstructured":"Differential Privacy Team , Apple. Learning with privacy at scale . Apple Machine Learning Journal , 2017 . Differential Privacy Team, Apple. Learning with privacy at scale. Apple Machine Learning Journal, 2017."},{"key":"e_1_2_1_11_1","volume-title":"Advances in Neural Information Processing Systems","author":"Ding B.","year":"2017","unstructured":"B. Ding , J. Kulkarni , and S. Yekhanin . Collecting telemetry data privately . In Advances in Neural Information Processing Systems 30, December 2017 . B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems 30, December 2017."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"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":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2016-0015"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2018.2877045"},{"key":"e_1_2_1_18_1","first-page":"2348","volume-title":"Advances in Neural Information Processing Systems","author":"Hardt M.","year":"2012","unstructured":"M. Hardt , K. Ligett , and F. McSherry . A simple and practical algorithm for differentially private data release . In Advances in Neural Information Processing Systems , pages 2348 -- 2356 , 2012 . M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, pages 2348--2356, 2012."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2827872"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015366"},{"key":"e_1_2_1_22_1","first-page":"2436","volume-title":"Proceedings of ICML","author":"Kairouz P.","year":"2016","unstructured":"P. Kairouz , K. Bonawitz , and D. Ramage . Discrete distribution estimation under local privacy . In Proceedings of ICML , pages 2436 -- 2444 , 2016 . P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In Proceedings of ICML, pages 2436--2444, 2016."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_2_1_24_1","volume-title":"Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053","author":"Nguy\u00ean T. T.","year":"2016","unstructured":"T. T. Nguy\u00ean , X. Xiao , Y. Yang , S. C. Hui , H. Shin , and J. Shin . Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053 , 2016 . T. T. Nguy\u00ean, X. Xiao, Y. Yang, S. C. Hui, H. Shin, and J. Shin. Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs\/1606.05053, 2016."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_1_26_1","volume-title":"4th Workshop on the Theory and Practice of Differential Privacy at CCS","author":"Pihur V.","year":"2018","unstructured":"V. Pihur , A. Korolova , F. Liu , S. Sankuratripati , M. Yung , D. Huang , and R. Zeng . Differentially-private \"draw and discard\" machine learning . In 4th Workshop on the Theory and Practice of Differential Privacy at CCS , July 2018 . V. Pihur, A. Korolova, F. Liu, S. Sankuratripati, M. Yung, D. Huang, and R. Zeng. Differentially-private \"draw and discard\" machine learning. In 4th Workshop on the Theory and Practice of Differential Privacy at CCS, July 2018."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544872"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_2_1_30_1","unstructured":"H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann 2005.   H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann 2005."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2805356"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00063"},{"key":"e_1_2_1_33_1","first-page":"729","volume-title":"Proceedings of the USENIX Security Symposium","author":"Wang T.","year":"2017","unstructured":"T. Wang , J. Blocki , N. Li , and S. Jha . Locally differentially private protocols for frequency estimation . In Proceedings of the USENIX Security Symposium , pages 729 -- 745 , 2017 . T. Wang, J. Blocki, N. Li, and S. Jha. Locally differentially private protocols for frequency estimation. In Proceedings of the USENIX Security Symposium, pages 729--745, 2017."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243742"},{"key":"e_1_2_1_37_1","first-page":"4130","volume-title":"Proceedings of ICML","author":"Zheng K.","year":"2017","unstructured":"K. Zheng , W. Mou , and L. Wang . Collect at once, use effectively: Making non-interactive locally private learning possible . In Proceedings of ICML , pages 4130 -- 4139 , 2017 . K. Zheng, W. Mou, and L. Wang. Collect at once, use effectively: Making non-interactive locally private learning possible. In Proceedings of ICML, pages 4130--4139, 2017."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:24:44Z","timestamp":1672223084000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339496"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339496","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}