Local Intrinsic Dimensionality (LID) is a measure of data complexity in the vicinity of a query point. In this work, we propose a novel Bayesian framework for LID estimation that improves robustness and accuracy, especially in scenarios with small neighborhood sizes ( k ≤ 10 ), where maintaining locality is critical. Our framework allows the incorporation of both informative and non-informative priors, enabling the integration of prior knowledge to enhance the estimation process. Using this framework, we derive new LID estimators and provide insights into transitional ones. Furthermore, we propose aggregation methods using linear and logarithmic pooling to combine multiple LID posteriors. These methods allow for principled integration of LID estimates across different training states of Deep Neural Networks (DNNs), such as epochs, thereby improving estimation stability and performance. We also derive a posterior predictive distribution (PPD) for modeling and synthesizing nearest-neighbor distances. Experiments demonstrate that the LID Bayesian estimation methods achieves a balanced approach between reducing variance and lowering squared bias, often leading to lower mean squared error (MSE) values for small number of nearest neighbors.

Local intrinsic dimensionality (LID) provides insight into the behavior of individual training points in deep neural networks, with applications including adversarial detection, prevention of dimensional collapse in self-supervised learning, and identification of untruthful responses from large language models (LLMs). In such contexts, efficient LID estimation has depended on the use of mini-batches, due to the high cost of computing neighborhoods in latent space. However, estimation with respect to small subsets of the training data usually reflects the dimensionality of the global manifold structure rather than the intended local distribution around each point. In this paper, we propose the Nearest Distance Cache (NDC), a method that improves the locality of LID estimation by reusing nearest-neighbor distances observed in past mini-batches. This strategy faces two key challenges: representations evolve over time, and limited memory prevents storing all past distances. To address these, NDC maintains a compact cache of nearest distances per example and uses window-based change detection to discard outdated samples affected by distributional drift. We also evaluate NDC on two tasks: an autoencoder trained on synthetic data with known ground-truth LID, and a ResNet trained on CIFAR-10. Results show that NDC captures local properties of deep representations not revealed by single mini-batch estimates.

We present a nonparametric method for outlier detection that takes full account of local variations in intrinsic dimensionality within the dataset. Using the theory of Local Intrinsic Dimensionality (LID), our ‘dimensionality-aware’ outlier detection method, DAO, is derived as an estimator of an asymptotic local expected density ratio involving the query point and a close neighbor drawn at random. The dimensionality-aware behavior of DAO is due to its use of local estimation of LID values in a theoretically-justified way. Through comprehensive experimentation on more than 800 synthetic and real datasets, we show that DAO significantly outperforms three popular and important benchmark outlier detection methods: Local Outlier Factor (LOF), Simplified LOF, and kNN.

Machine learning models may suffer from significant performance degradation when applied to data substantially different from the training data, known as out-of-distribution (OOD) data. One natural choice for unsupervised OOD detection is reconstruction-error (e.g., 3 sigma rule), which has been extensively used for anomaly detection. However, this criterion for OOD detection is problematic because reconstruction errors of some OOD instances can be similar to the training data. To address this problem, we propose a framework that integrates reconstruction errors with the theory of Local Intrinsic Dimensionality (LID). Specifically, we introduce the use of LID to characterize the data subspaces formed by data samples and their corresponding reconstruction by autoencoders (AEs) as a feature for OOD detection, revealing their localized geometrical properties. The learning histories of a model are realizations of the underlying distance distributions of such data subspaces, the pattern of which can be captured dimensionally by LID, portraying the model learning behavior on samples. The framework incorporates reconstruction loss in combination with LID for greater robustness by providing a global measure in addition to the localized one. Extensive empirical studies validate the feasibility of using LID to characterize learning histories and demonstrate the proposed framework's effectiveness.

Classifier explanations have been identified as a crucial component of knowledge discovery. Local explanations evaluate the behavior of a classifier in the vicinity of a given instance. A key step in this approach is to generate synthetic neighbors of the given instance. This neighbor generation process is challenging and it has considerable impact on the quality of explanations. To assess quality of generated neighborhoods, we propose a local intrinsic dimensionality (LID) based locality constraint. Based on this, we then propose a new neighborhood generation method. Our method first fits a local embedding/subspace around a given instance using the LID of the test instance as the target dimensionality, then generates neighbors in the local embedding and projects them back to the original space. Experimental results show that our method generates more realistic neighborhoods and consequently better explanations. It can be used in combination with existing local explanation algorithms.

Accurate estimation of Intrinsic Dimensionality (ID) is of crucial importance in many data mining and machine learning tasks, including dimensionality reduction, outlier detection, similarity search and subspace clustering. However, since their convergence generally requires sample sizes (that is, neighborhood sizes) on the order of hundreds of points, existing ID estimation methods may have only limited usefulness for applications in which the data consists of many natural groups of small size. In this paper, we propose a local ID estimation strategy stable even for ‘tight’ localities consisting of as few as 20 sample points. The estimator applies MLE techniques over all available pairwise distances among the members of the sample, based on a recent extreme-value-theoretic model of intrinsic dimensionality, the Local Intrinsic Dimension (LID). Our experimental results show that our proposed estimation technique can achieve notably smaller variance, while maintaining comparable levels of bias, at much smaller sample sizes than state-of-the-art estimators.

Given a query object q, reverse k -nearest neighbor (R k NN) search aims to locate those objects of the database that have q among their k -nearest neighbors. In this paper, we propose an approximation method for solving R k NN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.

This paper is concerned with the estimation of a local measure of intrinsic dimensionality (ID) recently proposed by Houle. The local model can be regarded as an extension of Karger and Ruhl's expansion dimension to a statistical setting in which the distribution of distances to a query point is modeled in terms of a continuous random variable. This form of intrinsic dimensionality can be particularly useful in search, classification, outlier detection, and other contexts in machine learning, databases, and data mining, as it has been shown to be equivalent to a measure of the discriminative power of similarity functions. Several estimators of local ID are proposed and analyzed based on extreme value theory, using maximum likelihood estimation (MLE), the method of moments (MoM), probability weighted moments (PWM), and regularly varying functions (RV). An experimental evaluation is also provided, using both real and artificial data.

Numerous applications in different fields, such as spatial databases, multimedia databases, data mining, and recommender systems, may benefit from efficient and effective aggregate similarity search, also known as aggregate nearest neighbor (AggNN) search. Given a group of query objects Q, the goal of AggNN is to retrieve the k most similar objects from the database, where the underlying similarity measure is defined as an aggregation (usually sum or max) of the distances between the retrieved objects and every query object in Q. Recently, the problem was generalized so as to retrieve the k objects which are most similar to a fixed proportion of the elements of Q. This variant of aggregate similarity search is referred to as “flexible AggNN”, or FANN. In this work, we propose two approximation algorithms, one for the sum variant of FANN, and the other for the max variant. Extensive experiments are provided showing that, relative to state-of-the-art approaches (both exact and approximate), our algorithms produce query results with good accuracy, while at the same time being very efficient.

Neighborhood graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. In this paper, we propose a new framework for the efficient construction of K-nearest neighbor (K-NN) graphs based on nearest-neighbor descent (NN-Descent), in which selective sparsification of object feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A local variant of the Laplacian Score is used to identify noisy features with respect to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments that our graph construction method is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets.

In data mining applications such as subspace clustering or feature selection, changes to the underlying feature set can require the reconstruction of search indices to support fundamental data mining tasks. For such situations, multi-step search approaches have been proposed that can accommodate changes in the underlying similarity measure without the need to rebuild the index. In this paper, we present a heuristic multi-step search algorithm that utilizes a measure of intrinsic dimension, the generalized expansion dimension (GED), as the basis of its search termination condition. Compared to the current state-of-the-art method, experimental results show that our heuristic approach is able to obtain significant improvements in both the number of candidates and the running time, while losing very little in the accuracy of the query results.

Data mining techniques for understanding how graphs evolve over time have become increasingly important. Evolving graphs arise naturally in diverse applications such as computer network topologies, multiplayer games and medical imaging. A natural and interesting problem in evolving graph analysis is the discovery of compact subgraphs that change in a similar manner. Such subgraphs are known as regions of correlated change and they can both summarise change patterns in graphs and help identify the underlying events causing these changes. However, previous techniques for discovering regions of correlated change suffer from limited scalability, making them unsuitable for analysing the evolution of very large graphs. In this paper, we introduce a new algorithm called ciForager, that addresses this scalability challenge and offers considerable improvements. The efficiency of ciForager is based on the use of new incremental techniques for detecting change, as well as the use of Voronoi representations for efficiently determining distance. We experimentally show that ciForager can achieve speedups of up to 1000 times over previous approaches. As a result, it becomes feasible for the first time to discover regions of correlated change in extremely large graphs, such as the entire BGP routing topology of the Internet.

Novel applications such as recommender systems, uncertain databases, and multimedia databases are designed to process similarity queries that produce ranked lists of objects as their results. Similarity queries typically result in disk access latency and incur a substantial computational cost. In this paper, we propose an 'active caching' technique for similarity queries that is capable of synthesizing query results from cached information even when the required result list is not explicitly stored in the cache. Our solution, the Cache Estimated Significance (CES) model, is based on shared-neighbor similarity measures, which assess the strength of the relationship between two objects as a function of the number of other objects in the common intersection of their neighborhoods. The proposed method is general in that it does not require that the features be drawn from a metric space, nor does it require that the partial orders induced by the similarity measure be monotonic. Experimental results on real data sets show a substantial cache hit rate when compared with traditional caching approaches.

Time, cost and energy efficiency are critical factors for many data analysis techniques when the size and dimensionality of data is very large. We investigate the use of Local Outlier Factor (LOF) for data of this type, providing a motivating example from real world data. We propose Projection-Indexed Nearest-Neighbours (PINN), a novel technique that exploits extended nearest neighbour sets in the a reduced dimensional space to create an accurate approximation for k-nearest-neighbour distances, which is used as the core density measurement within LOF. The reduced dimensionality allows for efficient sub-quadratic indexing in the number of items in the data set, where previously only quadratic performance was possible. A detailed theoretical analysis of Random Projection(RP) and PINN shows that we are able to preserve the density of the intrinsic manifold of the data set after projection. Experimental results show that PINN outperforms the standard projection methods RP and PCA when measuring LOF for many high-dimensional real-world data sets of up to 300000 elements and 102600 dimensions.

Recommender systems aim to substantially reduce information overload by suggesting lists of similar items that users may find interesting.Caching has been a useful technique for reducing stress on limited resources and improving response time. In this paper, we propose an 'active caching' technique for recommender systems based on a partial order approach that not only benefits from popularity and temporal locality, but also exploits spatial locality. This approach allows the processing of answers to neighboring non-cached queries in addition to the reporting of cached query results. Test results for several data sets and recommendation techniques show substantial improvement in the cache hit ratio and computational costs, while achieving reasonable recall rates.

This paper introduces a model for clustering, the Relevant-Set Correlation (RSC) model, that requires no direct knowledge of the nature or representation of the data. Instead, the RSC model relies solely on the existence of an oracle that accepts a query in the form of a reference to a data item, and returns a ranked set of references to items that are most relevant to the query. The quality of cluster candidates, the degree of association between pairs of cluster candidates, and the degree of association between clusters and data items are all assessed according to the statistical significance of a form of correlation among pairs of relevant sets and/or candidate cluster sets. The RSC significance measures can be used to evaluate the relative importance of cluster candidates of various sizes, avoiding the problems of bias found with other shared-neighbor methods that use fixed neighborhood sizes.

We propose a new model for feature evaluation and selection that assesses the propensity of the features to support two-set classification. For each item of the data set, the collection of features induce a ranking (ordered list) of the remaining items. The evaluation criterion favors features that result in the most consistent discrimination between relevant and non-relevant items within these ranked lists. The discrimination boundaries within a single list are determined combinatorially, according to the degree of correlation among the relevant sets of its members. The model makes no special assumptions on the nature of the data. A selection heuristic based on the model is also proposed using sequential forward generation, and an experimental comparison is made with other unsupervised feature selection methods.

This paper introduces a practical index for approximate similarity queries of large multi-dimensional data sets: the spatial approximation sample hierarchy (SASH). A SASH is a multi-level structure of random samples, recursively constructed by building a SASH on a large randomly selected sample of data objects, and then connecting each remaining object to several of their approximate nearest neighbors from within the sample. Queries are processed by first locating approximate neighbors within the sample, and then using the pre-established connections to discover neighbors within the remainder of the data set. The SASH index relies on a pairwise distance measure, but otherwise makes no assumptions regarding the representation of the data. Experimental results are provided for query-by-example operations on protein sequence, image, and text data sets, including one consisting of more than 1 million vectors spanning more than 1.1 million terms - far in excess of what spatial search indices can handle efficiently. For sets of this size, the SASH can return a large proportion of the true neighbors roughly 2 orders of magnitude faster than sequential search.

This paper introduces a scalable method for feature extraction and navigation of large data sets by means of local clustering, where clusters are modeled as overlapping neighborhoods. Under the model, intra-cluster association and external differentiation are both assessed in terms of a natural confidence measure. Minor clusters can be identified even when they appear in the intersection of larger clusters. Scalability of local clustering derives from recent generic techniques for efficient approximate similarity search. The cluster overlap structure gives rise to a hierarchy that can be navigated and queried by users. Experimental results are provided for two large text databases.