DecreaseKeys are Expensive for External Memory Priority Queues
| Autor: | Kasper Green Larsen, Huacheng Yu, Kasper Eenberg |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
Lower bound Computer science 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Upper and lower bounds 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Priority queues Data Structures and Algorithms (cs.DS) Communication complexity Cell-probe model Auxiliary memory Discrete mathematics Sequence Data structure External memory Computer Science - Computational Complexity 010201 computation theory & mathematics Double-ended priority queue Priority queue Algorithm |
| Zdroj: | Eenberg, K, Larsen, K G & Yu, H 2017, DecreaseKeys are expensive for external memory priority queues . in STOC 2017-Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . vol. Part F128415, Association for Computing Machinery, New York, NY, pp. 1081-1093, 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, 19/06/2017 . https://doi.org/10.1145/3055399.3055437 STOC |
| DOI: | 10.1145/3055399.3055437 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|