Streaming Algorithm for K-Median Dynamic Geometric Problem

Shrivastava, J M (2012) Streaming Algorithm for K-Median Dynamic Geometric Problem. Masters thesis, Indian Institute of Technology, Hyderabad.

Preview

Text
CS10M02.pdf - Submitted Version
Download (1MB)

Abstract

Many applications such as financial transactions data, customer click stream continuously generates huge data sets at very rapid rate. This is generally termed as data stream. These data sets are too huge to store on limited secondary storage. Therefore, it directs us to adopt a technique to maintain the sketch or summary of the data stream. This will allow us to answer any query, that we wish to perform on this data sets, approximately. Many applications on data streams such as counting of distinct items, estimating frequency moments [7, 8], the counting of frequent items [9, 3], clustering and the computation of histograms are of great interest among researchers. We consider k-median clustering problem in the geometric data stream. The task of the clustering is to partition a set of objects into disjoint group wherein the data objects in the same group are similar and objects in the different groups are dissimilar. We consider the k-median clustering algorithm in the context of data stream as proposed in [4]. We propose modified algorithm for 2-dimension that achieve improved time and space bounds for k-median problem in [4]. We run the experiment by implementing the modified algorithm to see execution time.

[error in script]

IITH Creators: