3.2 Euristiche implementate nel Wos
3.2.2 Sessioni
Proponiamo adesso i dettagli implementativi delle euristiche messe a di- sposizione dalla libreria per la ricostruzione delle sessioni.
Notiamo che in ognuna, poich´e al momento dell’identificazione delle sessioni si cerca di riconoscere le pagine visitate da uno stesso utente, una condizio- ne necessaria affinch´e due PageView appartengano alla stessa sessione `e che le richieste HTTP corrispondenti provengano dallo stesso indirizzo Ip e, se presente, abbiano lo stesso user agent.
Inoltre tutti gli algoritmi si basano su un ordinamento delle PageView secondo un attributo composto dalla concatenazione di indirizzo Ip e time stamp. In questo modo `e possibile identificare le sessioni semplicemente con una scansione del database contenente le PageView, e decidendo per ciascuna di esse se deve appartenere alla sessione corrente o di una nuova. Ci`o che differenzia le singole euristiche `e, come vedremo, il criterio scelto per prendere questa decisione.
Time window heuristic
La prima euristica che `e stata implementata `e la pi`u semplice e si basa sul controllo della durata dell’intervallo di tempo intercorso tra due PageView successive.
Ad ogni chiamata del metodonextSession()dell’euristica, come mostra- to nell’algoritmo 3.2, si costruisce un nuovo oggetto di tipo Session, a cui si aggiunge la PageView corrente estratta dal repository secondo l’ordine pre- cedentemente menzionato, memorizzandone indirizzo Ip, user agent e time
3.3.2.2 Sessioni 79
Algorithm 3.1 Metodo nextP v() dell’euristica di ricostruzione delle PageView
Input: HttpRequest repository httpRep time t timeSpanf rame
time t timeSpan Output: PageView pv
1. repeat
2. request = htppRep.get()
3. until request.isEntryP oint()
4. pv = new P ageV iew()
5. pv.elements.insert(request.id)
6. copia informazioni di request in pv
7. inP v = true
8. while inP v and htppRep.nextCompound() do
9. nextRequest = httpRep.get()
10. time = nextRequest.date − request.date
11. if nextP v.ipAddress = pv.ipAddress then
12. if (nextRequest.isEntryP oint() = false) and (time ≤ timeSpan) then
13. session.elements.insert(nextP v.id)
14. session.lenght ++
15. else if (nextRequest.isEntryP oint() = true) and (time ≤ timeSpanf rame) then
16. pv.elements.insert(nextRequest.id) 17. pv.lenght ++ 18. else 19. inP v = f alse 20. else 21. inP v = f alse 22. return pv
80 Euristiche di preprocessing
stamp (passi 1-5). Poi, per ogni PageView successiva (estratta nei passi 6-8) si controlla se pu`o appartenere o meno alla sessione, verificando che ci sia uguaglianza tra l’ indirizzo Ip di questa con i valori memorizzati e che tra le due non sia passato un intervallo di tempo superiore alla soglia fissata e, in caso di successo, si aggiunge alla sessione (passi 6-11).
Se non indicato diversamente al momento della costruzione dell’oggetto che implementa l’euristica la soglia `e fissata in 1800 secondi (30 minuti). Algorithm 3.2 Metodo nextSession() dell’euristica basata sul timewindow Input: PageView repository pvRep
time t timeW indow Output: Session session
1. session = new Session() 2. pv = pvRep.get()
3. session.elements.insert(pv.id)
4. copia informazioni di pv in session
5. inSession = true
6. while inSession and pvRep.nextCompound() do
7. nextP v = pvRep.get()
8. timeSpan = nextP v.date − pv.date
9. if nextP v.ipAddress = pv.ipAddress and timeSpan ≤ timeW indow then
10. session.elements.insert(nextP v.id)
11. session.lenght ++
12. else
13. inSession = f alse
14. return session
Path session heuristic
Con questo metodo si vuole ricostruire delle sessioni che rappresentino l’esatto percorso che ha seguito un utente navigando in uno o pi`u siti, ma sempre seguendo un link da una pagina all’altra.
3.3.2.2 Sessioni 81
L’utilizzo di questa euristica `e subordinato alla presenza del campo refer- rer nel log file contenente i dati in input, in quanto la condizione necessaria e sufficiente affinch´e una PageView venga inserita o meno all’interno della sessione costruita `e che il referrer sia uguale alla URI della PageView che la precede, come si pu`o vedere dallo pseudocodice fornito nell’algoritmo 3.3 al passo 8. L’unica differenza rispetto al procedimento descritto nella precedente sezione `e proprio la condizione di appartenenza ad una sessione.
Algorithm 3.3 Metodo nextSession() dell’euristica per ricostruire pathSession
Input: PageView repository pvRep Output: Session session
1. session = new Session()
2. pv = pvRep.get()
3. session.elements.insert(pv.id)
4. copia informazioni di pv in session
5. inSession = true
6. while inSession and pvRep.nextCompound() do
7. nextP v = pvRep.get()
8. if nextP v.ipAddress = pv.ipAddress and nextP v.ref errer =
pv.uri then 9. session.elements.insert(nextP v.id) 10. session.lenght ++ 11. else 12. inSession = f alse 13. return session
Nel prototipo del Wos ideato da [2] l’unica euristica per la ricostruzione delle sessioni prevedeva una tecnica mista basata sia sul tempo massimo che deve passare tra due PageView, che, se presente, sul controllo del campo referrer. Si `e preferito separare i due metodi in quanto talvolta, anche se si ha a disposizione il campo referrer, si pu`o voler considerare tutte le pagine visitate da un utente in un certo periodo di tempo indipendentemente dal fatto che siano collegate da link, oppure no. Nel caso di dati provenienti
82 Euristiche di preprocessing
da un proxy server, per esempio, `e facile che dalla navigazione di un sito si passi a quella di un altro, digitando l’indirizzo nel browser e magari si pu`o essere interessati ad osservare l’insieme dei siti, non necessariamente collegati l’uno all’altro e visitati da uno stesso utente nell’ambito di un certo intervallo temporale.
Path completion heuristic
Questa `e la prima di due euristiche che non si limitano ad aggregare le PageView disponibili in un insieme di sessioni, ma cercano di aggiungere ad una sessione anche le pagine le cui richieste non si trovano nel log file, in quanto gi`a presenti nei vari livelli di cache che si trovano tra il client e il server.
Lo pseudocodice dell’algoritmo 3.4 permetter`a di comprendere meglio il procedimento seguito. Iterando nuovamente sul repository delle PageView ricostruite, se due PageView, relative allo stesso indirizzo Ip, sono “concate- nate” da un link, cio`e il referrer di una pagina `e uguale alla URI della pagina precedente, la PageView viene aggiunta alla sessione che contiene la prima pagina (passi 9-12). Se questo collegamento diretto non c’`e si passa ad ana- lizzare le URI di tutte le pagine presenti nella storia recente dell’utente, in particolare di quelle che sono state inserite nella sessione ai passi precedenti (passi 13-15). Se il referrer `e uguale ad una di esse, la PageView verr`a inserita nella stessa sessione (passi 16-18), altrimenti sar`a la prima PageView di una nuova.
Inoltre alla sessione vengono aggiunte anche le pagine di backtracking, cio`e se dalla pagina A si raggiunge la B e poi si trova la pagina C che ha come referrer la pagina A, la sessione conterr`a, in ordine, le pagina A, B, A, C.
Osserviamo come per verificare se sono presenti delle PageView di back- tracking da inserire all’interno della sessione `e utilizzata una struttura dati ausiliaria (pathV ector) che memorizza, in modo ordinato, tutte le PageView inserite fino a quel momento nella sessione. Si potrebbe svolgere lo stesso procedimento con l’effettivo accesso agli oggetti persistenti che memorizza- no tali PageView, ma questo comporterebbe un gran numero di accessi al database, che possono invece essere evitati.
3.3.2.2 Sessioni 83
Algorithm 3.4 Metodo nextSession() dell’euristica P ath completion Input: PageView repository pvRep
Output: Session session
1. session = new Session()
2. pv = pvRep.get()
3. session.elements.insert(pv.id)
4. pathV ector.insert(pv)
5. copia informazioni di pv in session
6. inSession = true
7. while inSession and pvRep.nextCompound() do
8. nextP v = pvRep.get()
9. if nextP v.ipAddress = pv.ipAddress and nextP v.ref errer = pv.uri then
10. session.elements.insert(nextP v.id)
11. pathV ector.insert(nextP v)
12. session.lenght ++
13. else if ∃ p ∈ pathV ector : p.uri = nextP v.ref errer then
14. for all p0 ∈ pathV ector : p ≺ p0 ≺ nextP v do
15. session.elements.insert(p0.id) 16. session.elements.insert(p.id) 17. session.elements.insert(nextP v.id) 18. pathV ector.insert(nextP v) 19. session.lenght ++ 20. else 21. inSession = f alse 22. return session
84 Euristiche di preprocessing
Link completion heuristic
Come il precedente, anche questo algoritmo, presentato nello pseudoco- dice 3.5, cerca di completare il percorso seguito da un utente durante la sua navigazione, a prescindere dalla presenza di una cache locale o di un pro- xy. A differenza del precedente metodo, non `e sfruttato il referrer, ma sono necessarie informazioni sulla topologia del sito web da analizzare.
Infatti per verificare se un utente, durante la navigazione, `e passato da una pagina ad un’altra seguendo un link `e necessario controllare se nella prima pagina esiste un link che porti alla seconda.
Per poter implementare questa euristica `e stato utilizzato un nuovo og- getto, che permette di memorizzare in modo permanente la topologia del sito web.
L’oggetto utilizzato `e stato chiamato LinkedUri e contiene i seguenti campi: uri: la stringa rappresentante la Url della pagina rappresentata;
inputLink Uri: un vettore contenente l’elenco degli identificativo tutti gli oggetti di tipo LinkedUri, che hanno un link verso l’oggetto considerato; In questo modo si pu`o facilmente osservare che se tra due pagine A e B esiste un link allora nel vettore dell’oggetto che astrae la pagina B, dobbiamo tro- vare un riferimento all’oggetto rappresentante la pagina A e questa ricerca viene fatta con solo due estrazioni dal repository in cui sono memorizzati gli oggetti di tipo LinkedUri.
Al fine di testare la correttezza dell’euristica `e stato implementato un metodo che permette di ricostruire la struttura topologica di un sito anche a partire da un log file in cui sia presente il campo referrer. Eseguendo il parser del file, per ogni entry si procede nel seguente modo: se non esiste ancora un oggetto con la URI della richiesta come chiave, ne viene creato uno e aggiunto al repository e la stessa cosa viene fatta con la Url memorizzata nel campo referrer. Successivamente si aggiunge al vettore dell’oggetto rappresentante la URI l’id dell’oggetto corrispondente al referrer. Notiamo che, in questo modo, si inseriscono nel repository anche oggetti relativi agli elementi accessori della pagina, ma come gi`a detto `e stato implementato a scopo di test, in quanto
3.3.2.2 Sessioni 85
Algorithm 3.5 Metodo nextSession() dell’euristica Link completion Input: PageView repository pvRep
SiteStructure repository siteRep Output: Session session
1. session = new Session()
2. pv = pvRep.get()
3. session.elements.insert(pv.id)
4. pathV ector.insert(pv)
5. copia informazioni di pv in session
6. inSession = true
7. while inSession and pvRep.nextCompound() do 8. nextP v = pvRep.get(nextP v.uri)
9. linkP v = seRep.get by uri()
10. if nextP v.ipAddress = pv.ipAddress then
11. if nextP v.ref errer ∈ linkP v.inputLink U ri then
12. session.elements.insert(nextP v.id)
13. pathV ector.insert(nextP v)
14. session.lenght ++
15. else if ∃ p ∈ pathV ector : p ∈ linkP v.inputLink U ri then
16. for all p0 ∈ pathV ector : p ≺ p0 ≺ nextP v do
17. session.elements.insert(p0.id) 18. session.elements.insert(p.id) 19. session.elements.insert(nextP v.id) 20. pathV ector.insert(nextP v) 21. session.lenght ++ 22. else 23. inSession = f alse 24. else 25. inSession = f alse 26. return session
86 Euristiche di preprocessing
se nel log file `e presente il campo referrer `e inutile utilizzare questa euristica, visto che `e possibile applicare quella precedentemente descritta che risulta senza dubbio pi`u efficiente in quanto non necessita dell’accesso ripetuto al database che memorizza la struttura del sito.