Clustering data streams

By Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

903 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5eb75ac359fbd32c378a783741d7543186fe58d8

How researchers see this paper

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

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Clustering Data Streams: Theory and Practice (2003, background): “…abundant literature on these, books [45], [62], [55], provable algorithms [41], [49], [54], [53], [71], [31], [16], [15], [6], [52], [47], [14], [59], [7], [46], the running time of provable clustering heuristics [21], [10], [42], [34], [73], [60], and special metric spaces [6], [52], [43], [68].”
Efficient decision tree construction on streaming data (2003, background): “The existing algorithms typically achieve either a deterministic bound on the accuracy [17], or a probabilistic bound [10].”
Models and issues in data stream systems (2002, methodology): “[44] presented a single-pass algorithm for maintaining approximate k-medians (cluster centers) that uses O(N ) space for some < 1 using O(poly(logN)) amortized time per data element, to compute a constant factor approximation to the k-median problem.”
A Comprehensive Survey of Clustering Algorithms (2015, neutral): “For more detailed information about this kind of clustering algorithms, you can refer to [128–131], D-Stream [41,132].”
A Framework for Projected Clustering of High Dimensional Data Streams (2004, background): “The ubiquitous presence of data streams in a number of practical domains has generated a lot of research in this area [8, 10, 12, 13, 17].”
Processing complex aggregate queries over data streams (2002, background): “ments for different problems; examples include quantile and orderstatistics computation [16, 21], estimating frequency moments and join sizes [3, 2], data clustering and decision-tree construction [10, 18], estimating correlated aggregates [13], and computing one-dimensional (i.”
A Framework for Clustering Evolving Data Streams (2003, methodology): “For testing the accuracy and e(cid:14)ciency of the CluStream algorithm, we compare CluStream with the STREAM algorithm [8, 13], the best algorithm re-ported so far for clustering data streams.”
Streaming-data algorithms for high-quality clustering (2002, methodology): “Theorem 1 [13] If at each iteration i, a capproximation algorithm is run in Steps 2 and 4 of Algorithm STREAM, then the centers output are a 5capproximation to the optimum SSQ for X1 ∪ · · · ∪Xi, assuming a distance metric on R.”
On coresets for k-means and k-median clustering (2004, methodology): “[17] propose an algorithm which uses O(n) memory to compute 2 approximate kmedians.”
When Is the Right Time to Refresh Knowledge Discovered from Data? (2013, methodology): “Motivated by BIRTCH, a series of algorithms (Guha et al. 2000, 2003) were introduced for clustering data streams.”
Online Learning: A Comprehensive Survey (2018, neutral): “(Guha et al., 2000; O’callaghan et al., 2002; Guha et al., 2003).”
Frequency-sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres (2004, background): “Note that if is large for a particular , then that Gaussian shrinks more in the sense that the density gets more peaked around the mean.”
Maintaining variance and k-medians over data stream windows (2003, methodology): “Our solution incorporates the techniques of Guha, Mishra, Motwani, and O’Callaghan [12], but ensures a highquality sliding-window clustering.”
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.”