\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,math-envs,enumerate,xspace,theorem,fullpage,epsfig}
\usepackage{latin-abbrevs}
%\setlength{\parindent}{6pt}
%\setlength{\parskip}{12pt}

\title{Functional Set Operations with Treaps}
\author{Dan Blandford and Guy Blelloch\\
Computer Science Department\\
Carnegie Mellon University\\
Pittsburgh, PA  15213\\[.05in]
{\tt \{blandford,blelloch\}@cs.cmu.edu}}

\newcommand{\ignore}[1]{}
\newcommand{\comment}[1]{{$\clubsuit$ \sf #1}}
\renewcommand{\floatpagefraction}{.75}

\newcommand{\plines}{{$\mathbf{\big{|}\,\big{|}}$}}
\newcommand{\cif}{{\bf if\ }}
\newcommand{\cthen}{{\bf then}}
\newcommand{\celse}{{\bf else\ }}
\newcommand{\cnot}{{\bf not\ }}
\newcommand{\cand}{{\bf and\ }}
\newcommand{\corr}{{\bf or\ }}
\newcommand{\tand}{{\rm \ and\ }}
\newcommand{\tor}{{\rm \ or\ }}
\newcommand{\creturn}{{\bf return\ }}
\newcommand{\cunion}{{\sc union}}
\newcommand{\csplit}{{\sc split}}
\newcommand{\cjoin}{{\sc join}}
\newcommand{\csplitlr}{{\sc splitLR}}
\newcommand{\ctoltreap}{{\sc toLTreap}}
\newcommand{\ctolrtreap}{{\sc toLRTreap}}
\newcommand{\cjoinlr}{{\sc joinLR}}
\newcommand{\csplitleft}{{\sc splitLeft}}
\newcommand{\csplitright}{{\sc splitRight}}
\newcommand{\cjoinleft}{{\sc joinLeft}}
\newcommand{\cposinf}{{\sc positive\_infinity}}
\newcommand{\cneginf}{{\sc negative\_infinity}}

\newcommand{\sumik}{\sum_{i=1}^k}
\newcommand{\oklg}{O(k\lg(\frac{n}{k}+1))}

\input{code-env.tex}

\begin{document}

\maketitle

\input{intro.tex}

\section{Definitions}
\paragraph{The Block Metric.}
\label{sec:blockmetric}

Carlsson, Levcopoulos, and Petersson \cite{CLP90} define the Block Metric
measure of the presortedness of two lists as follows:

\begin{definition}
Let $X$ and $Y$ be two sorted sequences of length $n$ and $m$,
respectively, and let $Z = <z_1, ..., z_{n+m}>$ be the resulting merged
sequence.  Then

$$
Block(X, Y)=||\{i | 1 \le i < n + m \tand
z_i \in X \tand z_{i+1} \in Y \tor
z_i \in Y \tand z_{i+1} \in X\}|| + 1
$$
\end{definition}

Thus $Block$ measures the number of blocks in the input sequences that
appear in the merged sequence.  Note that, if $X$ and $Y$ share some
elements, those elements will appear multiple times in $Z$ and will be
counted as belonging to both lists.  For example, if $X = \{1, 2\}$ and 
$Y = \{2, 3, 4\}$ then $Z = \{1, 2, 2, 3, 4\}$.  Thus $z_2 \in X$ and
$z_2 \in Y$, and $Block(X, Y) = 4$.  In other words, any duplicate
element is considered to belong to a block of its own.

Carlsson et al. showed that a lower bound for the list merging problem is
$\oklg$, where $k=Block(X,Y)$.  We will present sequential set-operation
algorithms that meet that bound in Section \ref{sec:serialmerge} and
parallel algorithms that meets that bound in Section
\ref{sec:parallelmerge} and Appendix \ref{sec:intdiff}.  First, though, we
must develop the appropriate data structures.

\paragraph{Treaps.}

\input{treapcodefig}

A treap is a balanced tree in which each key has an associated random
priority \cite{Aragon89}.  In addition to the standard binary-tree
ordering of the keys, a treap maintains the invariant that every parent
has a higher priority than either of its children.  When both the keys and
priorities in a treap are unique, there is a unique treap containing those
keys and priorities, independent of the order in which those keys were
inserted. 

We use two operations to manipulate treaps.  The first operation, \csplit,
takes a treap $T$ and a key $v$, and returns a triple ($T_1$, $v'$,
$T_2$), such that all keys in $T_1$ are less than $v$, all keys in $T_2$
are greater than $v$, and $v'$ is a duplicate of $v$ if $v$ was in $T$.   
The second operation, \cjoin, takes two treaps $T_1$ and $T_2$ such that  
all keys in $T_1$ are less than any key in $T_2$.  It returns a single
treap $T$ containing the keys in $T_1 \cup T_2$.  Both of these
operations run in $O(\log(n))$ expected work.  Code for these operations
is shown in Figure \ref{fig:treapcode}.

Seidel and Aragon showed two properties of treaps which we will make use
of in this paper.  First, they showed that the expected depth of a treap
of size $n$ is $O(\log(n))$.  Second, they showed the Finger Search
property: if two keys in a treap are separated by $d$ other keys, then the
expected length of the path between them is $O(\log(d))$.  These
properties will be useful in proving bounds on our algorithms.

\paragraph{Biased and Unbiased Treaps.}

Since all of the priorities in a treap $T$ are drawn from the same
distribution, any key in a treap has an equal chance to be the root.  When
we split a treap $T$ on a key $v$, if we have not looked at $T$ beforehand
then we know nothing about the priorities of the keys in the resulting
treaps $T_1$ and $T_2$.  Thus those priorities are still random, and so
all of the properties of treaps still hold for $T_1$ and $T_2$.  We say
that such a treap is \emph{unbiased}.

\begin{definition}
A treap is \emph{unbiased} if the priorities of each of its keys are drawn
from the same distribution.  (That is, the priorities are identically and
independently distributed.)
\end{definition}

However, if we look at the priorities in $T$ before choosing our split, we
have to be careful not to introduce bias into the result.  For example, if
we use a rule in which we always split $T$ on the rightmost possible key
which is still to the left of the root, then the root of our result treap
$T_2$ will always be the leftmost element of that treap.  In our analysis
we can assume that the initial input treaps to our algorithms are
unbiased, but whenever we choose where to split a treap based on knowledge
of its priorities we will need to show that the result is unbiased before
making any assumptions about its balance.  This will prove important in
the analysis of our parallel union algorithm in Section
\ref{sec:analysis}. \label{sec:bias}

\section{The Left Spinal Treap}

\begin{figure}
 \begin{center}
  \epsfig{file=figures/ltreap.eps}
  \caption{An LTreap is a Treap in which the pointers along the left
spine are flipped.  \label{fig:ltreap}}
 \end{center}
\end{figure}

The first new data structure we define is the left spinal treap,
abbreviated LTreap.  An LTreap is a treap in which the pointers along the
left spine are flipped---that is, each node on the left spine has a
pointer to its right child and a pointer to its parent.  (We present an
example in Figure \ref{fig:ltreap}.)  We maintain a handle into the
structure at the leftmost node, and all searches in the structure start
from that node.  

We use four functions to manipulate our LTreap data structures.  The first
function, {\sc toLTreap}, converts a standard treap into an LTreap;  the
second, {\sc fromLTreap}, converts an LTreap into a Treap.  The third
function, {\sc joinLeft}, joins a Treap onto an LTreap provided that the
largest key in the Treap is less than the smallest key in the LTreap.  The
fourth function, {\sc splitLeft}, splits an LTreap on a given key $v$.  It
returns a triple consisting of a Treap containing keys less than $v$, the
key $v$ if it was found, and an LTreap containing keys greater than $v$.
Pseudocode for these functions can be found in Figure \ref{fig:ltreapcode}.

For convenience, throughout our pseudocode we will use $T$, $T'$, $T_1$,
etc, to refer to Treaps, and $L$, $L'$, $L_1$, etc, to refer
to LTreaps.

We need to analyze the work required for these algorithms.  \ctoltreap~and
{\sc fromLTreap}~touch only the nodes along the left spine of the treap; 
the left spine of a treap contains expected $O(\log(n))$ nodes, so the
expected work required for these algorithms is $O(\log(n))$.

Our \csplitleft~algorithm touches only the nodes on the path from the
leftmost node in the LTreap to the predecessor of $v$ in that LTreap.  If
there are $d$ nodes which are less than $v$ in the LTreap, then that path
has length $O(\log(d))$, so the expected work required for \csplitleft~is
$O(\log(d))$. 

Using \cjoinleft~requires the same amount of work as is needed by
\csplitleft~to split the result into back into its components.  Thus the
expected work needed for \cjoinleft~is $O(\log(d))$ where $d$ is the
number of nodes to the left of the split---that is, the number of nodes in
the Treap. 

We can also define a ``Right Spinal Treap'' (RTreap), which is just
like an LTreap except that the pointers are flipped along the right spine
rather than the left.

\input{ltreapcodefig}

\paragraph{Sequential Set Operations.}
\label{sec:serialmerge}

As an example of how we can use the LTreap we present sequential
algorithms which perform the set operations (See Figure
\ref{fig:serialunioncode}).  Each of our algorithms uses one split and one
join on each block in the input.  Using split and join on a given block
costs at most $O(\log(s))$ expected work where $s$ is the size of that
block.  Thus the total work is $O(\sumik \log(s_i))$.  The logarithm is
convex, so in the worst case each block is the same size and the work is
$\oklg$ where $k=Block(L_1,L_2)$, which is optimal. 

We can also use our LTreap data structures to implement the algorithm of
Demaine et al. \cite{Demaine00} for finding the union of multiple
sets.  This simplifies the code somewhat---we can construct the data 
structure at the same time as we locate the blocks, rather than
performing the two tasks in separate phases.  Pseudocode is shown in
Figure \ref{fig:multiunioncode}, in the Appendix.

Unfortunately, these algorithms do not parallelize.  To create
parallelizable algorithms we need a data structure that allows some
form of divide-and-conquer. 

\input{sequentialcodefig}

\section{The LRTreap}

We have defined data structures which permit finger searches from either
the left or the right sides.  We will now create a data structure which
combines the two types, allowing finger searches from either side.  This
data structure, called an LRTreap, is represented by a triple ($L$, root,
$R$) where $L$ is an LTreap containing the keys to the left of the root,
and $R$ is an RTreap containing the keys to the right.  We can convert an
LRTreap to a standard treap or vice versa in $O(\log(n))$ expected time
just by traversing the spines.  In our pseudocode we refer to LRTreaps
using the variable $\Upsilon$. 

We define two operations, \csplitlr~and \cjoinlr, which can be used on
LRTreaps.  \csplitlr\  is a function which splits an LRTreap on a given
key, producing two LRTreaps.  It works by testing the key against the root
and then calling either {\sc splitLeft}~or {\sc splitRight}~as
appropriate. \cjoinlr~ does the opposite---it joins two LRTreaps into one
by converting one of them to a standard treap and calling either {\sc
joinLeft}~or {\sc joinRight}.  Pseudocode for these operations can be
found in Figure \ref{fig:lrtreapcode}, in the Appendix. 

Henceforth, when discussing a specific key $v$, we will denote the number
of keys less than $v$ by $a$ and the number of keys greater than $v$ by
$b$.  We wish to show that the \csplitlr~operation requires
$O(\log(\min(a,b)))$ expected work.

We know that, if nodes $v$ and $v'$ are separated in a treap by $d$ nodes,
then the expected distance from $v$ to $v'$ is $O(\log(d))$. 
Unfortunately, our algorithm may not always be able to take the shorter
path to the target key because it cannot search along any path that
includes the root.  The bound still holds, however:

\begin{theorem}
The expected work required to split an LRTreap on a key $v$ is
$O(\log(\min(a,b)))$. 
\label{th:searchtime}
\end{theorem}

\begin{proof} 
There are three possibilities, depending on where in the treap the
root is.  

First, the root could be to the left of $v$.  This occurs with
probability $(a/n)$, and the expected work required to find $v$ is
$O(\log(b))$.

Similarly, the root could be to the right of $v$.  This occurs with
probability $(b/n)$, and the expected work required to find $v$ is
$O(\log(a))$. 

Lastly, $v$ could be the root.  In this
case, we have to convert the whole LRTreap into a standard treap, perform
the operation, and convert it back, which takes $O(\log(a+b))$ work.
Fortunately, this only happens with probability $(1/n)$. 

So the total expected work to find $v$ is

$$
O\Big{(}\frac{a\log(b)+b\log(a)+\log(a+b)}{n}\Big{)}
$$

But when $a<b$, $a\log(b)<b\log(a)$ and $\log(a+b)<b$, so this
is equivalent to $O(b\log(a)/n)$, which is $O(\log(a))$.  Likewise, when
$b<a$, this is equivalent to $O(\log(b))$.  Thus the total expected work
is $O(\log(\min(a,b)))$.  
\end{proof}

Joining two LRTreaps $\Upsilon_1$ and $\Upsilon_2$ (where all
keys in $\Upsilon_1$ are less than all keys in $\Upsilon_2$) requires
touching no more nodes than would be required to split them apart after
they were joined.  Thus this bound applies to the join operation as well. 

Likewise, we can use \csplitlr~and \cjoinlr~ to implement search, insert,
and delete functions, so the work bounds for \csplitlr~and \cjoinlr~also
apply to these functions. 

We note that the code as shown in Figure \ref{fig:lrtreapcode} makes two
passes along the spines of the smaller LRTreap.  A more practical
implementation could gain a constant factor of efficiency by merging those
two passes into one. 

\section{Set Operations: Union}
\label{sec:parallelmerge}

\begin{figure}
 \begin{center}
  \psfig{figure=figures/merge.eps,height=1.5in}
  \caption{The four steps of our algorithm: split $\Upsilon_2$, split
$\Upsilon_1$, recurse, rejoin.\label{fig:merge}}
 \end{center}
\end{figure}

We now turn our attention to the problem of computing the union of the
elements of two treaps in parallel.  Given two sorted sets of keys
represented by LRTreaps, we wish to find an LRTreap containing the union
of the two sets.

Our algorithm is illustrated in Figure \ref{fig:merge}, and can be
described in four steps. Given two LRTreaps $\Upsilon_1$ and $\Upsilon_2$,
with $\Upsilon_1$.root.priority $\ge \Upsilon_2$.root.priority, we first
split $\Upsilon_2$ on the root of $\Upsilon_1$.  We then split
$\Upsilon_1$ on the two keys of $\Upsilon_2$ that were nearest the
previous split.  This separates from $\Upsilon_1$ a maximal block
containing the root.  In the third step, we recursively compute the union
of the pieces of the two LRTreaps; and in the fourth step, we join the
results back together.

Pseudocode for our algorithm is shown in Figure \ref{fig:maincode}.  We
use a \plines~symbol to mark places where a new thread can be spawned to
deal with a recursive call.  Note that, should $\Upsilon_{2A}$ be empty
(that is, if the first split made is trivial), then {\sc
greatestValue}($\Upsilon_{2A}$) will return \cneginf~(see Figure
\ref{fig:gvcode}).  Thus $\Upsilon_{1A}$ will also be empty, and
\cunion($\Upsilon_{1A}$,$\Upsilon_{2A}$) will immediately return an empty
LRTreap.  A similar case applies if $\Upsilon_{2C}$ is empty---so the
possibility of trivial splits is handled without the necessity of checking
for them in the code. 

Note also that we never use the $v$, $v'$, and $v''$ values returned by
our calls to \csplitlr.  If one of those values is non-null, then it is a
duplicate key and can be safely discarded.

\input{unioncodefig}

\section{Analysis}
\label{sec:analysis}

In this section, all expectations are calculated over the random
assignment of priorities to keys in $\Upsilon$.

In Section \ref{sec:bias} we defined an ``unbiased'' treap to be one in
which all of the priorities are identically and independently distributed.
This is important, because our bounds on a treap's expected depth only
apply when the treap is known to be unbiased.  If we make decisions based
on the priorities of the keys in a treap, we may bias the structure.  For
example, suppose we adopt the rule that we always split a treap
immediately to the left of the highest-priority key in the structure.  One
of the result treaps would then be biased---the location of its root would
no longer be random.  Our parallel algorithm does make decisions based on
the priorities of the keys, and so we need to show that we do not cause
bias in the intermediate treaps.

How can we bound the bias introduced by our algorithm?  At any recursive
step, we decide which splits to make based only on the location of the
highest-priority root among the two LRTreaps.  We then use splits to
remove that root from future recursive steps.  This ensures that we do not
introduce bias: at any recursive step, every key is equally likely to be
the root. 

We formalize this property with the following definition:

\begin{definition}
An ``almost-unbiased'' split of an LRTreap is one which is chosen with no
knowledge about that LRTreap other than its root node.
\end{definition}

Almost-unbiased splits have an interesting property that we will make use
of in our analysis: 

\begin{lemma} 
\label{lm:cut} 
In an unbiased LRTreap $\Upsilon$ of size $n$, let $N$ be the number of
nodes visited by any almost-unbiased split.  If that split visits $N_{ns}$
non-spinal nodes and $N_s$ spinal nodes, then $E[N] \le 2E[N_{ns}]+1$. 
\end{lemma}

\begin{proof} Our \csplitleft~and \csplitright~algorithms visit nodes of two
categories: spinal nodes and non-spinal nodes.  They first travel up the
spine of $\Upsilon$ until they reach a place to begin the split; then,
they enter the interior of $\Upsilon$ and split the two LRTreaps apart. 
Thus we have $N = N_s+N_{ns}$. 

Consider any LRTreap $\Upsilon'$ that has been split off from $\Upsilon$
with an almost-unbiased split.  The split was chosen without regard for
the priorities of the keys in $\Upsilon'$, so all of those priorities now
are drawn from the same distribution.  Thus $\Upsilon'$ is unbiased, so
each of its spines has the same expected length, independent of the root
of $\Upsilon$.  We know that one of those spines contains exactly $N_s$
nodes;  the other spine contains at most $N_{ns}+1$ nodes.  (Some of the
non-spinal nodes involved in the split may have stayed in $\Upsilon$.  The
root of $\Upsilon'$, however, counts as a spinal node but still
contributes $1$ to the length of each spine of $\Upsilon'$.) Thus we have
$E[N_s] \le E[N_{ns}]+1$.  We know $E[N] = E[N_s]+E[N_{ns}]$, so we have
$E[N] \le 2E[N_{ns}]+1$. \end{proof}


We can now begin to analyze the work required by our algorithm.  To do
this we will need the following lemma:

\begin{figure}
 \begin{center}
  \epsfig{file=figures/path.eps,width=2.5in}
  \caption{The path (bold) connecting any $k$ leaves (squares) of a treap
to each other and to the root contains expected $\oklg$ nodes.}
 \end{center}
\end{figure}

\begin{lemma} 
\label{lm:path} 

Given any unbiased treap $T$, and given $k$ leaves of that treap, there is
a unique minimal set of nodes $P$ (called a ``path'')  which connects
those $k$ leaves to each other and to the root of $T$, and $E[\,|P|\,]$ is
$\oklg$.

\end{lemma}

\begin{proof} The path is unique because the treap is acyclic.  To show the size
of the path, we consider an algorithm which traverses exactly that path. 

Suppose that we take each of the $k-1$ leaves that the path touches and
finger-search for them in order starting from the root.  For each pair of
adjacent leaves the finger search will travel up the tree until it finds
the common ancestor of the two, then travel back down to the target leaf.
The first search takes $O(\log(n))$ expected work, and the rest take
$O(\log(d))$ expected time per search, where $d$ is the number of keys
separating two endpoints.  Thus the total work is $O(\log(n)+\sumik d_i)$. 
The logarithm is convex, so in the worst case all the spaces between the
endpoints will be equal, and the finger-search algorithm will take
expected time $\oklg$. 

The finger-searches described above touch exactly the nodes which are on
the path we describe, so there can be at most $\oklg$ of those nodes. \end{proof}

We can now state the following theorem:

\begin{theorem}

The expected work required for the \cunion~algorithm is $\oklg$, where $k
= Block(\Upsilon_1, \Upsilon_2)$ and $n=|\Upsilon_1|+|\Upsilon_2|$.

\label{th:time}
\end{theorem}

We defer the proof to Appendix \ref{sec:mainproof}.

\paragraph{Parallel Performance.}

We still need to consider the parallel performance of this algorithm.  We
can easily make our algorithm parallel by spawning separate threads for
each recursive call.  Since each call deals with a separate portion of the
LRTreap, each thread will read and write from a separate part of the
memory, so the algorithm will run on an EREW PRAM. 

We would like to analyze the depth of our algorithm.  Observe that, every
time the algorithm recurses, the root is cut out of one of the LRTreaps.
Thus the depth of the part of that LRTreap in the next recursion will be
one less.  That means that the sum of the depths of the LRTreaps decreases
at each recursion.  The expected depth of an LRTreap is $O(\log(n))$, so 
the depth of the recursion is $O(\log(n))$.

At each step of the recursion, the algorithm does at most $O(\log(n))$   
expected work, so the total depth of the algorithm is $O(\log^2(n))$.  To
map this onto an EREW PRAM we need to deal with load-balancing.  This can
be done with a primitive scan operation or by including the depth of a
scan in our time bound.

\section{Set Operations: Intersect and Difference}
\label{sec:intdiff}

With only slight modifications, we can also use our \cunion~algorithm
to find the intersection or difference of two sets.  Code, description
and analysis for these operations will be included in the final
version of our paper.

\section{Future Work}

One interesting avenue for future work would be to improve the parallel
depth of this algorithm.  Suppose we let $n$, $m$ be the sizes of the two
inputs, with $n \ge m$.  At present our algorithm always chooses the
higher-priority root among the two treaps for the first split.  This
results in a parallel depth of $O(\log^2(n))$.  If instead we let our
algorithm choose the lower-priority root, then the recursive call depth
drops to $O(\log(m))$, so the total depth drops to $O(\log(n)\log(m))$. 
Unfortunately, this leads to the intermediate treaps becoming biased,
which violates our work bound for this algorithm.  If we use Kaplan and
Tarjan's structure, though, bias ceases to be a problem, and the
modification we described above will work.

\bibliographystyle{abbrv}
\bibliography{/afs/cs/project/scandal/papers/bib/main,mergetree}

\appendix
\newpage

\section{Proof of Theorem \ref{th:time}}
\label{sec:mainproof}
\input{mainproof}

\input{discussion}
\input{implementation}

\input{multiunion}
\input{lrtreapcodefig}

\end{document}
