WP6 - Knowledge services for
intensive data analysis and
intelligent query answering
Responsabile:
Membri TB:
Franco Turini (UniPI)
Dino Pedreschi (UniPI)
Domenico Saccà (ICAR-CNR)
27-28.5.2003
Workshop di Rimodulazione
1
WP6 - Obiettivi
 Costruzione di servizi di middleware per
applicazioni e processi knowledge intensive:
 estrazione e ricerca di informazione e
conoscenza da
 fonti strutturate (basi di dati, data
warehouses)
 semi-strutturate (pagine web,
documenti XML)
 utilizzo dell’informazione e della conoscenza
estratta per servizi ad alte prestazioni di
search, di retrieval e di query answering
27-28.5.2003
Workshop didi
Rimodulazione
(efficienza e qualità
servizio)
2
WP6 - Approccio
 Basic services: per
data management e
performance
 Knowledge services:
per applicazioni e
computazioni di
knowledge discovery
distribuite
 Retrieval services:
per il recupero di
informazioni sul Web
27-28.5.2003
knowledge
services
Workshop di Rimodulazione
retrieval
services
basic services
3
WP6 – Basic services





resource discovery and description
accesso ai dati
compressione e ricerca sui dati
primitive di data mining, di data preprocessing
grid mining (attività fortemente esplorativa)
 Partecipano:



ICAR-CNR CS (Talia, Saccà)
ISTI-CNR PI (Giannotti, Perego)
UniPI (Ferragina, Ghelli, Pedreschi, Ruggieri)
27-28.5.2003
Workshop di Rimodulazione
4
WP6 – Low-level Basic Services
 High-performance web switching
 Partecipano:
 UniPI (Attardi)
 IEIIT-CNR TO (De Martin)
 PoliTO (Meo)
27-28.5.2003
Workshop di Rimodulazione
5
WP6 – Knowledge services
 ambienti di supporto al processo di
knowledge discovery
 linguaggi di interrogazione per data
mining
 Partecipano
 ICAR-CNR CS (Talia, Saccà)
 ISTI-CNR PI (Giannotti)
 UniPI (Pedreschi, Ruggieri, Turini)
27-28.5.2003
Workshop di Rimodulazione
6
WP6 – Retrieval services
 focused crawling su grid
 Partecipano:




UniPI (Starita)
UniPD (Sperduti)
UniSI (Gori, Maggini)
UniFI (Frasconi, Soda)
27-28.5.2003
Workshop di Rimodulazione
7
Basic Services: stato e prospettive
 Grid DB per resource discovery and
description
 Strumenti per XML indexing and
compression
 Architettura di integrazione di strumenti
di Data Mining su GRID
 Open Web Switching
27-28.5.2003
Workshop di Rimodulazione
8
GRID DB per resource
discovery and description
Principal Investigator:
Giorgio Ghelli
27-28.5.2003
Workshop di Rimodulazione
9
Background
Mancanza di servizi dati DB-like nei
toolkit standard
Progetti esistenti
 Datagrid: non DB oriented
 Spitfire: accesso distribuito a basi di dati
relazionali
 Polar*: riformulazione in ambito GRID del
DBMS parallelo ad oggetti Polar
 GGF DAIS-WG: servizi per l’accesso a DB
esistenti
27-28.5.2003
Workshop di Rimodulazione
10
Obiettivi del nostro progetto
 L’attenzione è spesso focalizzata sulle
problematiche tradizionali di decomposizione
dei piani di accesso e gestione distribuita delle
transazioni
 Noi vogliamo focalizzare l’attenzione sulle
problematiche peculiari della griglia:
 dinamicità della struttura dell’Organizzazione
Virtuale
 integrazione di domini amministrativi diversi
 (se possibile) high performance
27-28.5.2003
Workshop di Rimodulazione
11
Il nostro obiettivo
 Progettare un Semistructured GRIDDB, ovvero un DB GRID-distribuito
caratterizzato da:
 struttura distribuita e dinamica, ovvero
la capacità di accettare l’apparizione e
sparizione di componenti del sistema
 modello dei dati semistrutturato
 utilizzo di linguaggi standard (XQuery) e
protocolli standard (LDAP like?) per
l’accesso
27-28.5.2003
Workshop di Rimodulazione
12
Applicazioni tipiche
 Complementare l’approccio
tradizionale; ad esempio:
 il GRID-DB per gestire i metadati, e i
database federati per gestire i dati
 il GRID-DB per affiancare la gerarchia
GRIS-GIIS quando il modello dei dati del
GRIS (LDAP data model) non è
sufficiente
27-28.5.2003
Workshop di Rimodulazione
13
Integrazione nell’ambito del
progetto
 Metteremo a disposizione gli strumenti da
noi sviluppati nell’ambito del WP6
integrandoci in particolare con le attivita di:
 adattamento all’architettura grid di un ambiente
di knowledge discovery basato su XML
 livello core dei basic services for knowledge
discovery on grids
 Disponibili ad un integrazione con altri WP
27-28.5.2003
Workshop di Rimodulazione
14
Gruppo di lavoro
 Sartiani (borsa Giugno 2003 – Maggio
2003)
 Ghelli, Manghi, Albano, Conforti
27-28.5.2003
Workshop di Rimodulazione
15
Deliverables
 12 mesi: un documento di
progettazione dell’architettura,
modello dei dati, linguaggio, e
protocollo del GRID-DB
 18 mesi: documento di progettazione
del prototipo
 30 mesi: prototipo
 36 mesi: rapporto sulla
sperimentazione del prototipo
27-28.5.2003
Workshop di Rimodulazione
16
Strumenti per XML indexing
and compression
Principal Investigator:
Paolo Ferragina
27-28.5.2003
Workshop di Rimodulazione
17
Attività svolte: XML indexing and compression

Flat: nessun preprocessing del file e ricerca per scansione (SAX o DOM)
– Molto lento e, nel caso del DOM, si usa molta memoria

IR oriented: indice testuale non specializzato all’XML


Le ricerche su testo+struttura possono essere molto lente
Database oriented: uso di un DBMS a oggetti o relazionale
– Abbiamo bisogno di indici extra, l’occupazione in spazio aumenta
– Query strutturali necessitano di numerose join, e sono quindi lente

XML nativo: tecniche ad hoc di storage e indicizzazione per XML
XCDE Library: approccio nativo, e pressocchè unico nel suo genere
• Libreria C con licenza LGPL, altamente personalizzabile
• Tecniche indicizzazione e compressione allo stato dell’arte
27-28.5.2003
Workshop di Rimodulazione
18
XCDE Library: deliverable e ricerche future
XML Query
solver
XCDE Library
API
Console
Disk
Text
query solver
query solver
Context
extractor
Query engine
API
Text engine
1° anno
Tag-Attribute
Tag engine
Data engine
Context engine
• Documenti e indici in forma compressa (tutto entro la dimensione originale del file)
• Supporto a query testuali e strutturali complesse (errori, regexp, proximity, nesting, ...)
• Relizzazione per single-machine e studio di fattibilità per l’estensione al Grid
Piani futuri:
• Realizzazione di primitive di query più potenti, vicino a XQuery e orientate ai testi
• Uso come componente base di applicazioni del WP6
• Nuove tecniche di compressione e indicizzazione su file XML
27-28.5.2003
Workshop di Rimodulazione
19
Architettura di integrazione di
strumenti di Data Mining su GRID
Principal Investigators:
Mimmo Talia, Mimmo Sacca`
27-28.5.2003
Workshop di Rimodulazione
20
Obiettivi
1) le attivita` che saranno svolte con chiari riferimenti al
contesto del progetto

Realizzazione di una architettura per supportare applicazioni di
KDD parallele e distribuite su Griglie computazionali (Knowledge
Grid).


L’architettura permette di integrare strumenti e algoritmi di data mining
con gli ambienti di Grid computing.
Definizione e realizzazione di un sistema di distribuzione e
aggregazione di fonti informative

Il sistema permette di rappresentare una fonte informativa (ad esempio
stream data) come una rete di viste con diversi livelli di aggregazione
in modo che ogni nodo abbia nella sua vista i dettagli dei dati di sua
pertinenza e un sintesi di quelli presenti presso altri nodi
27-28.5.2003
Workshop di Rimodulazione
21
Risultati
2) i primi risultati ottenuti in questi primi mesi
 Schema funzionale dell’architettura del KDD parallelo e
distribuito e definizione delle componenti di base e delle loro
interfacce.
 Definizione di algoritmi e modelli di aggregazione di datacube e
stream data e loro distribuzione su griglia
3) i deliverable del primo anno
 Documenti di specifica dell’architettura del KDD parallelo e
distribuito e sviluppo di un primo prototipo realizzato su Globus
Toolkit.
 Documenti di specifica per la aggregazione e distribuzione di
datacube e prototipo di un sistema distribuito di gestione di
stream data
27-28.5.2003
Workshop di Rimodulazione
22
Web Switching
Gruppo di Lavoro:
Centro Serra, Università di Pisa
Giuseppe Attardi
Vivek Sinha
Stefano Suin
27-28.5.2003
Workshop di Rimodulazione
23
Setting
Server Farm
Clients
Web Switch
Internet
 Large number of transactions (>1000/sec)
 Large amount of data (billions of
documents)
27-28.5.2003
Workshop di Rimodulazione
24
Switch Technology
 Local Director with Direct Routing
Replies go directly to clients
Interne
t
Requests
Web Switch
Single IP
address
Internal
Network
27-28.5.2003
Workshop di Rimodulazione
25
Details
 IP packet forwarding:
 Modified Linux kernel
 Switch chooses server and changes MAC
address of packet
 Switch maintains table of connections, to
ensure persistency
 Each server connects to outside with same
IP:
 Modified Linux kernel to avoid responding to ARP
27-28.5.2003
Workshop di Rimodulazione
26
Status
 Experimenting with Linux Virtual
Server
 Benchmarks and testing with RLX
blade server
27-28.5.2003
Workshop di Rimodulazione
27
Test beds
 Distributed Crawler
 Goal: collect 300 million Web documents
in a month
 Distributed Search Engine
 Collection partitioned into several
indexes
 Cluster for each partition
 Web Switch redirects to various clusters
27-28.5.2003
Workshop di Rimodulazione
28
Open Web Switching
Gruppo di lavoro:
Politecnico di Torino/IEIITCNR
Espedito Antonio Mancuso
Juan Carlos De Martin
Angelo Raffaele Meo
27-28.5.2003
Workshop di Rimodulazione
29
Attività
 Obiettivo: sostituire i layer-7 switch costosi e proprietari - con web switch ai
margini della rete - economici, flessibili
ed aperti
 Switching: MPLS-based
 Piattaforma: Linux
 Risultati: Progettato architettura
complessiva (v. rapporto tecnico)
27-28.5.2003
Workshop di Rimodulazione
30
Attivita`
 Obiettivo: sostituire i layer-7 switch –costosi e
proprietari- con web switch ai margini della
rete – economici, flessibili e aperti.
 Switching: MPLS-based
 Piattaforma: Linux
 Deliverable: progetto dell’architettura
complessiva
27-28.5.2003
Workshop di Rimodulazione
31
Knowledge Services: stato e
prospettive
 Knowledge Grid
 Costruzione di ambienti di KDD su
Grid
27-28.5.2003
Workshop di Rimodulazione
32
Knowledge Grid
Principal Investigators:
Mimmo Talia
Mimmo Sacca`
27-28.5.2003
Workshop di Rimodulazione
33
Attivita`
1) le attivita` che saranno svolte con chiari
riferimenti al contesto del progetto



Realizzazione di strumenti di alto livello per lo sviluppo di
processi di KDD su Griglie computazionali costruiti a partire
dell’architettura e dei servizi di base della Knowledge Grid
Progettazione e sviluppo di metodi, strumenti e meccanismi
basati su XML per la descrizione di risorse e processi di
KDD, la loro ricerca e integrazione sulla Griglia
Sviluppo di una ontologia per il data mining da usare nella
Knowledge Grid
27-28.5.2003
Workshop di Rimodulazione
34
Attivita` (2)


Definizione e realizzazione prototipale di un ambiente per la
composizione di risorse e servizi disponibili su griglia,
modellati tramite un workflow, e per l’analisi, la predizione
e il monitoraggio degli scenari di utilizzo attraverso
l’integrazione di tecniche di Knowledge Discovery e di
Reasoning
Definizione e sviluppo di tecniche di data mining per l’analisi
di workflow di composizione di servizi su griglia al fine di
individuare pattern frequenti, situazioni di probabile
successo (o insuccesso) e per ristrutturare la composizione
al fine di aumentare la qualità complessiva
27-28.5.2003
Workshop di Rimodulazione
35
Risultati
2) i primi risultati ottenuti in questi primi mesi
 Definizione di un servizio di informazione per la
Knowledge Grid.
 Progettazione di uno strumento per lo sviluppo di
applicazioni KDD sulla Griglia.
 Definizione di un modello deduttivo-induttivo per la
definizione di workflow di servizi e la predizione di
scenari di comportamento
 Definizione di tecniche di mining di regole associative su
istanze di workflow rappresentate come grafi
27-28.5.2003
Workshop di Rimodulazione
36
Deliverables
3) i deliverable del primo anno
 Documenti sulle tematiche elencate.
 Prototipi di strumenti e servizi di alto livello per KDD
sulla Griglia.
27-28.5.2003
Workshop di Rimodulazione
37
Ambienti di KDD su Grid
Principal Investigators:
Fosca Giannotti,Salvatore Ruggieri,
Dino Pedreschi, Franco Turini
27-28.5.2003
Workshop di Rimodulazione
38
Strategia
 marcatura stretta dei risultati del
WP8 ovvero:
1. sequenziale
2. parallelo
3. GRID-aware
27-28.5.2003
Workshop di Rimodulazione
39
Sistema KDDML
 Principio base:
 utilizzo di XML come linguaggio per la interoperabilità
 un documento XML si dice valido se rispetta le
specifiche definite nella corrispondente DTD
(Document Type Definition)
 forte espressività del QL
 sistema aperto
 In KDDML (KDD Markup Language):
 implementazione in Java
 ogni modello (RDA, Alberi, Clusters) viene
rappresentato come un documento XML
(KDD_OBJECT)
 anche i problemi di estrazione di conoscenza sono
documenti XML (KDD_QUERY)
27-28.5.2003
Workshop di Rimodulazione
40
Architettura originaria di KDDML
Legenda:
Query Executor
XML
RunTimeException
Componente
esterna
Repository
LotusXSL
Graphic
User
Interface
XML-DOM
Operatori
rappresentation
Browser
Componente
implementata
Wrappers
WEKA
Sorgente
Dati
Classe
Paths
27-28.5.2003
Workshop di Rimodulazione
41
Esecuzione seq. di una KDD query
 Ad ogni documento XML che rappesenta il modello o
la query puo’ essere associato un albero DOM
(Document Object Model).
 Utile dare al programmatore una visione concettuale
dei dati contenuti nel documento.
 Disponibili interfacce per manipolare e leggere i nodi
dell’albero (getChilds(), getAttribute() …).
 Il QueryExecutor di KDDML effettua una visita in
profondità dell’albero DOM che rappresenta la query
da eseguire. Per ogni operatore individuato si
richiama la classe corrispondente per l’esecuzione.
27-28.5.2003
Workshop di Rimodulazione
42
Come parallelizzare l’esecuzione?

Introduzione in KDDML di un operatore
“esplicito” di parallelismo: Parallel
Operatori scelti:
And_Or_Committee
Rule_Exception
Rule_Support
Preserved_Rules
Classify
Take_By_If

27-28.5.2003
Motivazioni:

consentono l’annidamento di sotto operatori

vi si puo’ applicare il “Task Parallel”

utilizzo della strategia “Replicazione degli
alg. DM seq.”
Workshop di Rimodulazione
43
Architettura del sistema parallelo
File risultati
KDD Query
GUI
Query_Executor
Parallel
Legenda:
JVM1
Package
classi
JavaVm.hpp
FileAstJava
Flusso dei dati
ASSIST
File.ast
File
System
pipe
librerie
JVM2
AstFile
Operatori
Parquery_Executor
Wrappers
27-28.5.2003
Workshop di Rimodulazione
44
Deliverables
 versione parallela di KDDML
 progetto di integrazione di algoritmi
di DM paralleli
 Studio di fattibilita` sul Grid Mining
27-28.5.2003
Workshop di Rimodulazione
45
Retrieval services
 focused crawling su grid
Principal Investigators:
Antonina Starita,
Alessandro Sperduti,
Marco Gori,
Paolo Frasconi
27-28.5.2003
Workshop di Rimodulazione
46
Motivations
General purpose search engines must
trade recency for coverage
Coverage: fraction of Web documents
that are crawled and indexed
Recency: index is -current at time
if no changes occurred in
Focused crawling
 Crawl the Web only for a specific “topic”
 Given the available bandwidth both coverage and recency
will be high for that topic
 AI algorithms are necessary to:
 decide whether or not a page is off-topic
 predict whether following out-links from a given page
will increase coverage
 filter crawled documents
 Different machine learning tools may be used
Objectives
 Crawling:
 Use grid infrastructure to distribute crawling
activity on several nodes
 Learning and categorization:
 Very large collections of (physically distributed)
documents
 Large number of classes
 Exploit link analysis
Deliverables
 1st year
 Prototype of a learning and categorization
service deployed on the grid
 2nd year
 Deployment of a service capable of dynamic
management of classification agents
 First prototype of parallel distributed crawlers
 3rd year
 Implementation and testing of the adaptive
focused crawler