Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
One of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the question of classification of data according to some clustering rule. Often the data is noisy and even approximate classification is of extreme importance. The difficulty of such classification stems from the fact that usually the data has many incomparable attributes, and often results in the question of clustering problems in high dimensional spaces. Since they require measuring distance between every pair of data points, standard algorithms for computing the exact clustering solutions use quadratic or nearly quadratic running time&semi; i.e., O(dn2(d)) time where n is the number of data points, d is the dimension of the space and (d) approaches 0 as d grows. In this paper, we show (for three fairly natural clustering rules) that computing an approximate solution can be done much more efficiently. More specifically, for agglomerative clustering (used, for example, in the Alta Vista search engine), for the clustering defined by sparse partitions, and for a clustering based on minimum spanning trees we derive randomized (1 approximation algorithms with running times (d2 n2) where  > 0 depends only on the approximation parameter &epsi; and is independent of the dimension d.
Introduction
Clustering of data is an essential ingredient in many information
retrieval systems (e.g., for building and maintaining
taxonomies), and plays a central role in statis-
tics, pattern recognition, biology, web search engines,
distributed networks, and other fields. Recently, the
concept of clustering has taken on some added significance
as researchers have begun to view "data mining"
as a question of finding "hidden clusters" in large collections
of data. (For a survey of clustering methods
see [18, 7] and references therein.) Informally, clustering
algorithms attempt to form groups of similar objects
into clusters based on the attributes of these ob-
jects. The question as to how best to define "the clustering
problem" seems to be particularly difficult in large
unstructured databases whose members are viewed as
points in some high dimensional vector space.
The most successful formulations of clustering seem
to be graph-theoretic formulations, providing results
which have the best agreement with human performance
[13]. In this formulation, the main ingredient of graph-theoretic
clustering can be stated as follows: given n
data points in some metric space, do the following: (1)
compute some spanning graph (such as the complete
graph, or a minimumspanning tree) of the original data
set; (2) Delete (in parallel) some edges of this graph (ac-
cording to some criterion, such as distance); (3) output
clustering (such as connected components or some partitioning
of the nodes which depends on the topology)
of the resulting graph.
For a more concrete example, consider the frame-work
of hierarchical clustering where data points are
joined into sets of objects, called clusters, with the property
that any two sets are either disjoint or nested.
In the agglomerative approach to hierarchical cluster-
ing, clusters are joined to form larger clusters based on
the distance between the clusters. That is, all clusters
with inter-cluster distance below a certain threshold are
joined to form bigger clusters and so on. The distance
between clusters can be defined in a number of ways. A
simple and common choice is to compute the distance
between the centroids of the clusters. Examples for applications
that use such clustering rules include methods
for determining consensus in biological sequencing
data, and the mutual fragments heuristic for computing
traveling salesman tours, see Eppstein [7].
choice of distance function is the so-called single-
linkage distance, where the distance between clusters
is the minimum distance between a point in one cluster
and a point in the other cluster. Of course, measuring
the distance between centroids, as well as other
choices for a distance function, can be formulated as a
single-linkage distance between cluster representatives;
i.e., sets of points that replace the clusters.)
In this formulation, the core task for computing an
agglomerative clustering is the following: Start with a
complete weighted graph on the data set (points, or
cluster representatives). Delete edges whose weight exceeds
some given absolute bound, then output the connected
components of the resulting graph. In addition
to the afore-mentioned application to hierarchical clus-
tering, this graph-theoretic clustering is used by the
Alta Vista tm search engine in order to prune identical
documents from its world-wide web database [4]. We
shall refer to it, somewhat imprecisely, as agglomerative
clustering.
A second type of clustering with many applications
in distributed computing (e.g., for routing tables, load
file allocation) is defined by the sparse partitions
of Awerbuch and Peleg [1]. Roughly speaking,
in our setting it says that given n points and a distance
r, as above define a graph where two points are adjacent
if they are at (weighted) distance r or less. Nodes
must be partitioned into a collection of possibly overlapping
clusters. The constraints on the clusters are that
(i) the (unweighted graph theoretic) diameter of each
each cluster is small (a typical value is O(logn)); (ii)
the clusters belong to a small number (again a typical
number is O(logn)) of color classes, so that the clusters
within each class are disjoint and, (iii) for every point
x and all its neighbors are contained entirely in at
least one cluster. Notice that this type of clustering is
not hierarchical, as clusters (from different classes) may
overlap.
A third type of clustering requires computing a mini-
mumspanning tree (MST), so we call it MST-clustering.
The clusters are the connected components of the forest
that results from eliminating edges in the MST whose
length exceeds a given parameter. Exact MST-clustering
is equivalent to exact agglomerative clustering. It is
not hard to see, however, that the approximate versions
may differ substantially (because the approximation of
MST is with respect to the total length of edges, and
not with respect to the length of each edge separately).
We remark that MST can be used as a subroutine for
a variety of clustering methods.
We study all these clustering problems for points in
d dimensional Euclidean space. (Our results extend to
other norms, we leave that to the full version of the
paper.) This is a natural setting for applications to information
retrieval and data mining. The main issue
we address is the following: A naive approach for any
one of these problems (in high dimension) is to compute
the distances among all pairs of points, and then execute
any of the above clustering rules on the resulting graph.
Of course, this naive approach has quadratic (in n) or
worse time complexity. Can this quadratic behavior be
avoided? This is the context in which similar problems,
such as minimum spanning tree or closest pair, have
been studied in computational geometry (see [9]), but
often the solutions are better than quadratic for low dimensions
only. For example, Yao [19] shows that MST
can be computed in subquadratic time but the exponent
is rapidly converging to 2 as the dimension grows.
However, recent work on another geometric problem
nearest neighbor search (NNS) - shows that performance
degradation as the dimension increases can
be avoided if an approximation to the distances is allowed
[14, 10, 15].
We therefore focus on approximate versions of the
agglomerative and MST clustering problems. In most
applications, the choice of both distances and the clustering
rule is done on a heuristic basis, so approximate
clustering is quite sufficient. The problem of sparse
partition clustering already contains a certain degree
of approximation implicit in the use of the "big Oh"
notation and our methods can be used to derive improved
bounds for the "exact problem" as defined with
the understanding that the "big Oh" hides a factor of
uniformity, we refer to our sparse partition
algorithm as an approximation algorithm.) For all of
the above problems and for any (approximation factor)
ffl, we derive clustering algorithms with time complexity
~
O(d depends only on ffl. (The ~
O
notation also hides factors of log n.) Our subquadratic
algorithms use some of the recent results on approximate
NNS. In particular, we use modified versions of
the algorithms and data structures of Kushilevitz et
al. [15]. One of the difficulties in obtaining our results
is that these NNS algorithms are randomized, and their
probabilistic guarantees are not strong enough to allow
a simple high-probability successful termination of
the clustering algorithms (without requiring quadratic
or worse running time). We note that Indyk and Motwani
[10] suggest that their NNS algorithms can be used
to derive subquadratic 2 approximations for some
of the problems mentioned here. Subsequent to the acceptance
of this paper, they informed us that the full
version of their paper [11] explicitly states an improved
approximation guarantee of 1 ffl, as well as mentioning
applications of approximate nearest neighbor algorithms
to additional problems, including the approximate
MST computation.
Once we are willing to settle for approximate solutions
we can appeal to the dimension reduction techniques
of Johnson and Lindenstrauss [12] (see also [8,
16, 10]). Simply stated, any n points in Euclidean space
of any dimension d can be probabilistically mapped to
an O(log n=ffl 2 ) dimensional space so that no distance
is increased and (with high probability) no distance
shrinks by more than a factor and this mapping
has time complexity O(dn log n=ffl 2 ). It follows that for
all the approximate clustering algorithms we consider,
we can assume that d = O(log n). However, for the
sake of completeness (and because the dependence on
d is interesting even for "small" d), we state all results
in terms of d and n as well as the approximation factor
ffl.
The naive approach to clustering in Euclidean space
is to first compute all \Gamma n\Delta
distances, and then apply a
clustering algorithm to the resulting weighted complete
graph. For agglomerative clustering, (with standard implementations
of a connected components algorithm)
this naive approach would require O(n 2 ) time. Broder,
Glassman, Manasse, and Zweig [4] give a heuristic used
in Alta Vista tm that seems to give good running time
in practice, but requires quadratic time in the worst
case.
For sparse partitions Awerbuch and Peleg [1] give
a polynomial time algorithm (in the number of edges).
In the naive approach, we have a weighted complete
graph, where all \Gamma n\Delta
edges are present. The following
bounds are stated for this setting. Linial and Saks [17]
yield a randomized ~
(where the
~
O notation hides polylog(n) factors). The best result
to date for the above setting (on a complete graph) is
the deterministic ~
of Awerbuch, Berger,
Cowen and Peleg [2].
The bottleneck for MST-clustering is computing the
MST. We show how to apply the agglomerative clustering
algorithm to derive a subquadratic approximate
Euclidean minimum spanning tree (MST) algorithm.
Sollin (see in [3]) shows how to reduce the MST problem
to a problem similar to exact NNS. Yao [19] gives another
reduction, and uses it to give a subquadratic algorithm
for (exact) MST in low dimension. (Yao mentions
obtaining a fast approximate MST algorithm as an open
problem.) Yao's reduction seems specific to exact NNS,
whereas Sollin's may be adapted to approximate NNS,
though it is not clear how to overcome the probabilistic
guarantees problem without resorting to our methods.
The reduction of Yao yields an MST algorithm with
time complexity O(n 2\Gamma2 \Gammad+1
(log n) 1\Gamma2 \Gammad+1
). (This is
somewhat better than what would result from using
Yao's algorithm with Sollin's reduction.) Chazelle [6]
improves this bound further, still the bound approaches
quadratic behavior as the dimension grows. Notice that
dimension reduction techniques cannot guarantee low
distortion unless the dimension reduces
to\Omega\Gamma/23 n), for
which Chazelle's algorithm is still quadratic.
We also briefly indicate some other applications of
our methods and algorithms to traditional computational
geometry problems, for example a subquadratic
algorithm for the Euclidean closest pair problem. The
problem has many applications; for a full history see
Cohen and Lewis [5] and Eppstein[7] and references
therein. Kleinberg [14] uses his approximate NNS results
to get an approximate closest pair algorithm with
eliminating
the dependency on the dimension for d - n= log n). We
show how to solve approximate closest pair (and approximate
furthest pair) problems in subquadratic time
for all d.
Preliminaries
We denote by E d the d dimensional Euclidean space;
i.e., IR d with the metric induced by the L 2 norm.
An ffl-approximate \Delta-proximity table for a finite set
is a data structure supporting the following
operations
ffl construct(P ), which creates a new instance of
the data structure for data structure
consists of jP j O(1) "entries", where O(1) may
depend on ffl.
ffl neighbors(x), for any x 2 E d , which returns a
subset (obtained from one of the above
entries) containing all the points in P within distance
\Delta of x, and perhaps some additional points
of P within distance (1 + ffl)\Delta of x. (Notice that
there may be several possible correct answers to
neighbors.)
An efficient construction of an ffl-approximate \Delta-proximity
table lies at the heart of our results. We can get such
a construction by adapting the approximate nearest
neighbor search algorithm of [15]. These results provide
the following guarantee:
Lemma 1. For every ffl ? 0 and every fi ? 0 there
exists c ? 0 such that there is a randomized implementation
of an ffl-approximate \Delta-proximity tables with the
following properties:
1. construct takes T (jP
operations

2. neighbors takes q(jP operations

3. for any x 2 E d , the probability that an entry, and
hence neighbors(x), returns an incorrect list is
at most jP j \Gammafi .
We also need to apply frequently a union/find algo-
rithm. For our purposes it is sufficient to assume simply
(say using balanced trees) that any union or find operation
in a universe of n elements can be performed within
steps.
We also need to call approximate nearest (and fur-
thest) neighbor algorithms 1 of [15]. These algorithms
work for all queries and all distances. In particular, an
ffl-ANN/ffl-AFN table for a finite set P ae E d is a data
structure supporting the following operations
which creates a new instance of the data structure
for data structure consists of
may depend on ffl,
and every entry contains either a single element of
P or a symbol indicating that the entry is empty.
ffl closest(x), for any x 2 E d , which returns a point
in P (contained in one of the entries), whose distance
from x is at most 1 times the minimum
distance of a point in P from x.
ffl furthest(x), for any x 2 E d , which returns a
point in P (contained in one of the entries), whose
distance from x is at least 1 \Gamma ffl times the maximum
distance of a point in P from x.
1 The algorithms of [15] are easily adapted to finding furthest
neighbors.
An efficient construction of an ffl-ANN/ffl-AFN table
is easily constructed from the approximate nearest
neighbor search algorithm of [15]. These results provide
the following guarantee:
Lemma 2. For every ffl ? 0 and every fi ? 0 there
exists c ? 0 such that there is a randomized implementation
of an ffl-ANN/ffl-AFN table with the following
properties:
1. construct-ANN/construct-AFN
takes T (jP
2. closest takes ~
3. furthest takes ~
4. for any x 2 E d , the probability that closest(x)
or furthest(x) returns an incorrect answer is at
most jP j \Gammafi .
Agglomerative Clustering
In this section we discuss the following clustering prob-
lem: Given a set P ae E d of n points and \Delta ? 0,
partition P into the connected components of the following
graph . The graph GP;\Delta has node set P
and an edge connecting every pair of nodes at distance
or less. In the approximate version of the problem,
we are given an additional parameter ffl, and the graph
is replaced by a graph GP;\Delta;ffl . The graph GP;\Delta;ffl
has the same node set as GP;\Delta . Its edge set contains
all the edges of GP;\Delta . In addition, it may contain edges
connecting pairs of nodes at distance greater than \Delta,
but no greater than (1 ffl)\Delta. (Notice that the choice
of GP;\Delta;ffl is not necessarily unique - any such graph
gives a correct solution to the approximate problem.)
We remark that in addition to separating the graph
into connected components, our algorithm can be easily
modified to output a witness spanning tree for each
component.
The algorithm. We maintain a union/find structure
with element set P and a multigraph G(P; E), represented
by the adjacency list for each node. In addi-
tion, we maintain several proximity tables for subsets
of P . We set be the
Partition P arbitrarily into n 1\Gammaffi sets
Repeat k times:
Initialize the union/find structure
(each element is a set);
For each
Mark each entry in T by 0;
For each node x
If
If L is marked 1 and dist(x;
If L is marked by 0 and 8i, dist(x; y i
8i, union(x,y i
Mark L by 1.

Figure

1: The agglomerative clustering algorithm.
constant guaranteed by Lemma 1 Set
The algorithm is shown in Figure 1.
At the end of the algorithm, the desired partition of
into clusters is the partition of the (sparse) graph G
constructed by the algorithm into its connected components

Notation. Let x 2 IR d and let ' ? 0. Denote by
B(x; ') the closed ball around x with radius '; i.e., the
set fy 2 IR d j 'g.
Correctness. The correctness of the algorithm is an
immediate corollary of the following claim:
3.
1. With high probability, (i.e.,
is in the same connected component as all
the nodes in B(u; \Delta).
2. If u; v 2 P are in the same connected component
of G, then there is a sequence of nodes
v, such that for all
To see (1), consider an
used by the algorithm and let u be some point in P .
be the event that u retrieves a proximity table
entry containing all of B(u; \Delta) " P i and none of
(call such an entry good). Pr[E i
is the failure probability of a query. Thus
We have n nodes and n 1\Gammaffi
sets P i , so with high probability every event
pens. happens and u retrieves a good entry
marked by 0, then we connect u to all the nodes in that
entry. Otherwise (the entry is marked 1), there is another
node v connected to all the nodes in the entry,
and u connects to one of the nodes of the entry.
For (2), use induction on the number of union operations
performed. Consider a union(x,y) operation
which joins two components y. The
only case which does not follow from the induction hypothesis
is But by the induction
hypothesis, there is a sequence
another sequence
v, such that for every i
ffl)\Delta. By the specification of the
algorithm,
Analysis. We analyze the complexity of one iteration
of the outer "Repeat loop" and then multiply by k to obtain
the total running time. For simplicity we suppress
the influence of c and ffl in the big Oh notation. The time
complexity of the "Repeat loop" is upper bounded by
the sum
where D is the cost of building the n 1\Gammaffi proximity ta-
bles, N is the minimum search cost for the nodes (i.e.,
assuming they retrieve entries marked 1 only), B is the
cost for retrieving bad entries, G is the cost induced by
retrievals of good 0-marked entries, and U is the cost
of performing union/find. We analyze each term separately

4. Let c(fi) be the constant
from Lemma 1. Let n) be the worst case
cost of a union/find algorithm. Then,
ffl For D: In each iteration we have to construct n 1\Gammaffi
proximity tables, each for n ffi points. The construction
of each table takes T (n ffi ) steps.
ffl For N : In each iteration we process each of the
n points. Each point requires a search in n 1\Gammaffi
proximity tables. The search in each proximity
table takes q(n time. If the retrieved entry is
not empty and is marked 1, there is an additional
cost of O(d) to compute the distance to the first
point on the list.
ffl For B: In each iteration we access n 1\Gammaffi proximity
tables, searching for n points in each table. For
each table, for each point, the probability that
the point retrieves a bad entry is at most \Gamma
Therefore the expected number of bad entries handled
in each proximity table is at most n 1\Gammaffi . For
each bad entry, we may have to compute the distance
to all the points in the table. This costs
O(n
ffl For G: In each iteration we handle n 1\Gammaffi proximity
tables. Each table has at most T (n ffi ) entries. An
entry is accessed as a good entry that is marked
0 at most once. If this happens, we compute the
distances to all the points listed, at most n ffi . Each
distance costs O(d).
ffl For U : The bound follows from an estimate on
the total number of union operations performed.
In each iteration we handle n 1\Gammaffi proximity table.
Each proximity table is accessed by n points. If
a point retrieves an entry marked 1, it causes at
most one union operation, so there are at most n
such operations per table. Good entries marked 0
cause at most n ffi union operations. For each entry
we do this at most once. Thus, the number of these
union operations per table is at most n ffi T (n
Theorem 5. The total running time of the agglomerative
clustering algorithm is O(d 2 n 2\Gammaffl 2 =2c log n)
Partitions
In this section we discuss computing a sparse partition
clustering of a finite set of points
xng. Our definition of sparse partitions is the
Euclidean analogue of the definitions given in [1], [2]
and [17] for undirected graphs where in those papers
distance refers to path length.
A sparse partition C of P (with parameter r ? 0), is
a collection of subsets (called clusters)
P satisfying the following conditions:
1. The (Euclidean) diameter of each cluster S i is at
most O(r log n).
2. For every contained completely
in at least one of the clusters where B(x; r)
is the Euclidean ball of radius r centered at x.
3. The clusters can be grouped into O(logn) classes,
so that the clusters in each class are disjoint. (It
follows that for each x 2 P , there are at most
O(logn) clusters containing x.) Furthermore, the
distance between any two clusters in the same class
is greater than r; that is, if clusters S i and S j are
in the same class with x
the Euclidean distance between x and y is greater
than r.
(The original definition of sparse partitions is more general
in that it allows tradeoffs between the values in
conditions 1 and 3. The definition here uses the most
common values in applications. Our results extend to
these general tradeoffs.)
The algorithm. As in [17], we run O(logn) phases. In
each phase we grow a new class (of clusters) which contains
a constant fraction of all the nodes. In a phase,
the status of each node is either free or used (initially
in a phase, all nodes are free). We grow a cluster
by picking a free node and adding its free neighbors
in a breadth first search manner, stopping at a
distance chosen at random using the truncated geometric
distribution of [17] (i.e., choose the distance to be i
Repeat O(log n) times:
Initialize proximity tables (see below);
Mark all x 2 P as free;
Choose at random i 2 ng
with geometric truncated distribution;
While there is a free node x
Initialize a new cluster S / ;;
Mark node x as used
Initialize F / fxg, F 0 / ;;
For i steps do:
For each y
For each free z 2 ~
mark z as used;
S

Figure

2: The sparse partitions algorithm.
with probability 2 \Gammai , for i ranging from 1 to 2 log
and with probability 2 \Gamma2 log n+1 , for
n). The main difference with [17] is in our
implementation of the breadth first search, which exploits
the underlying structure of the graph, giving the
speedup in the running time. In particular, we need
to be able (with high probability) to determine all so
points in an approximate ball
~
r) centered at y of radius r which contains B(y; r)
and may also include some (so far free) points in the
slightly larger ball ffl)r). A more formal description
of the algorithm appears in Figure 2.
Computing neighbors. We compute the set ~
using the proximity tables that are initialized at the beginning
of the phase. We first explain the initialization:
Let ffi and k be as in the previous section. We partition
disjoint sets of size n ffi each. For each set
we construct k independent ffl-approximate r-proximity
tables. We also mark all the entries in all the tables by
This completes the initialization. We construct the
set ~
r) as follows: We fetch neighbors(y) in each
of the kn 1\Gammaffi tables. Let be the resulting
lists. We ignore all lists marked by 1. For every
list L marked 0 we compute dist(y; z), for all z 2 L. If
any point in L is further from y than (1 ffl)r, we leave
L marked by 0. Otherwise we add the elements of L to
~
r) and mark L by 1.
Correctness. Here we prove that the above algorithm
indeed produces the desired sparse partition clustering
with high probability. The main issue is to show that
~
B(y; r) is computed correctly. The rest of the argument
follows in general the line of argument in [17]. The
added difficulty is that because we have approximate
distances only, proximity between points is no longer a
symmetric property.
at least 19
20 the following
holds for every y If the algorithm computes ~
then this set contains all the points in B(y; r) that are
still free, and none of the points in B(y; (1
Proof : The latter claim is obvious because the algorithm
checks the distances to the points it adds to
~
r). To see the former claim, we argue as in the
proof of Claim 4 that the probability that the good
entries retrieved by y do not contain all the points in
r) is at most n \Gamma2 , and therefore the probability
that this happens for any y is at most n \Gamma1 . Finally,
notice that if an entry is marked 1, then the status of
all the points listed in the entry (in the current phase)
is used.
7. Consider any particular phase. Let y 2 P
be the first point in B(x; r) that is placed in F in that
phase. If y is placed in F just before the execution of
iteration of the "For" loop of that phase,
then B(x; r) is contained in a cluster generated in the
phase with probability at least 1
5 .
be the set of points in B(x; r) that are
in F at the start of iteration j; that is, if
are the points that were placed in F 0 during iteration
1. Assume for the moment that x 62 F j . Clearly,
. Moreover, at the start of the jth iteration,
all the points in B(x; r) n F j (and in particular x) are
free. As the jth iteration is executed, we know that
Given that i - j, and that j - 2 log
the conditional probability that
4 . So
assume that the event
assume that the event in Claim 6 holds. This happens
2 The choice of constant is arbitrary
with probability at least 1
5 . As y 2 B(x; r),
r), and x
is placed in F 0 during the jth iteration (by Claim 6).
Let F j+1 be the set of points in B(x; r) that are placed
in F 0 during the jth iteration. At the end of the jth
iteration, all the points in F j are added to the cluster S,
and all the points in F 0 are placed in F . In particular,
x is placed in F , and so are all the other points in F j+1 .
We have assumed that i - j+2. Therefore iteration j+1
is executed. Notice that at the start of this iteration, the
points in B(x; r) n are free. Denote these
points by F j+2 . As x 2 F , during iteration
B(x; r) are placed in F 0 . These include
all the points of F j+2 . At the end of iteration 1, the
points in F , and in particular the points of F j+1 , are
placed in the cluster S. The points in F 0 , in particular
all of F j+2 are placed in F . As we are assuming that
iteration executed as well, at the end of that
iteration the points of F j+2 are placed in the cluster S.
Because are all the points in B(x; r),
the claim follows. If x 2 F j then a similar argument
shows that S will contain all the points in B(x; r) with
even larger probability.
8. Consider any particular phase. 8x, the probability
that the first y 2 B(x; r) to be clustered is
reached in the last two iterations of the main loop for
that phase is 4
once each phase, and the probability
that
The above claims imply
Theorem 9. With high probability the algorithm produces
a sparse partitioning clustering with parameter r.
the following holds. In any phase, the probability that
completely contained in a cluster generated
in that phase is a bit below 1
5 , but clearly more
than, say 1
6 . Thus, after O(log n) phases, with high
probability this property holds for all points x. The
bound on the diameters of the clusters follows from
the choice of i. The bound on the number of clusters
containing a point follows from the fact that there are
O(log n) iterations, and each iteration generates a collection
of disjoint clusters.
Analysis. Let ffi and k be as described in the implemen-
tation. The time complexity for a phase in the above
algorithm is (similar to agglomerative clustering) upper
bounded by the sum
where D is the cost of building the kn 1\Gammaffi log n r-proximity
tables, N is the minimum search cost for ~
cost of retrieving all the pointers only), B is the cost
for retrieving entries that are marked 0, but which contain
points further then (1 ffl)r, G is the cost induced
by retrievals of good 0-marked entries (i.e. such that
all are at distance within (1 ffl)r, and U is the cost
of performing set unions. Again, we analyze each cost
separately.
c(fi) be the constant
from Lemma 1. Then,
Analogous to Lemma 4.
Theorem 11. The total running time of the sparse
partitions algorithm is O(d 2 n 2\Gammaffl 2 =2c log 2 n)
5 Computing an approximate MST and other related
problems
In this section we discuss several other geometric problems
that can be approximated in subquadratic time
using our methods. First, we consider the problems of
computing a 1 appoximation to the closest and to
the furthest pair of points, an application also considered
by Kleinberg [14]. We have the following result:
Lemma 12. For each constant ffl there exists
(the same ffi as in agglomerative clustering) so that in
time ~
O(d 2 n 2\Gammaffi ) we can compute w.h.p. a pair of points
which are within a of the distance of the
closest (or furthest) pair of points.
Proof sketch : The idea is to partition the set P
into n 1\Gammaffi subsets of size n ffi each, as before. For each
subset we build an ffl-ANN (or an ffl-AFN) data structure.
We then search each of the structures for each point in
. By repeating the search several times and taking
the best answer, we can reduce the error probability
sufficiently.
We now consider the problem of computing an approximate
minimum spanning tree (MST).
Lemma 13. For each constant ffl there exists ffi so that
we can compute w.h.p. a (1 + ffl)-approximation to the
minimum spanning tree in time ~
O(d
Proof sketch : The idea here is to iterate over several
computations of agglomerative clustering, each time re-
duing the parameter \Delta by a factor of about 1+ ffl. Notice
that our agglomerative clustering algorithm outputs a
sparse graph G as a witness to the connectivity of each
cluster. We use such a witness here (i.e., a "black-
box" agglomerative clustering algorithm that outputs
the partition into clusters alone is insufficient). Whenever
a cluster in one iteration is split in the next, we
add to the growing forest edges connecting the current
fragments of the cluster. These edges are taken from
the graph G computed in the previous iteration. (No-
tice that the graph in the current iteration may differ
from the the graph in the previous iteration.) We add
edges of G, that do not connect two points that are
currently also in the same cluster, and do not close a
cycle. (Because G is sparse enough, we can check all its
edges.)
We can begin with any \Delta which on the one hand
guarantees a single cluster, and on the oher hand is not
too big (close enough to a lower bound on the MST).
For example, we can take 1 times the result of an
approximate furthest pair search. We can stop when
reaches a value small enough to allow us to take the
remaining connections as we please. Because an MST
contains a value of about ffl=n times the initial
value of \Delta is sufficient (recall that the initial value
is close to a lower bound on the MST). Thus, the number
of agglomerative clustering computations, for fixed
ffl, is O(log n).
As mentioned previously, we can now use such an
approximate MST and any threshold value ' as the basis
for approximate MST clustering by deleting from the
MST any edges of distance larger than ' and viewing
the resulting components as clusters. We note that this
MST clustering might be different from an approximate
agglomerative clustering using the same parameter '.

Acknowledgment

We thank Andrei Broder for his motivating discussions
regarding the Alta-Vista tm search engine.



--R

Sparse partitions.


Syntactic clustering of the Web.
Approximating matrix multilication for pattern recognition tasks.
How to search in history.
Fast hierachical clustering and other applications of dynamic closest pair.
The Johnson- Lindenstrauss lemma and the sphericity of some graphs
Handbook of Decrete and Computational Geometry
Approximate nearest neighbors: Towards removing the curse of dimen- sionality
Private communica- tion
Extensions of Lipschitz mappings into Hilbert space.
Relative neighborhood graphs and their relatives.
Two algorithms for nearest-neighbor search in high dimensions
Efficient search for approximate nearest neighbor in high dimensional spaces.
The geometry of graphs and some of its algorithmic ap- plications
Decomposing graphs into regions of small diamater.
Pattern recogni- tion
On constructing minimum spannning trees in k-dimensional spaces and related prob- lems
--TR
How to search history
The Johnson-Lindenstrauss Lemma and the sphericity of some graphs
Decomposing graphs into regions of small diameter
Two algorithms for nearest-neighbor search in high dimensions
Approximate nearest neighbors
Efficient search for approximate nearest neighbor in high dimensional spaces
Syntactic clustering of the Web
Handbook of discrete and computational geometry
Pattern recognition
Approximating matrix multiplication for pattern recognition tasks
Fast hiearchical clustering and other applications of dynamic closet pairs
Pattern Classification (2nd Edition)
sparse partitions;high dimensional spaces;graph-theoretic clustering