A note on the use of nearest neighbors for implementing single linkage document classifications

Best match search algorithms provide an efficient means of identifying the sets of nearest neighbors for each of the documents in a collection. These sets contain much of the important similarity data contained in a full interdocument similarity matrix and may be used for the generation of hierarchic document classifications, such as those arising from the use of the single linkage clustering method. Cluster based retrieval experiments based upon such classifications are shown to give results that are comparable in effectiveness with those obtained using the full similarity matrix.