From 12e0112fbab389a8aa78abbfedb763afe0e27f1d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 16:35:59 +0200 Subject: [PATCH] Intro to RAM data structures improved. --- PLAN | 2 -- adv.tex | 3 +-- biblio.bib | 35 +++++++++++++++++++++++++++++++++++ mst.tex | 2 +- ram.tex | 44 ++++++++++++++++++++++++++++---------------- 5 files changed, 65 insertions(+), 21 deletions(-) diff --git a/PLAN b/PLAN index 3967d5d..2c44db9 100644 --- a/PLAN +++ b/PLAN @@ -74,8 +74,6 @@ Related: Models: - bit tricks: reference to HAKMEM -- mention in-place radix-sorting? -- consequences of Q-Heaps: Thorup's undirected SSSP etc. - add more context from thorup:aczero, also mention FP operations - Tarjan79 is mentioned by Pettie to define Pointer machines - add references to the C language diff --git a/adv.tex b/adv.tex index 104a814..3f1ae00 100644 --- a/adv.tex +++ b/adv.tex @@ -265,8 +265,7 @@ to minor-closed classes. %-------------------------------------------------------------------------------- -\section{Using Fibonacci heaps} -\id{fibonacci} +\section{Iterated algorithms}\id{iteralg}% We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time. Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci} diff --git a/biblio.bib b/biblio.bib index 7f6107f..f6f5aa1 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1432,3 +1432,38 @@ year={1998}, publisher={Springer} } + +@article{ thorup:usssp, + title={{Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time}}, + author={Thorup, Mikkel}, + journal={Journal of the ACM}, + volume={46}, + number={3}, + pages={362--394}, + year={1999} +} + +@article{ thorup:sssp, + author = {Mikkel Thorup}, + title = {Integer priority queues with decrease key in constant time and the single source shortest paths problem}, + journal = {Journal of Computer and System Sciences}, + volume = {69}, + number = {3}, + year = {2004}, + issn = {0022-0000}, + pages = {330--353}, + doi = {http://dx.doi.org/10.1016/j.jcss.2004.04.003}, + publisher = {Academic Press, Inc.}, + address = {Orlando, FL, USA}, +} + +@inproceedings{ hagerup:sssp, + author = {Torben Hagerup}, + title = {Improved Shortest Paths on the Word RAM}, + booktitle = {ICALP '00: Proceedings of the 27th International Colloquium on Automata, Languages and Programming}, + year = {2000}, + isbn = {3-540-67715-1}, + pages = {61--72}, + publisher = {Springer-Verlag}, + address = {London, UK}, +} diff --git a/mst.tex b/mst.tex index 929f783..2cfe5d0 100644 --- a/mst.tex +++ b/mst.tex @@ -439,7 +439,7 @@ From this, we can conclude: Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$. \rem -We will show several faster implementations in section \ref{fibonacci}. +We will show several faster implementations in section \ref{iteralg}. \paran{Kruskal's algorithm}% The last of the three classical algorithms processes the edges of the diff --git a/ram.tex b/ram.tex index 9b0084a..27e0222 100644 --- a/ram.tex +++ b/ram.tex @@ -505,38 +505,50 @@ roles in Sections \ref{verifysect} and \ref{optalgsect}. \section{Data structures on the RAM} \id{ramdssect} -There is a~lot of data structures designed specifically for the RAM, taking -advantage of both indexing and arithmetics. In many cases, they surpass the known -lower bounds for the same problem on the~PM and they often achieve constant time +There is a~lot of data structures designed specifically for the RAM. These structures +take advantage of both indexing and arithmetics and they often surpass the known +lower bounds for the same problem on the~PM. In many cases, they achieve constant time per operation, at least when either the magnitude of the values or the size of the data structure are suitably bounded. -A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt}, -which represent a~subset of the integers $\{0,\ldots,U-1\}$, allowing insertion, +A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt} +which represent a~subset of the integers $\{0,\ldots,U-1\}$. They allow insertion, deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$, regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$, -where $w_{max}$ is the maximum weight. We will show later that it is even -possible to achieve linear time complexity for arbitrary integer weights. +where $w_{max}$ is the maximum weight. -A~real breakthrough has been made by Fredman and Willard, who introduced -the Fusion trees~\cite{fw:fusion} which again perform membership and predecessor -operation on a~set of $n$~integers, but this time with complexity $\O(\log_W n)$ +A~real breakthrough has been however made by Fredman and Willard who introduced +the Fusion trees~\cite{fw:fusion}. They again perform membership and predecessor +operation on a~set of $n$~integers, but with time complexity $\O(\log_W n)$ per operation on a~Word-RAM with $W$-bit words. This of course assumes that each element of the set fits in a~single word. As $W$ must at least~$\log n$, -the operations take $\O(\log n/\log\log n)$ and we are able to sort $n$~integers +the operations take $\O(\log n/\log\log n)$ time and thus we are able to sort $n$~integers in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and faster sorting algorithms, culminating with the work by Thorup and Han. They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort} and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort}, both in linear space. -Despite the recent progress, the corner-stone of most RAM data structures -is still the representation of data structures by integers introduced by Fredman -and Willard. It will also form a~basis for the rest of this chapter. - -\FIXME{Add more history.} +The Fusion trees themselves have very limited use in graph algorithms, but the +principles behind them are ubiquitious in many other data structures and these +will serve us well and often. We are going to build the theory of Q-heaps in +Section \ref{qheaps}, which will later lead to a~linear-time MST algorithm +for arbitrary integer weights in Section \ref{iteralg}. Other such structures +will help us in building linear-time RAM algorithms for computing the ranks +of various combinatorial structures in Chapter~\ref{rankchap}. + +Outside our area, important consequences of these data structures include the +Thorup's $\O(m)$ algorithm for single-source shortest paths in undirected +graphs with positive integer weights \cite{thorup:usssp} and his $\O(m\log\log +n)$ algorithm for the same problem in directed graphs \cite{thorup:sssp}. Both +algorithms have been then significantly simplified by Hagerup +\cite{hagerup:sssp}. + +Despite the progress in the recent years, the corner-stone of all RAM structures +is still the representation of combinatorial objects by integers introduced by +Fredman and Willard. It will also form a~basis for the rest of this chapter. %-------------------------------------------------------------------------------- -- 2.39.2