Buckets

Explot indirect addresssing in RAM model.

review shortest path algorithm.

In shortest paths, often have edge lengths small integers (say max $C$).

Observe heap behavior:

• heap min increasing (monotone property)
• max $C$ distinct values
• (because don't insert $k+C$ until delete $k$).

Idea: lots of things have same value. Keep in buckets.

How to exploit?

• standard heaps of buckets. $O(m\log C)$ (slow) or $O(m+n\log C)$ with Fib (messy).
• Dial's algorithm: $O(m+nC)$.
• in fact, $O(m+D)$ for max distance $D$

space?

• use array of size $C+1$
• wrap around

Can we improve this?

• where are we wasting a lot of effort?
• scanning over big empty regions
• can we arrange to leap whole regions?
• some kind of summary structure?

2-level buckets.

• make blocks of size $b$
• add layer on top: $nC/b$ block summaries
• in each summary, keep count of items in block
• insert updates block and summary: $O(1)$
• ditto decrease key
• delete min scans summaries, then scans one block
  • over whole algorithm, $nC/b$ scanning summaries
  • also, scan one block per delete min: $b$ work
  • over $n$ delete mins, work $nb+nC/b$
  • balance, optimize with $b=\sqrt{C}$
• result: SP in $O(m+n\sqrt{C})$
• as before “space trick” to keep array sizes to $C$
• if know $D$ (or binary search for it) make bucket size $\sqrt{D/n}$ and get $O(m+\sqrt{nD})$
• Generalize: 3 tiers?
  • blocks, superblocks, and summary
  • block size $C^{1/3}$
  • runtime $O(m+nC^{1/3})$
  • how far can this go? To $m+n$? no, because insert cost rises.

Tries.

• depth $k$ tree over arrays of size $\Delta$
• range $C$ (details of reduction from $nC$ omitted)
• expansion factor $\Delta=(C+1)^{1/k}$ (power of 2 simplifies)
• insert: $O(k)$ (also find, delete-non-min, decrease-key)
• delete-min: $O(k\Delta)=O(kC^{1/k})$ to find next element
• Shortest paths: $O(km+knC^{1/k})$
• Balance: $nC^{1/k}=m$ so $C=(m/n)^k$ so $k=\log(C)/\log(m/n)$
• Runtime: $m\log_{m/n}(C)$
• Space: $k\Delta=kC^{1/k}=km/n\le (m/n)\log C$ using circular array trick.

Problems: space and time

Idea: be lazy! (Denardo and Fox 1979)

• don't push items down trie until you must
• unique block (array) on each level active
• keep other stuff piled up in buckets in each level
• keep count of items in (buckets of) each level (not counting below)
• only expand bucket when needed (and update level counts)

Operations:

• Insert
  • walk item down tree till stop in (inactive) bucket or bottom
  • increment level count
  • $O(k)$ work
• Decrease key
  • Remove from current bucket
  • put in proper bucket
  • maybe descend (and revise level counts)
  • new bucket must be a prior sibling since monotone
    • so bucket exists
    • and no higher levels need be touched
• amortization:
  • items descend once per touch, but never rise,
  • (critically relies on monotone property)
  • so $k$ expansion per item
  • alternatively, consider “potential” as “total heights of items”
  • inserting at top adds $k$ potential
  • then all descents are free
• Delete-min
  • remove item, update bottom level count
  • advance to new min
    • rise to first nonempty level
    • traverse to first nonempty bucket
    • expand till find min
  • time:
    • pushdowns are accounted for in insert cost
    • identifying min happens during pushdowns
    • rise to nonempty bucket costs less than pushdowns from it
    • so, cost to scan only one block
  • cost $C^{1/k}$
• space to $kC^{1/k}$
• Times:
  • $O(k)$ insert (charge expansions to insert)
  • $O(1)$ decrease key
  • $O(C^{1/k})$ delete-min
• paths runtime: $O(m+n(k+C^{1/k}))$, choose $k = 2\log C/\log \log C$: $O(m+n(\log C)/\log\log C)$
• great, even if e.g. $C=2^{32}$
• Further improvement: heap on top (HOT) queues get $O(m+n(\log C)^{1/3})$ time. Cherkassky, Goldberg, and Silverstein. SODA 97.
• Implementation experiments---good model for project

VEB

Van Emde Boas, “Design and Implementation of an efficient priority queue” Math Syst. Th. 10 (1977)

Thorup, “On RAM priority queues” SODA 1996.

Idea

• idea: in bucket heaps, problem of finding next empty bucket was heap problem. Recurse!
• $b$-bit words
• $\log b$ running times
• thorup paper improves to $\log\log n$
• consequence for sorting.

Algorithm.

• array of buckets but fast lookup on top.
• queue $Q$ on $b$ bits is struct
  • $Q.\min$ is current min, not stored recursively
  • Array $Q.low[]$ of $\sqrt{U}$ queues on low order bits in bucket
  • $Q.high$, vEB queue on high order bits of elements other than current min in queue
• Insert $x$:
  • if $x < Q.\min$, swap
  • now insert $x$ in recursive structs
  • expand $x=(x_h,x_l)$ high and low half words
  • If $Q.low[x_h]$ nonempty, then insert $x_l$ in it
  • else, make new queue holding $x_l$ at $Q.low[x_h]$, and insert $x_h$ in $Q.high$
  • note two inserts, but one to an empty queue, so constant time
• Delete-min:
  • need to replace $Q.\min$
  • Look in $Q.high.\min$. if null, queue is empty.
  • else, gives first nonempty bucket $x_h$
  • Delete min from $Q.low[x_h]$ to finish finding $Q.\min$
  • If results in empty queue, Delete-min from $Q.high$ to remove that bucket from consideration
  • Note two delete mins, but second only happens when first was constant time.

Problem: space

• need constant time hash table.
• non-trivial complexity theory,
• but can manage with randomization or slight time loss.