{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:25Z","timestamp":1779174805202,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>Many modern key-value stores rely on an in-memory index to map the location of each data entry in storage. The size of this index often becomes a memory bottleneck that makes it difficult to scale the system to large data sizes. To address this problem, the state-of-the-art approach is to structure this index as a succinct perfect hash table using only \u2248 4 bits per key. The downside is that the hash table encoding is computationally expensive to parse and may harm overall system performance.<\/jats:p>\n          <jats:p>We introduce Sphinx, a succinct perfect hash table reengineered for high performance on commodity CPUs. Sphinx is encoded in a manner that lends itself to efficient access using rank and select primitives, and it uses auxiliary metadata to decode common hash table slots instantaneously. Sphinx is also expandable and parallelizable. We compare Sphinx to the best alternatives and show that it leads to a 2x reduction in query latency, update latency, and memory footprint.<\/jats:p>","DOI":"10.14778\/3749646.3749703","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4424-4437","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Sphinx: A Succinct Perfect Hash Index for x86"],"prefix":"10.14778","volume":"18","author":[{"given":"Sajad Faghfoor","family":"Maghrebi","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niv","family":"Dayan","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"General-Purpose and System Instructions. https:\/\/docs.amd.com\/v\/u\/en-US\/24594_3.37 Accessed: 2025-07-14.","author":"AMD","year":"2024","unstructured":"AMD, Inc. 2024. AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions. https:\/\/docs.amd.com\/v\/u\/en-US\/24594_3.37 Accessed: 2025-07-14."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.3129"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Martin Farach-Colton Mayank Goswami Rob Johnson Samuel McCauley and Shikha Singh. 2018. Bloom Filters Adaptivity and the Dictionary Problem. arXiv:1711.01616 [cs.DS] https:\/\/arxiv.org\/abs\/1711.01616","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2009.12.003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457565"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2018 International Conference on Management of Data (SIGMOD). 275\u2013290","author":"Chandramouli Badrish","unstructured":"Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin J. Levandoski, Jordan Hunter, and Michael F. Barnett. 2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD). 275\u2013290."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378515"},{"key":"e_1_2_1_11_1","volume-title":"Aleph Filter: To Infinity in Constant Time. arXiv preprint arXiv:2404.04703","author":"Dayan Niv","year":"2024","unstructured":"Niv Dayan, Ioana Bercea, and Rasmus Pagh. 2024. Aleph Filter: To Infinity in Constant Time. arXiv preprint arXiv:2404.04703 (2024)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476373"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989327"},{"key":"e_1_2_1_16_1","unstructured":"Cameron Desrochers. [n.d.]. ConcurrentQueue: An industrial-strength lock-free queue for C++. https:\/\/github.com\/cameron314\/concurrentqueue. GitHub repository. Accessed: 2025-02-19."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02652-2_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698820"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_21_1","unstructured":"Kevin P Gaffney and Jignesh M Patel. 2024. Is Perfect Hashing Practical for OLAP Systems?. In CIDR."},{"key":"e_1_2_1_22_1","volume-title":"Poster Proc.","volume":"38","author":"Gonz\u00e1lez Rodrigo","year":"2005","unstructured":"Rodrigo Gonz\u00e1lez, Szymon Grabowski, Veli M\u00e4kinen, and Gonzalo Navarro. 2005. Practical implementation of rank and select queries. In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). CTI Press and Ellinika Grammata Greece, 27\u201338."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508284.1508271"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11833529_11"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5935158"},{"key":"e_1_2_1_26_1","unstructured":"Intel Corporation. 2024. Intel\u00ae 64 and IA-32 Architectures Software Developer's Manual. https:\/\/cdrdv2.intel.com\/v1\/dl\/getContent\/671200 Accessed: 2025-07-14."},{"key":"e_1_2_1_27_1","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC 22)","author":"Kim Juwon","year":"2022","unstructured":"Juwon Kim, Minsu Kim, Muhammad Danish Tehseen, Joontaek Oh, and Youjip Won. 2022. IPLFS: Log-Structured File System without Garbage Collection. In 2022 USENIX Annual Technical Conference (USENIX ATC 22). USENIX Association, Carlsbad, CA, 739\u2013754. https:\/\/www.usenix.org\/conference\/atc22\/presentation\/kim-juwon"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.60"},{"key":"e_1_2_1_30_1","volume-title":"ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems. In 21st USENIX Conference on File and Storage Technologies (FAST 23)","author":"Li Pengfei","year":"2023","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, and Jiajie Sheng. 2023. ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems. In 21st USENIX Conference on File and Storage Technologies (FAST 23). USENIX Association, Santa Clara, CA, 99\u2013114. https:\/\/www.usenix.org\/conference\/fast23\/presentation\/li-pengfei"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588962"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 41st IEEE International Conference on Data Engineering (ICDE). IEEE. https:\/\/pkuzhao.net\/publication\/cuckooduo\/CuckooDuo.pdf","author":"Liu Zirui","year":"2025","unstructured":"Zirui Liu, Xian Niu, Wei Zhou, Yisen Hong, Zhouran Shi, Tong Yang, Yuchao Zhang, Yuhan Wu, Yikai Zhao, Zhuochen Fan, and Bin Cui. 2025. CuckooDuo: Extensible Dynamic Perfect Hashing for RDMA-based Remote Memory KV Store. In Proceedings of the 41st IEEE International Conference on Data Engineering (ICDE). IEEE. https:\/\/pkuzhao.net\/publication\/cuckooduo\/CuckooDuo.pdf"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261567"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339504"},{"key":"e_1_2_1_36_1","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_37_1","unstructured":"Faisal Nawab Vaibhav Arora Divyakant Agrawal and A. El Abbadi. 2015. Chariots: A Scalable Shared Log for Data Management in Multi-Datacenter Cloud Environments. In International Conference on Extending Database Technology. https:\/\/api.semanticscholar.org\/CorpusID:16457773"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/65762.65765"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Rasmus Pagh Gil Segev and Udi Wieder. 2013. How to Approximate A Set Without Knowing Its Size In Advance. 10.48550\/arXiv.1304.1188","DOI":"10.48550\/arXiv.1304.1188"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1706.00990"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654681"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/146941.146943"},{"key":"e_1_2_1_47_1","unstructured":"Margo I Seltzer Keith Bostic Marshall K McKusick Carl Staelin et al. 1993. An Implementation of a Log-Structured File System for UNIX.. In USENIX Winter. 307\u2013326."},{"key":"e_1_2_1_48_1","volume-title":"Bitcask: A Log-Structured Hash Table for Fast Key\/Value Data. Basho White Paper.","author":"Sheehy Justin","year":"2010","unstructured":"Justin Sheehy and Dave Smith. 2010. Bitcask: A Log-Structured Hash Table for Fast Key\/Value Data. Basho White Paper."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007276"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536372"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336673"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551839"},{"key":"e_1_2_1_53_1","volume-title":"Pacman: An Efficient Compaction Approach for Log-Structured Key-Value Store on Persistent Memory. In 2022 USENIX Annual Technical Conference (USENIX ATC 22)","author":"Wang Jing","year":"2022","unstructured":"Jing Wang, Youyou Lu, Qing Wang, Minhui Xie, Keji Huang, and Jiwu Shu. 2022. Pacman: An Efficient Compaction Approach for Log-Structured Key-Value Store on Persistent Memory. In 2022 USENIX Annual Technical Conference (USENIX ATC 22). USENIX Association, Carlsbad, CA, 773\u2013788. https:\/\/www.usenix.org\/conference\/atc22\/presentation\/wang-jing"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364333"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677128"},{"key":"e_1_2_1_56_1","volume-title":"NOVA: A Log-structured File System for Hybrid Volatile\/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST 16)","author":"Xu Jian","year":"2016","unstructured":"Jian Xu and Steven Swanson. 2016. NOVA: A Log-structured File System for Hybrid Volatile\/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST 16). USENIX Association, Santa Clara, CA, 323\u2013338. https:\/\/www.usenix.org\/conference\/fast16\/technical-sessions\/presentation\/xu"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.2200469"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511895"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T02:54:27Z","timestamp":1757040867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":58,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749703"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749703","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}