Fast and explainable clustering in the Manhattan and Tanimoto distance

Stefan Güttel, Kaustubh Roy · 2026

Read Fast and explainable clustering in the Manhattan and Tanimoto distance by Stefan Güttel, Kaustubh Roy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-08781.txt.

Introduction

Stefan Guttel and Kaustubh Roy extend a fast group sorting tool called CLASSIX. The tool puts like data points in one group and odd ones apart. It is fast, and a user can see why each group formed. At first it used plain straight line distance to judge how near two points are.

The pair adds two more ways to judge nearness. One suits city grid like moves, where you go along streets, not across blocks. The next suits data made of traits, such as chem traits of a drug. Both forms keep the speed and the clear logic of the first tool. A reader who sorts data gets more reach from a tool they can still explain.

Catalog record

CREATORStefan Güttel, Kaustubh Roy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-08781

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and explainable clustering in the Manhattan and Tanimoto distance Stefan Güttel, Kaustubh Roy Abstract The CLASSIX algorithm [X. Chen & S. Güttel, Pattern Recognition, 150:110298, 2024] is a fast and explainable approach to data clustering. In its original form, this algorithm exploits the sorting of the data points by their first principal component to truncate the search for nearby data points, with nearness being defined in terms of the Euclidean distance. Here we extend CLASSIX to other distance metrics, including the Manhattan distance and the Tanimoto distance. Instead of principal components, we use an appropriate norm of the data vectors as the sorting criterion, combined with the triangle inequality for search termination. In the case of Tanimoto distance, a provably sharper intersection inequality is used to further boost the performance of the new algorithm. On a real-world chemical fingerprint benchmark, CLASSIX is about 30 times faster than the Taylor–Butina algorithm, and about 80 times faster than DBSCAN, while computing higher-quality clusters in both cases. 1 Introduction Unsupervised clustering is a widely used machine learning technique employed to find patterns and similarity between elements in large datasets. Clustering involves grouping data points in a way such that points in the same cluster have similar properties and points belonging to separate clusters are dissimilar. Broadly, clustering is done using either distance or density-based approaches. The two most commonly used distance-based methods are k -means [ 11 ] and k -medoids [ 14 ] , and popular density-based methods include mean shift [ 7 ] , Quickshift [ 18 ] , DBSCAN [ 8 ] , OPTICS [ 1 ] , among others [ 15 ] . Distance-based methods such as k -means partition the data into k clusters by iteratively relocating the cluster centers and reassigning data points to their nearest center. These methods perform well for spherical and well-separated clusters. Density-based methods like mean shift and DBSCAN assume that the data appear in connected regions of high density. Mean shift performs clustering by iteratively shifting data points to nearby modes of the empirical density function computed by kernel density estimation. Quickshift uses Euclidean medoids as shifts. DBSCAN progressively scans through the data using a radius-based neighborhood search. The original implementation uses an R* tree data structure to perform range queries. These tree structures are not trivial to implement efficiently and can make the algorithm have a worst-case complexity of O(n^{2}) in practice. CLASSIX integrates key elements of both distance- and density-based clustering paradigms, with its original formulation [ 6 ] limited to the Euclidean norm. As a first step, CLASSIX performs a greedy aggregation phase, assigning data points into groups centered around so-called starting points, which are points of the data that serve as approximate density estimators akin to the neighborhood centers in DBSCAN. However, in CLASSIX the groups are also reused to cluster the data, not just as estimators. CLASSIX’s two-stage approach also shares features with hierarchical clustering methods like HDBSCAN [ 5 ] . A key ingredient of the original CLASSIX method is an initial sorting of the data points along the first principal component of the data, combined with an early termination criterion for the neighborhood search. In this work, we show that CLASSIX can be readily adapted to more general distance metrics, demonstrated by implementing the algorithm in the Manhattan (or p=1 ) norm \|\cdot\|_{1} and the Tanimoto distance. The Tanimoto distance (also known as Jaccard distance) is widely used for comparing binary data, making it particularly suitable for applications such as text mining, chemistry, and bioinformatics. It measures the similarity between two sets by dividing the cardinalities of the intersection of two sets by their union. For binary vectors, the Tanimoto distance is defined as D_{\text{Tanimoto}}(u,v):=1-\frac{\|u\land v\|_{1}}{\|u\lor v\|_{1}}\in[0,1], (1) where u and v are binary vectors representing the sets. A popular way of representing structural features of chemical compounds is by first encoding them as molecular fingerprints, such as MACCS structural key3 and extended-connectivity fingerprint (ECFP), commonly known as the Morgan fingerprint [ 13 ] . Searching for molecules with similar chemical and physical properties or comprising of similar reaction groups then becomes a task of finding compounds with similar Morgan fingerprints. The Tanimoto distance is the most widely-used metric for this task [ 4 , 2 ] . Several established clustering algorithms, including DBSCAN, HDBSCAN, and OPTICS, have been extended to support the Manhattan and Tanimoto distances and are available through highly optimized implementations in the scikit-learn library. In this work, we compare the computational performance and clustering quality of CLASSIX with these widely-used methods. Contributions and paper overview This paper extends the CLASSIX clustering framework beyond the Euclidean norm and makes several main contributions: (i) we formulate a norm-agnostic aggregation strategy based on sorting by a scalar score derived from \|x_{i}\| and using reverse-triangle-inequality bounds for early search termination; (ii) for the Manhattan norm we study the effect of data shifting (“orthant shifting”) and provide analysis that explains when score-based pruning is effective; (iii) for binary fingerprints clustered in the Tanimoto distance we derive and exploit a sharper pruning criterion based on the Baldi intersection inequality, enabling fast exact neighborhood filtering in high dimensions. The structure of the paper is as follows. Section 2 briefly reviews the existing CLASSIX method for the Euclidean norm. Section 3 introduces the new general norm-based extension and provides an efficiency analysis for the Manhattan norm. Section 4 develops the Tanimoto distance variant, including deterministic bounds and an average-case probabilistic efficiency analysis. Section 5 reports extensive experiments on synthetic and real datasets (including chemical fingerprints) comparing runtime and clustering quality against established baselines. Section 6 briefly discusses explainability. We conclude in Section 7 and provide an outlook on future work. Our code can be found on Github 1 1 1 https://github.com/kaustubhroy1995/classix_tanimoto_manhattan . 2 CLASSIX in the Euclidean distance Let us briefly review the original CLASSIX method [ 6 ] in order to put our contribution in context and introduce notation. Assume we are given data points x_{1},x_{2},\dots,x_{n}\in\mathbb{R}^{d} which are already mean-centered by subtracting the empirical mean of each feature from the vectors. An SVD is performed on the n\times d data matrix X:=[x_{1},x_{2},\dots,x_{n}]^{T} , X=U\Sigma V^{T} where U\in\mathbb{R}^{n\times d},V\in\mathbb{R}^{d\times d} have orthonormal columns and \Sigma\in\mathbb{R}^{d\times d} is a diagonal matrix with elements \sigma_{1}\geq\sigma_{2}\geq\dots\geq\sigma_{d}\geq 0 . The data points are then scored according to their first principal component \alpha_{i} given by \alpha_{i}={x_{i}}^{T}v_{1} where v_{1}\in\mathbb{R}^{d} is the first column of V . The data is then sorted so that in the new ordering, \alpha_{1}\leq\alpha_{2}\leq\dots\leq\alpha_{n} . In CLASSIX’s aggregation phase, data points are grouped together based on the Euclidean distance criterion D(u,v):=\|u-v\|_{2}\leq\texttt{radius}. Here, radius is a hyperparameter chosen by the user. In order to reduce pairwise distance computations, CLASSIX uses a greedy aggregation approach as follows: Starting with the first data point x_{i} , i=1 , in the sorted set of data, we traverse the data points x_{i+1},x_{i+2},\ldots in their order and exploit the inequality |\alpha_{i}-\alpha_{j}|\leq\|x_{i}-x_{j}\|_{2}=D(x_{i},x_{j}). Hence, if \alpha_{j}-\alpha_{i}>\texttt{radius} for some index j>i , the point x_{j} and all the following points x_{j+1},x_{j+2},\ldots do not need to be considered for the grouping with x_{i} . CLASSIX then moves on to form a new group with the first (smallest index) data point

Read the complete text