Newsgroup: it.lavoro.informatica
Titolo: [ot]come fa google...

...a compiere  una ricerca di 4 parole a caso su 3 miliardi di pagine web in 
0,8 secondi ?
Voi ci credete , che data base userŕ?
saluti e grazie delle informazioni 

> Voi ci credete , che data base userà?
Avevo letto di un cluster da 11 mila macchine
Linux. Ma forse era monnezza da pennivendoli :-)
Fra

 Voi ci credete , che data base userà?
Basta parallelizzare le ricerche.
Creare una rete di nodi distribuiti, ognuno con una porzione dell'indice
globale. Quando si lancia una ricerca, il capo nodo manda ai sotto nodi
le direttive e ognuno fa la ricerca sul suo sotto indice.
Fatta la ricerca sul sotto indice si ricompongono i risultati dei vari
nodi e quindi si manda all'utente il risultato ottenuto.
Potrebbero usare qualsiasi database per una base di dati cosi` semplice,
ma deve essere un database in grado di distribuirsi.
La base di dati di un motore di ricerca e` una delle piu` semplici
possibili, a meno che mi sfugga qualcosa in questo momento.
Ovviamente il tutto va opportunamente replicato e bilanciato.
-- 
Valentino Volonghi aka Dialtone
Now Running MacOSX 10.4
Blog: 
http://vvolonghi.blogspot.com
http://weever.berlios.de

 Linux. Ma forse era monnezza da pennivendoli :-)
Più vicino ai 100mila che ai 10mila. Sono per il resto computer
normali, non server. 
-- 
Per rispondermi, togli il nome del poeta

 
hahahahah mi hai fatto troppo ridere..

 Hai detto cotica.
Per caso l'OP ha chiesto: "spiegatemi per filo e per segno come fa
google"? No, ha semplicemente chiesto come fa a essere cosi` veloce che
lui fatica a crederci.
Guarda che tu stai equivocando... Io non ho scritto: google lo fai in 2
giorni senza impegno e a mezza giornata. Questo l'hai pensato tu.
Io ho scritto una sola volta semplice, riferendomi alla base di dati
pensando a una possibile soluzione. Quella di avere N database ognuno
con un suo indice indipendente in grado di fare ricerche fulltext sul
proprio contenuto.
Questo e` abbastanza elementare da realizzare con tsearch2 per
postgresql.
Tra il realizzare una cosa, e il realizzarla perche` sia il massimo
incredibile dell'efficenza ce ne passa e ognuna delle tue domande
retoriche puo` ricevere un milione di risposte differenti.
La cosa incredibilmente complessa in google pero` non e` tanto la
ricerca, ma i crawler assieme alla struttura di rete distribuita gia` a
livello di dns.
Conosci xapian? E` l'indexer che sta dietro a gmane. 5 o 6 computer che
indicizzano con xapian in una architettura distribuita posso tirarli in
piedi in 2 o 3 giorni, parto pero` con meta` lavoro pronto visto che
userei Twisted Matrix. Anzi, puoi guardare direttamente in Quotient a
http://www.divmod.org
.
Utilizza appunto questo approcio per indicizzare le mail di tutti gli
utenti e permettere la ricerca.
Il punto e` che google ha creato il suo indexer, il suo filesystem
distribuito, la sua architettura distribuita ecc ecc. Per fare tutte
queste cose serve ovviamente molto tempo, nel caso di google alla fine
ha pagato tantissimo e hanno fatto bene. Ma un motore di ricerca senza
troppe pretese (e senza crawler) lo puoi tirare su in pochi giorni di
lavoro. Poi aggiungi i crawler intelligenti e vedrai che impiegherai
decisamente tanto tanto tempo.


 
tanti computers
cache cache cache
l'algoritmo di ranking è basato sull'algoritmo di flusso (sources e 
sinks, quella roba lì) di oddio Floyd - Patterson (Vado a memoria , II 
anno di università, Ricerca Operativa) credo
--
Leo
"So, putting it simply, STL is the result of a bacterial infection." (A. 
Stepanov)


ah boh...qualcosa mi puzza di albero binario...
ce lo sapevo che quelle lezioni all'universita' mi sarebbero tornate utili
prima o poi :))
Linus

 dati (coi metodi tradizionali).
per l'appunto, per quello presumo usino un sistema adattivo complesso

 Ma io sono un sistemista, quindi nutro stima per questi mestieri!!
ehe :).
Posso concludere con un, allora siamo d'accordo su tutto. Potevo essere
un po` meno semplicista diciamo.


dividi et impera
Chiedo scusa se mi intrometto. Sto seguendo questo interessante thread
(e spero vivamente continuiate!). Un'unica richiesta: da amante della
lingua latina, mi si torcono le budella tutte le volte che lo vedo (e
credi, non sei solo tu, in realtà tu sei centinaia di persone); la
forma corretta è "divide et impera". Grazie.
--
Ciao!
Luca Menegotto

 forma corretta č "divide et impera". Grazie.
Odio il latino avendolo studiato :). Lo storpiero` fino alla morte :P.


 Voi ci credete , che data base userà?
ci credo si, se lo fa!
non so che db usa, però so che usa gli indici inversi, in poche parole
usa una struttura tipo:
parola1->(url1, url2, ..., urlN)
parola2->(url1, url2, ..., urlN)
...
parolaN->(url1, url2, ..., urlN)
se cerchi: parola1 parola4 parola7 parola9
fa semplicemente un'intersezione fra gli indici sopra
e ti restituisce il risultato
detto in parole poverissime però...
per maggiori info puoi leggere qualcosa qui:
http://tinyurl.com/7cs3z
più precisamente qui:
http://tinyurl.com/exmn9
-- 
Rosario

 Odio il latino avendolo studiato :).
Evidentemente, NON avendolo studiato :)
Peraltro anche a me ha suscitato qualche interesse solo da quando non mi č 
piů stato imposto.
F.B.
(non č mai troppo tardi) 

 più stato imposto.
Spero non ne susciti a me.


 Voi ci credete , che data base userà?
http://www.google.com/technology/pigeonrank.html
:)
-- 
http://narcisiss.bitchx.it
As far as we know, our computer has never had an undetected error.
                -- Weisert

Ciao,
ecco un articolo che spiega come funziona Google, anche se un po'
datato (molte cose sono cambiate nel frattempo, ma i principi generali
sono piu' o meno sempre quelli)
www-db.stanford.edu/pub/papers/google.pdf
Puoi trovare altri articoli piu' o meno collegati a Google qui:
http://labs.google.com/papers.html
Anche se questa pagina sembra non essere piu' aggiornata da circa un
paio d'anni...
Saluti,
Fabio

 Luca Menegotto
Finalemente una mante della bela linga ! :)


Finalemente una mante della bela linga ! :)
Ho capito, finalmente! Sei Ratko!! :))
--
Ciao!
Luca Menegotto