File ListRanking.h

↰ Parent directory (ADS/external)

The ranking of a list, the distance of each item from the tail, in the memory and in the two-level memory [see File TwoLevelMemory.h], following chapter 4 of the notes.

Definition (ADS/external/ListRanking.h)

Detailed Description

A list of n items is the vector succ of their successors, the items being 0 , … , n - 1 and the tail t the only one with succ[ t ] = t.

  • listRank() is the sequential algorithm: the predecessors, then a walk back from the tail, O( n ) time, but up to one I/O per item on the disk, since the links jump anywhere.

  • listRankPointerJumping() is the parallel algorithm of Wyllie: every item at once adds the rank of its successor to its own and jumps to the successor of its successor, so that the rank of i is the distance between i and its current successor; :math:` lceil log_2 n rceil ` rounds, :math:` O( n log n ) ` operations (Lemma 4.1).

  • parallelStep() simulates one parallel step :math:` A[ a_i ] leftarrow op( A[ a_i ] , A[ b_i ] ) ` on the disk by two sorts and three scans (Theorem 4.1): the triples :math:` langle a_i , b_i , cdot rangle ` sorted by :math:` b_i , filled in by a scan of A, sorted back by :math: a_i ` and applied by a second scan of A; any parallel algorithm of T steps on n processors becomes :math:` tilde O( ( n / B ) T ) ` I/Os (Theorem 4.3, of Chiang et al.). externalPointerJumping() is the algorithm of Wyllie so simulated, the rank and the successor carried in one record, :math:` tilde O( ( n / B ) log n ) ` I/Os (Theorem 4.2).

  • The divide and conquer of section 4.3 removes an independent set I (no item of I is the successor of another one of I), letting the predecessors of its items jump over them, ranks the shorter list and puts the items of I back, each one adding the rank of its successor. randomIndependentSet() tosses a coin per item and takes the heads whose successor shows tails, n / 4 items on average; deterministicCoinTossing() is the technique of Cole and Vishkin: the colors start as the distinct indices and each round replaces the color of i by :math:` 2 pi + z , :math: pi ` the lowest bit where it differs from the color of the successor and z that bit of i (the tail compares with its bit 0), so that adjacent colors stay different while b bits become :math:` lceil log_2 b rceil + 1 , down to six colors in :math: log^* n ` rounds, and three by recoloring 5, 4 and 3; independentSetOfColors() takes the local minima, at least about n / 4 items. listRankIndependentSet() is the recursion in the memory with either set, and externalListRank() is the same recursion on the disk with the random coins, each step a join of records by sorts and scans, :math:` T( n ) = tilde O( n / B ) + T( 7 n / 8 ) = tilde O( n / B ) ` I/Os (Theorem 4.5; the coins are tossed again until :math:` | I | geq n / 8 `, which happens after O( 1 ) attempts on average), the list in memory once it fits.

Compared with the literature: the optimal parallel rankings of Cole and Vishkin and of Anderson and Miller reach O( n ) operations in O( log n ) time by the same independent sets; on the disk the bound :math:` Theta( mathrm{sort}( n ) ) ` of Chiang et al. is optimal, and is what externalListRank() attains, while the deterministic recursion on the disk would repeat the joins of the coins :math:` log^* n ` times per level, and is here only in the memory. The records of the disk are atomic items of the model.

The contracts [see File Contract.h]: succ is a list, one tail and every item reached from the only head, an audit; the ops of a parallel step have distinct destinations and the indices are in A, an audit; the colors of adjacent items differ and the independent sets are independent, audits; the files share the memory, which is at least 3 B, and the outputs are empty. The functions are defined in ListRanking.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 4

    1. Wyllie, The complexity of parallel computations, PhD thesis, Cornell University, 1979

  1. Cole, U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70(1), 32-53, 1986, doi:10.1016/S0019-9958(86)80023-7

    1. Anderson, G. L. Miller, Deterministic parallel list ranking, Algorithmica 6, 859-868, 1991, doi:10.1007/BF01759076

Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, J. S. Vitter, External-memory graph algorithms, Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 139-149, 1995

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions