{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T03:43:59Z","timestamp":1770522239228,"version":"3.49.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>\n            We propose DigitHist, a histogram summary for selectivity estimation on multi-dimensional data with tight error bounds. By combining multi-dimensional and one-dimensional histograms along regular grids of different resolutions, DigitHist provides an accurate and reliable histogram approach for multi-dimensional data. To achieve a compact summary, we use a sparse representation combined with a novel histogram compression technique that chooses a higher resolution in dense regions and a lower resolution elsewhere. For the construction of DigitHist, we propose a new error measure, termed\n            <jats:italic>u<\/jats:italic>\n            -error, which minimizes the width between the guaranteed upper and lower bounds of the selectivity estimate. The construction algorithm performs a single data scan and has linear time complexity. An in-depth experimental evaluation shows that DigitHist delivers superior precision and error bounds than state-of-the-art competitors at a comparable query time.\n          <\/jats:p>","DOI":"10.14778\/3137628.3137658","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1514-1525","source":"Crossref","is-referenced-by-count":16,"title":["DigitHist"],"prefix":"10.14778","volume":"10","author":[{"given":"Michael","family":"Shekelyan","sequence":"first","affiliation":[{"name":"Free University of Bozen-Bolzano, Italy"}]},{"given":"Anton","family":"Dign\u00f6s","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Italy"}]},{"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Italy"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304184"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375686"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0090-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1526987.1526989"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749438"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/169725.169708"},{"key":"e_1_2_1_11_1","first-page":"24","volume-title":"VLDB","volume":"98","author":"Jagadish H. V.","year":"1998","unstructured":"H. V. Jagadish , N. Koudas , S. Muthukrishnan , V. Poosala , K. C. Sevcik , and T. Suel . Optimal histograms with quality guarantees . In VLDB , volume 98 , pages 24 -- 27 , 1998 . H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, volume 98, pages 24--27, 1998."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304200"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276344"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/971701.50205"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_37"},{"key":"e_1_2_1_16_1","first-page":"486","volume-title":"VLDB","author":"Poosala V.","year":"1997","unstructured":"V. Poosala and Y. E. Ioannidis . Selectivity estimation without the attribute value independence assumption . In VLDB , pages 486 -- 495 , 1997 . V. Poosala and Y. E. Ioannidis. Selectivity estimation without the attribute value independence assumption. In VLDB, pages 486--495, 1997."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233342"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116646.3116839"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304199"},{"key":"e_1_2_1_20_1","first-page":"252","volume-title":"SODA","author":"Wei Z.","year":"2013","unstructured":"Z. Wei and K. Yi . The space complexity of 2-dimensional approximate range counting . In SODA , pages 252 -- 264 . SIAM , 2013 . Z. Wei and K. Yi. The space complexity of 2-dimensional approximate range counting. In SODA, pages 252--264. SIAM, 2013."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375724"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:58:12Z","timestamp":1672221492000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137658"}},"subtitle":["a histogram-based data summary with tight error bounds"],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137658"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137658","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}