Current exact hierarchical density-based clustering algorithms for high-dimensional data have asymptotically quadratic complexity. We present algorithms for approximate hierarchical density-based clustering, namely for single-linkage clustering and for HDBSCAN, with empirically near-linear time scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality. For both single-linkage clustering and HDBSCAN, our algorithms yield highly accurate clusterings while being up to two orders of magnitude faster than industry-standard baselines such as scikit-learn’s hdbscan .

Searching for similar objects in intrinsically high-dimensional data sets is a challenging task. The use of compact sketches has been proposed for faster similarity search using linear scans. Binary sketches are one such approach to find a good mapping from the original data space to bit strings of a fixed length. These bit strings can be compared efficiently using only few XOR and bit count operations, replacing costly similarity computations with an inexpensive approximation. We propose a new scheme to initialize and improve binary sketches for similarity search in Euclidean spaces. Our optimization iteratively improves the quality of the sketches with a form of orthogonalization. We provide empirical evidence that the quality of the sketches has a peak beyond which it is not correlated to neither bit independence nor bit balance, which contradicts a previous hypothesis in the literature. Regularization in the form of noise added to the training data can turn the peak into a plateau and applying the optimization in a stochastic fashion, i.e., training on smaller subsets of the data, allows for rapid initialization. We provide a loss function that allows to approximate the same objective using neural network frameworks such as PyTorch, elevating the approach to GPU-based training.

The intrinsic dimensionality refers to the “true” dimensionality of the data, as opposed to the dimensionality of the data representation. For example, when attributes are highly correlated, the intrinsic dimensionality can be much lower than the number of variables. Local intrinsic dimensionality refers to the observation that this property can vary for different parts of the data set; and intrinsic dimensionality can serve as a proxy for the local data complexity of the data set. Most popular methods for estimating the local intrinsic dimensionality are based on distances, and the rate at which the distances to the nearest neighbors increase, a concept known as “expansion dimension”. In this paper we introduce an orthogonal concept, which does not use any distances: we use the distribution of angles among the neighbors with respect to the query point. We derive the theoretical distribution of angles and use this to construct an estimator for intrinsic dimensionality. We derive a regularized version that obeys an upper bound of the true intrinsic dimensionality for idealized data. We generalize the estimator to arbitrary moments and discuss the relation of the regularized second moment to approaches based on principal component analysis. Experimentally, we verify that this measure behaves similarly but complementarily to existing measures of intrinsic dimensionality. By introducing a new idea of intrinsic dimensionality to the research community we hope to contribute to a better understanding of intrinsic dimensionality and to spur new research in this direction.