comparison is between
where n1 < n2 < . . . < nt = N,
and t is the number of updates.
In the limit when n is
a continuous variable and the sum becomes an integral we are better
off with N2.
In the discrete case the
comparison depends rather on the size of the updates ni - ni -
So unless we can design an n log n dependence as
extra documents are added, we may as well stick with the n2 methods which satisfy the soundness
conditions and preserve n2 dependence
In any case, if one is willing to forego some of the theoretical
adequacy conditions then it is possible to modify the n2 methods to 'break the n2 barrier'.
One method is to sample from the
document collection and construct a core clustering using an
n2 method on the sample of the
The remainder of the documents can then be fitted into the
core clustering by a very fast assignment strategy, similar to a
search strategy which has log n dependence.
A second method is
to initially do a coarse clustering of the document collection
and then apply the finer classification method of the n2 kind to each cluster in turn.
So, if there
are N documents and we divide into k coarse clusters by
a method that has order N time dependence (e.g. Rieber and
Marathe's method) then the total cluster time will be of order
N + (N/k)2 which will
be less than N2.
Another comment to be made about n log n methods is that
although they have this time dependence in theory, examination of a
number of the algorithms implementing them shows that they actually
have an n2 dependence (e.g. Rocchio's
Furthermore, most n log n methods have only
been tested on single-level classifications and it is doubtful whether
they would be able to preserve their n log n dependence
if they were used to generate hierarchic classifications (Senko).
In experiments where we are often dealing with only a few thousand documents, we may find that the proportionality constant in the n log n method is so large that the actual time taken for clustering is greater than that for an n2 method.
Croft recently found this when he compared the efficiency of SNOB (Boulton and Wallace), an n log n cluster method, with single-link.
In fact, it is possible to implement single-link in such a way that the generation of the similarity values is overlapped in real time with the cluster generation process.
The implementation of classification algorithms for use in IR is by necessity different from implementations in other fields such as for example numerical taxonomy.
The major differences arise from