Cache-oblivious dynamic dictionaries with update/query tradeoffs
Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better O(logB N over M )) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent struc...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62807 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811083645994139648 |
|---|---|
| author | Brodal, Gerth Stolting Demaine, Erik D. Fineman, Jeremy T. Iacono, John Langerman, Stefan Munro, J. Ian |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Brodal, Gerth Stolting Demaine, Erik D. Fineman, Jeremy T. Iacono, John Langerman, Stefan Munro, J. Ian |
| author_sort | Brodal, Gerth Stolting |
| collection | MIT |
| description | Several existing cache-oblivious dynamic dictionaries
achieve O(logB N) (or slightly better O(logB
N over M )) memory
transfers per operation, where N is the number of
items stored, M is the memory size, and B is the
block size, which matches the classic B-tree data structure.
One recent structure achieves the same query
bound and a sometimes-better amortized update bound
of O (...) memory transfers.
This paper presents a new data structure, the xDict,
implementing predecessor queries in O(...)worstcase
memory transfers and insertions and deletions in
O (...) amortized memory transfers, for any constant " with 0 < epsilon < 1. For example, the xDict achieves subconstant amortized update cost when N = ..., whereas the B-tree’s ... is subconstant only when ... is subconstant only when N = .... The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between (...) and O(1= lg3 N) memory transfers. |
| first_indexed | 2024-09-23T12:36:29Z |
| format | Article |
| id | mit-1721.1/62807 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:36:29Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/628072022-10-01T10:03:48Z Cache-oblivious dynamic dictionaries with update/query tradeoffs Brodal, Gerth Stolting Demaine, Erik D. Fineman, Jeremy T. Iacono, John Langerman, Stefan Munro, J. Ian Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Erik D. Fineman, Jeremy T. Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better O(logB N over M )) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O (...) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(...)worstcase memory transfers and insertions and deletions in O (...) amortized memory transfers, for any constant " with 0 < epsilon < 1. For example, the xDict achieves subconstant amortized update cost when N = ..., whereas the B-tree’s ... is subconstant only when ... is subconstant only when N = .... The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between (...) and O(1= lg3 N) memory transfers. Danish National Research Foundation (MADALGO (Center for Massive Data Algorithmics)) National Science Foundation (U.S.) (NSF Grants CCF-0541209) National Science Foundation (U.S.) (NSF Grants CCF-0541209) Computing Innovation Fellows 2011-05-10T19:22:51Z 2011-05-10T19:22:51Z 2010-01 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/62807 Brodal, Gerth Stolting et al. "Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs." Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Jan, 17-19, 2010, Hyatt Regency Austin, Austin, TX. Session 11C. https://orcid.org/0000-0003-3803-5703 en_US http://www.siam.org/proceedings/soda/2010/SODA10_117_brodalg.pdf Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Society for Industrial and Applied Mathematics MIT web domain |
| spellingShingle | Brodal, Gerth Stolting Demaine, Erik D. Fineman, Jeremy T. Iacono, John Langerman, Stefan Munro, J. Ian Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title | Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title_full | Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title_fullStr | Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title_full_unstemmed | Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title_short | Cache-oblivious dynamic dictionaries with update/query tradeoffs |
| title_sort | cache oblivious dynamic dictionaries with update query tradeoffs |
| url | http://hdl.handle.net/1721.1/62807 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT brodalgerthstolting cacheobliviousdynamicdictionarieswithupdatequerytradeoffs AT demaineerikd cacheobliviousdynamicdictionarieswithupdatequerytradeoffs AT finemanjeremyt cacheobliviousdynamicdictionarieswithupdatequerytradeoffs AT iaconojohn cacheobliviousdynamicdictionarieswithupdatequerytradeoffs AT langermanstefan cacheobliviousdynamicdictionarieswithupdatequerytradeoffs AT munrojian cacheobliviousdynamicdictionarieswithupdatequerytradeoffs |