Approximate nearest neighbor (ANN) search in the high-dimensional Euclidean space is a pivotal problem for various data science and AI applications. The performance of traditional in-memory ANN methods decreases dramatically when handling large-scale data due to their substantial expansion of main memory. Recently, disk-resident ANN methods have drawn considerable attention to enable large-scale ANN search. However, despite their significant improvements, they still suffer from high query latency due to heavy I/O cost. In this paper, we propose ANN-CACHE, an I/O-efficient cache-conscious ANN framework that leverages the skew in query workloads to reduce I/O cost. To the best of our knowledge, we are the first to formally study exploring caching to accelerate disk-based ANN search. ANN-CACHE consists of two components: (i) a discriminator that checks whether a query's ANN points are cached. If so, an in-memory lookup in the cache is triggered; otherwise, a lookup in the disk-resident index is conducted; and (ii) an LSH-based cache that stores historical queries and their results to support efficient ANN search. Considering a query q, if the cache contains historical queries that are similar to q and their ANNs, we can obtain q's result from these queries' results without accessing the disk-resident index. Experimental results demonstrate that our framework achieves 3×-9× speedup while maintaining consistently higher accuracy compared to the baselines, by introducing less than 50 MB of additional memory overhead on datasets of 10M size.

The problem of similarity search in high-dimensional space is a fundamental problem with numerous applications in computer science, yet it remains challenging due to the curse of dimensionality. This paper introduces DForest, a novel indexing approach designed to address this challenge for both range and kNN queries on high-dimensional data. Unlike previous similarity search approaches that apply a fixed dimensionality reduction to all objects uniformly, our approach determines the minimal dimensionality required for each object within a specified loss threshold and then reduces the dimensionality for each object individually. Furthermore, the query performance is also optimized by deriving the upper and lower bounds of retrieved blocks and computing distances in a low-embedding space preferentially. Theoretical analysis is provided to support our search strategy. Extensive experiments on a variety of datasets verify the superiority of DForest over the state-of-the-art methods.

The objective of entity resolution (ER) is to identify records referring to the same real-world entity. Traditional ER approaches identify records based on pairwise similarity comparisons, which assumes that records referring to the same entity are more similar to each other than otherwise. However, this assumption does not always hold in practice and similarity comparisons do not work well when such assumption breaks. We propose a new class of rules which could describe the complex matching conditions between records and entities. Based on this class of rules, we present the rule-based entity resolution problem and develop an on-line approach for ER. In this framework, by applying rules to each record, we identify which entity the record refers to. Additionally, we propose an effective and efficient rule discovery algorithm. We experimentally evaluated our rule-based ER algorithm on real data sets. The experimental results show that both our rule discovery algorithm and rule-based ER algorithm can achieve high performance.

In this paper, we consider the entity resolution(ER) problem, which is to identify objects referring to the same real-world entity. Prior work of ER involves expensive similarity comparison and clustering approaches. Additionally, the quality of entity resolution may be low due to insufficient information. To address these problems, by adopting context information of data objects, we present a novel framework of entity resolution, context-based entity description (CED), to make context information help entity resolution. In our framework, each entity is described by a set of CEDs. During entity resolution, objects are only compared with CEDs to determine its corresponding entity. Additionally, we propose efficient algorithms for CED discovery and CED-based entity resolution. We experimentally evaluated our CED-based ER algorithm on the real DBLP datasets, and the experimental results show that our algorithm can achieve both high precision and recall as well as outperform existing methods.