
\section{Information Needs}
This section samples the space of information needs
of different communities.
First, we
present a use case for {\IT} from the perspective of the Surgeon-General
tracking disease patterns across the country.
Next,
we review a recent analysis of information needs from a recent survey of 100+ programmers at
Microsoft. 
A case will be made that this concept of {\em information needs}
is common to a variety of domains: specifically, we will
show that
there are many similarities
between the information needs of the
Surgeon-General, and of the Microsoft software developers.

\subsection{Use Case}
Every morning, the Surgeon General checks for new disase patterns.
Waving at the display wall of her office, she orders
``show infectious cases presenting to ERs''.
Dots appeared on a map of the country. ``Show
percent admissions to main hospitals ... benchmark against
same from last year''.
Concerned, the Surgeon General leant forward to study the map which
now shows an 
increase in admission rates. Needing
to explain this, she displays other properties saying ``show regional
median unemployment times..  show temperature min .. show temperature
max ...''.

After a while, the  map is chocked with too many
symbols. ``Fold'' she orders, and the geographical map disappears
as hospitals on different sides of the country marched
towards their nearest similar institution.
 ``Cluster'', she orders, and
 similar hospitals 
are grouped together into sectors. She then orders
``overlay with  percent admissions to hospitals'' which highlights 
the hospitals where most the ER patients with infections were not
discharged home.

She taps twice in the air to
 highlight two clusters with highest and lowest
discharge rates. ``Constrast'' she commands, so {\IT} searchers for
rules (conjunctions of hospital properties)
that selects for one cluster while avoiding the other. The
pattern is now clear.

Waving at her ear, she says ``Utah, Health''.
A few seconds later, she is sharing her displays with Salt Lake City.
Utah agrees that  their unseasonal rains has lead to spore
counts generating severe URTIs in infants.   They agree to issue
an advisory about updating air conditioner filters.

``How do we monitor this?'' asks Utah. The Surgeon General draws a line in the air
between the highest and lowest clusters. Sensing her moves, a line
appears on her display (copied to Utah) connecting regions of lowest
and highest infection rates.
Twirling her fingers
here, here, and here she defines three goal points and marks them with
a date.  They agree to meet on those dates to see if the at-risk
hospitals are
moving towards regions of lower infection.

\subsubsection{Analysis of Use Case}
The technology described above divides into 1) motion-aware controllers;
2) data warehousing (that {\em collects} and {\em stores} data); and
3) business intelligence operators
(that {\em extract} knowledge from the warehouse). 
Motion-aware controllers are now
available from commercial vendors (e.g. Microsoft Kinect\textsuperscript{\textregistered}) 
and data warehousing
is a well-studied problem~\cite{sen11}. Hence, in this paper, we  focus just
on 
the business intelligence.
 
\subsection{Information Needs at Microsoft}
{\IT} adapts $kd$-trees~\cite{bentley90} to
recusively divides high-dimensional data according 
the two dimensions of greatest variability seen at every level of the clustering
(so it may be considered a $k(d=2)$-tree algorithm).
These two dimensions are found in linear time using FASTMAP~\cite{Faloutsos1995}.

Leaf clusters are combined using grid-clustering 
to combine related neighboring regions. In $log_4(N)$ time, new test instances
can be mapped down the $k(d=2)$ tree to their relevant cluster.
Each cluster maintains histograms describing the distribution of data seen
in that cluster.  
Each cluster can be scored in numerous ways such as (a) the median of some
dependent variable in that cluster or (b) the performance bias and variance
of a classifer applied to that cluster.
The delta between histograms reveals values
that most distinguish 
two sets of clusters, which might be called $asIs$ and $toBe$.
Management actions can be computed by restricting those deltas to just the features
that management can control.
If those contollable deltas are computed using a $toBe$ with better scores than the current
$asIs$, then 
those deltas are now a \underline{plan} of how to move to a better place. Conversely,
if $toBe$ has a worse score, then the those deltas are  \underline{alerts} which, if they occur,
should be notified to management.
\section{Motivating Example}
\section{Related Work}
There is a long history of attempts to clarify and extend prior
information processing research into some simpler and unifed new framework.
For example, knowledge engineering research into rule-based programming


learners  
This document defines a unified toolkit to support the Busmann. In
this toolkit, we make decisions based on our experience with
building low-order polynomial time instance-based reasoning tools. We
offer this implementation as a baseline business intelligence
toolkit. At the very least, it is the tool that generates lower-bound
performance values (and, hopefully, other tools will do better). At
the very most, it is the tool that will be a framework that glues
together a community of researchers exploring business intelligence.

Notes:
\bi
\item[1.] Alerts are the monitors (learned in modeling) being triggered.
\item[2.] Summarization is range ranking (e.g. BORE the ranges, show a plot).
Modeling is exploring the effects of combinations of ranges, biased by the range rankings,
where the targets are neighboring clusters with higher or lower scores.
Simulation is also exploring the effects of combinations of ranges, but this
time, the user specifies those ranges.
\item[3.] Overlays are showing the clusters, colored by their mean performance score.
Goals are overlays where the performance score is the mean of the cluster - goal values.
Benchmarks are overlays where the performance score is the mean of the cluster - industrial standards.
\ei
\newpage
\section{to do}
\section{Origins}
{\IT} began as an optimzer to a rule-based learner. Everytime that learner proposed a rule, it was
assessed by passing it over a database of labelled test cases, then counting how often the rule's conclusions
were the same as   the labels of the instances selected by that rule.
To optimize that process, the database of examples was clustered and an index tree was built on-top of the clusters
so that a rule can find the nearest subset of test cases  $O(log_2(N))$ time. Then, it was realized that if
the same indexing scheme was applied to the training data, that many of the queries used to form the rules
could also be quickly executed. After a time, the rule learner faded away as more of its functionality was moved
into the tree-of-clusters abstract data type.

This approach is only interesting if the tree of clusters can be quickly generated. Naive
approaches to generating this tree take time $O(N^2)$ and have issues with high dimensionality data.
For example, 
Agglomerative Clustering (GAC)~\cite{Beeferman2000,Guha1998,Eisen}. 
GAC executes
bottom-up by grouping
together at a higher level $(i+1)$ the closest pairs of instances found at level
$i$.  The  resulting tree has $N$ instances at each level $i$ so building level $i+1$ 
requires $O(N^2)$ distance
calculations.

A faster approach may be to use Bentley's kd-tree algorithm~\cite{bentley90}. The algorithm
cycles through the $k$-dimensions of the data, splitting first on $k_1$, then $k_2$, etc, cycling back
to $k_1$ (unless some stopping criteria is satisfied). At each level,  the data is sorted according to
$k_i$ and a split created at the median point. This approach is faster than GAC since
two new splits are created in $O(N{\cdot}log(N))$ time
from the $N$ instances found in the current split. The algorithm can be further optimized via heuristics
that randomly select some subset of the $x$ points in the current split.

$kd$-trees can be further optimized by reducing the number of dimensions.
In other work, we have found that such {\em dimensionality reduction} is  a useful pre-processor for learning.
Real world data is often 
``noisey''  (containing spurious signals not associated with target values), or may contain irrelevant or
correlated dimensions. 
Hence, a standard result is that $k$ dimensions can be replaced wth $k' \ll k$, without lose of performance in
the learner~\cite{kohavi98,hall03,chen05}. A commonly used dimensionality reduction  mechanism is to replace
the original $k$ dimensions with an sorted list of orthogonal $component$. Each $component_i$ is a linear
combination of $k$, that accounts for as much of the variability of the data as possible (and the orthogonal
$component_{i+1}$ tries to account for the remaining variance).  The traditional way to find these components
is principled components analysis (PCA) but Du \& Fowler~\cite{Du2008} report that the matrix manipultions required for PCA
takes time $O(N{\cdot}k^2)$ 
for
data with $k$ columns and $N$ rows. Whiile this is less that then $O(N^2)$ cost of GAC, we still wish to avoid
polynomical time inference in the core of algorithm. 

Fasloutsos \& Lin~\cite{Faloutsos1995} offer a linear-time
heuristic for generating components. Given $N$ instances,
their ``FASTMAP'' heurestic sets the
the dimension of greatest  variablility to a line drawn between the two furthest points. 
These two points are found in linear time, as follows:
\bi
\item Pick any instance $Z$ at random;
\item Find the instance $X$ that is furthest away from $Z$;
\item Find the instance $Y$ that is furthest away from $X$;
\ei
The line $\overline{XY}$ is the FASTMAP approximation to PCA's $component_1$. 
An orthogonal 
$component_{2}$ can be found as follows:
\bi
\item Declare that the line $\overline{XY}$ is of length $c$ and runs from point $(0,0)$ to $(0,c)$.
\item Each of the $N$ instances has a distance $a$ to the 
origin (instance $X$) and distance $b$ to most remote point (instance $Y$).
\item By the cosine rule, each instance can be mapped into a 2-D space as follows: 
\begin{equation}\label{eq:ab}
\begin{array}{ccl}
x&=&(b^2 - c^2 -a^2)/(-2c)\\
y&=&\sqrt{a^2 -x^2}
\end{array}
\end{equation}
\ei
Note that this process maps the $N$ instances in $k$ dimensions to the two-dimensions $(x,y)$
in time $O(2N)$.
Since such a two dimensional space can be readily visualized, we experimented with this approach.
{\IT}'s modification to $kd$-trees is,  at each recursive step:
\be
\item 
Use the FASTMAP heuristic to find two distant points $X$ and $Y$ .
\item Using $X$ and $Y$ and \eq{ab}, map the data into $k=2$ dimensions.
\item On each dimension, find $\hat{x},\hat{y}$,  the distance of the median points to the origin.
We say that $\hat{x}$ and $\hat{y}$ divides the data west-vs-east
and south-vs-north, respectively. 
\item Split the data into one of four quadrants $(north,east)$ or 
$(north,west)$ or $(south,east)$ or $(south,west)$.
\item
Recurses into each quadrant.
\item
Stop when  a quadrant contains
less that $\sqrt{N}$ of the original
$N$ instances in the entire training set.
\ee
As a side-effect of the above,
{\IT} builds a tree of quadrants (and the top-most quadrant contains  the entire data set). Each node
of this tree is defined by \[(X,Y,c,\hat{x},\hat{y}\] 
A test instance $T$ can find its relevant sub-quadrant by computing $a=dist(T,X)$, $b=dist(T,Y)$,
$x=(b^2 - c^2 -a^2)/(-2c)$, and $y=\sqrt{a^2-x^2}$. The correct sub-quadrant could be found from
the following labels:
\bi
\item
if $y > \hat{y}$, then ``north'', else ``south'';
\item
if $x >\hat{x}$ then ``east'', else ``west''.
\ei
uhe instance then recurses to one of the quadrants (e.g. $(north,east)$).
Since
this process divides the data into four equal regions at each level of the tree, test instances
find their relevant data in time $log_4(N)$.

Once the data is projected into $k=2$ dimensions, we can visualize the results. Since we are using the most
remote point to define our dimensions, the presence of a single outlier can lead to very uneven displays of the
data. Hence, in our displays, we  set $x=log(x)$ and $y=log(y)$.

rule is This generates an index tree of clusters

The data is then split
into four (one each s
 
That is, ``optimizing'' $kd$-trees in this way would incur a computational cost
equivalent to GAC trees.

process. Real-world data is often ``noisey'' (contains signals not associated with  
The variability in the output of a model is some product of the variability in the $k$ dimensions
of the training data. Miller shows that reducing $k$

eften, $k$ dimensions
can be replaced with $k' \ll k$ 

used to split the data at the median a split is created
at the median point where (according  the k-dimensions
of the data set,  which, for a data sets
with $k$ dimensions, takes average time that is linear for 

For example kd-trees~\cite{bentley90}


prediction: probablity mass ina  cluster

minitoring: 2d constrast sets  from now to worse

planning: 2d constrast set from now to better

explanation: nd contrast sets 

unsupervised learning: split on median

k-th enarest neighbor: unsupervised, then membersho

contrast sets: 
	give a path root to node with sub-trees c1,c2
    give ignored clusters on path c3,c4,c5...
    find the stuff that is in c1 that is not in c2,c3,c4,c5,...
    i.e. fss

ripple down rules: see contrast sets

classification: walk the cluster tree then runa  classifer at the leaves

association rules:
 	high probabilty entriesl in local region that are not high prob elswhere. aka. contrast sets

feature sunset selection 
	difference in split points of two clusters. and if we keep some simple stats on each cluster, can rank those contrast sets

instance selection
	prune sub-trees with ambigous results (e.g. large variance)
	prune sub-trees with clear results (low variance)

dimensionality reduction
	comes for free

\subsection{meta-stuff}
anomaly detection
	outside the certification envelope

active learning
	find two clusters you want to prune and ask around the middle (i.e around their daddy)

stability: repeat above analysis using 20*66% of data

bagging: do stability and report mean predictions

integration: do for N and sum over the results

	
\section{Definitions}
\subsection{Distance}

A set of instances $I$ consists of independent and dependent attributes. For
example, the ``LOC'' of a system might be an independent attribute
while ``number of bugs'' or ``effort hours" might be dependent.

We assume that discrete classes can be mapped to some numeric utility
$U$ and that numeric classes have some direction of $better$ and
$worst$.

We also assume some distance function $dist$ defined for independent
attributes that satisfies the standard distance axioms; i.e.  for
instances $(x,y,z) \in I$:

\bi
\item
$dist(x,x)=0$
\item
$dist(x,y) = dist(y,x)$
\item
$dist(x,z) \le dist(x,y) + dist(y,z)$.
\ei
Also, we assume that $dist$ is defined between two instances
with values for some subset of their independent attributes.

\subsection{Clusters}

At time $T_i$, instances $I_j$ belong to clusters $C_k,C_l,...$ where
probability at probability $0 \le in(T_i,I_j,C_k) \le 1$.

Each cluster holds a set $D$ containing the intra-cluster distances
between all pairs $(x,y) \in C_i, x > y$, sorted in ascending order.
If the cardinality of $D$ is $d$, then the cumulative probability
distribution function $pdf$ is computed by normalizing the first $i$
elements of $D$ according to the sum of all sorted distances in $D$:
\[pdf_i =  \frac{\sum_i D_i}{\sum_d D_d}\]
(This $pdf$ function will be used to detect anomalies, see below.)

\subsection{Predictions}
The $prediction$ of the dependent attributes is computed from a $summary$
of the $k$-th $nearest$ neighbors.

This definition is independent of the clustering method. For example:
\bi
\item
Some clustering such as EM algorithms allows for instances to exist in
multiple clusters at one time.
\item
On the other hand, clustering algorithms such as k-means, demand that
an instance can only exist in one cluster at one time, i.e.
\[in(T_i,I_j,C_x)=1
\wedge \forall x \not= y, in(T_i,I_j,C_y)=0\]
\item
Within these definitions, an implementation is free to make its own
decisions regarding how to $summarize$ the neighbors, how many
neighbors to include in that summary (i.e. what value to use for $k$)
and how to compute $nearest$.  \ei Optionally, it may be a useful
optimization to pre-compute and cache the $summary$ values for each
cluster before processing test instances.

\section{Some Details}
Our current implementation uses a top-down recursive partitioning of
the instance space, followed by a clustering together of neighboring
sub-trees with similar densities of instances.  In this approach: \bi
\item
Two instances are $near$ if they exist in the same cluster.
\item
Each cluster has its own $summary$ being the expected value of the
dependent variables in that cluster (which is the median for number
dependent variables and the most frequent value for discrete dependent
variables).
\ei 
This approach results in a binary tree that can map a
new test instance to its near neighbors in time logarithmic on the
number of instances. 

The root of the binary tree contains all instances. Each leaf represents a cluster containing a subset of the instance space. Intra-cluster distances computed amongst clusters allow us to compare metrics applied to cluster $C_i$ with neighbors $C_j, C_k...$.

Something about linear-time dimensionality reduction allowing us to graphically represent clusters, summarizing performance with respect to metrics applied to dependent variables amongst instances within a cluster.  Or is this too specific?

Doodle?

Something about being able to ``Drill Down'' to the instance level.

\section{Graphics Placeholder}
\newpage
\begin{figure}
\center{\includegraphics[width=200pt]
{includes/neighborhood_effort_grayscale_trimmed_small.png}}
\caption{\label{fig:neighborhood} 
Instances are mapped into a two-dimensional space and are then 
clustered through a recursive, equal frequency partitioning of the 
instance space.}
\end{figure}

\begin{figure}
\center{\includegraphics[width=200pt]
{includes/neighborhood_effort_grayscale_trimmed_small_scores.png}}
\caption{\label{fig:neighborhood2}
Same thing with a score scale.}
\end{figure}

\begin{figure}
\center{\includegraphics[width=200pt]
{includes/zoom3_you_are_here_grayscale_trimmed_small.png}}
\caption{\label{fig:neighborhood3}
Close view of clusters. You are here is the larger instance.}
\end{figure}
\pagebreak
\section{Implementing the Busmann9}
\subsection{Exploration}
\subsubsection{Trends}

We say that the $trend$ for of an instance is ordered set of pairs
$((T_i,C_k), ...)$ denoting when an instance was in some cluster at
probability $in>0$.

\subsubsection{Alerts}

We raise an alert on an  instance if either:
\bi
\item Its {\em dependent variables} values are significantly different to
the $summary$ value of the cluster containing them.
\item Or if the {\em independent variables} values are ``too
far away'' from its closest neighbor.
Our current implementation defines ``too far away'' as
follows. If the distance of an instance to its nearest neighbor in a cluster
is $x$, then we find the position of $x$ in $pdf$ using 
\[i= argmin_i \left(D_{i+1} > x\right)\] 
Then, 
the instance is anomalous if   $rand() > \frac{i}{|D|}$ (where $0 \le rand() \le 1$).
\ei

\subsubsection{Forecasting}
If an instance falls into some cluster, then the distribution of
attribute values within a cluster are the forecasts for all instances
in that cluster.

\subsection{Analysis}

\subsubsection{Summarization}
To summarize the key aspects of a cluster, we perform range ranking:
\bi
\item Discretize the numeric dependent variables into X\% $best$ and (100-X)\% $rest$;
\item Discretize the numeric independent variables into $B$ equal frequency
bins;
\item Find the frequency of each bin in each class for best or rest;
\item Find the bins whose frequency is very different in the different classes;
\item Present those as a nomogram.
\ei
\subsubsection{Overlay}
We present a visualization of the clusters, each one colored according
to its utility scores (0 for worst, 8 for best, sliding scale in
between).  We then indicate ``you are here''.

\subsubsection{Goals}
Goals are displayed in the same way as overlays, but this time worst,
best is computed from a user-supplied table of goal values. If a
cluster meets a goal, it scores 4. Otherwise, if it falls below goal,
it scores zero to three.  Otherwise, if it falls above goal, it scores
five to eight.

\subsection{Experimentation}
\subsubsection{Modeling}
In this instance-based framework, a model is the delta between two
clusters (selected by users) computed by ranking bins using BORE,
then testing what happens if all items in cluster one are changed by
the top $i$-th ranked items in the BORE list. This is reported as a
decision ordering diagram (see http://menzies.us/pdf/10keys.pdf).

Note that models can result in:
\bi
\item $Plans$ that we want to perform; (i.e. deltas between worse and better clusters);
\item or $Monitors$ for conditions we want to avoid; i.e. deltas between
better and worse clusters).
\ei
\subsubsection{Benchmarking}
Benchmarks are displayed in the same way as overlays/ goals, but this
time worst, best are computed from a user-supplied table of
established benchmarks.

\subsubsection{Simulation}
Simulations are almost the same as modeling. However, in modeling, the
contrast sets were between clusters. Here, there are a set of proposed
changes (made by the user) and we want to assess the effects of these
changes on the ``you are here''. If the users' changes are ordered
(from ``really want to do'' to ``might do'') then the results of these
``what-if'' queries can be presented as decision ordering diagrams.


 F


At each recursive call, WHERE builds its quadrants using

This continues till some stopping criteria is 
Data mining technology can find patterns in complex data.
Consquently, much current research is applying data mining technology to the new
discipline of business intellgience
(a.k.a. predictive analytics).

After decades of work in this area, we assert that there are significant gaps between
what business users want and what is provided by data miners.
For example:
\bi
\item
Some learners produce verbose and hard to understand output
(e.g. the decision trees of C4.5~\cite{quinlan92}).
Such verboisty can be dramatically reduced using
tree-pruning algorithms~\cite{me00e} that report just the minimal, most influential,
differences between 
classifications~\cite{me03o,me07}.
\item
Users may evaluate the learnt
rules by domain-specific criteria (i.e. not merely accuracy but
other issues relating to local business goals). For such users,  we have built stochastic
learners that biased their internal model selection via domain-specific
predictates~\cite{me10a,milton08}.  
\item
Sometimes users want to rewrite local
business policies using the  learner output. For these uses,
feature subset selection
to reduce the variance in that output~\cite{me10c,me05c,me10d}.
\item
For business client that use learners 
to find better management actions, we used learners in a cylic
manner (where the model learned at round $i$ constrains the simulations studied
in round $i+1$)~\cite{me07f,me09g,me09i}.
\ei
Based on this experience, we are concerned
that 
the future of applying data mining to software engineering
is an endless sequence of hacks and tweaks of existing data miners to accomodate
an endless sequence of new business requirements?
Perhaps it is time to take a more basic look at the information processing
needs of business users.
Rather than 
{\em reacting} to the needs of our current
business users, it might be better to
should  {\em anticipate} those needs.

One place to start would be
to
synthesize past work into a simpler combined framework that was easily extended
to future needs.
Such a framework should:
\be
\item
{\em Unify} many business-level learning functions;
\item
Offer a {\em simple interface} to its users;
\item
Increase {\em trust} in the models generated by the learners;
\item
Enable {\em sharing} of knowledge across communities;
\item
Be based on a some underlying {\em small set of simple} data structures and algorithms;
\item
Simplify the {\em implementation of current methods};
\item
Simplify the {\em creation of new methods};
\item
{\em Scale} to large and complex data sets.
\ee
{\IT}  is a candidate framework that supports the above eight points.
It is an instance-based approach
for
uncovering important business patterns from multi-dimensional data.
{\IT} indexes historical cases using a recursuve
divisive (top-down) clustering  algorithm
and  constrast set learners
report the minimum deltas between clusters.
It scale to very large dimensionality data and
offers a intuitive visualization interface.
Also, {\IT} supports sharing and privacy and discovery tools (compression, noise reduction,
hyper-k anomization, active learning).

Our analysis shows that {\IT}
subsumes a decade  of our research into business-level learning: all the essential
functionality
of~\cite{me00e,me03o,me07,me10a,milton08,me10c,me05c,me10d,me07f,me09g,me09i}
can be coded using {\IT}
(specifically:
clustering, contrast-set learning, classification
can execute in {\IT}, and in linear time). 
At the very least, {\IT} could be used as an
optimization of the working memory of other learning methods
(e.g. instance selection, feature selection,
association rule learning, anomlay detection).
At the very most, it replaces those methods with faster implementations.
 
This paper introduces {\IT} and, using examples from software effort estimation
and defect detection, show the current empirical from tools built in this framework.
Also, we audit {\IT} using a recent survey of information processing needs conducted at 
Microsoft~\cite{busezimmermann11}:
we show that {\IT} offers support across the full space of those information needs.

The rest of this paper is structured as follows.
XXX


\section{Scalability}
If our advice widely applied, the then the hunt for local lessons will become very extensive.
In that case, it is vital that the device used to find localities within a software project
will scale to large data sets. One reason we prefer the algorithms described above is that they
support such scaling.  This is not true for other approaches:
\bi
\item Like WHERE, KD-trees build an index structure over a set of divided instances.
For each attribute in turn, the data is divided on median point of that attribute.
Recursive calls to KD-trees further divide the data on the remaining attributes. 
As the number of attributes grows, 
KD-trees become slow.
WHERE, on the other hand, recursively divides the
data on the two dimensions of greatest variance and so can handle very large attribute sets.
\item
Like WHERE, principle component analysis (or PCA) generates orthogonal dimensions that span the direction
of greatest variance. However, matrix factoring methods like PCA take polynomial time to execute~\cite{Du2008}
while WHERE takes linear time (since it uses the FASTMAP heuristic~\cite{Faloutsos1995}).
\ei

{\em Scalability:}
To assess the scalabilty of this process, we collected the runtimes for the different stages
of {\IT}-1 using data sets where the rows were copied once, twice, four, and eight times.
The results are show in \fig{runtimes}: note the linear growth rates in the total time, as well
as the main sub-routines of the process. 
\begin{figure}[!b]
\begin{center}
\includegraphics[width=3.5in]{all.pdf}
\end{center}
\caption{Runtimes for a PYTHON version of RPC-1,measured against
data sets whose rows have been copied once, twice, four, and eight times. 
Note that the runtimes scale linearly with data set size.
}\label{fig:all}
\end{figure}


{\em Low complexity:} Overall, the complexity for quadtree generation and GRIDCLUS is very low:
\bi
\item
Each recursive call for quadtree generation requires
2N distance calculations to find the distant points that define the 2D plot
of \fig{geo}. At each recursive level of quadtree generation,
this $O(N)$ calculation is repeated four times on 
one-fourth the data seen in the previous level of recursion. Hence, the total time for quadtree
generation is linear on the training data size $N$. 
\item
GRIDCLUS must sort the leaf quadrants, which takes times
$L(C{\cdot}log(L))$, where $L$ is the number of leaf quadrants. Typically, $L$ is some small fraction
of $N$ so, as shown in \fig{all}, it is the fastest sub-routine inside {\IT}. 
\ei
{\em Indexing:}  a side-effect of this process is the creation of the quadtree over a set of clusters.
 This quadtree can be used by
test instances to find their nearest neighboring instances in $O(log_4N)$ (at each level of the quadtree,
select the sub-quadrant by relecting over the distance of the instance to $X,\hat{x},\hat{y}$).

{\em Speed:}
One implementation RPC-1 can complete the above process in 2.5 seconds
for an 800K table
of data (6500 rows, 26 columns) with  $\alpha=20$\footnote{ 
On a OS/X iMac,
with 4GB of RAM. Time excludes load time from disk}\footnote{andrew: what data?}. 
That implementation was written in Steel Bank Common Lisp so faster speeds could result
from coding this in ``C''.


