\newcommand{\DoubleSpace}{\edef\baselinestretch{1.2}\Huge\normalsize}
\newcommand{\SingleSpace}{\edef\baselinestretch{1.0}\Huge\normalsize}
\newcommand{\CrunchPreSecSpace}   {\vspace{-1em}}
\newcommand{\CrunchSecSpace}   {\vspace{-1em}}
\newcommand{\SpaceItem}   {\vspace{-1em}}
\newcommand{\CrunchParaSpace}  {\vspace{-1em}}
\newcommand{\AddSpaceAfterFigure}  {\vspace*{2ex}}
\newcommand{\EatSpace}  {\vspace*{-1ex}}
\newcommand{\eat}[1] {}
\newcommand{\Mark}{\markright{DRAFT: Prelim document}}
%\newcommand{\Mark}{}

\newcommand{\threefigures}[9]{
\begin{figure*}[htbp]
\centerline{\epsfxsize=2in \epsfysize=2.0in \epsffile{#1}
\hfill \epsfxsize=2in \epsfysize=2.0in \epsffile{#4}
\hfill \epsfxsize=2in \epsfysize=2.0in \epsffile{#7}}
%\vspace {-2em}
\SingleSpace
\centerline{\parbox{2in}{\caption{#2} \label{#3}}
\hfill \parbox{2in}{\caption{#5} \label{#6}}
\hfill \parbox{2in}{\caption{#8} \label{#9}}}
\DoubleSpace
\vspace*{-0.6em}
\end{figure*}}

\newcommand{\twofigures}[6]{
\begin{figure}[ht]
\centerline{\epsfxsize=3in \epsfysize=3.0in \epsffile{#1}
\hfill \epsfxsize=3in \epsfysize=3.0in \epsffile{#4}}
\centerline{\parbox{3in}{\caption{#2} \label{#3}}
\hfill \parbox{3in}{\caption{#5} \label{#6}}}
\end{figure}}

\newcommand{\twolargefigures}[6]{
\begin{figure}[ht]
\centerline{\epsfxsize=3in \epsfysize=4.0in \epsffile{#1}
\hfill \epsfxsize=3in \epsfysize=4.0in \epsffile{#4}}
\centerline{\parbox{3in}{\caption{#2} \label{#3}}
\hfill \parbox{3in}{\caption{#5} \label{#6}}}
\end{figure}}

% condensed list with smaller spacing than itemize
\newenvironment{mylist}{
%\baselineskip 10 pt
\begin{list}{$\bullet$}{
\setlength{\leftmargin}{1.5ex}
\setlength{\labelwidth}{1ex}
\setlength{\labelsep}{0.5ex}
\setlength{\itemsep}{0.6ex}
\setlength{\parsep}{0.6ex}
}}
{\end{list}}

\documentstyle[11pt, palatino]{article}    % Specifies the document style.
%\documentstyle[11pt]{article}    % Specifies the document style.
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\footheight}{0in}
\setlength{\footskip}{0.6in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\textwidth}{6.6in}
\setlength{\textheight}{9.1in}
\setlength{\parskip}{2ex}
\setlength{\parindent}{0ex}


%\pagestyle{headings}
\pagestyle{plain}

\title{\protect \vspace*{-.5in} Efficient Database Support for
Spatial Database Applications\thanks{This work was partially supported
by NASA Contracts \#USRA--5555-17 and \#NAGW--3895 and by an IBM
Research Initiation Grant.}}

\author{
Jignesh M. Patel  \\
Computer Sciences Department,\\
University of Wisconsin, Madison \\ jignesh@cs.wisc.edu }

\begin{document}           % End of preamble and beginning of text.

\DoubleSpace
\maketitle                 % Produces the title.
\input epsf

\Mark
\vspace*{-2em}
\section {Introduction}
\CrunchSecSpace
The focus of my research is on designing, building and implementing a
database system that is capable of efficiently handling large amounts
of spatial data. Data stored in a {\em spatial database system}
includes simple geometric types like points, lines, polygons and
surfaces, and more complex types like swiss--cheese--polygons (which
are polygons with holes) that are derived from the simpler geometric
types. Frequent operations on spatial data includes, selection based
on spatial or non--spatial attributes, joins of two spatial relations,
and aggregation over some spatial attributes (example, find the river
closest to a city). Of these operations, the joins are the most
expensive operation, and will be a major focus of my work.

\CrunchPreSecSpace
\section {Thesis Outline}
\CrunchSecSpace

My thesis will contain three parts:
\begin{description}
\CrunchParaSpace
\SingleSpace
\item [Part I:] Investigation of efficient spatial join operations.
\item [Part II:] Investigation of the use of parallelism for spatial databases.
\item [Part III:] Comparison of different spatial data models.
\DoubleSpace
\end{description}
\CrunchParaSpace

I have completed Part I, and am currently working on the other two
parts. Each of these parts are described in the following sections.

\CrunchPreSecSpace
\section {Part I: Efficient Centralized Spatial Join Algorithm}
\CrunchSecSpace
\label {sec-central-spjoin}

Spatial database users frequently need to combine two spatial inputs
based on some spatial relationship between the objects in the two
inputs.  For example, {\em map overlap}, which requires combining two
maps to produce a third, is an important operation in a spatial
database~\cite{Burrough,MGR-VOL1}.  This operation of combining two
inputs based on their spatial relationship is called a {\em spatial
join}. Spatial joins, just like their counterparts in a relational
system, are an expensive operation.  Consequently, efficient spatial
join algorithms are a critical component of any spatial database
system.

I have developed a spatial join algorithm, called Partition Based
Spatial--Merge (PBSM) Join, which partitions the inputs to the join
into manageable chunks (chunks that can fit in memory), and joins the
chunks using a computational geometry based plane--sweeping technique.
The partitioning strategy of PBSM can be considered to be the spatial
equivalent of the partitioning strategy used by relational hash based
join algorithms. The plane--sweeping techniques used for joining the
chunks can be considered to be the spatial equivalent of the
relational sort--merge join algorithm. I have implemented this
algorithm in Paradise~\cite{Paradise-94}, a database system that
handles GIS type of applications, and compared the performance of the
algorithm with existing spatial join algorithms. The performance study
demonstrates the effectiveness of the PBSM algorithm in situations
when indices do not pre--exist on the inputs to the
join~\cite{PBSM}. This paper is attached as an appendix.

\CrunchPreSecSpace
\section {Part II: Handling Large Amounts of Spatial Data.}
\CrunchSecSpace

To efficiently handle large volumes of spatial data (as will be
required by future GIS systems), the use of parallelism seems to be a
natural solution. Of the various parallel
architectures~\cite{Ston86a}--{\em shared memory, shared--disk, and
shared nothing}, shared--nothing architectures are specially
attractive because of their scalability and their ability to utilize
emerging technological trends~\cite{DeWitt92}. Consequently, my
efforts are targeted for a shared--nothing architecture (initially an
SP2, and later {\em COPS}--A Cluster of PCs).

Parallel spatial databases pose the following challenges:

\begin {enumerate}
\CrunchParaSpace
\SingleSpace
\item How should spatial data, which includes polygons, poly--lines,
swiss--cheese--polygons etc., be declustered?
\SpaceItem
\item How does one parallelize spatial operations?
\DoubleSpace
\end {enumerate}
\CrunchParaSpace

The following sections discuss each of these issues.

\CrunchSecSpace
\subsection{Declustering of Spatial Data}
\CrunchSecSpace

Similar to declustering in parallel relational databases, declustering
of spatial data can be expected to play a crucial role in the
performance of a parallel spatial database system.  We would like a
declustering mechanism that allows both a uniform distribution of data
across all the nodes in the system and the efficient parallelization
of spatial operations.

There are two issues involved in declustering data based on a spatial
attribute:
\begin{enumerate}
\CrunchParaSpace
\SingleSpace
\item {\bf Mapping} a tuple to one or more nodes.
\SpaceItem
\item The {\bf replication strategy}, for tuples that are mapped to
more than one node.
\DoubleSpace
\end{enumerate}
\CrunchParaSpace

Each of these issues are discussed in the following sections.

\CrunchSecSpace
\subsubsection*{\bf Tuple to Node Mapping}
\label{sec-spPart}
\CrunchSecSpace

To decluster a relation based on a spatial attribute, each tuple in
the input relation is {\em mapped}\footnote{We will discuss what it
means to map a tuple to multiple nodes below.} to one or more nodes in
the system. When executing a spatial operation in parallel, each node
is responsible for processing the tuples that have been mapped to
it. Tuples that are mapped to more than one node might produce
duplicates in the result of the spatial operation. Special processing
might be required to remove these duplicates.

To map a tuple to one or more nodes, a {\em spatial partitioning
function}, can be used.  The spatial partitioning function works as
follows:

\begin{enumerate}
\CrunchParaSpace
\SingleSpace
\item 

First, the {\em universe} of the declustering spatial attribute is
estimated. The {\em universe} of a spatial attribute is the smallest
rectangle that covers the spatial attribute of all the tuples in the
relation. In a spatial database system, the universe information is
used in a variety of situations including, estimation of selectivities
of spatial predicates during query optimization to determine if a
spatial index should be used instead of a simple scan. Consequently,
it is likely that the universe information will be stored as
statistics in the database catalogs. If the universe information is
not contained in the catalogs, then spatial sampling
techniques~\cite{Lo95} can be used to estimate the universe.

\item The universe is then decomposed into a $N$ subparts ($N$ is the
number of nodes in the parallel system). As an example, consider
Figure~\ref{fig-spNode} where the number of nodes is 4.

\item Finally, the spatial partitioning function is applied to the
maximum bounding rectangle ({\em MBR}) of the declustering attribute
of a tuple. The partitioning function determines all the subparts of
the universe with which the {\em MBR} overlaps, and maps the tuple to
each node corresponding to these subparts. Thus, if a {\em MBR}
overlaps with multiple subparts, then it is mapped to multiple
nodes. For example, the object shown in Figure~\ref{fig-spNode}, will
be mapped to nodes 0 and 2. 

Recall that the universe computed in step 1 is just an estimate, and
it is possible for an object to lie outside the computed universe. In
this case, the entire region outside the estimated universe can be
treated as a single subpart, and this subpart could be assigned to a
node. Alternatively, for better load balancing, the region outside the
estimated universe could be broken into multiple subparts (example,
north, south, east, west, north--east ...).

\DoubleSpace
\end {enumerate}
\CrunchParaSpace

\begin{figure}[htb]
\centerline{
  \epsfxsize=4.0in
  \epsffile{fig/spNode.fig}
}
  \vspace{-0.1in}
  \epsfysize=1in
\caption{\label{fig-spNode}
         The Spatial Partitioning Function (number of nodes = 4).}
\end{figure}

In the presence of a non--uniform distribution, the partitioning
function just described could produce unbalanced partitions.  As an
example consider Figure~\ref{fig-spNodeSkew} where the number of nodes
is 4. Here, most of the tuples are (spatially) in the top left corner,
and the spatial partitioning function will map all these tuples to
node 0. Nodes 2 and 3, on the other hand will have very few tuples.

\begin{figure}[htb]
\centerline{
  \epsfxsize=4.0in
  \epsffile{fig/spNodeSkew.fig}
}
  \vspace{-0.1in}
  \epsfysize=1in
\caption{\label{fig-spNodeSkew}
    Skew Caused by The Spatial Partitioning Function (number of Nodes = 4).}
\end{figure}

To remedy this situation, the partitioning function can decompose the
universe regularly into $NT$ {\em tiles}, where $NT$ is greater than
or equal to $N$. Starting from the upper left corner, the tiles are
numbered from 0 to $NT-1$. Each tile is assigned to a node using a
scheme like round robin or hashing on the tile number. For example,
consider Figure~\ref{fig-spNodeHash} where the universe is divided
into 12 tiles, the number of nodes $N$ is 3, and tiles are assigned to
nodes using a round robin scheme. Thus tiles 0, 3, 6, and 9 are
assigned to node 0, tiles 1, 4, 7 and 10 are assigned to node 1, and
tiles 2, 5, 8 and 11 are assigned to node 2.  To apply the spatial
partitioning function to a {\em MBR}, all the tiles that overlap with
the {\em MBR} are determined, and, the tuple is mapped to the nodes
corresponding to these tiles. Thus, if the {\em MBR} of a tuple's
spatial attribute overlaps with tiles from multiple nodes, then the
tuple is mapped to all these nodes. Consequently, the tuple shown in
Figure~\ref{fig-spNodeHash}, is mapped to nodes 0, 1 and 2.

\begin{figure}[htb]
\centerline{
  \epsfxsize=4.0in
  \epsffile{fig/spNodeHash.fig}
}
  \vspace{-0.1in}
  \epsfysize=1in
\caption{\label{fig-spNodeHash} 
         The Virtual Processor Spatial Partitioning Function.}
\end{figure}

The spatial partitioning function just described is the spatial analog
of virtual processor round robin partitioning for handling skews in
parallel relational joins~\cite{VirtualP}. A similar partitioning
function has been independently proposed for redundancy--based
declustering of spatial objects in a parallel spatial
database~\cite{spdeclust}, but, in that proposal, the number of tiles
always equals the number of nodes (i.e. it is equivalent to the
spatial partitioning function of Figure~\ref{fig-spNode}).

The design space for choosing the spatial partitioning function has
two axes: the number of tiles used in the partitioning function, and
the scheme for assigning tiles to nodes. Decomposing the universe into
small tiles produces many small containers, which are easier to pack
into nodes to produce a more uniform tuple distribution across the
nodes. However, spatial objects that span tiles from multiple nodes
are mapped to all those nodes, and this leads to some replication
overhead (the replication policy is discussed in the next
section). For assigning tiles to nodes, one could use either round
robin or hashing on the tile number.

To explore these alternatives, data from the TIGER/Line
files~\cite{Tiger} was used. This data represents roads in the state
of Wisconsin. The road data set contains 655,821 tuples and the size
of the entire data set was 89.7MB. Figure~\ref{graph-spHash} shows the
effect of increasing the number of tiles, and choosing different
schemes for assigning tiles to nodes. The graph uses the coefficient
of variation\footnote{The coefficient of variation is defined as the
standard deviation divided by the mean.} of the distribution of the
tuples at each node as its metric. A perfect spatial partitioning
function would be one that assigns an equal number of tuples to each
node, and, consequently, would have a coefficient of variation of 0
for the distribution of the tuples at each node.

\twofigures
{graphs/declust/spHash.ps}
    {Tiger Data: Comparison of Spatial Partitioning Function Alternatives.}
    {graph-spHash}
{graphs/declust/spRepl.8.ps}
    {Tiger Data: Replication Overhead (\# Nodes = 8).}
    {graph-spHash.repl} 

>From Figure~\ref{graph-spHash}, the following observations can be
made. First, using a large number of tiles and hashing on the tile
number gives a good partitioning function. Second, all the
partitioning functions improve as the number of tiles is
increased. This is because with a larger number of tiles, ``dense''
regions get subdivided into more tiles, and these tiles can be mapped
to different nodes.  Third, for a given number of tiles, the
partitioning function yields a more uniform distribution for a smaller
number of nodes (compare the graphs for hashing with 8 and 128
nodes). This, once again, is because the distribution of tiles that
cover ``dense'' regions is better with a smaller number of nodes. For
example, when the universe was decomposed into 256 tiles, 100 tiles
covered 78.5\% of the data. These 100 tiles could be spread across 8
nodes more uniformly than over 128 nodes, and, as a result, the
coefficient of variation for 8 nodes is lower than that for 128
nodes. \eat{Finally, we observe, that the curve for round robin has
some spikes. This is because with round robin, when the number of
tiles is an integral multiple of the number of nodes, it is possible
that an entire column will be mapped to a single node. This is
equivalent to having fewer number of tiles (each column now behaves
like a single tile). Consequently, the partitions produced by the
partition function are less balanced.}

Figure~\ref{graph-spHash.repl} shows the replication overhead for
various number of tiles. Replication overhead is computed assuming
that p tuples are created for each tuple that is mapped to p
nodes. The replication overhead is then computed as the percentage
increase in the number of tuples due to declustering. The figure shows
that, for this data set, even with a very large number of tiles the
replication overhead is very modest (an increase of about 4.9\% in the
number of tuples for 4500 tiles).  The figure also shows some spikes
in the curve for round robin. This is because with round robin, when
the number of tiles is an integral multiple of the number of nodes, it
is possible that an entire column will be mapped to a single
node. This is equivalent to having fewer number of tiles (each column
now behaves like a single tile). Consequently, fewer tuples have to be
replicated. However, at these points, the partitions produced by the
partitioning function are less balanced (observe the jumps in
Figure~\ref{graph-spHash} for round robin with 8 nodes).

\CrunchSecSpace
\subsubsection*{\bf Replication Policy}
\label {sec-repl}
\CrunchSecSpace

Using the spatial partitioning function described above, any
particular spatial attribute can overlap multiple tiles and hence
would be mapped to multiple nodes. When a tuple is mapped to more than
one node, a replication policy must be chosen to represent the tuple
at all the nodes that it has been mapped to. Various replication
policies can be used. For example, the entire tuple could be
replicated at each node, or only the declustering attribute could be
replicated. Replicating the tuple, or the declustering attribute, can
potentially increase the size of the declustering relation
significantly. As an example, consider
Figure~\ref{graph-spRepl.seq.128.repl}, which shows the percentage
increase in the number of tuples as a result of declustering the
polygon data set from the Sequoia benchmark~\cite{Ston93}. This data
set is 21.9MB, and contains 58,115
polygons. Figure~\ref{graph-spRepl.sequoia.128.size.repl} shows the
percentage increase in the size of the relation used to represent this
data set when each tuple that maps to more than one node is replicated
in its entirety. For example, with 4096 tiles, and using hashing on
tile number, declustering produced 21\% additional tuples (caused by
tuples being mapped to more than one node). The actual increase in the
size of the declustered relation, was much greater (82\%), because
polygons that are large in size, tend to cover large areas, and, as a
result, are more likely to be mapped to multiple nodes.

\twofigures
{graphs/declust/spRepl.sequoia.128.ps}
    {Sequoia Data: Replication Overhead (\# Nodes = 128).}
    {graph-spRepl.seq.128.repl} 
{graphs/declust/spRepl.sequoia.size.128.ps}
    {Sequoia Data: Tuple replicated in its entirety (\# Nodes = 128).}
    {graph-spRepl.sequoia.128.size.repl} 

When a tuple is mapped to more than one node, an alternative
replication strategy, is to designate one of the ``mapped'' nodes to
be the {\em home node} for the tuple. The entire tuple is stored only
at the home node, while all nodes (including the home node) store the
global OID\footnote{We assume that the system has a global object
identifier for every tuple.} of the tuple and the $MBR$ of the part of
the spatial attribute that overlaps with the area covered by that
node.  This replicated $MBR$ is called the {\em fragment box}.  The
fragment box and the OID of the tuple are collectively called the {\em
partial spatial surrogate} of the declustered spatial attribute, and
are stored in a separate relation.  If required, a spatial index could
be built over the fragment boxes in this relation. Since a partial
spatial surrogate requires very little space (about 16 bytes for the
MBR, and 16 bytes for the OID), the increase in size of the
declustered relation due to replication will be minimal. For example,
using the Sequoia polygon data, with 4096 tiles, and using hashing on
tile number, the cardinality of the partial spatial surrogate relation
would be 21\% of the number of polygons in the data set. The size of
the partial spatial surrogate relation would be only 1.8\% of the size
of the polygon data set.

The home node for a tuple can be chosen in a variety of ways. The home
node could be the node with which the declustering spatial attribute
has the maximum overlap, or it could be the node that contains the
center of gravity of the declustering spatial attribute.

\begin{figure}[htb]
\centerline{
  \epsfxsize=4.0in
  \epsffile{fig/spDecl.fig}
}
  \vspace{-0.15in}
  \epsfysize=1in
\caption{\label{fig-spDecl} Declustering Spatial Data.}
\end{figure}

As an example of the declustering scheme, consider
Figure~\ref{fig-spDecl} which shows a tuple being declustered on a
polygon attribute. The universe has been divided into 12 tiles and the
tiles have been assigned to nodes using round robin on the tile
number. Let node 0 be the home node for the tuple, and let $OID_{H}$
represent the global OID of the tuple.  Then, node 1 will store the
fragment box $FB1$ and $OID_{H}$, node 2 will store the fragment box
$FB2$ and $OID_{H}$, and node 0, in addition to storing the tuple,
will also store the fragment box $FB0$ and $OID_{H}$.  Now, consider a
selection query corresponding to the query box shown in
Figure~\ref{fig-spDecl} . Using the partial spatial surrogate
information at node 1, an overlap between the query box and $FB1$ will
be detected. This indicates that the object pointed to by $OID_{H}$
could be part of the query result. A message could then be sent to
node 0, requesting it to check if the query box overlaps with the
actual object (and not just its $MBR$).

\CrunchPreSecSpace
\subsection{Parallel Spatial Join Algorithms}
\CrunchSecSpace

As mentioned in Section~\ref{sec-central-spjoin}, spatial joins are a
critical component of a spatial database system. This section
describes some techniques for parallelizing the spatial join
operation. The parallel spatial join algorithms that are proposed here
execute in three phases:

\begin{description}
\SingleSpace
\item [Partitioning Phase:] In this phase, if necessary, the inputs 
to the join are redeclustered over all the available nodes in the
system. Assuming full redeclustering, this phase produces partitions
of the input relations at every node in the system.

\item [Joining the Partitions:] In this phase, each node joins its
local partitions. For joining the partitions, any centralized spatial
join algorithm can be used. Some alternatives are: indexed nested
loops join, PBSM~\cite{PBSM}, and the R--tree based join
algorithms~\cite{BKS93, Lo95}. Depending on the partitioning phase, this
phase could produce as output, {\em candidates} that represent a
superset of the actual result.  The use of candidates will become
clear when all the possible join algorithms have been enumerated.

\item [Refinement Step:] This step is executed only if the previous
steps produces candidates. In this step, the candidates are processed
to produce the actual result tuples.
\DoubleSpace
\end{description}

Varying the redeclustering strategy used in the partitioning phase
yields different parallel spatial join algorithms. These algorithms
can be classified along two axes. The first axis determines the number
of relations that are redeclustered by the join algorithm, and the
second axis determines the join possibilities.  For the first axis,
there are three possibilities: redecluster neither relation
(redecluster--none), redecluster 1 relation (redecluster--one), and
redecluster both relations (redecluster--both).  For the join
possibilities, there are three alternatives depending on whether
partial spatial surrogates or entire tuples are used by the ``local''
join at each node. The alternatives are: join the partial spatial
surrogates of the two input relations (partial spatial surrogates
only), join whole tuples from both the input relations (whole tuples
only), and join partial spatial surrogates from one relation with
whole tuples from the other relation (partial spatial surrogates \&
whole tuples).

\twolargefigures
{fig/ops/red0-frag-frag.fig} 
{Operator Tree: Redecluster--none, Join Using Partial Spatial Surrogates Only}
{fig-red0-frag-frag}
{fig/spOvlp.fig} {Overlap Detection.} {fig-Ovlp}

{\bf Redecluster--none} (redecluster neither relation) makes sense
only if both relations are already declustered on the joining
attribute, and if the same spatial partitioning function was used for
declustering both the relations (i.e. the spatial partitioning
function had the same number of tiles and the same scheme for
assigning tiles to nodes). In this case, the only option for the local
join is to use the partial spatial surrogates of both relations.  The
operator tree for this algorithm is shown in
Figure~\ref{fig-red0-frag-frag}. The first operator in this algorithm
is the local join operator which joins the partial spatial surrogates.
This local join uses the fragment box information in the surrogates as
an approximation of the actual spatial attribute. For example, if the
join predicate is overlap between two polygons, then the local join
checks for overlap between the fragment boxes. The OID information in
the surrogates is used to produce an intermediate result set, which is
a set of {\em candidates}.  The {\em candidates} are represented as an
OID pair.  One of the OIDs in the pair refers to a tuple from one of
the join inputs, and the other OID in the pair refers to a tuple from
the other join input.  Since the fragment boxes are approximations,
two non--overlapping spatial objects could have overlapping fragment
boxes.  Consequently, the tuples corresponding to the two OIDs must be
brought together at some node (probably one of the tuples' home node),
and the join attributes must be checked to determine if the join
condition is satisfied.  To do this, Operator 2 redeclusters the
candidates based on $OID\ A$. This sends each candidate to the home
node of the $A$ tuple. Next, Operator 3 ``joins'' the candidates by
fetching the $A$ tuples corresponding to $OID\ A$. To avoid random
seeks in fetching the $A$ tuples, Operator 3, could sort the
candidates on $OID\ A$. This sorting step could also be used to
eliminate duplicate candidates. The output of Operator 3 is a set of
objects of the form $<Tuple\ A,\ OID\ B>$. Operator 4 then
redeclusters these objects on $OID\ B$. The last operator, Operator 5,
fetches the $B$ corresponding to $OID\ B$, and checks the spatial
attributes of the $A$ and $B$ tuples to determine if the join
condition is satisfied. Tuples that satisfy the join condition are
produced as the final result. 

Note that with redecluster--none, neither the 'whole tuples only' or
the 'partial spatial surrogates \& whole' algorithms make sense, as we
would not be able to find all possible overlaps. To illustrate this
point, consider Figure~\ref{fig-Ovlp}, where polygon 1 is stored at
node 1 and polygon 2 is stored at node 0. The two polygons overlap at
node 2, where only partial spatial surrogates exist for both the
polygons. Consequently, the overlap between the two polygons can be
detected only by checking the partial spatial surrogates at node 2. If
only whole polygons are examined at each node, then the overlap
between the two polygons will not be detected.

\twolargefigures
{fig/ops/red1-frag-frag.fig}
{Operator Tree:  Redecluster--one, Join Using Partial Spatial Surrogates Only}
{fig-red1-frag-frag}
{fig/ops/red1-frag-whole.fig}
{Operator Tree: Redecluster--one, Join Partial Spatial Surrogates and Whole}
{fig-red1-frag-whole}


{\bf Redecluster--one} involves redeclustering one of the relations on
the joining attribute. This strategy can be used if the two relations
do not have the same declustering characteristics for their joining
attribute. For the 'partial spatial surrogates only' case, when the
relation is redeclustered, partial spatial surrogates are created.
These are joined locally with the existing partial spatial surrogates
of the other relation, producing candidates that contains OID pairs.
The operator tree for this algorithm is shown in
Figure~\ref{fig-red1-frag-frag}.  For the 'partial spatial
surrogates--whole' case, the relation to be redeclustered must be the
``whole'' relation.  For this declustering, when a tuple is mapped to
more than one node, whole tuples are sent to all the ``mapped'' nodes.
The whole tuples are then joined with the fragment boxes from the
partial spatial surrogates of the other relation producing $<Tuple\ A,
OID\ B>$ pairs ($Tuple\ A$ comes from the relation that was
redeclustered, and $OID\ B$ comes from the partial spatial surrogates
of the other relation). This is then processed to get the tuples
corresponding to $OID\ B$.  The operator tree for this algorithm is
shown in Figure~\ref{fig-red1-frag-whole}.

\threefigures
{fig/ops/red2-frag-frag.fig}
{Operator Tree: Redecluster--both, Join Using Partial Spatial Surrogates Only}
{fig-red2-frag-frag}
{fig/ops/red2-frag-whole.fig}
{Operator Tree: Redecluster--both, Join Partial Spatial Surrogates and Whole}
{fig-red2-frag-whole} 
{fig/ops/red2-whole-whole.fig}
{Operator Tree: Redecluster--both, Join Using Whole Tuples Only}
{fig-red2-whole-whole}


{\bf Redecluster--both} can be used when neither relation is spatially
declustered or when redeclustering is required for load balancing.
For the 'partial spatial surrogates only' case, when both relations
are redeclustered, partial spatial surrogates are created and the join
is then processed as described in redecluster--none.  For the 'partial
spatial surrogate--whole' case, whole tuples from one relation are
used for redeclustering, while partial spatial surrogates are created
for the other relation. The join is then processed as described in
redecluster--1. For the 'whole tuples only' case, whole tuples from
both relations are used for redeclustering. The local join at each
node uses entire tuples from both the inputs and produces actual
result tuples. Note that this is the only algorithm in which the
actual result is immediately produced (as opposed to candidates which
require chasing OIDs).  The operator trees for these
(redecluster--both) algorithms are shown in
Figures~\ref{fig-red2-frag-frag} through~\ref{fig-red2-whole-whole}.

Table~\ref{table-designSpace} shows the compatibility matrix, and the
intermediate results produced by the local join operator, for the
entire design space of parallel spatial join algorithms.

\begin{table}[hbt]
\centering
\begin{small}
\begin{tabular}{||l|c|c|c||}\hline
  {}  & {\bf Partial Spatial} &  {\bf Whole Tuples} & {\bf Partial Spatial Surrogates \& } \\ 
  {}  & {\bf Surrogates only} & {\bf only}     & {\bf Whole Tuples} \\ \hline
                        & Yes                    &     &    \\
{\bf Redecluster--none} & Intermediate result    &  No & No \\
                        & is (OIDA, OIDB)        &     &    \\ \hline

                       & Yes                 &    & Yes     \\
{\bf Redecluster--one} & Intermediate result & No & Intermediate Result \\
                       & is (OIDA, OIDB)     &    & is (TupleA, OIDB) \\ \hline

                        & Yes                 & Yes & Yes     \\
{\bf Redecluster--both} & Intermediate result & Result Tuples are & Intermediate Result \\
                        & is (OIDA, OIDB)     & produced directly & is (TupleA, OIDB) \\ \hline
\end{tabular}
\end{small}
\vspace{-0.6em}
\caption{\label{table-designSpace} 
         Design Space of Parallel Spatial Join Algorithms.}
\end{table}

I am planning on implementing all the above algorithms and comparing
the performance of the algorithms using a variety of data sets.

\CrunchPreSecSpace
\subsection{Parallel Spatial Selection Algorithms}
\CrunchSecSpace

A spatial selection involves selecting tuples that satisfy a spatial
predicate. Examples of spatial selections are:
\CrunchParaSpace
\begin{verbatim}
    Find all cities within a circle.
    Find all rivers that overlap with a rectangle.
\end{verbatim}
\CrunchParaSpace

A simple parallel algorithm for spatial selection, is to
simultaneously apply the selection to the whole tuples at each node in
the system.  Another parallel algorithm for spatial selection, which
is similar to the one proposed in~\cite{spdeclust}, is to make use of
the partial spatial surrogates.  This algorithm is shown in
Figure~\ref{fig-selection}.  In this approach, the first operator,
applies the selection predicate to the fragment box information in the
partial spatial surrogates. The OIDs that are produced as a result of
this operator, are then redeclustered by operator 2.  A third operator
then ``joins'' these OIDs with the whole tuples, and checks to see if
the the whole tuples actually satisfy the selection predicate.  This
second algorithm, might have better performance if a spatial index
exists over the fragment boxes of the partial spatial surrogates, and
if a spatial index does not exist over the selection attribute of the
whole tuples relation.

\begin{figure}[htb]
\centerline{
  \epsfxsize=5.0in
  \epsffile{fig/ops/select.fig}
}
  \vspace{0in}
  \epsfysize=1in
\caption{\label{fig-selection} Select Operation Using The Partial
Spatial Surrogates}
\end{figure}

\newpage
\CrunchPreSecSpace
\subsection{Parallel Spatial Aggregate Algorithms}
\CrunchSecSpace

A spatial aggregate, involves computing an aggregate on a spatial
attribute. Examples of spatial aggregates are:

\CrunchParaSpace
\begin{verbatim}
Find the closest gas station to my house.
Find the average distance of all State capitals in the US from Madison.
\end{verbatim}
\CrunchParaSpace

For spatial aggregates, one can adapt the standard parallel aggregate
algorithm that is used by parallel relational
databases~\cite{Gamma}. This algorithm executes in two phases: a local
phase followed by a global phase. In the first phase, each node
computes the aggregate based on the data at its local node. In the
second phase, each node sends its results to a centralized coordinator
node, which combines these ``partial'' results into the final
answer. For example, consider a relation that stores information
about the gas stations (the location, the address, the phone number
...). Further, assume that the relation is declustered on the location
attribute. To find the closest gas station to a reference point, each
node would find the closest gas station amongst the tuples stored at
that node. This information, along with the distance of the closest
gas station from the reference point at each node, is then sent to a
centralized coordinator, which uses the distance information to find
the globally closest gas station.

\CrunchPreSecSpace
\section {Part III: Study of Different Data Models}
\CrunchSecSpace

The data models used in databases that store spatial data can be
classified into two broad categories: the {\em coordinate--based}
models and the {\em topography--based} models~\cite{simplex,
realms}. The coordinate based models represent spatial objects in the
database by their coordinates which are usually expressed as integers
or reals. These models use Euclidian geometry to find relationships
between spatial objects. For example, to determine if a point lies on
a line, these systems use the exact coordinates of the end--points of
the line to calculate the perpendicular distance between the point and
the line. If this perpendicular distance is equal to 0, then the point
lies on the line.

There are two popular ways of implementing the coordinate based models.
\begin{enumerate}
\CrunchParaSpace
\item The first approach has been used in ARC/INFO~\cite{Arcinfo}, which
is a very popular spatial database system. This implementation can be
summarized with an example of how polygons are represented. A polygon
is composed of a set of lines. Each line in the database is assigned a
unique line--id, and each line is stored in a ``lines'' relation as a
tuple. A tuple in this relation contains the line--id and the
end--points of the line. Each polygon is also assigned a unique
polygon--id. Another relation holds tuples that have two
attributes---an attribute for storing a polygon--id, and an attribute
for storing a line--id. This relation maintains the association
between the polygons and the lines that are part of the polygon. Thus,
if a polygon is composed of 10 lines, then there will be 10 entries in
this relation. With this approach, lines that are parts of two
polygons are stored only once in the lines relation~\footnote{These relations
are called geo--relations in ARC/INFO}.
\item The second approach, is based on using abstract data types (ADTs)
for representing spatial object. As an example, in this approach each
polygon would be represented by a polygon ADT, which may store the
end--points of the polygon as an array inside the ADT. This approach
has obvious performance benefits over the first approach as polygons
do not have to be ``assembled'' from their edges every
time. Illustra~\cite{Arcinfo} and Paradise use this approach.

\end{enumerate}


The drawback cited for the {\em coordinate--based} models is that
computers round off floating point numbers, and, as a result, the
following types of problems could arise~\cite{simplex, carterr}.

\begin{enumerate}
\CrunchParaSpace
\SingleSpace
\item Scaling of coordinates may change the topology, moving points,
initially close to a line, from one side of the line to the other
side.
\item The intersection of two lines does not necessarily lie on both the lines.
\item The application of two geometric inverses generates a geometry which
may differ from the original geometry.
\DoubleSpace
\end{enumerate}

As a solution to the above problems, another class of data models,
called the {\em topography--based} models, have been
proposed~\cite{simplex, realms}. These models maintain that, when
dealing with spatial data, the relationship (like the neighborhood
relationship) between spatial objects is of crucial importance. This
is in contrast to the coordinate--based models where the relationships
are computed on the fly; usually using special access structures, like
spatial indices, to speed up the computation.

As an example of a topography--based model, consider the simplex
model~\cite{simplex}.  This model is based on two concepts, {\em
simplex} and {\em simplical objects}. For each dimension {\em d}, a
{\em d--simplex} is a minimal object in that dimension.  Thus a
0--dimension simplex is a point, a 1--dimension simplex is a line and
a 2--dimension simplex is a triangle.  Note that an n--dimension
simplex ($n > 1$) is composed of {\bf n+1} (n-1)--dimension simplexes.
The components used in a simplex are called its {\em faces}. Thus the
faces of the 2--simplex, which is a triangle, are the 3 vertices of
the triangle, the 3 edges of the triangle, and the triangle itself.  A
{\em simplical complex} is a finite set of simplices and their faces,
such that the intersection of any two simplices in the set is a face.
Thus, the simplex model breaks up the entire space into the simpler
simplex elements and represents spatial objects in terms of these
simple elements. As an example, Figure~\ref{fig-simplex} shows two
simplical complexes.

\begin{figure}[htb]
\centerline{
  \epsfxsize=4.0in
  \epsffile{fig/simplex.fig}
}
  \vspace{-0.1in}
  \epsfysize=1in
\caption{\label{fig-simplex} Simplical Complexes.}
\end{figure}


As expected, topography--based models have very different
implementation from the coordinate--based models.  As an example,
consider the representation of a polygon object in the simplex
model. In this model, the polygon object is represented by a set of
2--simplices. In an object--oriented system, the implementation of the
polygon object would have pointers to all the 2--simplices that are
part of it.  The 2--simplices in turn would have pointers to three
1--simplices, and the 1--simplices would have pointers to two
0--simplices.  To determine neighborhood relationships efficiently,
these systems might have back pointers too.  For example, a 1--simplex
could have pointers to the 2--simplices that it composes.

For the last part of my thesis, I would like to study these data
models, and the different ways of implementing them, and analyze the
performance implications of implementing them in a database system.

\CrunchPreSecSpace
\section {Applying Spatial Joins to Multi--Attribute Relational Joins}
\CrunchSecSpace

An interesting idea might be to apply spatial join algorithms to
multi--attribute relations joins. As a motivating example consider a
database that has the following relations:

\begin{description}
\CrunchParaSpace
\SingleSpace
\item
{\em {\bf EmployeeFirm1}} (name: {\bf String}, age: {\bf Integer}, experience : {\bf Integer}, salary: {\bf Real}, ...)
\SpaceItem
\item
{\em {\bf EmployeeFirm2}} (name: {\bf String}, age: {\bf Integer}, experience : {\bf Integer}, salary: {\bf Real}, ...)
\SpaceItem
\DoubleSpace
\end{description}

The relation {\bf EmployeeFirm1} and {\bf EmployeeFirm2} contain
information about employees in firms ``Firm1'' and ``Firm2''
respectively. Each relation has tuples containing information about
the age of an employee, the experience of the employee (which could be
in number of years), and the salary paid to the employee. Suppose
Firm2 wants to buy Firm1 and replace all employees in Firm1 with
``suitable'' employees from its firm.  Here, a ``suitable'' employee
might be a person whose age is within 5 years of the age of the
employee being replaced, whose experience is within 4 years of the
experience of the employee being replaced, and whose salary is within
the 5\% range of the salary of the employee being replaced. Such a
query would be a multi--attribute range query between the two
relations. One way of visualizing this join is by considering the
employee tuples as points in a 3--dimensional space, and drawing cubes
of ``appropriate'' sizes around the employees. The join then becomes a
spatial join between the two sets of cubes.

\SingleSpace
\Mark
\begin{small}
\bibliographystyle{alpha}
\bibliography{references}
\end{small}

\end{document}
