{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:05:54Z","timestamp":1768028754097,"version":"3.49.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>\n            The\n            <jats:italic>packed-memory array<\/jats:italic>\n            (\n            <jats:italic>PMA<\/jats:italic>\n            ) is a data structure that maintains a dynamic set of\n            <jats:italic>N<\/jats:italic>\n            elements in sorted order in a \u0398(\n            <jats:italic>N<\/jats:italic>\n            )-sized array. The idea is to intersperse \u0398(\n            <jats:italic>N<\/jats:italic>\n            ) empty spaces or\n            <jats:italic>gaps<\/jats:italic>\n            among the elements so that only a small number of elements need to be shifted around on an insert or delete. Because the elements are stored physically in sorted order in memory or on disk, the PMA can be used to support extremely efficient range queries. Specifically, the cost to scan\n            <jats:italic>L<\/jats:italic>\n            consecutive elements is\n            <jats:italic>O<\/jats:italic>\n            (1 +\n            <jats:italic>L<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ) memory transfers.\n          <\/jats:p>\n          <jats:p>\n            This article gives the first\n            <jats:italic>adaptive packed-memory array<\/jats:italic>\n            (\n            <jats:italic>APMA<\/jats:italic>\n            ), which automatically adjusts to the input pattern. Like the traditional PMA, any pattern of updates costs only\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>N<\/jats:italic>\n            ) amortized element moves and\n            <jats:italic>O<\/jats:italic>\n            (1 + (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>N<\/jats:italic>\n            )\/\n            <jats:italic>B<\/jats:italic>\n            ) amortized memory transfers per update. However, the APMA performs even better on many common input distributions achieving only\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            ) amortized element moves and\n            <jats:italic>O<\/jats:italic>\n            (1+ (log\n            <jats:italic>N<\/jats:italic>\n            )\/\n            <jats:italic>B<\/jats:italic>\n            ) amortized memory transfers. The article analyzes\n            <jats:italic>sequential<\/jats:italic>\n            inserts, where the insertions are to the front of the APMA,\n            <jats:italic>hammer<\/jats:italic>\n            inserts, where the insertions \u201chammer\u201d on one part of the APMA,\n            <jats:italic>random<\/jats:italic>\n            inserts, where the insertions are after random elements in the APMA, and\n            <jats:italic>bulk<\/jats:italic>\n            inserts, where for constant \u03b1 \u03f5 [0, 1],\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>\u03b1<\/jats:sup>\n            elements are inserted after random elements in the APMA. The article then gives simulation results that are consistent with the asymptotic bounds. For sequential insertions of roughly 1.4 million elements, the APMA has four times fewer element moves per insertion than the traditional PMA and running times that are more than seven times faster.\n          <\/jats:p>","DOI":"10.1145\/1292609.1292616","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["An adaptive packed-memory array"],"prefix":"10.1145","volume":"32","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Haodong","family":"Hu","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms (ESA)","author":"Bender M. A.","unstructured":"Bender , M. A. , Cole , R. , Demaine , E. D. , and Farach-Colton , M. 2002a. Scanning and traversing: Maintaining data for traversals in a memory hierarchy . In Proceedings of the 10th Annual European Symposium on Algorithms (ESA) . Lecture Notes in Computer Science , vol. 2461 . Springer , Berlin, Germany , 139--151. Bender, M. A., Cole, R., Demaine, E. D., and Farach-Colton, M. 2002a. Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2461. Springer, Berlin, Germany, 139--151."},{"key":"e_1_2_1_2_1","volume-title":"Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409","author":"Bender M. A.","unstructured":"Bender , M. A. , Demaine , E. D. , and Farach-Colton , M . 2000 . Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409 . Bender, M. A., Demaine, E. D., and Farach-Colton, M. 2000. Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389956"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the of the 13th Annual Symposium on Discrete Mathematics (SODA). 29--38","author":"Bender M. A.","unstructured":"Bender , M. A. , Duan , Z. , Iacono , J. , and Wu , J . 2002b. A locality-preserving cache-oblivious dynamic dictionary . In Proceedings of the of the 13th Annual Symposium on Discrete Mathematics (SODA). 29--38 . Bender, M. A., Duan, Z., Iacono, J., and Wu, J. 2002b. A locality-preserving cache-oblivious dynamic dictionary. In Proceedings of the of the 13th Annual Symposium on Discrete Mathematics (SODA). 29--38."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 3rd International Conference on Fun with Algorithms (FUN). 16--23","author":"Bender M. A.","unstructured":"Bender , M. A. , Farach-Colton , M. , and Mosteiro , M . 2004b. Insertion sort is O(n log n) . In Proceedings of the 3rd International Conference on Fun with Algorithms (FUN). 16--23 . Bender, M. A., Farach-Colton, M., and Mosteiro, M. 2004b. Insertion sort is O(n log n). In Proceedings of the 3rd International Conference on Fun with Algorithms (FUN). 16--23."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074009"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA). 39--48","author":"Brodal G. S.","unstructured":"Brodal , G. S. , Fagerberg , R. , and Jacob , R . 2002. Cache oblivious search trees via binary trees of small height . In Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA). 39--48 . Brodal, G. S., Fagerberg, R., and Jacob, R. 2002. Cache oblivious search trees via binary trees of small height. In Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA). 39--48."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802184"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 4th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science","volume":"824","author":"Dietz P. F.","unstructured":"Dietz , P. F. , Seiferas , J. I. , and Zhang , J . 1994. A tight lower bound for on-line monotonic list labeling . In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science , vol. 824 . Springer, Berlin, Germany, 131--142. Dietz, P. F., Seiferas, J. I., and Zhang, J. 1994. A tight lower bound for on-line monotonic list labeling. In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 824. Springer, Berlin, Germany, 131--142."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science","volume":"447","author":"Dietz P. F.","unstructured":"Dietz , P. F. and Zhang , J . 1990. Lower bounds for monotonic list labeling . In Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science , vol. 447 , Springer, Berlin, Germany. Dietz, P. F. and Zhang, J. 1990. Lower bounds for monotonic list labeling. In Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 447, Springer, Berlin, Germany."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 8th Internationl Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science","volume":"115","author":"Itai A.","unstructured":"Itai , A. , Konheim , A. G. , and Rodeh , M . 1981. A sparse table implementation of priority queues . In Proceedings of the 8th Internationl Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science , vol. 115 , Springer, Belin, Germany, 417--431. Itai, A., Konheim, A. G., and Rodeh, M. 1981. A sparse table implementation of priority queues. In Proceedings of the 8th Internationl Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 115, Springer, Belin, Germany, 417--431."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289142"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802183"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16879"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90034-D"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1292609.1292616","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1292609.1292616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:27Z","timestamp":1750258347000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1292609.1292616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1292609.1292616"],"URL":"https:\/\/doi.org\/10.1145\/1292609.1292616","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}