Deterministic Cache-Oblivious Funnelselect Algorithms

Cache-Oblivious, Sorting, Randomized, Quicksort, Selection

• English

moen_nt Follow

Uploaded on Apr 30, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Deterministic Cache-Oblivious Funnelselect Gerth St lting Brodal Sebastian Wild 19th Scandinavian Symposium on Algorithm Theory (SWAT), June 12-14, 2024, Helsinki, Finland

2. Problem Algorithm Computational Model Randomized Sorting Internal memory Memory access (element comparisons) 77 24 36 58 70 1 29 42 13 92 2 77 24 36 58 70 1 29 42 13 92 1 13 24 29 36 42 58 70 77 92 4 10 rank 2 Deterministic External memory Cache aware, I/O Single selection 77 24 36 58 70 1 29 42 13 92 M B I/O rank CPU 29 4 internal external Aggarwal, Vitter 1988 Multiple selection Cache oblivious Result of this talk Algorithms do not know B and M (optimal offline cache replacement) 77 24 36 58 70 1 29 42 13 92 M B I/O ranks 13 29 92 2 4 10 sorted CPU internal external Frigo, Leiserson, Prokop, Ramachandran 1999

3. Internal Memory Sorting Randomized Quicksort random pivot [Hoare 1959] Expected time O(n log2n) partition 9 1 36 74 39 16 38 63 66 20 51 19 71 48 86 10 26 12 11 97 36 39 16 38 20 19 10 26 12 11 48 74 63 66 51 71 86 97 9 1 10 12 11 16 36 39 38 20 19 26 63 51 66 74 71 86 97 9 1 9 20 19 26 36 39 38 51 63 74 71 86 97 1 10 12 11 10 11 12 19 20 36 39 38 71 74 38 39 1 9 10 11 12 16 19 20 26 36 38 39 48 51 63 66 71 74 86 97 sorted result (inplace in original array)

4. Internal Memory Single Selection Randomized rank 8 random pivot Quickselect [Hoare 1961] partition 9 1 36 74 39 16 38 63 66 20 51 19 71 48 86 10 26 12 11 97 36 39 16 38 20 19 10 26 12 11 48 74 63 66 51 71 86 97 9 1 10 12 11 16 36 39 38 20 19 26 63 51 66 74 71 86 97 9 1 Expected time O(n) 9 20 19 26 36 39 38 51 63 74 71 86 97 1 10 12 11 10 11 12 19 20 36 39 38 71 74 38 39

5. Internal Memory Multiple Selection Randomized r1 r2 r3 r4 Multiple selection [Chambers 1971] Expected time O(n log2 q) for q queries Expected time [Prodinger 1995] 1 2 3 4 5 partition 9 1 36 74 39 16 38 63 66 20 51 19 71 48 86 10 26 12 11 97 36 39 16 38 20 19 10 26 12 11 48 74 63 66 51 71 86 97 9 1 10 12 11 16 36 39 38 20 19 26 63 51 66 74 71 86 97 9 1 9 20 19 26 36 39 38 51 63 74 71 86 97 1 10 12 11 10 11 12 19 20 36 39 38 71 74 O( + n) q+1 n i 38 39 = i=1 (query rank entropy) ilog2

6. Internal Memory Multiple Selection Deterministic + Multiple selection [Chambers 1971] Deterministic linear median pivots [Blum, Floyd, Pratt, Rivest, Tarjan 1973] Deterministic multiple selection [Dobkin, Munro 1981] optimal O( + n) time

7. [Frigo, Leiserson, Prokop, Ramachandran 1999] Internal Internal memory memory Cache Cache- -oblivious oblivious I/Os I/Os n Blog2 O(n / B) Cache-oblivious Optimal I/Os ? n BlogM/B O(n / B) n M n M O O Sorting Sorting O(n log2 n) Single Single selection selection O(n) Multiple Multiple selection selection O( + n) O(n / B + / B) O(n / B + / B / log2 M B) q+1 n i M B I/O = i=1 (query rank entropy) ilog2 CPU internal external Lower bound [Dobkin, Munro 1981] + [Arge, Knudsen, Larsen 1993] r1 r2 r3 r4 1 2 3 4 5 Upper bounds Randomized [ESA 2023] Deterministic [SWAT 2024] 9 1 36 74 39 16 38 63 66 20 51 19 71 48 86 10 26 12 11 97

8. Cache-aware Multiple Selection Randomized r2 r1 r4 r3 multi-way partition 45 23 20 28 66 40 38 2 22 61 54 59 32 6 97 92 81 57 69 55 95 42 43 78 48 90 65 3 53 15 64 33 85 80 52 3 15 33 38 45 40 42 43 48 66 61 54 59 57 55 65 53 64 52 69 97 92 81 95 78 90 85 80 23 20 28 2 22 32 6 recurse recurse Pick (M/B) random pivots and distribute to buckets Recurse on buckets with queries ( la Chambers) Expected optimal O(n / B + / B / log2 M B) I/Os

9. Cache-aware Multi-way Partition Deterministic n/k next batch 45 23 20 28 66 40 38 2 22 61 54 59 32 6 97 92 81 57 69 55 95 42 43 78 48 90 65 3 53 15 64 33 85 80 52 current buckets and pivots 28 45 30 38 54 32 55 57 23 20 2 22 6 66 61 59 97 92 81 69 Goal Goal : k = (M/B) buckets each of size [n/k, 2n/k] Repeatedly distribute batches of n/k elements into buckets (initially one) Split overflowing buckets (> 2 n/k elements; at most 3n/k) [using Blum et al. median finding algorithm; median new pivot] Distribution sort : On BlogM/B Multiple selection : O(n / B + / B / log2 [Hu, Tao, Yang, Zhou 2014] achieved both I/O and work optimality n M I/Os and O(n log n) internal work M B) I/Os Distribution sort

10. [Frigo, Leiserson, Prokop, Ramachandran 1999] Cache-oblivious Funnelsort Deterministic sorted output k-merger Tall cache assumption M B1+ Neccessary [Brodal, Fagerberg 2002] Binary mergesort with buffered output buffer size k (1/ ) k-merger k-merger , k = n ( ) n BlogM/B n M I/Os O k recursively sorted input streams of size n/k

11. Cache-oblivious Multiple Selection Idea unsorted elements sorted ranks Reverse computation of k-merger k-partitioner algorithm la Chambers k-partitioner pivot Challenges Pivots ? Pruning subtree computations before knowning ranks of pivots ?

12. [Brodal, Wild 2023] Cache-oblivious Multiple Selection Randomized unsorted elements sorted ranks Sort n / log n size sample Select k = n ( ) pivots uniformly in sample Estimate pivot ranks within n2/3 w.h.p. Prune inside k-partitioner subtrees w.h.p. no query Buckets just sort Expected O(n / B + / B / log2 k-partitioner pivot M B) I/Os

13. [Brodal, Wild 2024] Cache-oblivious Multiple Selection Deterministic Entropy bound sort sort Otherwise, small k n ( ) Prune buckets with no query n/2 elements pruned Recurse on buckets Pivots deterministically Incremental batches of size n/k Split bucket + rebuild k-partitioner O(n / B + / B / log2 k = n/ = min{ i| j i j n/2} unsorted elements sorted ranks k-partitioner pivot M B) I/Os

14. Summary Optimal O(n / B + / B / log2 M B) I/Os