GESTIONE EFFICIENTE DEI DATI IN UNGESTIONE EFFICIENTE DEI DATI IN UNDATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

Università degli studi di Modena e Reggio EmiliaUniversità degli studi di Modena e Reggio Emilia

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea Magistrale in Informatica

Relatore:Ing. Riccardo Martoglia

Correlatori:Dott. Federica MandreoliIng. Luca Carafoli

Candidato:Federico Di Bernardo

Anno Accademico 2009-2010

INTRODUZIONEINTRODUZIONE

o Situazione Situazione criticacritica del traffico nelle città del traffico nelle città

Aumento del Aumento del consumoconsumo di carburante ed di carburante ed inquinamentoinquinamento

Incremento del numero di Incremento del numero di incidentiincidenti

Forte Forte congestionamentocongestionamento della rete stradale della rete stradale

Necessità di una Necessità di una nuova concezionenuova concezione di mobilità di mobilità e trasportoe trasporto

Sfida nell’ambito di ricerca dell’Sfida nell’ambito di ricerca dell’ICTICT ( (Information Information and Communication technologyand Communication technology ) )

INTRODUZIONEINTRODUZIONE

Mission del progetto:

Smart Navigation: Mobilità intelligente.

Urban Mobility: Incremento dell'efficienza nell'uso degli attuali mezzi di trasporto e delle infrastrutture.

Safety: Incremento della sicurezza e riduzione degli impatti ambientali.

PEGASUSPEGASUS = = PProgrogEEtto per la tto per la GGestione della mobilità estione della mobilità AAttraverso ttraverso SSistemi istemi infotelematici per l’ambito infotelematici per l’ambito UUrbano, per la rbano, per la SSicurezza di passeggeri, veicoli e icurezza di passeggeri, veicoli e merci.merci.

• Realizzato in collaborazione con Realizzato in collaborazione con l’università di Bologna.l’università di Bologna.

OBIETTIVO DELLA TESI:OBIETTIVO DELLA TESI:

Studiare e sviluppare un sistema per la Studiare e sviluppare un sistema per la gestione efficientegestione efficiente dei dati dei datiprovenienti dalle OBU (provenienti dalle OBU (On-Board UnitOn-Board Unit) installate sui veicoli urbani) installate sui veicoli urbani

CONTENUTI:CONTENUTI:

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS Data Stream Management SystemData Stream Management System Prototipo SoftwarePrototipo Software Prove Sperimentali EffettuateProve Sperimentali Effettuate Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS

Data Stream Management SystemData Stream Management System

Prototipo SoftwarePrototipo Software

Prove Sperimentali EffettuateProve Sperimentali Effettuate

Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

PANORAMICA SUL SISTEMA PEGASUSPANORAMICA SUL SISTEMA PEGASUS

OBU ( On-Board Unit ) = Dispositivo installato a bordo dei veicoli in grado di raccogliere varie informazioni sul veicolo e comunicarle sottoforma di data stream

• VelocitàVelocità• PosizionePosizione• AccelerazioneAccelerazione

Real-time commsengine

Smart navigationengine

Maps & real-time

data

User interface

GPS unitAccel unit

GPRS V2I unit

WiFi V2V unit

PANORAMICA SUL SISTEMA PEGASUSPANORAMICA SUL SISTEMA PEGASUS

ad-hoc, multi-hop, V2V communicationad-hoc, multi-hop, V2V communication

V2I communicationV2I communication

BTSBTS

BTSBTS

Control Centre

Infr

astr

uctu

red

Netw

ork

Infr

astr

uctu

red

Netw

ork

OBUsOBUs

Comunicazioni Comunicazioni GPRS GPRS costosecostose ! !

Differenti Differenti tipologie di tipologie di comunicazione:comunicazione:

V2VV2V (WiFi)(WiFi) V2IV2I (GPRS) (GPRS)

Il Il Centro Di Centro Di ControlloControllo colleziona ed colleziona ed integra i dati e integra i dati e gestisce i gestisce i POIPOI ed ed EOIEOI

PANORAMICA SUL SISTEMA PEGASUSPANORAMICA SUL SISTEMA PEGASUS

Centro di ControlloCentro di Controllo

OBU OBUOBU

OBU

Communication Manager

EOI Ontolog

y

Recom-mender System

Recom-mender System

POI Ontology

OBU

OBU

V2I interaction

V2I interaction

V2Vinteraction

V2Vinteraction

Data acquisitionData acquisition

Storage Manager

GIS tables

Query ProcessingEngine

DSMS

Communication-saving!

OBU

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS

Data Stream Management SystemData Stream Management System

Prototipo SoftwarePrototipo Software

Prove Sperimentali EffettuateProve Sperimentali Effettuate

Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

DATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

Applicazione di streaming data-intensive con Applicazione di streaming data-intensive con requisiti spaziali e temporalirequisiti spaziali e temporali

GIS DSMS TemporaleGIS DSMS Temporale Linguaggio di interrogazione SQL-LikeLinguaggio di interrogazione SQL-Like Acquisizione ed accesso a dati tempo e spazio Acquisizione ed accesso a dati tempo e spazio localizzatilocalizzati

Streaming items utilizzati non solo per i servizi Streaming items utilizzati non solo per i servizi real-timereal-time

Query continueQuery continue Ad-Hoc QueryAd-Hoc Query Analisi OLAP su dati storiciAnalisi OLAP su dati storici

Tipiche soluzioni accoppiano il sistema di Storage Tipiche soluzioni accoppiano il sistema di Storage Management con quello di Query ProcessingManagement con quello di Query Processing

Scarsa flessibilitàScarsa flessibilità Difficoltà di ottimizzazioneDifficoltà di ottimizzazione

DATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

Storage ManagerStorage Manager

DSMSDSMS

Query Processing EngineQuery Processing Engine

Query nQuery 2Query 1 …

QueryQueryOptimizerOptimizer

QueryQueryExecutorExecutor

QueryQueryParserParser

Interface

Read /Setup

ResultsSet

StoragePoint 1

StoragePoint 2

StoragePoint n…

LoadLoadShedderShedder

DataDataManagerManager

OBUsOBUs Input StreamInput Stream

GISGISDBMSDBMS

DSMS profondamente diversi dai DSMS profondamente diversi dai DBMSDBMS

DATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

DBMS: Dati:

• Dati “statici” e persistenti• Gestione del dato “presente”• Dati corretti• Spazio “illimitato”

Query:• Query one-shot complesse• Risposte precise• Update poco frequenti• Query plan statico• HADP (Human-Active, Database-Passive)

DSMS: Dati:

• Stream transienti• Nozione di “tempo”• Memoria primaria limitata• Dati danneggiati o mancanti

Query:• Query continue “semplici”• Approximate answering• Query plan dinamico• Diverse query in esecuzione• DAHP (Database-Active, Human-Passive)

DATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

PROBLEMA: Dati potenzialmente infiniti e memoria primaria limitata !

Soluzioni Soluzioni ““LosslessLossless”:”:

Window ModelsWindow Models

Presente vs StoricoPresente vs Storico

Old tuples Newly arrival tuples

DBMS

Main Memory

WINDOW

DATA STREAM MANAGEMENT SYSTEMDATA STREAM MANAGEMENT SYSTEM

Ottimizzazioni Ottimizzazioni ““LossyLossy”:”:

Load SheddingLoad Shedding

SynopsesSynopses

Batch ProcessingBatch Processing

Memory

P = 0,33

DSMSDSMSIncident detection

Near vehicle

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS

Data Stream Management SystemData Stream Management System

Prototipo SoftwarePrototipo Software

Prove Sperimentali EffettuateProve Sperimentali Effettuate

Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

Sviluppo di un Sviluppo di un Storage Management Storage Management System System disaccoppiato dal modulo di disaccoppiato dal modulo di Query Query Processing EngineProcessing Engine

Storage ManagerStorage Manager Query produttore Query produttore pull-basedpull-based Registrazione queries consumatoreRegistrazione queries consumatore Switch dinamicoSwitch dinamico delle strutture dati delle strutture dati Gestione delle Gestione delle finestre temporalifinestre temporali MigrazioneMigrazione dati storici dati storici

Storage Manager

Interface

Query Engine

PostGIS

OBUsOBUs Input StreamInput Stream

readsetup results

ResultsResults

Query Processing EngineQuery Processing Engine Sottomissione query consumatoreSottomissione query consumatoreEsecuzione concorrenteEsecuzione concorrente di diverse queries di diverse queries Invio comandi di lettura (con o senza filtri)Invio comandi di lettura (con o senza filtri) Scrittura risultati su fileScrittura risultati su file

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

Strutture dati dinamicheStrutture dati dinamiche

Never ConsumeOrdered ConsumeEager Consume

Never Expire

Ordered Expire

Unordered Expire

Replaced Expire

PERSISTENT

IN-PLACE IN-PLACE IN-PLACE

RANDOM RANDOM RANDOM

FIFO FIFO FIFO \ RANDOM

FIFO \ RANDOMFIFO

in scritturapieno pienoconsumativuoti

FIFO – FIFO – Lista concatenata Lista concatenata circolarecircolareRANDOM – RANDOM – Lista concatenataLista concatenata

consumato in scrittura

Produttore

Consumatore

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

Esecuzione concorrente di diverseEsecuzione concorrente di diverse query query continuecontinue

Gestione Gestione overlapping overlapping finestre multiplefinestre multiple Singola passataSingola passata sui dati sui dati

0 s 5 s 10 s 15 s 20 s 25 s 30 s

t1 t2 t3 t4 t5 t6 t7

C2C3 C1

0 s 5 s 10 s 15 s 20 s 25 s 30 s

t1 t2 t3 t4 t5 t6 t7

C2C3 C1

Newly arrival tuples

tt tt

Old TuplesOld Tuples

ConsumedConsumedPostGIS

Polling 10 sPolling 10 s

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

Dati storici gestiti tramite Dati storici gestiti tramite DBMS DBMS PostgreSQLPostgreSQL con estensione spaziale con estensione spaziale PostGISPostGIS

Driver JDBC di tipo 4Driver JDBC di tipo 4 Estesione GIS molto utile per la gestione dei dati Estesione GIS molto utile per la gestione dei dati georeferenziatigeoreferenziati

• obuidobuidIdentificativo vetturaIdentificativo vettura

• speedspeedVelocità al tempo tVelocità al tempo t

• timetimeTempo di ricezione della tuplaTempo di ricezione della tupla

• timestamptimestampTempo logico di ricezioneTempo logico di ricezione

• position (position (lat, longlat, long))Posizione spaziale modellato Posizione spaziale modellato come punto bidimensionalecome punto bidimensionale

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

main()startDSMS()stopDSMS()submitQuery()stopQuery()

DSMSCoordinator

submitConsumer()stop()stopAll()

QueryEngine

start()stop()seqRead()randRead()setConsumer()removeConsumer()

StorageManager

IDLatitudeLongitudeSpeedTimeecc

Tuple

ConsumerTypeProducerTypeSchemaecc…

DataStructure

ConsumerIDWindowSamplePeriodFilterecc…

Consumer

inizializeInterface()setTextOBU_Store()ecc…

DSMSInterface

inizializeInterface()

start()

submitConsumer()

GUI

StorageManagerInterface

seqRead()randRead()setConsumer()removeConsumer()

resultSet

<<use>>

<<use>>

<<use>>

UtenteUtente Grafo delle classiGrafo delle classi

PROTOTIPO SOFTWAREPROTOTIPO SOFTWARE

Caratteristiche del produttoreproduttore Caratteristiche del/dei

Consumatore/iConsumatore/i

Produttore:Produttore:

Dimensione Dimensione dei blocchidei blocchi

FinestraFinestra

Tempo di Tempo di riesecuzioneriesecuzione

Modalità di Modalità di inserimentoinserimento

ConsumatoreConsumatore::

Tipologia di Tipologia di consumoconsumo

FiltriFiltri

Polling timePolling time

ID queryID query

FinestraFinestra

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS

Data Stream Management SystemData Stream Management System

Prototipo SoftwarePrototipo Software

Prove Sperimentali EffettuateProve Sperimentali Effettuate

Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

PROVE SPERIMENTALIPROVE SPERIMENTALI

Misura dei Misura dei tempi di rispostatempi di risposta al al variare di:variare di:

N. Thread ConsumerN. Thread Consumer

Frequenza di letturaFrequenza di lettura delle tupledelle tuple

Quantità di tuple perQuantità di tuple per filefile Algoritmo di lettura Algoritmo di lettura lineare lineare O(K)O(K)

Singola passataSingola passata Nessuna Nessuna approssimazioneapprossimazione

Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS

Data Stream Management SystemData Stream Management System

Prototipo SoftwarePrototipo Software

Prove Sperimentali EffettuateProve Sperimentali Effettuate

Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri

CONCLUSIONICONCLUSIONI E’ stato effettuato uno E’ stato effettuato uno studio approfonditostudio approfondito delle delle

caratteristiche e delle problematiche relative ai sistemi per la caratteristiche e delle problematiche relative ai sistemi per la gestione di stream di dati, ovvero dei gestione di stream di dati, ovvero dei Data Stream Data Stream Management SystemManagement System

Sono stati Sono stati analizzanti i principali DSMSanalizzanti i principali DSMS in via in via sperimentale, come ad esempio: TelegrapCQ, STREAM, sperimentale, come ad esempio: TelegrapCQ, STREAM, Cougar, Aurora e NiagaraCQ.Cougar, Aurora e NiagaraCQ.

E’ stato progettato ed implementato un innovativo E’ stato progettato ed implementato un innovativo DSMSDSMS in in JavaJava, in cui la parte di gestione dei dati è ben , in cui la parte di gestione dei dati è ben separata rispetto alla parte di query processing engine, in separata rispetto alla parte di query processing engine, in modo da garantire la massima flessibilità ed ottime modo da garantire la massima flessibilità ed ottime possibilita di ottimizzazione.possibilita di ottimizzazione.

Per la gestione dei dati storici, ci si è appoggiati al Per la gestione dei dati storici, ci si è appoggiati al DBMS DBMS PostgreSQLPostgreSQL, con l’estensione , con l’estensione PostGISPostGIS per poter per poter gestire i dati georeferenziati comunicati dalle OBU.gestire i dati georeferenziati comunicati dalle OBU.

Sono state effettuate delle Sono state effettuate delle prove sperimentaliprove sperimentali in modo da in modo da misurare le prestazioni e la scalabilità del sistema.misurare le prestazioni e la scalabilità del sistema.

Tutte le parti del lavoro di Tesi che mi è stato proposto sono Tutte le parti del lavoro di Tesi che mi è stato proposto sono state portate a termine in maniera state portate a termine in maniera concretaconcreta e e completacompleta..

CONCLUSIONICONCLUSIONI

… … studiati ed analizzati studiati ed analizzati più di 20 articoli scientifici articoli scientifici e documenti di ricerca nel campo dei DSMS:e documenti di ricerca nel campo dei DSMS:

• I. Botan, G. Alonso, P. M. Fischer, D. Kossmann, and N. Tatbul. Flexible and scalable storage management for data-Flexible and scalable storage management for data-intensive stream processingintensive stream processing

• F. Mandreoli, R. Martoglia, W. Penzo, S. Sassatelli. Data Data Management Issues for Intelligent Transportation SystemsManagement Issues for Intelligent Transportation Systems

• Lukasz Golab and M. Tamer Ozsu. Issues in Data Stream Issues in Data Stream ManagementManagement

• Brian Babcock Shivnath Babu Mayur Datar Rajeev Motwani Jennifer-Widom. Models and Issues in Data Stream Systems.Models and Issues in Data Stream Systems.

• Arkady Zaslavsky Mohamed Medhat Gaber and Shonali Krishnaswamy. Mining Data Streams: A Review.Mining Data Streams: A Review.

• Ecc…

SVILUPPI FUTURISVILUPPI FUTURI Il progetto Il progetto PEGASUSPEGASUS è un è un sistema molto complessosistema molto complesso

che richiederà all’università e ai collaboratori alcuni anni che richiederà all’università e ai collaboratori alcuni anni di lavoro tra sviluppo e testingdi lavoro tra sviluppo e testing

Il lavoro prodotto si inserisce quindi nell’ambito di una Il lavoro prodotto si inserisce quindi nell’ambito di una problematica ben più vasta di quanto è possibile trattare problematica ben più vasta di quanto è possibile trattare in una Tesi di Laurea e si presta di conseguenza a molti in una Tesi di Laurea e si presta di conseguenza a molti ed interessanti sviluppi sotto diversi aspettied interessanti sviluppi sotto diversi aspetti

Per quanto riguarda il DSMS, dovrà essere implementata Per quanto riguarda il DSMS, dovrà essere implementata l’interfaccia di retel’interfaccia di rete verso le OBU in modo da gestire verso le OBU in modo da gestire stream di dati reali e dovrà essere stream di dati reali e dovrà essere sviluppato il sviluppato il motore di query processing enginemotore di query processing engine (query parsing, (query parsing, query optimization, etc.).query optimization, etc.).

Infine, Infine, dovranno essere implementati tutti i servizi dovranno essere implementati tutti i servizi di di Smart NavigationSmart Navigation, , SafetySafety e e Urban MobilityUrban Mobility e e dovrà essere dovrà essere implementato il Recommender implementato il Recommender SystemSystem collaborativo per la gestione dei POI. collaborativo per la gestione dei POI.

FINEFINE