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
Top Related