{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T03:11:10Z","timestamp":1774321870923,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF","award":["CSR-1938180"],"award-info":[{"award-number":["CSR-1938180"]}]},{"name":"NSF","award":["CCF-2106999"],"award-info":[{"award-number":["CCF-2106999"]}]},{"name":"NSF","award":["CCF-2118620"],"award-info":[{"award-number":["CCF-2118620"]}]},{"name":"NSF","award":["CCF-2118832"],"award-info":[{"award-number":["CCF-2118832"]}]},{"name":"NSF","award":["CCF-2106827"],"award-info":[{"award-number":["CCF-2106827"]}]},{"name":"NSF","award":["CCF-1725543"],"award-info":[{"award-number":["CCF-1725543"]}]},{"name":"NSF","award":["CSR-1763680"],"award-info":[{"award-number":["CSR-1763680"]}]},{"name":"NSF","award":["CCF-1716252"],"award-info":[{"award-number":["CCF-1716252"]}]},{"name":"NSF","award":["CNS-1938709"],"award-info":[{"award-number":["CNS-1938709"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"\n This article introduces a new data-structural object that we call the tiny pointer. In many applications, traditional\n \n \\(\\log n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -bit pointers can be replaced with\n \n \\(o(\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor\n \n \\(1-\\delta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , then the optimal tiny-pointer size is\n \n \\(\\Theta(\\log\\log\\log n+\\log\\delta^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits in the fixed-size case, and\n \n \\(\\Theta(\\log\\delta^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n expected bits in the variable-size case.\n <\/jats:p>\n Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest.<\/jats:p>\n \n Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that:\n \n \n \u2014<\/jats:label>\n \n A data structure storing\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n \n \\(v\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -bit values for\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n keys with constant-factor time modifications\/queries can be implemented to take space\n \n \\(nv+O(n\\log^{(r)}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits, for any constant\n \n \\(r>0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , as long as the user stores a tiny pointer of expected size\n \n \\(O(1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with each key\u2014here,\n \n \\(\\log^{(r)}n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the\n \n \\(r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n th iterated logarithm.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n Any binary search tree can be made succinct, meaning that it achieves\n \n \\((1+o(1))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n times the optimal space, with constant-factor time overhead, and can even be made to be within\n \n \\(O(n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits of optimal if we allow for\n \n \\(O(\\log^{*}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time modifications\u2014this holds even for rotation-based trees such as the splay tree and the red-black tree.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and\n \n \\((1+o(1))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -factor space overhead.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of\n \n \\(\\log^{(r)}n+O(\\log j)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits per\n \n \\(j\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -bit value for an arbitrary constant\n \n \\(r>0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of our choice.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n Given an external-memory array\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of size\n \n \\((1+\\varepsilon)n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n containing a dynamic set of up to\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n key-value pairs, it is possible to maintain an internal-memory stash of size\n \n \\(O(n\\log\\varepsilon^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits so that the location of any key-value pair in\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be computed in constant time (and with no IOs).\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.<\/jats:p>","DOI":"10.1145\/3700594","type":"journal-article","created":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T11:25:12Z","timestamp":1729509912000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Tiny Pointers"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1395","authenticated-orcid":false,"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Abseil. 2024. Google\u2019s Abseil C \\(++\\) Library. Retrieved July 18 2024 from https:\/\/abseil.io\/"},{"key":"e_1_3_2_3_2","first-page":"263","volume-title":"Doklady Akademii NaukRussian Academy of Sciences","author":"Adel\u2019son-Vel\u2019skii George","year":"1962","unstructured":"George Adel\u2019son-Vel\u2019skii and Evgenii Landis. 1962. An algorithm for organization of information. In Doklady Akademii Nauk, Vol. 146, Russian Academy of Sciences, 263\u2013266."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380842"},{"key":"e_1_3_2_5_2","unstructured":"AMDManual. 2024. AMD64 Architecture Programmer\u2019s Manual Volume 2: System Programming. Retrieved July 18 2024 from https:\/\/www.amd.com\/content\/dam\/amd\/en\/documents\/processor-tech-docs\/programmer-references\/24593.pdf"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_2_8_2","first-page":"487","volume-title":"Doklady Akademii NaukRussian Academy of Sciences","author":"Arlazarov Vladimir L\u2019vovich","year":"1970","unstructured":"Vladimir L\u2019vovich Arlazarov, Yefim A Dinitz, MA Kronrod, and IgorAleksandrovich Faradzhev. 1970. On economical construction of the transitive closure of an oriented graph. In Doklady Akademii Nauk, Vol. 194, Russian Academy of Sciences, 487\u2013488."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461814"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3625817"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519969"},{"key":"e_1_3_2_14_2","unstructured":"Ioana Oriana Bercea and Guy Even. 2020. A space-efficient dynamic dictionary for multisets with constant time operations. arXiv:2005.02143. Retrieved from https:\/\/arxiv.org\/abs\/2005.02143"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-01057-0"},{"key":"e_1_3_2_16_2","unstructured":"c \\(++\\) std::map. 2023. cpppreference std::map. Retrieved July 18 2024 from https:\/\/en.cppreference.com\/w\/cpp\/container\/map"},{"key":"e_1_3_2_17_2","unstructured":"c \\(++\\) std::set. 2024. cpppreference std::set. Retrieved July 18 2024 from https:\/\/en.cppreference.com\/w\/cpp\/container\/set"},{"key":"e_1_3_2_18_2","unstructured":"c \\(++\\) std::unordered \\(\\_\\) map. 2024. cpppreference std::unordered \\(\\_\\) map. Retrieved July 18 2024 from https:\/\/en.cppreference.com\/w\/cpp\/container\/unordered_map"},{"key":"e_1_3_2_19_2","unstructured":"c \\(++\\) stl \\(\\_\\) set.h. 2024. gcc-mirror\/gcc libstdc \\(++\\) -v3 stl \\(\\_\\) set.h. Retrieved July 18 2024 from https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/stl_set.h"},{"key":"e_1_3_2_20_2","unstructured":"c \\(++\\) sty \\(\\_\\) map.h. 2024. gcc-mirror\/gcc libstdc \\(++\\) -v3 stl \\(\\_\\) map.h. Retrieved July 18 2024 from https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/stl_map.h"},{"key":"e_1_3_2_21_2","unstructured":"c \\(++\\) unordered \\(\\_\\) map.h. 2024. gcc-mirror\/gcc libstdc \\(++\\) -v3 unordered \\(\\_\\) map.h. Retrieved July 18 2024 from https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/unordered_map.h"},{"key":"e_1_3_2_22_2","unstructured":"c \\(++\\) unordered \\(\\_\\) set. 2024. cpppreference std::unordered \\(\\_\\) set. Retrieved July 18 2024 from https:\/\/en.cppreference.com\/w\/cpp\/container\/unordered_set"},{"key":"e_1_3_2_23_2","unstructured":"c \\(++\\) unordered \\(\\_\\) set.h. 2024. gcc-mirror\/gcc libstdc \\(++\\) -v3 unordered \\(\\_\\) set.h. Retrieved July 18 2024 from https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/unordered_set.h"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2016.04.031"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11786-017-0294-4"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_34"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2019.24"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2007.02.054"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_3_2_32_2","unstructured":"F14. 2024. Facebook\u2019s F14 Hash Table. Retrieved July 18 2024 from https:\/\/engineering.fb.com\/2019\/04\/25\/developer-tools\/f14\/"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2010.10.030"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-004-1195-X"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45078-8_11"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42274"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582021"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_3_2_39_2","first-page":"1","volume-title":"J. Inf. Process","author":"Gunji Takao","year":"1980","unstructured":"Takao Gunji and E. Goto. 1980. Studies on hashing part-1: A comparison of hashing algorithms with key deletion. J. Inf. Process. 3, 1 (1980), 1\u201312."},{"key":"e_1_3_2_40_2","unstructured":"Intel. 2024. Intel\u00ae64 and IA-32 Architectures Software Developer\u2019s Manual Combined Volumes 3A 3B 3C and 3D: System Programming Guide. Retrieved from https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/download\/intel-64-and-ia-32-architectures-sdm-combined-volumes-3a-3b-3c-and-3d-system-programming-guide.html. Accessed: 2024-07-18."},{"key":"e_1_3_2_41_2","unstructured":"Don E. Knuth. 1963. Notes on \u201cOpen\u201d Addressing."},{"key":"e_1_3_2_42_2","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","year":"1973","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Vol. III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322407"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/44498.44500"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/358105.358193"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2020.79"},{"key":"e_1_3_2_47_2","unstructured":"M. Molloy and B. Reed. 2013. Graph Colouring and the Probabilistic Method. Springer Berlin. Retrieved from https:\/\/books.google.com\/books?id=gU3xCAAAQBAJ"},{"key":"e_1_3_2_48_2","first-page":"529","volume-title":"Proceedings of the 12th Annual Symposium on Discrete Algorithms","author":"Munro J. Ian","year":"2001","unstructured":"J. Ian Munro, Venkatesh Raman, and Adam J. Storm. 2001. Representing dynamic binary trees succinctly. In Proceedings of the 12th Annual Symposium on Discrete Algorithms. S. Rao Kosaraju (Ed.), ACM\/SIAM, New Yor, NY, 529\u2013536. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=365411.365526"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/060658400"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JALGOR.2003.12.002"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1147\/RD.12.0130"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_2_56_2","unstructured":"Peter Sanders. 2018. Hashing with linear probing and referential integrity. arXiv:1808.04602. Retrieved from http:\/\/arxiv.org\/abs\/1808.04602"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109605"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:43Z","timestamp":1757346703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3700594"],"URL":"https:\/\/doi.org\/10.1145\/3700594","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2023-07-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}