Incremental clustering and dynamic information retrieval

By Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani. 1997

Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications. The goal is to efficiently maintain clusters of small diameter as new points are inserted. We analyze several natural greedy algorithms and demonstrate that they perform poorly. We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance, and which we believe should also perform well in practice. We complement our positive results with lower bounds on the performance of incremental algorithms. Finally, we consider the dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Gradient based sample selection for online continual learning (2019, methodology): “We adapted the doubling algorithm for incremental clustering described in [3].”
Efficient phrase-based document indexing for Web document clustering (2004, background): “Charikar et al. discussed an incremental hierarchical clustering [35] as well.”
An Algorithm for Online K-Means Clustering (2014, methodology): “For information retrieval, [9] investigated the incremental k -centers problem.”
Information Theoretic Clustering (2002, methodology): “Information theory [47], [48] was used in clustering by Watanabe [50] and by many other researchers [8], [22], [49].”
Continual Learning in Neural Networks (2019, methodology): “We adapted the doubling algorithm for incremental clustering described in [23].”
On clusterings-good, bad and spectral (2000, background): “These include minimum diameter, k-center, k-median, and minimum sum (for example: [3],[4],[6], [8],[9], etc.”
Evolutionary spectral clustering by incorporating temporal smoothness (2007, background): “There exists a large research literature on incremental clustering algorithms, whose main task is to efficiently apply dynamic updates to the cluster centers [13], medoids [12], or hierarchical trees [4] when new data points arrive.”
A Practical Online Framework for Extracting Running Video Summaries under a Fixed Memory Budget (2021, methodology): “Condn KC RR TS Sieve Ours [37] We compare our approach against baseline meth-ods, including the streaming optimization procedure proposed by Doubling K-Centers algorithm [5] and Resource Restricted Online Minimum Sparse Reconstruction procedure [23] (RR).”
Clustering data streams (2000, background): “Charikar, Chekuri, Feder, and Motwani [1] gave a constant-factor algorithm for the incremental k{Center problem, which is also a single-pass algorithm requiring O(nk log k) time and O(k) space.”
Effective Attack Models for Shilling Item-Based Collaborative Filtering Systems (2005, methodology): “Consider, as an example, a recommender system that identifies books that users might like to read using a user-based collaborative algorithm [3].”
Hierarchical Document Clustering using Frequent Itemsets (2003, background): “† We may want to incrementally update [ 12 ] the cluster tree when some new documents arrive, for example, a new research paper is submitted to the database or”
Scalable sparse approximation of a sample mean (2014, methodology): “We anticipate that our approach will extend to online and divide-andconquer implementations, because corresponding algorithms for the k-center problem exist for these settings [23–25].”
Better streaming algorithms for clustering problems (2003, methodology): “In fact, the algorithm in [7] maintains at most k clusters at all times and modi.es the clustering solution using a very restricted set of operations that do not allow an existing cluster to be broken up and its points distributed to di.erent clusters.”
Clustering Data Streams: Theory and Practice (2003, methodology): “Charikar et al. [13] gave a constant-factor, single-pass k -Center algorithm using O (cid:133) nk log k (cid:134) time and O (cid:133) k (cid:134) space.”
RAPID: randomized pharmacophore identification for drug design (1997, methodology): “While we have obtained reasonable experimental results, we are investigating optimizations via incremental clustering techniques [ 16 ].”