TY - GEN
T1 - DecreaseKeys are expensive for external memory priority queues
AU - Eenberg, Kasper
AU - Larsen, Kasper Green
AU - Yu, Huacheng
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/6/19
Y1 - 2017/6/19
N2 - One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing O((N/B) lgM/B N) I/Os over a sequence of N operations, where B is the disk block size in number of words and M is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only O((N/B) lg2 N) I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of Ω((N/B) lglgN B) I/Os for processing a sequence of N intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.
AB - One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing O((N/B) lgM/B N) I/Os over a sequence of N operations, where B is the disk block size in number of words and M is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only O((N/B) lg2 N) I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of Ω((N/B) lglgN B) I/Os for processing a sequence of N intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.
KW - Communication complexity
KW - External memory
KW - Lower bound
KW - Priority queues
UR - http://www.scopus.com/inward/record.url?scp=85024391830&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024391830&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055437
DO - 10.1145/3055399.3055437
M3 - Conference contribution
AN - SCOPUS:85024391830
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1081
EP - 1093
BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
A2 - McKenzie, Pierre
A2 - King, Valerie
A2 - Hatami, Hamed
PB - Association for Computing Machinery
T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Y2 - 19 June 2017 through 23 June 2017
ER -