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.

CS10M02.pdf - Submitted Version

Download (1MB)


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:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Uncontrolled Keywords: TD58
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 03 Nov 2014 03:35
Last Modified: 24 May 2019 10:17
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 601 Statistics for this ePrint Item