TY - GEN
T1 - Scanning and traversing
T2 - 10th Annual European Symposium on Algorithms, ESA 2002
AU - Bender, Michael A.
AU - Cole, Richard
AU - Demaine, Erik D.
AU - Farach-Colton, Martin
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a simple two-level memory hierarchy. We explore this traversal problem on more realistic memory models: the cache-oblivious model, which applies to unknown and multi-level memory hierarchies, and sequential-access models, where sequential block transfers are less expensive than random block transfers.
AB - We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a simple two-level memory hierarchy. We explore this traversal problem on more realistic memory models: the cache-oblivious model, which applies to unknown and multi-level memory hierarchies, and sequential-access models, where sequential block transfers are less expensive than random block transfers.
UR - https://www.scopus.com/pages/publications/84938098594
U2 - 10.1007/3-540-45749-6_16
DO - 10.1007/3-540-45749-6_16
M3 - Conference contribution
AN - SCOPUS:84938098594
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 139
EP - 150
BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
A2 - Möhring, Rolf
A2 - Raman, Rajeev
PB - Springer Verlag
Y2 - 17 September 2002 through 21 September 2002
ER -