Università degli studi di Modena e Reggio Emilia
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea Magistrale in Informatica
GESTIONE EFFICIENTE DEI DATI IN UN
DATA STREAM MANAGEMENT SYSTEM
Relatore:
Ing. Riccardo Martoglia
Correlatori:
Dott. Federica Mandreoli
Ing. Luca Carafoli
Candidato:
Federico Di Bernardo
Anno Accademico 2009-2010
INTRODUZIONE
o Situazione critica del traffico nelle città
 Aumento del consumo di carburante ed inquinamento
 Incremento del numero di incidenti
 Forte congestionamento della rete stradale
 Necessità di una nuova concezione di mobilità e trasporto
 Sfida nell’ambito di ricerca dell’ICT (Information and
Communication technology )
INTRODUZIONE
PEGASUS = ProgEtto per la Gestione della mobilità Attraverso Sistemi infotelematici
per l’ambito Urbano, per la Sicurezza di passeggeri, veicoli e merci.
• Realizzato in collaborazione con l’università di Bologna.
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.
OBIETTIVO DELLA TESI:
Studiare e sviluppare un sistema per la gestione efficiente dei dati
provenienti dalle OBU (On-Board Unit) installate sui veicoli urbani
CONTENUTI:





Panoramica sul Sistema PEGASUS
Data Stream Management System
Prototipo Software
Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri

Panoramica sul Sistema PEGASUS

Data Stream Management System

Prototipo Software

Prove Sperimentali Effettuate

Conclusioni e Sviluppi Futuri
PANORAMICA 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à
• Posizione
• Accelerazione
GPS unit
Accel
unit
GPRS
V2I unit
Real-time comms
engine
Smart navigation
engine
User interface
WiFi V2V
unit
Maps &
real-time
data
PANORAMICA SUL SISTEMA PEGASUS
BTS
Differenti tipologie
di comunicazione:
OBUs
BTS
V2V (WiFi)
V2I (GPRS)
Il Centro Di Controllo
colleziona ed integra i
dati e gestisce i POI ed
EOI
Infrastructured
Network
Comunicazioni GPRS
costose !
Control
Centre
ad-hoc, multi-hop, V2V communication
V2I communication
PANORAMICA SUL SISTEMA PEGASUS
Centro di Controllo
Service Module
EOI
Ontology
Service Manager
POI
Ontology
Recommender
System
DSMS
Smart
Navigation
Urban
Mobilit
y
Safet
y
Query Processing
Engine
Storage Manager
Communication Manager
GIS tables
Data acquisition
V2I
interaction
OBU
OBU
OBU
OBU
Communication
-saving!
OBU
V2Vinteractio
n
OBU
OBU

Panoramica sul Sistema PEGASUS

Data Stream Management System

Prototipo Software

Prove Sperimentali Effettuate

Conclusioni e Sviluppi Futuri
DATA STREAM MANAGEMENT SYSTEM
Applicazione di streaming data-intensive con requisiti
spaziali e temporali
 GIS DSMS Temporale
 Linguaggio di interrogazione SQL-Like
 Acquisizione ed accesso a dati tempo e spazio localizzati
Streaming items utilizzati non solo per i servizi real-time
 Query continue
 Ad-Hoc Query
 Analisi OLAP su dati storici
Tipiche soluzioni accoppiano il sistema di Storage
Management con quello di Query Processing
 Scarsa flessibilità
 Difficoltà di ottimizzazione
DATA STREAM MANAGEMENT SYSTEM
DSMS
Query Processing Engine
Query 1
Query 2
…
OBUs
Input Stream
Query
Optimizer
Query
Executor
Read /
Setup
Query n
Query
Parser
ResultsSet
Interface
Storage Manager
Storage
Point 1
Storage
Point 2
…
Storage
Point n
Load
Shedder
Data
Manager
GIS
DBMS
DATA STREAM MANAGEMENT SYSTEM
DSMS profondamente diversi dai DBMS
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 SYSTEM
PROBLEMA: Dati potenzialmente infiniti e memoria
primaria limitata !
Main Memory
Soluzioni “Lossless”:
 Window Models
WINDOW
 Presente vs Storico
Old tuples
DBMS
Newly arrival tuples
DATA STREAM MANAGEMENT SYSTEM
Memory
Ottimizzazioni “Lossy”:
P = 0,33
 Load Shedding
 Synopses
Near vehicle
 Batch Processing
Incident
detection
DSMS

Panoramica sul Sistema PEGASUS

Data Stream Management System

Prototipo Software

Prove Sperimentali Effettuate

Conclusioni e Sviluppi Futuri
PROTOTIPO SOFTWARE
Sviluppo di un Storage Management System
disaccoppiato dal modulo di Query Processing Engine
Results
Storage Manager
 Query produttore pull-based
 Registrazione queries consumatore
 Switch dinamico delle strutture dati
 Gestione delle finestre temporali
 Migrazione dati storici
OBUs
Input Stream
Query Processing Engine
 Sottomissione query consumatore
Esecuzione concorrente di diverse queries
 Invio comandi di lettura (con o senza filtri)
 Scrittura risultati su file
Query Engine
read
setup
results
Interface
Storage Manager
PostGIS
PROTOTIPO SOFTWARE
Strutture dati dinamiche
Consumatore
Produttore
Never Consume Ordered Consume Eager Consume
Never Expire
PERSISTENT
FIFO
FIFO \ RANDOM
Ordered Expire
FIFO
FIFO
FIFO \ RANDOM
Unordered Expire
RANDOM
RANDOM
RANDOM
Replaced Expire
IN-PLACE
IN-PLACE
IN-PLACE
FIFO – Lista concatenata circolare
vuoti
consumati
pieno
pieno
in scrittura
RANDOM – Lista concatenata
consumato
in scrittura
PROTOTIPO SOFTWARE
Esecuzione concorrente di diverse query continue
 Gestione overlapping finestre multiple
 Singola passata sui dati
C3
C2
C1
C3
C2
C1
Newly arrival tuples
t1
t2
t3
t4
t5
t6
t7
t1
t2
t3
t4
t5
0s
5s
10 s
15 s
20 s
t6
t7
25 s
30 s
Polling 10 s
0s
5s
10 s
15 s
20 s
25 s
30 s
t
Old Tuples
PostGIS
Consumed
t
PROTOTIPO SOFTWARE
Dati storici gestiti tramite DBMS PostgreSQL con
estensione spaziale PostGIS
 Driver JDBC di tipo 4
 Estesione GIS molto utile per la gestione dei dati georeferenziati
• obuid
Identificativo vettura
• speed
Velocità al tempo t
• time
Tempo di ricezione della tupla
• timestamp
Tempo logico di ricezione
• position (lat, long)
Posizione spaziale modellato
come punto bidimensionale
PROTOTIPO SOFTWARE
Grafo delle classi
Utente
GUI
DataStructure
DSMSInterface
inizializeInterface()
<<use>>
inizializeInterface()
setTextOBU_Store()
ecc…
ConsumerType
ProducerType
Schema
ecc…
DSMSCoordinator
main()
startDSMS()
stopDSMS()
submitQuery()
stopQuery()
StorageManager
start()
Consumer
start()
stop()
seqRead()
randRead()
setConsumer()
removeConsumer()
<<use>>
StorageManagerInterface
seqRead()
randRead()
setConsumer()
removeConsumer()
resultSet
Tuple
QueryEngine
submitConsumer()
submitConsumer() stop()
stopAll()
ConsumerID
Window
SamplePeriod
Filter
ecc…
<<use>>
ID
Latitude
Longitude
Speed
Time
ecc
PROTOTIPO SOFTWARE
Produttore:
 Dimensione dei
blocchi
 Finestra
 Tempo di
riesecuzione
 Modalità di
inserimento
Consumatore:
 Tipologia di
consumo
 Filtri
 Polling time
 ID query
 Finestra
Caratteristiche del
produttore
Caratteristiche del/dei
Consumatore/i

Panoramica sul Sistema PEGASUS

Data Stream Management System

Prototipo Software

Prove Sperimentali Effettuate

Conclusioni e Sviluppi Futuri
PROVE SPERIMENTALI
Misura dei tempi di risposta al variare di:
 N. Thread Consumer
 Frequenza di lettura
delle tuple
 Quantità di tuple per
file
Algoritmo di lettura
lineare O(K)
 Singola passata
 Nessuna approssimazione

Panoramica sul Sistema PEGASUS

Data Stream Management System

Prototipo Software

Prove Sperimentali Effettuate

Conclusioni e Sviluppi Futuri
CONCLUSIONI

E’ stato effettuato uno studio approfondito delle caratteristiche e delle
problematiche relative ai sistemi per la gestione di stream di dati,
ovvero dei Data Stream Management System

Sono stati analizzanti i principali DSMS in via sperimentale, come ad
esempio: TelegrapCQ, STREAM, Cougar, Aurora e NiagaraCQ.

E’ stato progettato ed implementato un innovativo DSMS in Java, in cui
la parte di gestione dei dati è ben separata rispetto alla parte di query
processing engine, in modo da garantire la massima flessibilità ed
ottime possibilita di ottimizzazione.

Per la gestione dei dati storici, ci si è appoggiati al DBMS PostgreSQL,
con l’estensione PostGIS per poter gestire i dati georeferenziati
comunicati dalle OBU.

Sono state effettuate delle prove sperimentali in modo da misurare le
prestazioni e la scalabilità del sistema.

Tutte le parti del lavoro di Tesi che mi è stato proposto sono state
portate a termine in maniera concreta e completa.
CONCLUSIONI
… studiati ed analizzati più di 20 articoli scientifici 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-intensive stream
processing
•
F. Mandreoli, R. Martoglia, W. Penzo, S. Sassatelli. Data Management
Issues for Intelligent Transportation Systems
•
Lukasz Golab and M. Tamer Ozsu. Issues in Data Stream Management
•
Brian Babcock Shivnath Babu Mayur Datar Rajeev Motwani JenniferWidom. Models and Issues in Data Stream Systems.
•
Arkady Zaslavsky Mohamed Medhat Gaber and Shonali Krishnaswamy.
Mining Data Streams: A Review.
•
Ecc…
SVILUPPI FUTURI

Il progetto PEGASUS è un sistema molto complesso che
richiederà all’università e ai collaboratori alcuni anni di lavoro tra
sviluppo e testing

Il lavoro prodotto si inserisce quindi nell’ambito di una
problematica ben più vasta di quanto è possibile trattare in una
Tesi di Laurea e si presta di conseguenza a molti ed interessanti
sviluppi sotto diversi aspetti

Per quanto riguarda il DSMS, dovrà essere implementata
l’interfaccia di rete verso le OBU in modo da gestire stream di
dati reali e dovrà essere sviluppato il motore di query processing
engine (query parsing, query optimization, etc.).

Infine, dovranno essere implementati tutti i servizi di Smart
Navigation, Safety e Urban Mobility e dovrà essere implementato
il Recommender System collaborativo per la gestione dei POI.
FINE