Incremental Mining of Sequential Patterns in Large Databases

Abstract : In recent years the emergence of new real-world applications such as network traffic monitoring, intrusion detection systems, sensor network data analysis, click stream mining and dynamic tracing of financial transactions, calls for studying a new kind of model. Named data stream, this model is in fact a continuous and potentially infinite flow of information as opposed to finite and statically stored data sets. We study the problem of sequential pattern mining in data streams. This problem has been extensively studied for the conventional case of disk resident data sets. In the case of data streams, this problem becomes more challenging as the volume of data is usually too huge to be stored on permanent devices, main memory or to be scanned thoroughly more than once. In this case, it may be acceptable to generate approximable solutions for our mining problem. In this paper we introduce a new approach based on biased reservoir sampling to achieve a more efficient mining of sequential patterns. Furthermore, we theoretically prove that our biased reservoir size is always bounded whatever the size of the stream is. This property often allows us to keep the entire relevant reservoir in main memory. We also show a simple algorithm to build the biased reservoir for the special case of sequential pattern mining. Experimental evaluation supports the claim that sequential pattern mining based on biased reservoir sampling needs small memory requirements. Besides, we also propose an adapted approach to handle the case of mining sequential patterns in a sliding window model. The experiment show that the results are accurate.
Type de document :
Article dans une revue
Data and Knowledge Engineering, Elsevier, 2003, 46 (1), pp.97-121. 〈10.1016/S0169-023X(02)00209-4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269547
Contributeur : Christine Carvalho de Matos <>
Soumis le : samedi 3 novembre 2018 - 22:42:11
Dernière modification le : mercredi 21 novembre 2018 - 19:48:04

Fichier

ise.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Florent Masseglia, Pascal Poncelet, Maguelonne Teisseire. Incremental Mining of Sequential Patterns in Large Databases. Data and Knowledge Engineering, Elsevier, 2003, 46 (1), pp.97-121. 〈10.1016/S0169-023X(02)00209-4〉. 〈lirmm-00269547〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

10