Author name cluster

Liadan O'Callaghan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

STOC Conference 2003 Conference Paper

Better streaming algorithms for clustering problems

Moses Charikar
Liadan O'Callaghan
Rina Panigrahy

We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k --Median problem which produces a constant factor approximation in one pass using storage space O(k poly log n ). This is a significant improvement of the previous best algorithm which yielded a 2 O (1/ε) approximation using O(n ε ) space. Next we give a streaming algorithm for the k --Median problem with an arbitrary distance function. We also study algorithms for clustering problems with outliers in the streaming model. Here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.

Details

FOCS Conference 2000 Conference Paper

Clustering Data Streams

Sudipto Guha
Nina Mishra
Rajeev Motwani 0001
Liadan O'Callaghan

We study clustering under the data stream model of computation where: given a sequence of points, the objective is to maintain a consistently good clustering of the sequence observed so far, using a small amount of memory and time. The data stream model is relevant to new classes of applications involving massive data sets, such as Web click stream analysis and multimedia data analysis. We give constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass. We also show negative results implying that our algorithms cannot be improved in a certain sense.

Details