{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T23:07:35Z","timestamp":1774307255704,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>\n            All data is not equally popular. Often, some portion of data is more frequently accessed than the rest, which causes a skew in popularity of the data items. Adapting to this skew can improve performance, and this topic has been studied extensively in the past for disk-based settings. In this work, we consider an in-memory data structure, namely\n            <jats:italic>hash table<\/jats:italic>\n            , and show how one can leverage the skew in popularity for higher performance.\n          <\/jats:p>\n          <jats:p>\n            Hashing is a low-latency operation, sensitive to the effects of caching and code complexity, among other factors. These factors make learning in-the-loop challenging as the overhead of performing additional operations can have significant impact on performance. In this paper, we propose VIP hashing, a hash table method that uses lightweight mechanisms for\n            <jats:italic>learning<\/jats:italic>\n            the skew in popularity and\n            <jats:italic>adapting<\/jats:italic>\n            the hash table layout on the fly. These mechanisms are non-blocking, i.e, the hash table is operational at all times. The overhead is controlled by\n            <jats:italic>sensing<\/jats:italic>\n            changes in the popularity distribution to\n            <jats:italic>dynamically switch-on\/off<\/jats:italic>\n            the mechanisms as needed.\n          <\/jats:p>\n          <jats:p>\n            We ran extensive tests against a host of workloads generated by\n            <jats:italic>Wiscer<\/jats:italic>\n            , a homegrown benchmarking tool, and we find that VIP hashing improves performance in the presence of skew (22% increase in fetch operation throughput for a hash table with 1M keys under low skew) while adapting to insert and delete operations, and changing popularity distribution of keys on the fly. Our experiments on DuckDB show that VIP hashing reduces the end-to-end execution time of TPC-H query 9 by 20% under low skew.\n          <\/jats:p>","DOI":"10.14778\/3547305.3547306","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"1978-1990","source":"Crossref","is-referenced-by-count":6,"title":["VIP hashing"],"prefix":"10.14778","volume":"15","author":[{"given":"Aarati","family":"Kakaraparthy","sequence":"first","affiliation":[{"name":"University of Wisconsin"}]},{"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"University of Wisconsin"}]},{"given":"Brian P.","family":"Kroth","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab"}]},{"given":"Kwanghyun","family":"Park","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"MariaDB. Retrieved","year":"2013","unstructured":"MariaDB 2013 . MariaDB Storage Index Types . MariaDB. Retrieved June 23, 2022 from https:\/\/mariadb.com\/kb\/en\/storage-engine-index-types\/ MariaDB 2013. MariaDB Storage Index Types. MariaDB. Retrieved June 23, 2022 from https:\/\/mariadb.com\/kb\/en\/storage-engine-index-types\/"},{"key":"e_1_2_1_2_1","volume-title":"Intel Xeon Silver 4114 processor","author":"Intel Corporation 2017.","year":"2022","unstructured":"Intel Corporation 2017. Intel Xeon Silver 4114 processor . Intel Corporation . Retrieved June 23, 2022 from https:\/\/intel.ly\/3fDidSb Intel Corporation 2017. Intel Xeon Silver 4114 processor. Intel Corporation. Retrieved June 23, 2022 from https:\/\/intel.ly\/3fDidSb"},{"key":"e_1_2_1_3_1","volume-title":"Intel TBB hash map","author":"Intel Corporation 2020.","year":"2022","unstructured":"Intel Corporation 2020. Intel TBB hash map . Intel Corporation . Retrieved June 23, 2022 from https:\/\/oneapi-src.github.io\/oneTBB\/main\/tbb_userguide\/concurrent_hash_map.html Intel Corporation 2020. Intel TBB hash map. Intel Corporation. Retrieved June 23, 2022 from https:\/\/oneapi-src.github.io\/oneTBB\/main\/tbb_userguide\/concurrent_hash_map.html"},{"key":"e_1_2_1_4_1","volume-title":"Data types in Redis","author":"Ltd Redis","year":"2022","unstructured":"Redis Ltd . 2022. Data types in Redis . Redis Ltd . Retrieved June 23, 2022 from https:\/\/redis.io\/topics\/data-types Redis Ltd. 2022. Data types in Redis. Redis Ltd. Retrieved June 23, 2022 from https:\/\/redis.io\/topics\/data-types"},{"key":"e_1_2_1_5_1","volume-title":"Intel Corporation. Retrieved","author":"Intel Corporation","year":"2022","unstructured":"Intel Corporation 2022 . Intel Intrinsics . Intel Corporation. Retrieved April 22, 2022 from https:\/\/intel.ly\/3nxA416 Intel Corporation 2022. Intel Intrinsics. Intel Corporation. Retrieved April 22, 2022 from https:\/\/intel.ly\/3nxA416"},{"key":"e_1_2_1_6_1","volume-title":"Intel performance monitoring events","author":"Intel Corporation 2022.","year":"2022","unstructured":"Intel Corporation 2022. Intel performance monitoring events . Intel Corporation . Retrieved June 2, 2022 from https:\/\/perfmon-events.intel.com\/ Intel Corporation 2022. Intel performance monitoring events. Intel Corporation. Retrieved June 2, 2022 from https:\/\/perfmon-events.intel.com\/"},{"key":"e_1_2_1_7_1","volume-title":"SQLite. Retrieved","year":"2022","unstructured":"SQLite 2022 . SQLite hash table implementation . SQLite. Retrieved June 23, 2022 from https:\/\/sqlite.org\/src\/file\/src\/hash.c SQLite 2022. SQLite hash table implementation. SQLite. Retrieved June 23, 2022 from https:\/\/sqlite.org\/src\/file\/src\/hash.c"},{"key":"e_1_2_1_8_1","volume-title":"TPC. Retrieved","author":"TPC","year":"2022","unstructured":"TPC 2022 . TPC-H Benchmark (Version 3) . TPC. Retrieved June 23, 2022 from http:\/\/www.tpc.org\/tpch\/ TPC 2022. TPC-H Benchmark (Version 3). TPC. Retrieved June 23, 2022 from http:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_1_9_1","volume-title":"Retrieved","author":"Appleby Austin","year":"2016","unstructured":"Austin Appleby . 2016 . MurmurHash3 . Retrieved June 23, 2022 from https:\/\/github.com\/aappleby\/smhasher\/wiki\/MurmurHash3 Austin Appleby. 2016. MurmurHash3. Retrieved June 23, 2022 from https:\/\/github.com\/aappleby\/smhasher\/wiki\/MurmurHash3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_2_1_12_1","volume-title":"Google. Retrieved","author":"Benzaquen Sam","year":"2018","unstructured":"Sam Benzaquen , Alkis Evlogimenos , Matt Kulukundis , and Roman Perepelitsa . 2018 . Swiss Tables and absl::Hash . Google. Retrieved June 23, 2022 from https:\/\/abseil.io\/blog\/20180927-swisstables Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa. 2018. Swiss Tables and absl::Hash. Google. Retrieved June 23, 2022 from https:\/\/abseil.io\/blog\/20180927-swisstables"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989328"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2002.11457"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286760.1286772"},{"key":"e_1_2_1_19_1","volume-title":"Retrieved","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper . 2010 . YCSB Core Workloads . Retrieved November 29, 2020 from https:\/\/github.com\/brianfrankcooper\/YCSB\/wiki\/Core-Workloads Brian F. Cooper. 2010. YCSB Core Workloads. Retrieved November 29, 2020 from https:\/\/github.com\/brianfrankcooper\/YCSB\/wiki\/Core-Workloads"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3358807.3358809"},{"key":"e_1_2_1_22_1","volume-title":"MySQL. Retrieved","author":"Fr\u00f8seth Erik","year":"2019","unstructured":"Erik Fr\u00f8seth . 2019 . Hash join in MySQL 8 . MySQL. Retrieved November 13, 2019 from https:\/\/mysqlserverteam.com\/hash-join-in-mysql-8 Erik Fr\u00f8seth. 2019. Hash join in MySQL 8. MySQL. Retrieved November 13, 2019 from https:\/\/mysqlserverteam.com\/hash-join-in-mysql-8"},{"key":"e_1_2_1_23_1","volume-title":"Understanding the Memcached source code. Retrieved","author":"Holmes He.","year":"2021","unstructured":"Holmes He. 2021. Understanding the Memcached source code. Retrieved January 1, 2021 from https:\/\/holmeshe.me\/understanding-memcached-source-code-V Holmes He. 2021. Understanding the Memcached source code. Retrieved January 1, 2021 from https:\/\/holmeshe.me\/understanding-memcached-source-code-V"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517894"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357381"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2206.12380"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037022"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","author":"Nath Kousik","year":"2017","unstructured":"Kousik Nath . 2017 . A little internal on Redis hash table implementation . Retrieved June 23, 2022 from https:\/\/bit.ly\/3pfVvTm Kousik Nath. 2017. A little internal on Redis hash table implementation. Retrieved June 23, 2022 from https:\/\/bit.ly\/3pfVvTm"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170081"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850585"},{"key":"e_1_2_1_33_1","volume-title":"Retrieved","author":"Rogov Egor","year":"2019","unstructured":"Egor Rogov . 2019 . Indexes in PostgreSQL . Retrieved March 19, 2019 from https:\/\/bit.ly\/3c7L52A Egor Rogov. 2019. Indexes in PostgreSQL. Retrieved March 19, 2019 from https:\/\/bit.ly\/3c7L52A"},{"key":"e_1_2_1_34_1","volume-title":"When Are Learned Models Better Than Hash Functions? CoRR abs\/2107.01464","author":"Sabek Ibrahim","year":"2021","unstructured":"Ibrahim Sabek , Kapil Vaidya , Dominik Horn , Andreas Kipf , and Tim Kraska . 2021. When Are Learned Models Better Than Hash Functions? CoRR abs\/2107.01464 ( 2021 ). https:\/\/arxiv.org\/abs\/2107.01464 Ibrahim Sabek, Kapil Vaidya, Dominik Horn, Andreas Kipf, and Tim Kraska. 2021. When Are Learned Models Better Than Hash Functions? CoRR abs\/2107.01464 (2021). https:\/\/arxiv.org\/abs\/2107.01464"},{"key":"e_1_2_1_35_1","volume-title":"Retrieved","author":"Skarupke Malte","year":"2018","unstructured":"Malte Skarupke . 2018 . Bytell hash map . Retrieved June 16, 2018 from https:\/\/bit.ly\/3fB8NX6 Malte Skarupke. 2018. Bytell hash map. Retrieved June 16, 2018 from https:\/\/bit.ly\/3fB8NX6"},{"key":"e_1_2_1_36_1","volume-title":"Hash table","year":"2022","unstructured":"Wikipedia. 2022. Hash table . Wikimedia Foundation, Ltd. Retrieved June 23, 2022 from https:\/\/en.wikipedia.org\/wiki\/Hash_table Wikipedia. 2022. Hash table. Wikimedia Foundation, Ltd. Retrieved June 23, 2022 from https:\/\/en.wikipedia.org\/wiki\/Hash_table"},{"key":"e_1_2_1_37_1","volume-title":"Inc. Retrieved","year":"2022","unstructured":"Wikipedia. 2022 . Hellinger's distance. Wikimedia Foundation , Inc. Retrieved May 24, 2022 from https:\/\/en.wikipedia.org\/wiki\/Hellinger_distance Wikipedia. 2022. Hellinger's distance. Wikimedia Foundation, Inc. Retrieved May 24, 2022 from https:\/\/en.wikipedia.org\/wiki\/Hellinger_distance"},{"key":"e_1_2_1_38_1","volume-title":"Kullback-Leibler divergence","year":"2022","unstructured":"Wikipedia. 2022. Kullback-Leibler divergence . Wikimedia Foundation, Ltd. Retrieved June 19, 2022 from https:\/\/en.wikipedia.org\/wiki\/Kullback-Leibler_divergence Wikipedia. 2022. Kullback-Leibler divergence. Wikimedia Foundation, Ltd. Retrieved June 19, 2022 from https:\/\/en.wikipedia.org\/wiki\/Kullback-Leibler_divergence"},{"key":"e_1_2_1_39_1","volume-title":"Inc. Retrieved","year":"2022","unstructured":"Wikipedia. 2022 . Lindeberg-Levy CLT. Wikimedia Foundation , Inc. Retrieved June 10, 2022 from https:\/\/en.wikipedia.org\/wiki\/Central_limit_theorem#Classical_CLT Wikipedia. 2022. Lindeberg-Levy CLT. Wikimedia Foundation, Inc. Retrieved June 10, 2022 from https:\/\/en.wikipedia.org\/wiki\/Central_limit_theorem#Classical_CLT"},{"key":"e_1_2_1_40_1","volume-title":"Open addressing","year":"2022","unstructured":"Wikipedia. 2022. Open addressing . Wikimedia Foundation, Ltd. Retrieved April 17, 2022 from https:\/\/en.wikipedia.org\/wiki\/Open_addressing Wikipedia. 2022. Open addressing. Wikimedia Foundation, Ltd. Retrieved April 17, 2022 from https:\/\/en.wikipedia.org\/wiki\/Open_addressing"},{"key":"e_1_2_1_41_1","volume-title":"Power Law","year":"2022","unstructured":"Wikipedia. 2022. Power Law . Wikimedia Foundation, Ltd. Retrieved June 3, 2022 from https:\/\/en.wikipedia.org\/wiki\/Power_law Wikipedia. 2022. Power Law. Wikimedia Foundation, Ltd. Retrieved June 3, 2022 from https:\/\/en.wikipedia.org\/wiki\/Power_law"},{"key":"e_1_2_1_42_1","volume-title":"Inc. Retrieved","year":"2022","unstructured":"Wikipedia. 2022 . Z-test. Wikimedia Foundation , Inc. Retrieved April 18, 2022 from https:\/\/en.wikipedia.org\/wiki\/Z-test Wikipedia. 2022. Z-test. Wikimedia Foundation, Inc. Retrieved April 18, 2022 from https:\/\/en.wikipedia.org\/wiki\/Z-test"},{"key":"e_1_2_1_43_1","volume-title":"Zipf's law","year":"2022","unstructured":"Wikipedia. 2022. Zipf's law . Wikimedia Foundation, Ltd. Retrieved June 19, 2022 from https:\/\/en.wikipedia.org\/wiki\/Zipf's_law Wikipedia. 2022. Zipf's law. Wikimedia Foundation, Ltd. Retrieved June 19, 2022 from https:\/\/en.wikipedia.org\/wiki\/Zipf's_law"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311881"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:09:31Z","timestamp":1672225771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547306"}},"subtitle":["adapting to skew in popularity of data on the fly"],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547306"],"URL":"https:\/\/doi.org\/10.14778\/3547305.3547306","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}