
\section{Related Work}
This paper focuses on optimizations of genetic algorithms
building test coverage models for randomized unit testing.
% in large
%hyper-agile groups.  (XXX IMHO it's hard to say that we target
%specifically hyper-agile groups...)
While the
specifics of our techniques may not apply to other research, we suspect that the general problem explored here
is relevant to other data mining research. This will be
especially so for researchers exploring complex
tasks in environments demanding greater speed.
Some learning methods require very complex and costly computations
which need to be reiterated every time the data changes.  

Many researchers use
SVD (single value
decomposition) for performing tasks related to program
comprehension; for example,
Marcus and Maletic~\cite{marcus03} use it to find traceability
links between documentation and source code based on terms.
Once computed, the SVD
results can be queried in millisecond time to find (say) the 10
methods closest to a particular method.  This computation must be
repeated whenever the code base changes;
but in common practice, code base changes are becoming increasingly frequent.
% XXX IMHO this was redundant.
%.  As changeability is one
%of the essential properties of software~\cite{brooks87}, change is
%a day-to-day activity in software development and maintenance
%(particularly in hyper-agile environments).
  In order for the
representation of the software system to be accurate, and for the
tools to be able to help developers in real time during their daily
activities, the current techniques would need to perform these
complex computations over and over again, at an impractical
computational cost.

The complexity of SVD (single value decomposition)
on a $T*D$ term*document matrix is $O(min(T^2D, TD^2))$.  In terms
of algorithmic theory, this seems acceptable (since it is still
polynomial time), but Marcus (personal communication) reports
that, in practice, applying SVD over the large sparse $T*D$ matrices
seen with real world code bases can take hours to days to compute.

Many local 
learning schemes have slow runtimes.  For example, Frank et
al.'s~\cite{frank03} locally weighted Bayes classifier performs better 
than standard Bayes, but runs much more slowly since the
neighborhood of each test case is computed at test 
time.  In the worst case (when the test set is the entire
training set, of size $D$) this search takes time $O(D^2)$ ,
since the distance between each pair of examples must be computed.  While theoretically tractable, $D^2$ can 
be impractically large.

One way to optimize locally weighted learning schemes is to
pre-compute and cache
clusters that divide the space into pre-defined ``chunks''. Each
chunk is spatially indexed (e.g.\ using cover trees~\cite{bey06}
or kd-trees~\cite{bentley90}) so that local learning can be
constrained to just their most relevant ``chunk''.
Note that this approach requires the recomputation of the
clusters every time the training data changes.
% -- which Brooks
%predicts will be very often (due to software changability) and which we comment will be very rapid in hyper-agile
%environments.

The techniques discussed in this paper do not necessarily solve
the problems noted above.
However, these problems show that the general research area of this paper 
is a looming problem for many SE data mining tasks. We therefore
expect an increasing number of papers tackling the
same theme of this paper
(orders of magnitude runtime optimizations in learning method).

