A new model for the linear 1-dimensional online clustering problem

Acta Universitatis Sapientiae: Informatica

Németh József¹  London András¹  Pelyhe Áron¹  Németh Tamás¹ 

[1] University of Szeged Institute of Informatics;

关键词: data clustering;    online algorithms;    learning algorithms;    real-time locating systems;   

DOI  :  10.1515/ausi-2015-0001

来源: DOAJ

【 摘 要 】

In this study, a mathematical model is presented for an online data clustering problem. Data clustering plays an important role in many applications like handling the data acknowledgment problem and data stream management in real-time locating systems. The inputs in these problems are data sequences, each containing several data elements. Each data element has an arrival time and a weight that reflects its importance. The arrival times are not known in advance, and some data elements never arrive. Hence the system should decide which moment is optimal for forwarding the collected data for processing. This requires finding a good trade-off between the amount of collected information and the waiting time, which may be regarded as a minimization problem. Here, we investigate several online algorithms and present their competitive analysis and average case studies. Experimental results, based on simulations using artificially generated data, are also presented and they confirm the efficiency of our methods.

【 授权许可】

Unknown