A new approach to binary tree-based heuristics

The goals and limitations of some clustering methods are briefly reviewed. In order to avoid the usual methods which are very demanding on computer time and space, a new scheme is proposed for updating (generation) of, and retrieval from, large data bases organized as binary trees. The method is based on calculation of three distances at any given vertex l on the level n, A(l,n) instead of two. The respective distances d₁(X,A_l), d₂(X,A_r), d₃(A_lA_r) are calculated between the input vector X and the left and right descendant of the vertex A(l,n), A_l and A_r, respectively. The advantage of the method compared to the standard clustering methods or formation of hierarchal trees is that the required memory or computational time is reduced from N² to approximately N log N (N is the number of clustering objects).