Assumeremo che gli oggetti siano rappresentati come URL. Tale assunzione riflette l’uso tipico delle reti P2P (file sharing).
Secondo uno studio effettuato da: Giulleume, M. Latapy e L. Viennot [6], la dimensione media di un URL è di 63,4 byte. Ogni termine ha una stored interpretation costituita da un numero elevato di oggetti, rappresentati da URL che occupano molto spazio in memoria e che determinano un aumento del tempo di trasmissione dei dati.
Esistono tuttavia delle tecniche di compressione dei dati che permettono di ottenere un buon bilanciamento fra lo spazio e il tempo richiesto per memorizzare e trasmettere gli oggetti; infatti, se la dimensione dei messaggi trasmessi è elevata, si riscontrano ritardi influenzati: dalla banda di trasmissione, dal traffico della rete, dalla latenza e soprattutto dai malfunzionamenti che possono causare la perdita dei dati durante la loro trasmissione.
Di seguito sono descritte le tecniche di compressione degli URL più comunemente utilizzate dai motori di ricerca, che sono state adottate nell’implementazione dei due modelli di simulazione.
4.2.1. Compressione e decompressione degli URL
Dato un insieme di URL possiamo associare un unico identificatore a ogni URL e definire una funzione che preso un identificatore restituisce l’URL corrispondente.
Se effettuiamo un ordinamento lessicografico degli URL, nel quale l’identificatore coincide con la posizione dell’URL nell’ordinamento, otteniamo dei notevoli vantaggi nella compressione degli oggetti, infatti questa operazione determina un incremento delle ridondanze locali. Se comprimiamo prima di effettuare l’ordinamento degli oggetti, otteniamo una dimensione media di ciascun URL di 7,27 byte contro una dimensione media di 5,73 byte se l’insieme gli URL è ordinato.
Lo spazio richiesto da questa tecnica di compressione dei dati è relativamente basso, si ha un ottimo tasso di compressione che penalizza il processo di decompressione dei URL.
Per evitare di decomprimere delle intere liste di URL, alcuni motori di ricerca le suddividono in blocchi, in modo da ridurne il tempo di decompressione. Adotteremo questa tecnica per comprimere e decomprimere tutti gli URL che le peer del nostro simulatore si scambiano durante il processo di risoluzione delle query.
Gli URL appartenenti ai blocchi sono identificati dal primo URL di ciascun blocco.
La dimensione media di un URL compresso non incrementa significativamente finché i blocchi sono composti da più di 1.000 URL; in questo caso la loro dimensione è di 6,49 byte. Quando i blocchi sono composti da un centinaio di URL la dimensione media cresce di un byte, asse- standosi a 7,49 byte. Il metodo può essere migliorato creando blocchi di differenti dimensioni che raggruppano URL scelti in modo tale da determinare un aumento delle ridondanze locali nelle liste di URL.
Questa tecnica di compressione degli oggetti si adatta alle problematiche dei nostri simulatori, infatti ogni peer ha una propria tassonomia con una propria stored interpretation, composta da un insieme di URL raggruppati in sottoinsiemi e trasmessi sulla rete.
Supporremo di decomprimerli in blocchi nei quali tutti gli URL hanno la stessa lunghezza.
Per garantire questa proprietà, verranno aggiunti dei caratteri speciali a tutti gli URL della stored interpretation della rete.
Possiamo convertire un URL in un identificatore eseguendo l’algoritmo di compressione dei dati illustrato di seguito:
– Procedura di recupero del blocco in cui è memorizzato l’URL. Attività di ricerca che si basa sulla conoscenza del primo URL di ogni blocco; la sua complessità asintotica al caso pessimo è uguale log(numero _blocchi), dove numero _blocchi è il numero totale dei blocchi in cui sono memorizzati gli oggetti appartenenti alla stored interpretation della terminologia di ciascuna peer.
– Procedura di decompressione del blocco. La fase di espansione degli URL memorizzati in un blocco ha complessità asintotica proporzionale alla numero di oggetti che appartengono al blocco, ossia O(lunghezza _blocco).
– Procedura di ricerca dell’URL all’interno del blocco. L’identificatore dell’URL coincide con la posizione dell’URL dentro il blocco. Se si usa un algoritmo di ricerca lineare, la complessità asintotica dell’operazione è proporzionale alla lunghezza del blocco, se invece si utilizza un altro algoritmo, possiamo ottimizzare la complessità asintotica rendendola logaritmica, ossia O log (( lunghezza _blocco)).
Possiamo convertire un identificatore in un URL nel seguente modo:
– Procedura di recupero del blocco in cui è memorizzato l’identificatore. La complessità asintotica dell’operazione è costante, ossia O(1). Tutti i blocchi contengono lo stesso numero di URL, quindi l’indice del blocco contenente l’identificatore si ottiene dalla seguente formula:
identificatore/lunghezza_blocco
.– Procedura di decompressione del blocco. Complessità asintotica identica alla complessità asintotica della procedura di conversione dell’URL nel corrispondente identificatore.
– Procedura di ricerca dell’identificatore all’interno del blocco. Dato che tutti i blocchi hanno la stessa lunghezza e la stessa proprietà vale per la lunghezza degli URL, la procedura ha complessità asintotica costante e si risolve con un accesso diretto agli oggetti nel blocco. L’URL è collocato alla seguente posizione:
). _
_ (
_url identificatore lunghezza blocco numero blocco
lunghezza ⋅ − ⋅
Se la dimensione dei blocchi è troppo elevata si rischia di dover gestire insiemi di URL che utilizzano una grande quantità di caratteri speciali, inutili ai fini dell’archiviazione dei dati.
Nella Tabella 4.2 sono riportate le complessità asintotiche degli algoritmi di compressione e decompressione di ciascun blocco di URL.
Supporremo che gli oggetti scambiati possano essere compressi e spediti alle peer della rete e che il loro grado di compressione sia proporzionale al numero di URL trasmessi, in accordo con la funzione di compressione dei dati ottenuta discretizzando il grafico riportato nella Figura 4.6.
URLà identificatore Identificatoreà URL
Primo passo O(log (numero _blocchi)) O(1)
Secondo passo O(lunghezza _blocco) O(lunghezza _blocco) Terzo passo O(log(lunghezza _blocco)) O(1)
Tabella 4.2 Compressione e decompressione dei blocchi di URL
La funzione che utilizzeremo è definita per blocchi di URL con dimensione compresa fra 5 URL e 280 URL, nella Figura 4.7 è riportato il grafico della funzione per blocchi superiori a 300 URL. Nei nostri simulatori ci limiteremo a considerare la trasmissione di blocchi con dimensione inferiore ai 280 URL, come definito dalla seguente funzione:
− + 4 37 80 1 x x∈[5,140] kUrl= − + 8 67 160 1 x x∈[140,280]
Infine, supporremo che gli URL inviati singolarmente oppure in blocchi inferiori alle 5 unità, venga compresso e abbia dimensione uguale a 11,5 byte.
Dimensione degli URL in byte 6,5 7,0 7,5 8,0 8,5 9,0 9,5 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 blocchi di URL byte dimensione URL
Figura 4.6 Dimensione media di un URL compresso in blocchi di URL con cardinalità
compresa fra 5 URL e 280 URL
Dimensione degli URL in byte
6,0 6,5 7,0 7,5 8,0 8,5 9,0 9,5 0 100 200 300 400 500 600 700 800 900 1000 blocchi di URL byte Dimensione URL