The parallel complexities of the k-medians related problems

Author

Vittayakorn, Sirion ; Kantabutra, Sanpawat ; Tanprasert, Chularat

Author_Institution

Comput. Sci. Dept., Chiang Mai Univ., Chiang Mai

Volume

1

fYear

2008

fDate

14-17 May 2008

Firstpage

9

Lastpage

12

Abstract

K-medians is a well-known clustering algorithm in data mining literature. This paper describes three decision problems related to k-medians. These problems are called medians replacement in k-medians, median determination, and T iterations k-medians problems. We show that these problems are in NC, each has a (logn)^O(1) parallel time algorithm on an EREW PRAM model using n^O(1) processors, and the result in each case is the strongest possible.

Keywords

concurrency theory; data mining; pattern clustering; EREW PRAM model; clustering algorithm; data mining; k-medians problems; parallel complexities; parallel time algorithm; Clustering algorithms; Clustering methods; Computer science; Concurrent computing; Data mining; Data visualization; Image processing; Parallel algorithms; Phase change random access memory; Technology management;

fLanguage

English

Publisher

ieee

Conference_Titel

Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, 2008. ECTI-CON 2008. 5th International Conference on

Conference_Location

Krabi

Print_ISBN

978-1-4244-2101-5

Electronic_ISBN

978-1-4244-2102-2

Type

conf

DOI

10.1109/ECTICON.2008.4600360

Filename

4600360