{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:22:26Z","timestamp":1783437746330,"version":"3.54.6"},"reference-count":18,"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>Bloom filters are a great technique to test whether a key is not in a set of keys. This paper presents a novel data structure called ARF. In a nutshell, ARFs are for range queries what Bloom filters are for point queries. That is, an ARF can determine whether a set of keys does not contain any keys that are part of a specific range. This paper describes the principles and methods for efficient implementation of ARFs and presents the results of comprehensive experiments that assess the precision, space, and latency of ARFs. Furthermore, this paper shows how ARFs can be applied to a commercial database system that partitions data into hot and cold regions to optimize queries that involve only hot data.<\/jats:p>","DOI":"10.14778\/2556549.2556556","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1714-1725","source":"Crossref","is-referenced-by-count":57,"title":["Adaptive range filters for cold data"],"prefix":"10.14778","volume":"6","author":[{"given":"Karolina","family":"Alexiou","sequence":"first","affiliation":[{"name":"Systems Group, ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Donald","family":"Kossmann","sequence":"additional","affiliation":[{"name":"Systems Group, ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Per-\u00c5ke","family":"Larson","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond"}],"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\/321623.321632"},{"key":"e_1_2_1_2_1","volume-title":"Adaptive range filters for query optimization. Master Thesis 84","author":"Alexiou A.-K.","year":"2013","unstructured":"A.-K. Alexiou. Adaptive range filters for query optimization. Master Thesis 84, Systems Group, ETH Zurich, 2013."},{"key":"e_1_2_1_3_1","unstructured":"B. Baig H. Chan S. McCauley and A. Wong. Range queries using Bloom filters. http:\/\/www.scribd.com\/doc\/92463819\/Ranged-Queries-Using-Bloom-Filters-Final."},{"issue":"4","key":"e_1_2_1_4_1","first-page":"3","article-title":"The new jersey data reduction report","volume":"20","author":"Barbar\u00e1 D.","year":"1997","unstructured":"D. Barbar\u00e1, W. DuMouchel, C. Faloutsos, P. J. Haas, J. M. Hellerstein, Y. E. Ioannidis, H. V. Jagadish, T. Johnson, R. T. Ng, V. Poosala, K. A. Ross, and K. C. Sevcik. The new jersey data reduction report. IEEE Data Eng. Bull., 20(4):3-45, 1997.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"F. Bonomi M. Mitzenmacher R. Panigrahy S. Singh and G. Varghese. An improved construction for counting Bloom filters. In Y. Azar and T. Erlebach editors ESA volume 4168 of Lecture Notes in Computer Science pages 684-695. Springer 2006.","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261978"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191874"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673462"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066183"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375677"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/285237.285287"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/381992.383642"},{"key":"e_1_2_1_16_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth D. E.","year":"1973","unstructured":"D. E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544811"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400798"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556556","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:35:49Z","timestamp":1729722949000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556556"}},"subtitle":["avoiding trips to Siberia"],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":18,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556556"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556556","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}