.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
The
packed-memory array
(
PMA
) is a data structure that maintains a dynamic set of
N
elements in sorted order in a Θ(
N
)-sized array. The idea is to intersperse Θ(
N
) empty spaces or
gaps
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
L
consecutive elements is
O
(1 +
L
/
B
) memory transfers.
This article gives the first
adaptive packed-memory array
(
APMA
), which automatically adjusts to the input pattern. Like the traditional PMA, any pattern of updates costs only
O
(log
2
N
) amortized element moves and
O
(1 + (log
2
N
)/
B
) amortized memory transfers per update. However, the APMA performs even better on many common input distributions achieving only
O
(log
N
) amortized element moves and
O
(1+ (log
N
)/
B
) amortized memory transfers. The article analyzes
sequential
inserts, where the insertions are to the front of the APMA,
hammer
inserts, where the insertions “hammer” on one part of the APMA,
random
inserts, where the insertions are after random elements in the APMA, and
bulk
inserts, where for constant α ϵ [0, 1],
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.
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息