algorithm.tex

\section{Algorithm}

Using the previous work as a guide, we will explore various ways to 
parallelize gSpan\cite{gspan} using MPI.  Our first attempt will be to 
duplicate the algorithm used by \cite{buehrer2005parallel} and use
a dynamic queueing mechanism to farm the work of child candidate 
graph generation out to parallel nodes.  We will then conduct these 
experiments to attempt to improve the performance of the system:

\begin{enumerate}
	\item{Implement other queueing mechanisms to see if they perform
		better in distributed memory environment than dynamic
		queueing}
	\item{Attempt to parallelize the DFS code generation step as well
		as the subgraph mining step}
	\item{Explore a hybrid approach that uses a combination of 
		MPI for inter-node and pthreads or OpenMP for intra-node
		communication.}
\end{enumerate}

An analysis of these variations should illuminate useful techniques that
can be applied to a wider range of mining problems than the current
parallel gSpan systems can handle.