\begin{abstract}
\setcounter{page}{0}

Purely functional algorithms have the advantages of leading to full
persistence of all partial results, being easier to parallelize, and
being easier to formally analyze.  We present sequential and parallel
functional algorithms for computing the union, intersection and
difference of ordered sets using a variant of random balanced binary
search trees (treaps).  The algorithms are optimal with respect to the
Block Metric bound of Carlsson et al..  In particular for two sets of
length $n$ and $m$, with $m \leq n$, the algorithms run in $\oklg$
expected work, where $k$ is the least possible number of blocks that
we can break the two lists into before reforming them into one list.
The expected parallel depth of the parallel algorithms is
$O(\log^2(n))$.  The sequential bounds can also be achieved using the
purely functional catenable list data structures suggested by Kaplan
and Tarjan.  However, we believe our are structure is significantly
simpler---it only involves reversing the spines of a standard treap.
We also present experimental results that analyze the constant factors
involved in the algorithm.

A full implementation of our algorithms is available on the web at \\
\verb|http://www.cs.cmu.edu/~pscico/fingertrees.html| in both JAVA and SML.

\end{abstract}

\newpage
\section{Introduction}

A purely functional algorithm is one that involves no side effects,
\ie~ no overwriting of existing data.  Such algorithms have several
advantages over imperative (side-effecting) algorithms, including the
strongest form of persistence (data can never be overwritten), a more
direct path to parallelism (independent threads cannot interact
through memory writes), and a much better chance of formally or
automatically reasoning about them.  The purely functional model,
however, is provably less powerful than imperative model~\cite{Pip97},
and it is not well understood what problems can be solved in the
functional model with the same bounds as in the imperative model.  To
better understand the power of functional programs, there has been
significant recent interest in developing efficient purely functional
algorithms, both in the
sequential~\cite{Okasaki95,Kaplan95,Kaplan96,Okasaki98,BBCHMW01} and
in the parallel~\cite{ppa96,Blelloch98} context.  We note that
although purely functional algorithms are typically discussed in the
context of languages that are considered functional, such as ML or
Haskell, these algorithms can also be programmed in languages that are
considered imperative, such as JAVA.

In this paper we are interested in implementing set operations (union,
intersection and difference) using purely functional algorithms.  As
motivation for this interest, consider the following application to
search engines.  Almost all search engines use an ``inverted-lists''
structure for storing the mapping of terms to documents~\cite{WMB99}.  This
structure is simply a collection of ``lists'', one for each term in
the database, and each list contains all the documents in which that
term appears.  Abstractly each list is better thought of as a set
since the order has no importance.  When a query is made
involving and expression of AND and ORs on terms, this can be
translated to intersections and unions on the corresponding sets
(set difference can be used for ANDNOT queries).  It is well known
that these set operations can be implemented in time that is sublinear
in the sum of the input sizes.  Brown and Tarjan showed that merging
two lists $X$ and $Y$ of size $n$ and $m$ (with $n \ge m$) takes $O(m
\lg(\frac{n}{m}+1))$ comparisons using AVL trees
to represent the lists~\cite{merge79}.  Assuming a total order on the
set elements, it is not hard to extend the results to implement set
union, intersection and difference in the same bounds.  This sublinear
time is particularly important when one list is much longer than the
other, which happens frequently in practice (consider the query ``red
AND coeloglossum'').

The imperative algorithm of Brown and Tarjan modifies its input---it
inserts the elements from one list into the other.  This is clearly
undesirable in the suggested application since it will destroy the
original term lists, which presumably need to be reused.  Copying the
inputs before the operation is not efficient since the set operations
take sublinear time.  If the set operations can be implemented purely
functionally, however, the result set will share data with the input
without modifying the input (the operations are fully persistent).
This would not only save the original set for each term, but it would
allow caching of partial results.  Figure~\ref{fig:search} shows
an example of such caching.

\begin{figure}[b]
 \begin{center}
  \epsfig{file=figures/search.eps,width=4in}
 \end{center}
  \caption{An example set of searches that reuse the
cached result ``orchid or rose''.   The numbers are 
the approximate size of each set based on the AltaVista search engine.}
 \label{fig:search}
\end{figure}

For general inputs, the $O(m \lg(\frac{n}{m}+1))$ bound is a lower
bound for the list merging problem.  If we make some assumptions about
the inputs, however, the bounds can be improved.  Carlsson,
Levcopoulos and Petersson~\cite{CLP90} considered a block metric $k =
Block(X, Y)$ which represents the minimum number of blocks that the
lists need to be broken into before being recombined into one list.
Given this metric they present an algorithm for static merging with
bounds $\oklg$.  The static merging problem only generates cross
pointers that show where the blocks from one list can be inserted into
the other, but does not actually merge the results.  It is not hard to
show, however, that given split and join operations that run in
$O(\log(\min(|S_1|,|S_2|)))$ time, regular merging and all the set
operations can be implemented in $\oklg$ time~\cite{MPW98}.  Demaine,
L\'{o}pez-Ortiz and Munro extended this to methods for taking the
union, intersection and difference on multiple sets.  These
methods do not parallelize easily since they involve sequentially
pulling elements off of each input from one end.
%Examples of
%sequential algorithms that meet that bound are described in Section
%\ref{sec:serialmerge} and shown in Figure~\ref{fig:serialunioncode}.

The $\oklg$ bound can be met in the purely functional context with
a functional representation of a sorted list that supports split and
join in $O(\log(\min(|T_1|,|T_2|)))$ time.  Kaplan and
Tarjan~\cite{Kaplan95,Kaplan96} developed such a structure based on
2-3 trees.  The structure is described in Section~\ref{sec:23trees},
in the Appendix.  They point out that the structure can be used to
implement the list-merging algorithm of Brown and Tarjan
\cite{finger80} with an optimal $O(m\log(\frac{n}{m}+1))$ time bound.
However, the data structure they use is somewhat complex, the Brown
and Tarjan list-merging algorithm does not give the stronger $\oklg$
time bounds, and the extension based on split and join mentioned in
the previous paragraph does not parallelize.

In this paper we develop very simple functional data structures for
representing sets based on Treaps~\cite{Aragon89}.  For the sequential
set operations presented in Section~\ref{sec:serialmerge} we require
only the trivial technique of flipping the pointers along the left
spine of a Treap.  Our parallel set operations require that we flip
the pointers along both spines.  All of our algorithms require $\oklg$
expected work, and our parallel algorithms operate in $O(\log^2 n)$
expected depth.    
We present all the code for all our algorithms---the
only exception is for some symmetric routines for left and right
spines in which we only show the left version.\footnote{We have also
left the parallel intersection and difference code from this
submitted version.}  We also present some
experimental results that demonstrate that the constants in the work
bounds are reasonably small.  The experiments show that our
algorithm does slightly better than the Kaplan and Tarjan algorithm in
terms of number of comparisons.   

\paragraph{Related Work.}

All the techniques we know of for implementing fast set operations
originate from work on finger searching~\cite{Guibas77}.  The idea of
finger searching is that, given a pointer (or ``finger'') to any key
in a search structure, it should be possible to find nearby keys in
faster than the usual $O(\log(n))$ time.  Many types of balanced trees
permit finger searches using parent pointers.  Unfortunately, parent
pointers imply pointer cycles, which cannot be constructed using
purely functional programming.  The solution we use for this problem
is to flip the pointers along one or both spines of the tree---each
node along the left spine points to its parent instead of its left
child, and each node along the right spine points to its parent
instead of its right child.  Tarjan and Van Wyck \cite{Tarjan88}
describe this data structure as a ``heterogeneous finger search
tree''.

Cole et al.~\cite{Cole00} showed that splay trees can be used to
implement finger searches.  Splay trees can easily be made functional,
and this technique is much simpler than the others mentioned, but the
bounds are amortized.  Amortized bounds are weak for data structures
that may have multiple futures since an application could perform many
operations on the same version of a structure (consider the two
operations on ``Orchid or Rose'' in Figure~\ref{fig:search}).  If that
version of the structure had a high potential value, the amortized
bounds might not hold.

Demaine, L\'{o}pez-Ortiz, and Munro~\cite{Demaine00} considered
information-theoretic lower-bounds on the set operations which are
stronger than the Block Metric bounds in that they take the sizes of
the individual blocks into account.  These bounds were shown earlier
in the context of binary set operations~\cite{CLP90}, but they use
some nice analysis tools to extend the bounds to operations on an
arbitrary number of sets (\ie, taking the union of $m$ sets, or taking
the intersection of $m$ sets).  They also proposed a sequential
algorithm based on persistent B-trees which is optimal with respect to
this bound.  In Section~\ref{sec:serialmerge} we show how to implement
a version of their multi-set union operation using our sequential data
structures.  We believe it is significantly simpler than their
original algorithm and also believe it is optimal with respect to
their stronger bound.

In the parallel setting, previous work has focused either on merging
algorithms that take $O(n)$ work \cite{AMW89,DO89,HR89,VIHD90,GL91,KLP92}
and are optimal when the two sets have nearly equal sizes, or on
multi-insertion algorithms that take $O(m\log(n+1))$ work and are optimal
when the input values to be inserted are not presorted
\cite{Paul83,hs94,Ranade92,BD96}.
More recently, Blelloch and Reid-Miller \cite{Blelloch98} demonstrated a
non-functional parallel merging algorithm which operates in
$O(k\log(\frac{n}{k}+1))$ work and $O(\log(m)\log(n))$ depth using parent
pointers.  A functional version of this algorithm requires
$O(m\log(\frac{n}{m}+1))$ work, though the depth does improve to
$O(\log(n))$.

