{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:20:12Z","timestamp":1784830812185,"version":"3.55.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>In recent years, many approaches to differentially privately publish histograms have been proposed. Several approaches rely on constructing tree structures in order to decrease the error when answer large range queries. In this paper, we examine the factors affecting the accuracy of hierarchical approaches by studying the mean squared error (MSE) when answering range queries. We start with one-dimensional histograms, and analyze how the MSE changes with different branching factors, after employing constrained inference, and with different methods to allocate the privacy budget among hierarchy levels. Our analysis and experimental results show that combining the choice of a good branching factor with constrained inference outperform the current state of the art. Finally, we extend our analysis to multi-dimensional histograms. We show that the benefits from employing hierarchical methods beyond a single dimension are significantly diminished, and when there are 3 or more dimensions, it is almost always better to use the Flat method instead of a hierarchy.<\/jats:p>","DOI":"10.14778\/2556549.2556576","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1954-1965","source":"Crossref","is-referenced-by-count":121,"title":["Understanding hierarchical methods for differentially private histograms"],"prefix":"10.14778","volume":"6","author":[{"given":"Wahbeh","family":"Qardaji","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weining","family":"Yang","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ninghui","family":"Li","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043621.2043626"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989347"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_32"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835868"},{"key":"e_1_2_1_12_1","volume-title":"Overview of the 2003 kdd cup","author":"Gehrke J.","year":"2003","unstructured":"J. Gehrke, P. Ginsparg, and J. M. Kleinberg. Overview of the 2003 kdd cup, 2003."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020487"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2414456.2414477"},{"key":"e_1_2_1_19_1","volume-title":"Differentially private grids for geospatial data","author":"Qardaji W.","year":"2012","unstructured":"W. Qardaji, W. Yang, and N. Li. Differentially private grids for geospatial data, 2012. arXiv:1209.1322 [cs.CR] To appear in ICDE 2013."},{"key":"e_1_2_1_20_1","volume-title":"Integrated public use microdata series: Version 5.0 [machine-readable database]","author":"Ruggles S.","year":"2010","unstructured":"S. Ruggles, J. T. Alexander, K. Genadek, R. Goeken, M. B. Schroeder, and M. Sobek. Integrated public use microdata series: Version 5.0 [machine-readable database], 2010."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1889159.1889173"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.48"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350252"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556576","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:35:20Z","timestamp":1729722920000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556576"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":24,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556576"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556576","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}