Adaptive grid-based k-median clustering of streaming data with accuracy guarantee

Jianneng Cao, Yongluan Zhou, Min Wu

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review


Data stream clustering has wide applications, such as online financial transactions, telephone records, and network monitoring. Grid-based clustering partitions stream data into cells, derives statistical information of the cells, and then applies clustering on these much smaller statistical information without referring to the input data. Therefore, grid-based clustering is efficient and very suitable for high-throughput data streams, which are continuous, time-varying, and possibly unpredictable. Various grid-based clustering schemes have been proposed. However, to the best of our knowledge, none of them provides an accuracy guarantee for their clustering output. To fill this gap, in this paper we study grid-based k-median clustering. We first develop an accuracy guarantee on the cost difference between grid-based solution and the optimum. Based on the theoretical analysis, we then propose a general and adaptive solution, which partitions stream data into cells of dynamically determined granularity and runs k-median clustering on the statistical information of cells with an accuracy guarantee. An extensive experiment over three real datasets clearly shows that our solution provides high-quality clustering outputs in an efficient way.
TitelDatabase Systems for Advanced Applications : 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015, Proceedings, Part I
RedaktørerMatthias Renz et al.
ISBN (Trykt)978-3-319-18119-6
ISBN (Elektronisk)978-3-319-18120-2
StatusUdgivet - 2015
Begivenhed20th International Conference on Database Systems for Advanced Applications - Hanoi, Vietnam
Varighed: 20. apr. 201523. apr. 2015


Konference20th International Conference on Database Systems for Advanced Applications
NavnLecture Notes in Computer Science

Bibliografisk note

Best Paper Award

Fingeraftryk Dyk ned i forskningsemnerne om 'Adaptive grid-based k-median clustering of streaming data with accuracy guarantee'. Sammen danner de et unikt fingeraftryk.