Google - istoric si evolutie Google - de la inceput pana acum

Google pe scurt
Scurt Istoric Google
Anatomia unui mega-motor de cautare hipertext pentru Web

• Introducere
• Motoare de cautare - Evolutie: 1994-2000
• Google: Evolutie concomitenta cu Web-ul
• Caracteristici ale configuratiei
• Capacitate imbunatatita de cautare
• O cercetare academica a motorului de cautare
• Trasaturile sistemului
• PageRank: Ordonarea Web-ului
• Descrierea unui calcul PageRank
• Explicarea intuitiva
• Textul link-ului
• Alte trasaturi
• Activitati similare
• Extragerea de informatii
• Diferente intre Web si colectiile bine controlate
• Configuratia sistemului
• Scurta descriere a arhitecturii Google
• Structuri majore de date
• BigFiles
• Biblioteca (Repository)
• Indexul documentelor
• Lexiconul
• Listele de hit-uri (Hit Lists)
• Indexul primar (Forward Index)
• Indexul complementar

Indexarea Web-ului

Cautarea

• Sistemul de clasificare
• Scurta recapitulare

Rezultate si mod de functionare

• Parametri pentru stocare
• Modul de functionare a sistemului
• Procesul de cautare

Concluzii

• Activitati viitoare
• Cautare la standarde inalte
• Arhitectura scalabila
• Un instrument de cercetare

Google pe scurt

Google este cel mai mare motor de cautare si datorita parteneriatelor sale cu Yahoo!, Netscape si altele este capabil sa raspunda la mult mai multe interogari decat orice alt serviciu online asemanator.
Interogari solutionate in fiecare zi: peste 150 de milioane Pagini web parcurse: peste 2,4 miliarde Tipuri de fisiere cautate:
HyperText Markup Language (html)q Adobe Portable Document Format (pdf)q Adobe PostScript (ps)q Lotus 1-2-3 (wk1, wk2, wk3, wk4, wk5, wki, wks, wku)q Lotus WordPro (lwp)q MacWrite (mw)q Microsoft Excel (xls)q Microsoft PowerPoint (ppt)q Microsoft Word (doc)q Microsoft Works (wks, wps, wdb)q Microsoft Write (wri)q Rich Text Format (rtf)q Text (ans, txt)q Imagini: peste 330 milioane Mesaje Usenet: peste 700 de milioane

Utilizatori
Google.com este unul din primele zece dintre cele mai populare site-uri de pe Internet si este folosit de oameni din lumea intreaga

Media lunara a numarului de utilizatori: 55.6 milioane (Nilesen/NetRatings 5/02)
Gradul de utilizare atat acasa, cat si la birou: #4 (Nilesen/NetRatings 5/02)
Limbile pentru care Google asigura o interfata: 81 Limbile in care Google ofera rezultate: 35 Utilizatori: Mai mult de jumatate din traficul Google.com provine din afara USA

Administratie
Personalul Google include profesionisti cu experienta in domeniul tehnologiei, iar compania este sustinuta de fonduri provenite de la doua firme ce se ocupa cu investitiile de risc.
Numar aproximativ de angajati: 400 Detinatori ai titlului de doctor: peste 50

SCURT ISTORIC GOOGLE

1995
Martie-Decembrie 1995
Sergey Brin si Larry Page se intalnesc la o adunare a doctorilor in informatica de la Universitatea Stanford. Aproape de sfarsitul anului, colaboreaza in vederea dezvoltarii de tehnologii care vor deveni temelia motorului de cautare Google. Se spune ca fondatorii companiei Sergey Brin si Larry Page nu se intelegeau chiar foarte bine atunci cand s-au intalnit pentru prima oara. Totusi, opiniile puternice, dar si parerile contradictorii vor gasi in cele din urma un punct comun in incercarea de a solutiona una dintre cele mai mari provocari legate de domeniul computerelor: extragerea unor informatii relevante dintr-o serie masiva de date.

1996-1997
Ianuarie 1996-Decembrie1997
Sergey si Larry au inceput colaborarea la BackRub (precursorul motorului de cautare Google), numit astfel datorita capacitatii sale unice de a analiza back links - link-urile care fac referinta la un anumit site. Larry si-a asumat sarcina de a construi un nou tip de configurawie de server-e, utilizand PC-uri nepretentioase in locul unor sisteme scumpe.
Un an mai tarziu, perspectiva lor unica asupra analizei link-urilor a determinat o crestere a reputatiei motorului BackRub printre cei care mai vazusera aceasta tehnologie.

1998
Ianuarie-Iulie 1998
Larry si Sergey continua sa perfectioneze tehnologia de cautare Google. Urmand aceesi conceptie care va deveni o parte esentiala a metodei Google, ei ofera un terabyte de spatii de stocare la preturi accesibile si isi construiesc propriul centru de gazduire a calculatoarelor in dormitorul lui Larry de la Stanford, care devine si centrul de date Google, in timp ce camera lui Sergey devine birou. Si-au deschis propria companie incurajati de unul dintre fondatorii Yahoo! si coleg de universitate, David Filo. Filo a aprobat eficienta tehnologiei, dar i-a incurajat pe Larry si Sergey sa isi dezvolte singuri afacerea prin intemeierea unei companii de motoare de cautare.

August-Decembrie 1998
Neputand atrage atentia portalurilor importante, Sergey si Larry concep un plan de afaceri si, avand doar un bagaj de cunostinte, strang 1 milion de dolari de la familie, prieteni si investitori pentru a forma Google. Ca fondator al Sun Microsystems, Andy Bechtolsheim a fost solicitat sa isi spuna parerea. Cand a vazut varianta demo a lui Google, a intuit potentialul acestuia din primul moment.
Pe 7 septembrie 1998, Google Inc. este inregistrat, isi muta sediul in primul sa birou aflat in garajul unui prieten din California si are 4 angajati. Google raspunde la 10,000 de intrebari pe zi. PC Magazine include Google, care este inca in beta, in Topul 100 al site-urilor web si motoarelor de cautare din 1998.

1999
Februarie-Iunie 1999
Google isi muta sediul pe University Avenue din Palo Alto, California, are 8 angajati si raspunde la 500,000 de intrebari. Red Hat devine primul client comercial al Google. Google primeste 25 de milioane de dolari in mod egal de la Sequoia Capital si Kleiner Perkins Caufield & Byers. Michael Moritz de la Sequoia si John Doerr de la Kleiner Perkins si investitorul Ram Shriram se alatura consiliului director al Google. AOL/Netscape adauga tehnologia de cautare Google in portalul sau, Netcenter.

August-Decembrie 1999
Google se muta in Mountain View, California si isi lanseaza in mod oficial site-ul. Compania efectueaza 3 milioane de cautari pe zi si are 39 de angajati. Virgilio, portalul online leader in Italia, alege Google sa ofere servicii WebSearchTM. Google castiga o serie de premii in mai putin de 4 luni, printre care: Technical Excellence Award oferit de PC Magazine pentru inovatii in dezvoltarea aplicatiilor web, Top 100 pentru cele mai bune site-uri pe 1999 oferit de Shift si P.O.V. si Top Ten Best Cybertech pe 1999 oferit de TIME.

2000
Ianuarie-Aprilie 2000
Google prezinta prima tehnologie completa de cautare pentru telefoane WAP si accesorii si lanseaza o intreaga gama de servicii automate si personalizate Google WebSearch. Google inglobeaza si Open Directory Project de la Netscape, care diversifica si largeste rezultatele cautarii Google cu liste de directoare selectate manual. Revista Yahoo! InternetLife numeste Google cel mai bun motor de cautare, iar revista Smart Computing intorduce Google in top 50 Hot Technologies.

Mai-Iunie 2000
Google initiaza metode de cautare in alte 10 limbi in afara de engleza si castiga prestigiosul premiu Webby pentru cea mai buna realizare tehnica a anului 2000 si premiul People's Voice la categoria realizare tehnica a anului 2000. Discursul celor doi, Sergey si Larry, a avut doar cinci cuvinte: "We love you, Google users!".
In luna urmatoare, Google devine cel mai mare motor de cautare de pe web, avand un index nou continand 1 bilion de URL-uri. Yahoo! selecteaza Google ca suport informational standard pentru completarea directorului web si ghidului de navigare Yahoo!. Google ofera raspuns la 18 milioane de intrebari pe zi.
Pe 26 iunie, Google si Yahoo! anunta un parteneriat care asigura reputatia companiei nu doar ca agent ce asigura tehnologie, dar si ca o afacere substantiala ce se ocupa cu asigurarea raspunsurilor la peste 18 milioane de intrebari pe zi.

August-Octombrie 2000
Google semneaza acorduri cu portalurile si site-urile cele mai cunoscute din Statele Unite, Europa si Asia, lanseaza programe publicitare pentru suplimentarea serviciilor de cautare aflate intr-o ascensiune continua, si adauga o serie de trasaturi avansate in procesul de cautare care include Google Number SearchTM (GNS), care face introducerea de date de tip wireless mai usoara si mai rapida pe telefoanele WAP. Forbes include Google in clasamentul Best of the Web, PC World numeste Google cel mai bun motor de cautare si Google primeste premiul WIRED pentru cel mai inteligent agent de pe Internet.
Portalul important al Chinei NetEase si portalul NEC's BIGLOBE din Japonia au adaugat Google la site-urile lor
Noiembrie-Decembrie 2000
Google raspunde la mai mult de 60 de milioane de cautari pe zi. Indexul Google cuprinde mai mult de 1.3 bilioane de pagini web. Google lanseaza bara de unelte Google (Google ToolbarTM ), un browser care poate fi descarcat si care mareste abilitatea utilizatorilor de a cauta informatii pe orice pagina de pe intregul web. PC Magazine din Anglia recompenseaza Google cu premiul pentru cea mai buna inovatie de pe Internet.

2001
Ianuarie-Februarie 2001
Google raspunde la mai mult de 100 de milioane de cautari pe zi. Google achizitioneaza arhiva Usenet de la Deja.com care dateaza din 1995. Google lanseaza noi tehnologii wireless de cautare special destinate pentru I-mode pentru telefoanele mobile din Japonia. Portalul european multi-acces, Vizzavi, alege Google pentru motorul sau de cautare. Google lanseaza Google PhoneBook, care ofera numere de telefon si adrese valabile.

Martie-Aprilie 2001
Dr. Eric Schmidt, presedinte si CEO (Chief Executive Officer) al Novell, fost CTO al Sun Microsystems, se alatura Google ca presedinte al consiliului director. Google intareste serviciile de cautare la Yahoo! Japonia, Fujitsu NIFTY si NEC BIGLOBE, cele mai bune portaluri din Japonia, si, de asemenea, site-urile corporatiilor Procter&Gamble, IDG.net (care contine 300 de site-uri), Vodaphone si MarthaStewart.com. Google anunta ca a gasit ceea ce multe alte companii online au pierdut din vedere: profitul.

Mai-Iunie 2001
Handspring integreaza tehnologia de cautare Google in propriul browser web, Blazer, disponibil pentru orice computer bazat pe Palm. Google controleaza 130 de portaluri si site-uri din 30 de tari. Google adauga Yahoo!, Procter&Gamble, IDG.net (care continea 300 de site-uri), Vodaphone si MarthaStewart.com, Spring si Handspring listei sale, aflate in continua crestere, de clienti ai serviciilor sale de cautare.
Programele promotionale Google atrag mai mult de 350 de sponsori si mii de agenti publicitari AdWords, si ofera rate de accesare de la 4 pana la 5 ori mai mult decat pentru accesarea bannerelor obisnuite.
Google ofera domenii in UK, Germania, Franta, Italia, Elvetia, Canada, Japonia si Coreea. Utilizatorii pot selecta interfata Google in aproape 40 de limbi in afara de engleza. Optiunea Google de traducere automata traduce pagini gasite ca rezultat al procedeului de cautare in limba preferata a utilizatorului.

Iulie-August 2001
Dr. Eric E. Schmidt este numit noul CEO al Google, in timp ce co-fondatorii sai, Larry Page si Sergey Brin, devin presedinti. Google castiga alt premiu Webby, de aceasta data la categoria Best Practices. Google ofera posibilitatea de cautare si pentru utilizatorii Cingular Wireless si pentru mai mult de 300 de website-uri ale corporatiilor Sony. Noul index Google Image Search, cu 250 de milioane de imagini si cautare de informatii, devine disponibil prin pagina avansata de cautare Google. Sistemele de cautare, tendintele si noutatile sunt publicate pe Google Zeitgeist. Partenerii Google de la Logitech care ofereau iTouchTM ofereau utilizatorilor de tastatura si mouse-uri acces instantaneu pe motorul de cautare Google.

Octombrie 2001
Google semneaza un parteneriat cu Universo Online (cel mai mare ISP din America Latina, avand 80% din utilizatorii Internet din Brazilia).

Decembrie 2001
Indexul Google depaseste granita de 3 milioane de pagini; Google Groups (arhiva de newsgroup-uri) iese din stadiul beta.

Februarie 2002
EarthLink, unul dintre leaderii ISP din Statele Unite, adopta Google ca motor de cautare preferat pe site-ul www.earthlink.com.

Mai 2002
America On Line si Google semneaza un contract pe mai multi ani, prin care Google este folosit ca motor de cautare pentru site-urile AOL, CompuServe, AOL.COM si Netscape. De asemenea, Google va afisa link-uri platite de clientii sai, pe aceste site-uri (Google Sponsored links). Dupa terminarea programului de afisari, Google va ramane singurul furnizor de link-uri sponsorizate pe site-urile din proprietatea AOL.
Conform BtoB - cea mai importanta publicatie de marketing din SUA -, Google intra in top 10 al firmelor de reclama.

Iunie 2002
Google anunta ca firme ca The Boeing Company, Cisco Systems, PBS.org, National Semiconductor Corp., Sur La Table, Universitatea din Florida si altele au ales produsul Google Search Appliance pentru facilitatile de cautare de produse si informatii pe intranet-urile de corporatie si pe site-urile lor Web.

Iulie 2002
Cautarile Google devin disponibile pentru milioanele de clienti AT&T Worldnet ® Service. De asemenea, clientii AT&T vor avea acces si la reclamele AdWords SelectT.
AskJeeves si Google semneaza un contract pe trei ani, prin care AskJeeves va afisa Google Sponsored Links. Se estimeaza ca veniturile din afisarile link-urilor sponsorizate vor depasi 100 milioane de dolari.

Va prezentam in continuare un text realizat de creatorii Google, Sergey Brin si Larry Page, in perioada studentiei lor. La momentul redactarii, motorul Google, inca in varianta experimentala, indexa aproximativ 24 de milioane de pagini; pentru comparatie, la momentul actual, Google indexeaza peste 2 miliarde de pagini. Consideram utila prezentarea acestei lucrari, deoarece prezinta filosofia care sta la baza motorului si rationamentele care au facut din Google una dintre cele mai ingenioase si de succes constructii ale mintii umane pe Internet.


Anatomia unui mega-motor de cautare hipertext pentru Web

Aceasta lucrare prezinta Google, prototipul unui mega-motor de cautare care utilizeaza in mod extensiv structura existenta in hipertext. Google este conceput sa parcurga si sa indexeze in mod eficient web-ul, dar si sa ofere rezultate mult mai satisfacatoare decat celelalte sisteme. Prototipul continand textul integral si evidenta hyperlink-urilor a peste 24 milioane de pagini este disponibila la https://google.stanford.edu/.
Proiectarea unui motor de cautare este o provocare. Motoarele de cautare indexeaza zeci sau chiar sute de milioane de pagini web, implicand un numar echivalent de termeni distincti. Acestea raspund la zeci de milioane de intrebari in fiecare zi. Desi importanta acestor motoare de cautare pe web este mare, totusi ele nu au constituit subiectul unei cercetari academice amanuntite. In plus, datorita gradului rapid de avansare a tehnologiei si dezvoltarii continue a web-ului, metoda de creare a unui motor de cautare este foarte diferita de cea folosita acum trei ani. Aceasta lucrare ofera o descriere amanuntita a motorului nostru de cautare, prima de acest gen din cate stim noi.
In afara problemelor de masurare a capacitatii motoarelor traditionale de cautare pana la a putea suporta o cantitate importanta de date, exista noi provocari tehnice corelate cu utilizarea informatiilor aditionale prezente in hipertext, cu scopul producerii de rezultate mai bune. Lucrarea de fata pune aceasta intrebare, cum sa construiesti un sistem practic de masurare care poate folosi informatia aditionala din hipertext. De asemenea, luam in considerare modul de tratare efectiv al colectiilor de hipertext, care nu pot fi in intregime controlate si unde fiecare este liber sa publice ceea ce doreste.

Referat: Mediul de marketing Proiect: Masurarea si scalarea fenomenelor de piata - tipuri de scale

1. Introducere

Web-ul creeaza noi provocari pentru obtinerea de informatii. Cantitatea de informatii de pe web creste intr-un ritm alert, pe masura numarului de noi utilizatori lipsiti de experienta in arta cautarii pe web. De obicei, oamenii navigheaza pe web folosind graficul acestuia de link-uri, adeseori incepand cu indici superiori calitativ, mentinuti de interventia umana, cum ar fi Yahoo! sau cu motoare de cautare. Listele unde intervine mintea umana acopera subiecte diverse si populare, dar sunt subiective, costisitoare de intretinut si mentinut, greu de imbunatatit si nu pot acoperi toate subiectele ce tin de domenii specializate (ezoterice-). Motoarele de cautare automate, care se bazeaza pe potrivirea de cuvinte-cheie, ofera, in mod obisnuit, prea multe rezultate neconcludente. Pentru a inrautati situatia, unii agenti publicitari incearca sa castige atentia prin diferite metode destinate sa induca in eroare motoarele automate de cautare. Noi am construit un motor de cautare pe scara larga care are raspuns pentru multe din problemele sistemului existent. Acesta utilizeaza, in special, structura aditionala din hipertext pentru a oferi rezultate concludente. Am numit acest sistem Google deoarece este un cuvant asemanator cu googol sau 10100 si corespunde cel mai bine intentiei noastre de a construi motoare de cautare pe scara larga.

1.1 Motoare de cautare - Evolutie: 1994-2000

Tehnologia motoarelor de cautare a fost obligata sa se reinventeze in mod constant pentru a putea tine pasul cu expansiunea web-ului. In 1994, unul dintre primele motoare de cautare, World Wide Web Worm (WWWW) [McBryan 94], avea un index de 110,000 pagini web si documente accesibile pe web. In noiembrie 1997, motoarele de cautare cele mai performante realizau indexarea de la 2 milioane (WebCrawler) pana la 100 de milioane de documente web (din Search Engine Watch). Este previzibil ca, pana in anul 2000, un index complet al Web-ului sa contina peste un bilion de documente. In acelasi timp, numarul interogarilor la care pot face fata motoarele de cautare a crescut intr-un ritm incredibil de rapid. In martie si aprilie 1994, World Wide Web Worm primea in jur de 1500 de intrebari pe zi. In noiembrie 1997, Altavista pretindea ca rezolva aproximativ 20 de milioane de interogari pe zi. Odata cu cresterea numarului de utilizatori ai web-ului si sistemelor automate care puneau intrebari motoarelor de cautare, este posibil ca motoarele performante de cautare sa poata raspunde la sute de milioane de intrebari pe zi pana in anul 2000. Scopul sistemului nostru este sa rezolve multe dintre aceste probleme, atat din punct de vedere al calitatii, cat si al scalabilitatii, coordonate introduse de tehnologia motoarelor de cautare care au atins cifre extraordinare.

1.2 Google: Evolutie concomitenta cu Web-ul

Crearea unui motor de cautare care sa tina pasul cu web-ul zilelor noastre este subordonata multor provocari. Tehnologia rapida de parcurgere este necesara pentru a tine o evidenta a documentelor web si pentru al le actualiza in permanenta. Spatiul de stocare trebuie folosit in mod eficient pentru organizarea indicilor si, optional, chiar a documentelor. Sistemul de indexare trebuie sa proceseze cat mai bine sute de gigabiti de date. Intrebarile trebuie sa aiba un raspuns intr-un interval cat mai scurt, la o rata de sute pana la mii pe secunda.
Aceste sarcini devin din ce in ce mai dificile pe masura ce Web-ul se dezvolta. Totusi, performantele hardware si costurile au crescut si ele in mod constant pentru a rezolva partial aceasta problema. Exista, bineinteles, cateva exceptii importante de la acest progres cum ar fi timpul de cautare pe disc si performantele sistemului de operare. In proiectarea sistemului Google, am luat in considerare atat rata de evolutie a Web-ului, cat si schimbarile tehnologice. Google este construit in asa fel incat sa parcurga eficient mari cantitati de date. In acelasi timp, Google utilizeaza eficient spatiul de stocare pentru organizarea indexului. Structurile sale informationale sunt optimizate pentru accesul rapid si concludent (vezi sectiunea 4.2). Speram ca pretul indexarii si stocarii de text sau HTML sa devina in cele din urma mai mic in raport cu cantitatea de date ce va fi disponibila (vezi Anexa B). Acest lucru va genera caracteristici mai performante de organizare pentru sistemele centralizate ca Google.

1.3 Caracteristici ale configuratiei

1.3.1 Capacitate imbunatatita de cautare

Scopul principal a fost acela de a imbunatati calitatea motoarelor de cautare. In 1994, existau pareri ca un index complet de cautare va face posibila gasirea rapida a oricarui raspuns. In opinia Best of the Web 1994 - Navigators, "Cel mai bun sistem de navigare ar trebui sa faciliteze gasirea unui raspuns la aproape orice intrebare pe Web (din momentul introducerii datelor)". Totusi, Web-ul anului 1997 este diferit. Oricine a utilizat recent un motor de cautare, poate oricand sa spuna ca nu complexitatea indexului este singurul factor care asigura calitatea rezultatelor cautarii. Rezultatele neconcludente (junk results) estompeaza de obicei relevanta rezultatelor de care un utilizator este intr-adevar interesat. De fapt, din noiembrie 1997, numai unul dintre cele 4 motoare de cautare comerciale isi mentioneaza numele (returneaza pagina proprie de cautare ca raspuns la numele sau in topul primelor 10 rezultate). Una dintre principalele cauze ale acestei probleme este aceea ca numarul documentelor din indici a crescut progresiv acoperind diferitele grade de importanta, in timp ce modul de percepere al utilizatorului asupra acestor documente nu s-a schimbat. Oamenii manifesta in continuare interes doar pentru primele 10 rezultate. Din acest motiv, pe masura ce colectia de date se mareste, avem nevoie de instrumente cu un grad ridicat de precizie (adica numar de documente relevante returnate, sa zicem in topul primelor 10 rezultate). Intr-adevar, vrem ca notiunea de "relevant" sa includa caracteristica de cel mai important ignorand chiar cautarea in sine (numarul total de documente relevante pe care sistemul este capabil sa le ofere. Exista chiar un sentiment de optimism care se refera la utilizarea mai multor informatii hipertextuale ce pot contribui la imbunatatirea cautarii si la alte aplicatii [Marchiori 97] [Spertus 97] [Weiss 97] [Kleinberg 98]. In particular, structura si textul link-ului ofera multe informatii pentru efectuarea de analize relevante si filtrari de calitate. Google foloseste atat structura link-ului cat si textul acestuia (vezi sectiunile 2.1 si 2.2).

1.3.2. O cercetare academica a motorului de cautare

In afara de o crestere considerabila, Web-ul a adoptat si o caracteristica comerciala de-a lungul timpului. In 1993, 1,5% din serverele web erau pe domenii .com. Numarul acestora a atins 60 de procente in 1997. In acelasi timp, motoarele de cautare au parasit academicul in favoarea comercialului. Pana in prezent dezvoltarea majoritatii motoarelor de cautare a fost efectuata de companii care aveau prea putin de-a face cu detaliile tehnice. Acest fenomen a determinat ramanerea in umbra a tehnologiei motoarelor de cautare si orientarea acestora catre comercial (vezi Anexa A). Cu Google, scopul nostru este acela de a orienta dezvoltarea si perceperea acestora catre sfera academicului.
O alta trasatura importanta a acestei configuratii era construirea de sisteme pe care multi oameni sa le poate utiliza. Modul de utilizare era important pentru noi deoarece suntem de parere ca unele dintre cele mai interesante cercetari implica manipularea unei vaste cantitati de informatii care sunt disponibile pe sistemele web moderne. De exemplu, zilnic sunt initiate zeci de milioane de cautari. Totusi, toate aceste date sunt foarte dificil de obtinut, in special pentru ca se considera ca au valoare comerciala.
Scopul final al acestei configuratii era sa realizam o arhitectura care sa poata sustine activitati inedite de cautare pe scara larga a informatiei pe web. Pentru a sprijini aceste activitati de cautare, Google stocheaza toate documentele in format comprimat pe care le parcurge. Unul dintre scopurile principale ale configuratiei Google a fost acela de a stabili un mediu unde ceilalti cautatori puteau intra repede, procesa sectiuni considerabile ale web-ului si oferi rezultate interesante care ar fi fost greu de oferit prin adoptarea unei alte metode. In intervalul scurt de timp in care sistemul a fost construit, existau deja cateva lucrari care foloseau bazele de date oferite de Google si multe altele sunt realizate acum. O alta intentie a noastra este aceea de a constitui un mediu asemanator cu un laborator spatial unde cercetatorii sau chiar studentii sa poata propune si chiar executa experimente interesante folosind informatiile complexe ale web-ului.

2. Trasaturile sistemului

Motorul de cautare Google este caracterizat de doua trasaturi importante care ajuta la producerea de rezultate cu un grad ridicat de precizie. In primul rand, Google se foloseste de structura de link-uri a Web-ului pentru a calcula un indice calitativ al fiecarei pagini web. Aceasta estimare a nivelului calitativ se numeste PageRank In al doilea rand, Google utilizeaza link-urile pentru a imbunatati rezultatele cautarii.

2.1 PageRank: Ordonarea Web-ului

Graficul de link-uri al web-ului este o resursa importanta care a ramas in mare parte neutilizata de motoarele de cautare. Am realizat harti continand nu mai putin de 518 milioane din aceste hyperlink-uri, o mostra semnificativa a totalului. Aceste harti permit calcularea rapida a PageRank-ului unei pagini web, o masura obiectiva a importantei link-urilor care corespunde cu ideea subiectiva de importanta a oamenilor. Datorita acestei corespondente, PageRank reprezinta o metoda excelenta de stabilire a gradului de importanta a rezultatelor cautarilor bazate pe cuvinte cheie. Pentru cele mai populare subiecte, un text simplu care se potriveste cu cautarea si care este limitat la titluri ale paginii web este foarte bine reprezentat atunci cand PageRank stabileste importanta rezultatelor (demonstratie disponibila la google.stanford.edu). Pentru cautarile ce au la baza un text integral in sistemul principal Google, PageRank este, de asemenea, de mare ajutor.

2.1.1 Descrierea unui calcul PageRank

Literatura de specialitate referitoare la link-uri a fost raportata la web, in general prin numerotarea link-urilor sau backlink-urilor unei pagini date. Acest lucru stabileste cu aproximatie importanta sau calitatea unei pagini. PageRank extinde aceasta idee nu prin efectuarea unei numerotari a link-urilor din toate paginile, ci prin stabilirea numarului de link-uri dintr-o pagina. PageRank este definit dupa cum urmeaza:
Presupunem ca pagina A este formata din paginile T1 . Tn care se refera la aceasta (adica sunt link-uri). Parametrul d este un factor de nivelare care se afla intre 0 si 1. De obicei, stabilim valoarea 0.85 pentru acest factor. Mai multe detalii despre d sunt oferite in sectiunea urmatoare. De asemenea, C(A) este definit ca un numar de link-uri care nu fac parte din pagina A. PageRank-ul paginii A este dupa cum urmeaza:
PR(A) = (1-d) +d(PR(T1)/C(T1)+ . +PR(Tn)/C(Tn))
Trebuie retinut ca PageRank formeaza o distributie a probabilitatii paginilor web, astfel ca suma tuturor paginilor web ce tin de PageRank este 1.
PageRank sau PR(A) poate fi calculat utilizand un simplu algoritm repetabil si care corespunde principalului vector propriu al matricii link-ului normalizat al web-ului. De asemenea, un PageRank pentru 26 milioane de pagini web poate fi calculat in cateva ore intr-un punct de lucru de marime medie. Exista multe alte detalii care depasesc intentia acestei lucrari.

2.1.2 Explicarea intuitiva

PageRank poate fi considerat un model al comportamentului utilizatorului. Sa presupunem ca exista un navigator oarecare care viziteaza o pagina web aleasa la intamplare si care acceseaza link-urile, fara a reveni la pagina initiala: in cele din urma se va plictisi si se va orienta spre alta pagina web aleasa la intamplare. Probabilitatea ca acest navigator sa viziteze o pagina este reprezentata de PageRank. Iar d, factorul de nivelare, reprezinta probabilitatea ca navigatorul sa se plictiseasca la fiecare pagina accesata si sa continue cautarea paginilor la intamplare. O variatie importanta este aceea de a adauga doar factorul de nivelare d unei singure pagini sau unui grup de pagini. Acest lucru permite personalizarea si poate face aproape imposibila inducerea deliberata in eroare a sistemului pentru obtinerea unui calificativ superior. Pentru mai multe referiri la PageRank, vezi [Page 98]
O alta explicatie intuitiva este ca o pagina poate avea un PageRank ridicat daca exista mai multe pagini care fac referire la aceasta sau daca exista cateva pagini care au un PageRank ridicat si care o recomanda. In mod intuitiv, paginile la care se face referire din multe colturi ale web-ului sunt considerate importante. De asemenea, paginile care probabil au o singura referire de la gazda a Yahoo! sunt considerate importante. Daca o pagina nu are un nivel calitativ ridicat sau are un link insuficient, este mai mult decat probabil ca pagina gazda a Yahoo! nu va avea nici un link pentru aceasta. PageRank face fata ambelor situatii si chiar mai mult de atat prin propagarea recursiva a gradului de importanta in intreaga structura de link-uri a web-ului.

2.2 Textul link-ului

Textul link-ului este tratat intr-un mod cu totul special de motorul nostru de cautare. Majoritatea motoarelor de cautare asociaza textul link-ului cu pagina de care se leaga. In plus, noi il asociem cu pagina pe care link-ul respectiv o indica. Acest sistem prezinta mai multe avantaje. In primul rand, link-urile ofera deseori descrieri mai precise ale paginilor web decat o fac paginile respective. In al doilea rand, link-urile pot face referire la documente care nu pot fi indexate de un motor de cautare bazat pe text, cum ar fi: imagini, programe sau baze de date. Acest lucru face posibila returnarea paginilor web care nici macar nu au fost parcurse. Trebuie retinut ca paginile care nu au fost parcurse pot cauza probleme din moment ce nu le-a fost niciodata verificata validitatea inainte de a fi oferite utilizatorului. In acest caz, motorul de cautare poate oferi o pagina care nu a existat niciodata cu adevarat, dar care are hyperlink-uri care fac referire la ea. Totusi, este posibil ca rezultatele sa fie sortate, astfel ca aceasta problema apare rareori.
Ideea corelarii textului link-ului cu pagina web la care se refera a fost implementata in World Wide Web Worm [McBryan 94], in special pentru ca ajuta la cautarea informatiei de tip non-text si mareste aria de acoperire a cautarii prin numarul mai redus de documente descarcate. Folosim propagarea de link-uri deoarece textul link-ului poate contribui la oferirea de rezultate mai bune. Utilizarea eficienta a text-ului link-ului este dificila din punct de vedere tehnic din cauza cantitatilor mari de date care trebuie procesate. In procesul de parcurgere a 24 milioane de pagini, am indexat peste 259 de milioane de link-uri.

2.3 Alte trasaturi

In afara de PageRank si de utilizarea textului link-ului, Google are si alte trasaturi. Prima este aceea ca are informatii de baza pentru toate cautarile si astfel utilizeaza, in mod frecvent, proximitatea in procesul de cautare. A doua se refera la faptul ca Google are in vedere detaliile vizuale ale prezentarii cum ar fi marimea fonturilor. Cuvintele scrise cu un font mai mare sau cu caractere ingrosate sunt percepute altfel decat celelalte cuvinte. A treia trasatura este aceea ca se tine o evidenta a intregului sir al paginilor HTML.

3. Activitati similare

Cercetarea navigarii pe web are o istorie scurta si concisa. World Wide Web Worm (WWWW) [McBryan 94] a fost unul dintre primele motoare de cautare. Acesta a fost ulterior urmat de alte cateva motoare de cautare academice, dintre care multe sunt acum companii publice. Comparativ cu dezvoltarea Web-ului si importanta motoarelor de cautare, exista putine documente valoroase refe-ritoare la motoarele de cautare recente [Pinkerton 94]. Conform lui Michael Mauldin (cercetator la Lycos Inc) "serviciile variate (inclusiv Lycos) urma-resc indeaproape detaliile acestor baze de date". Totusi, exista studii despre trasaturile specifice ale motoarelor de cautare. Un studiu bine realizat este acela care duce la obtinerea de rezultate prin procesarea ulterioara a rezultatelor motoarelor de cautare comerciale sau la producerea, la scara redusa, de motoare de cautare individualizate. Cercetari amanuntite au fost facute pe sistemele care se ocupa cu extragerea de informatii, in special pe colectiile bine controlate. In urmatoarele doua sectiuni, discutam despre zone unde aceasta cerce-tare trebuie extinsa pentru a se putea lucra mult mai bine pe web.

3.1 Extragerea de informatii

Cercetarea sistemelor care se ocupa cu extra-gerea de informatii a fost initiata acum multi ani si este acum bine dezvoltata [Witten 94]. Totusi, majoritatea cercetarilor asupra acestor sisteme se concentreaza pe colectiile omogene si bine intre-tinute cum ar fi: colectiile de lucrari stiintifice sau articole despre un subiect apropiat. Intr-adevar, prototipul extragerii de informatii, The Text Retrie-val Conference [Trec 96] foloseste pentru teste colectii mici dar bine controlate. Testul "Very Large Corpus" are doar 20 GB in comparatie cu 147 GB ai 24 de milioane de pagini web pe care l-am parcurs noi. Tot ce functioneaza bine pe TREC nu ofera de obicei rezultate satisfacatoare pe web. De exemplu, modelul de vector spatial standard incearca sa returneze documentele care se apropie cel mai mult de interogare, tinand seama de faptul ca atat interogarea cat si documentul sunt vectori definiti de ocurenta cuvintelor lor. Pe web, aceasta strategie ofera de obicei documente scurte care contin interogarea si cateva cuvinte in plus. De exemplu, am observat ca un motor important de cautare returneaza o pagina continand doar "Bill Clinton Sucks" si o fotografie dintr-o interogare referitoare la Bill Clinton. Unii sunt de parere ca, pe web, utilizatorii ar trebui sa specifice cu mai multa acuratete ceea ce doresc sa afle si sa adauge mai multe cuvinte intrebarii respective. Noi nu suntem de acord cu aceasta conceptie. Daca un utilizator formuleaza o interogare de tipul "Bill Clinton" ar trebui sa primeasca rezultate conclu-dente din moment ce exista o cantitate consi-derabila de informatii valoroase disponibile pentru acest subiect. Prin aceste exemple credem ca procesul standard de extragere de informatii trebuie extins pentru a putea utiliza web-ul in mod eficient.

3.2 Diferente intre Web si colectiile bine controlate

Web-ul reprezinta o colectie vasta de docu-mente eterogene. Documentele de pe web sunt caracterizate printr-o variatie interna constanta a documentelor si de asemenea prin meta informatie externa care poate sa fie disponibila. De exemplu, documentele difera din punct de vedere intern prin limbaj (atat uman, cat si de programare), vocabular (adrese de e-mail, link-uri, coduri zip, numere de telefon, numere de productie), tip de format (text, HTML, PDF, imagini, sunete) si pot fi generate chiar de sistem (fisiere jurnal sau extrase din baza de date). Pe de alta parte, definim meta informatia externa ca informatia care poate fi dedusa despre un document, dar care nu este continuta de acesta. Exemple de meta informatie externa includ aspecte precum reputatia sursei, frecventa actualizarii, calitatea, popularitatea sau uzajul si link-urile. Nu numai ca sursele posibile ale meta informatiei externe sunt variate, dar lucrurile care sunt masu-rate variaza de asemenea din punct de vedere al gradelor de importanta. De exemplu, sa comparam informatia uzuala de pe o pagina gazda impor-tanta ca Yahoo!, care primeste zilnic milioane de accesari de pagini cu un articol istoric obscur care poate fi accesat o data la zece ani. In mod evident, aceste doua aspecte trebuie tratate in mod diferit de un motor de cautare.
O alta diferenta majora intre web si colectiile traditionale este aceea ca, practic, nu exista nici un control asupra a ceea ce pot publica oamenii pe web. Coreland aceasta flexibilitate de a putea publica orice cu influenta considerabila a motoa-relor de cautare care pot afecta traficul (si exista diverse companii care manipuleaza deliberat motoa-rele de cautare pentru a obtine profit), ajungem la o problema serioasa. Aceasta problema nu a fost pusa in cazul sistemelor traditionale de extragere de informatii. De asemenea, este interesant de observat ca eforturile depuse in cazul metadatelor au esuat in cazul motoarelor de cautare, deoarece orice text de pe pagina care nu este direct oferit utilizatorului este supus manipularii efectuate de motoarele de cautare. Exista chiar numeroase companii care s-au specializat in manipularea motoa-relor de cautare in vederea obtinerii de profit.

4. Configuratia sistemului

Mai intai vom directiona discutia catre un nivel superior si vom vorbi despre arhitectura. Apoi, vom avea in vedere cateva descrieri detaliate ale struc-turilor importante de date. In cele din urma, ne vom ocupa de aplicatiile majore: parcurgere, indexare si cautare vor fi analizate in amanunt.

4.1 Scurta descriere a arhitecturii Google

In aceasta sectiune vom oferi o descriere despre modul de functionare al sistemului dupa cum indica si Figura 1. In sectiunile urmatoare vom discuta despre aplicatiile si structurile de date care nu vor fi mentionate in aceasta sectiune. Cea mai mare parte din Google este realizata in C sau C++ pentru eficienta si poate rula atat in Solaris, cat si in Linux.
In Google parcurgerea web-ului (descarcarea de pagini) este facuta de mai multe crawlere diferite. Exista un server URL care trimite listele de URL-uri ce trebuie gasite de crawlere. Paginile web care sunt gasite sunt apoi returnate serverului de stocare, care le memoreaza. Acesta comprima paginile si le depune intr-o biblioteca. Orice pagina web are un numar de identificare numit docID, care este oferit ori de cate ori un nou URL este analizat si extras dintr-o pagina web. Functia de indexare este realizata de indexer si de sorter. Indexer-ul indeplineste o serie de functii. Citeste documentele din biblioteca, decomprima docu-mentele si le analizeaza. Fiecare document este convertit intr-o serie de asocieri de cuvinte numite hit-uri. Acestea inregistreaza cuvantul si pozitia sa in document, aproximeaza dimensiunea fontului si tipurile de litere folosite. Indexer-ul distribuie aceste hit-uri intr-o serie de categorii, creand un index partial dezvoltat de sortare. Indexer-ul mai indeplineste si o alta functie importanta. Anali-zeaza toate link-urile din fiecare pagina web si stocheaza informatii importante despre acestea intr-un fisier de link-uri. Acest fisier contine infor-matii suficiente pentru a stabili unde ne indreapta link-ul respectiv, precum si textul link-ului.
Sistemul de analizare a URL-urilor citeste fisie-rul de link-uri si converteste URL-urile relative in URL-uri absolute si, respectiv, in docID-uri. Plasea-za textul link-ului in indexul initial care este asociat cu docID-ul la care se refera link-ul. Acesta gene-reaza de asemenea o baza de date de link-uri care nu sunt altceva decat corespondentele docID-urilor. Aceasta baza de link-uri este folosita pentru calcu-larea PageRank-urilor pentru toate documentele.
Sorter-ul preia categoriile care sunt sortate de docID si le clasifica dupa wordID pentru a forma un index complementar (inverted index). Un pro-gram numit DumpLexicon preia aceasta lista impreuna cu lexiconul produs de indexer si formeaza un lexicon nou care poate fi utilizat de searcher. Searcher-ul este rulat de un server si foloseste lexiconul construit de DumpLexicon impreuna cu indexul complementar si PageRank pentru a raspunde intrebarilor.

4.2 Structuri majore de date

Structurile de date ale Google sunt optimizate astfel incat o colectie ampla de documente poate fi parcursa si indexata cu putin efort. Desi CPU-urile si majoritatea ratelor de input output s-au imbu-natatit de-a lungul anilor o simpla cautare pe disc tot necesita 10 ms pentru a fi realizata. Google este proiectat sa evite acest gen de cautari de cate ori este posibil, iar acest lucru a avut o influenta consi-derabila asupra formatului structurilor de date.

4.2.1 BigFiles

BigFiles reprezinta fisiere virtuale care parcurg multiple fisiere de sistem si care sunt operationale cu 64 de biti integrali. Impartirea intre multiplele fisiere de sistem este realizata in mod automat. Aceste fisiere suporta de asemenea alocarea si dealocarea descriptorilor de fisiere, din moment ce sistemele de operare nu ofera destul pentru ceea ce avem noi nevoie. BigFiles suporta si optiuni simple de comprimare.

4.2.2 Biblioteca (Repository)

Biblioteca contine HTML-ul integral al fiecarei pagini web. Fiecare pagina este comprimata prin folosirea zlib (vezi RFC 1950). Optarea pentru o tehnica de compresie reprezinta echilibrul intre viteza si proportia comprimarii. Am ales viteza zlib dintr-o serie de imbunatatiri semnificative aduse comprimarii de bzip. Rata compresiei bzip era de aproximativ 4 la 1 in biblioteca, in comparatie cu zlib care oferea o rata de 3 la 1. In biblioteca, documentele sunt stocate unul dupa altul si sunt prefixate de docID, precizandu-li-se lungimea si URL-ul dupa cum se observa in Figura 2. Biblioteca nu solicita alte structuri de date care sa fie folosite pentru ca aceasta sa fie accesata. Acest lucru contribuie la consistenta informatiei usurand dez-vol-tarea; putem reconstrui toate celelalte struc-turi de date doar din biblioteca si dintr-un fisier care listeaza erorile crawler-ului.

4.2.3 Indexul documentelor

Indexul documentelor pastreaza informatii despre fiecare document. Acesta este un index ISAM (Index sequential access mode) cu o latime fixa, ordonat de un docID. Informatia continuta de fiecare scurta introducere include statutul curent al documentului, un indicator catre biblioteca, o evidenta a documentului si statistici variate. Daca documentul a fost parcurs atunci contine un indi-cator catre un fisier cu multe variabile numit docinfo si care cuprinde URL-ul si titlul docu-mentului. In caz contrar, indicatorul se indreapta catre lista URL-urilor care cuprinde numai URL-uri. Aceasta hotarare de design a fost luata in confor-mitate cu dorinta de a avea o structura compacta de date, precum si cu abilitatea de stabili un record de accesare unica a discului in timpul unei cautari.
In plus, exista un fisier care este folosit in convertirea URL-urilor in docID-uri. Acesta contine o lista cu URL-uri impreuna cu docID-ul cores-pun-zator si este sortat de suma de control. Pentru a gasi docID-ul unui anume URL, suma de control a URL-ului este calculata si o cautare binara este realizata pe fisierul de sume de control pentru identificarea docID-ului. URL-urile pot fi convertite in docID-uri luand mai multe simultan prin alipirea la acest fisier. Aceasta este tehnica pe care cel ce solutio-neaza URL-uri o foloseste pentru a trans-forma URL-urile in docID-uri. Aceasta metoda de abordare este im-portanta pentru ca altfel trebuie sa efectuam o cautare pentru fiecare link care, tinand cont de disc, ar dura mai mult de o luna pentru baza noastra de 322 milioane de link-uri.

4.2.4 Lexiconul

Lexiconul are mai multe forme diferite. O modificare esentiala adusa, spre deosebire de siste-mele an-te-rioare, este ca lexiconul se poate ajusta memoriei la un pret rezonabil. In implementarea actuala putem pastra lexiconul in memorie intr-un sistem cu 256 MB de memorie. Lexiconul actual contine 14 milioane de cuvinte (desi cateva cuvinte rare nu au fost adaugate). Lexiconul are doua parti - o lista de cuvinte (insiruite impreuna, dar sepa-rate de zerouri) si o serie de indicatori. Pentru a indeplini diverse functii, lista de cuvinte are informatii auxiliare care se afla insa dincolo de scopul acestei lucrari.

4.2.5 Listele de hit-uri (Hit Lists)

O lista de hit-uri corespunde unei liste de aparitii ale unui anumit cuvant intr-un document, incluzand informatii despre pozitia, fontul si tipul de litera folosit. Listele de hit-uri explica cea mai mare parte a spatiului utilizat atat in indicele primar (forward index), cat si in indicele comple-mentar (inverted index).
Din aceasta cauza, este important sa le repre-zentam cat mai eficient posibil. Am luat in calcul mai multe alternative pentru pozitia de codificare, font si tipul de litera - codificarea simpla (un grup de trei numere inetgrale), codificarea compacta (o serie de biti optimizati manual) si codificarea Huffmann. In final, am ales codificarea compacta optimizata manual deoarece necesita de departe mai putin spatiu decat codificarea simpla si mult mai putina manipulare a bitilor decat codificarea Huffmann. Detalii despre aceste hit-uri sunt aratate in Figura 3.
Codificarea compacta foloseste doi biti pentru fiecare hit. Exista doua tipuri de hit-uri: hit-uri complexe (fancy hits) si hit-uri simple (plain hits). Hit-urile complexe includ aparitia hit-urilor intr-un URL, titlu, textul link-ului sau meta tag. Hit-urile simple includ restul. Un hit simplu consta dintr-un bit referitor la tipul de litera, marimea fontului si 12 biti de pozitii ale cuvantului intr-un document (toate pozitiile ce depasesc 4095 sunt catalogate 4096). Marimea fontului este reprezentata relativ fata de restul documentului utilizand 3 biti (doar 7 valori sunt de fapt folosite deoarece 111 este simbolul care semnaleaza aparitia unui hit com-plex). Un hit complex consta intr-un bit referitor la tipul de litera, marimea fontului este setata la 7 pentru a indica ca este vorba de un hit complex, 4 biti pentru codificarea tipului de hit complex si 8 biti de pozitie. Pentru hit-urile de tip anchor, cei 8 biti ai pozitiei sunt impartiti in 4 biti pentru pozitie in link si 4 biti pentru continutul docID-ului in care link-ul apare. Aceasta ne ofera o sintagma redusa de cautare din moment ce nu exista multe link-uri pentru un anumit cuvant. Trebuie sa actualizam metoda de stocare a hit-urilor anchor pentru permiterea unei rezolutii mai mari in cadrul pozitiei si campurilor de docID-uri. Folosim mari-mea fontului in legatura cu restul documentului deoarece, atunci cand cautam, nu dorim listarea diferita a unor documente identice doar pentru ca unul din documente este scris cu un font mai mare.
Lungimea unei liste de hit-uri este stocata inainte chiar de hit-urile in sine. Pentru a economisi spatiu, lungimea listei de hit-uri este combinata cu wordID-ul in indexul primar si cu docID-ul in indexul complementar. Acest lucru o limiteaza la 8 si respectiv 5 biti (exista o serie de trucuri care permit ca 8 biti sa fie imprumutati din wordID). Daca lungimea este mai mare si nu se poate incadra in respectivii biti, atunci un cod de rezerva este folosit in acesti biti, iar urmatorii 2 biti vor contine lungimea actuala.

4.2.6 Indexul primar (Forward Index)

Indexul primar este deja partial sortat si este stocat intr-o serie de categorii (am folosit 64). Fiecare categorie contine o serie de wordID-uri. Daca un document contine cuvinte care tin de un anumit barrel, docID-ul este intregistrat in cate-gorie urmat de o lista de wordID-uri cu liste de hit-uri care corespund cuvintelor respective. Aceasta schema necesita mai mult spatiu de stocare din cauza docID-urilor duplicate, dar diferenta este foarte mica pentru un numar considerabil de categorii si economiseste timp si complexitate de codificare in faza finala de indexare facuta de sorter. Mergand mai departe, in loc de a stoca wordID-urile actuale, stocam fiecare wordID ca o diferenta relativa de la wordID-ul minim care se gaseste in categoria in care se afla si wordID-ul. Astfel, putem folosi 24 biti pentru wordID-uri in categorii nesortate, lasand 8 biti pentru lungimea listelor de hit-uri.

4.2.7 Indexul complementar

Indexul complementar consta din aceleasi categorii ca si indexul primar, cu diferenta ca aces-tea au fost procesate de sorter. Pentru fiecare wordID valid, lexiconul contine un indicator catre categoria in care wordID-ul este inclus. Acest indicator se refera la o lista de docID-uri luate impreuna cu listele de hit-uri corespunzatoare. Aceasta lista reprezinta toate aparitiile acelui cuvant in toate documentele.
(sfarsitul in numarul viitor)3. Activitati similare
Cercetarea navigarii pe web are o istorie scurta si concisa. World Wide Web Worm (WWWW) [McBryan 94] a fost unul dintre primele motoare de cautare. Acesta a fost ulterior urmat de alte cateva motoare de cautare academice, dintre care multe sunt acum companii publice. Comparativ cu dezvoltarea Web-ului si importanta motoarelor de cautare, exista putine documente valoroase refe-ritoare la motoarele de cautare recente [Pinkerton 94]. Conform lui Michael Mauldin (cercetator la Lycos Inc) "serviciile variate (inclusiv Lycos) urma-resc indeaproape detaliile acestor baze de date". Totusi, exista studii despre trasaturile specifice ale motoarelor de cautare. Un studiu bine realizat este acela care duce la obtinerea de rezultate prin procesarea ulterioara a rezultatelor motoarelor de cautare comerciale sau la producerea, la scara redusa, de motoare de cautare individualizate. Cercetari amanuntite au fost facute pe sistemele care se ocupa cu extragerea de informatii, in special pe colectiile bine controlate. In urmatoarele doua sectiuni, discutam despre zone unde aceasta cerce-tare trebuie extinsa pentru a se putea lucra mult mai bine pe web.

4.4 Indexarea Web-ului

Analiza: orice sistem de analizare care este destinat sa ruleze pe intreg Web-ul trebuie sa faca fata unei mari cantitati de erori posibile. Acestea se pot intinde de la mici greseli in sintagmele HTML pana la kilobiti de zerouri in mijlocul unei sintagme, caractere non-ASCII, sintagme HTML depozitate in interior si o mare varietate de alte greseli care pot provoca imaginatia oricui pentru a-l determina sa apara cu altele noi. Pentru viteza maxima, in loc sa folosim YACC pentru a genera un sistem CFG de analiza, folosim un cablu electric pentru initierea unui analizator lexical which pe care il dotam cu propria informatie. Dezvoltarea acestui sistem de analiza care ruleaza cu o viteza rezonabila si care este foarte solid a insemnat un timp indelungat de munca continua.
Indexarea documentelor in categorii: dupa ce fiecare document este analizat, este codificat intr-o serie de categorii. Fiecare cuvant este convertit intr-un wordID utilizand un continut de tip in-memory - lexiconul. Adaugirile care se fac continutului lexiconului sunt consemnate intr-un fisier. Din momentul in care cuvintele sunt convertite in wordID-uri, aparitiile lor in documentul curent sunt traduse in liste de hit-uri si sunt scrise in categoriile primare. Principala dificultate cu simultaneitatea fazei de indexare este aceea ca lexiconul trebuie impartit. In loc de impartirea lexiconului, am considerat indicat sa scriem un logaritm pentru toate cuvintele auxiliare care nu se aflau in lexiconul de baza, pe care l-am fixat la 14 milioane de cuvinte. In acest fel, indexer-ele multiple pot rula in paralel si apoi fisierul jurnal cu logaritmii cuvintelor auxiliare poate fi procesat de un singur indexer final.
Sortarea: pentru a putea genera indexul complementar, sorter-ul preia fiecare categorie primara si o sorteaza dupa wordID pentru a produce o categorie complementara pentru titlu si hit-urile de tip anchor si o categorie complementara de text integral. Acest proces se intampla cu fiecare categorie in parte, necesitand astfel un spatiu mic de stocare temporara. De asemenea, comparam faza de sortare pentru a utiliza cat mai multe sisteme posibile prin simpla rulare de sorter-e multiple, care pot procesa categorii diferite in acelasi timp. Din moment ce categoriile nu sunt compatibile cu memoria principala, sorter-ul le subdivide mai departe in subcategorii care se potrivesc cu memoria bazata pe word ID si docID. Apoi, sorter-ul incarca fiecare subcategorie in memorie, o sorteaza si ii transcrie continutul in categorii complementare mici si in categorii complementare detaliate.O alta caracteristica importanta o reprezinta ordinea in care docID-urile trebuie sa apara in lista. O solutie simpla este sa le stocam in functie de docID. Acest lucru permite fuzionarea rapida a diferitelor liste pentru intrebarile cu multe cuvinte. O alta posibilitate este sa le stocam in functie de aparitia cuvantului in fiecare document. Acest lucru implica lipsa de valoare a raspunsurilor la intrebarile alcatuite dintr-un singur cuvant si face posibil faptul ca raspunsurile la intrebarile cu multe cuvinte sa se afle chiar la inceput. Totusi, fuzionarea este cu mult mai dificila. De asemenea, acest lucru face ca dezvoltarea sa devina mult mai dificila, in sensul ca o schimbare in functia de ordonare necesita o reconstruire a indexului. Am ales sa facem un compromis intre aceste optiuni, prin pastrarea a doua serii de categorii complementare - o serie pentru listele de hit-uri care include titlul sau link-ul si o alta serie pentru toate listele de hit-uri. In acest fel, verificam primul set de categorii si daca nu gasim destule potriviri in cadrul acestora le verificam si pe cele mai mari.
Rularea unui crawler web reprezinta o provocare. Exista actiuni riscante si subiecte sigure si, mult mai important, exista subiecte sociale. Parcurgerea (crawling) reprezinta cea mai fragila aplicatie din moment ce implica interactiunea cu sute de mii de servere web si nume de servere diverse care se afla dincolo de posibilitatea de control a sistemului.
Pentru a pacurge sute de milioane de pagini web, Google are un sistem rapid (fast distributed crawling). Un singur server URL ofera liste de URL-uri unui numar de crawlers (in general folosim in jur de 3). Atat server-ul URL, cat si crawler-ele sunt realizate in Python. Fiecare crawler tine in jur de 300 de conexiuni (connections) deschise simultan. Acest lucru este necesar pentru regasirea paginilor web la o viteza suficient de rapida. La viteze mari sistemul poate sa parcurga peste 100 de pagini pe secunda utilizand 4 crawlere. Acesta se ridica la aproximativ 600K de date pe secunda. O actiune importanta este reprezentata de verificarea DNS. Fiecare crawler mentine un cache DNS propriu, astfel ca nu este nevoie sa se faca un control DNS inainte de parcurgerea fiecarui document. Fiecare dintre sutele de conexiuni se poate afla in stadii diverse: verificarea DNS, conectarea la gazda, transmiterea solicitarilor si primirea raspunsurilor. Acesti factori fac din crawler o componenta complexa a sistemului. Acesta foloseste IO asincron pentru a face fata solicitarilor si un numar de secvente pentru mutarea preluarilor de pagini din sectiune in sectiune.
Se adevereste astfel ca rularea unui crawler care se conecteaza la mai mult de jumatate de milion de servere si care genereaza zeci de milioane de fisiere jurnal implica o cantitate considerabila de e-mailuri si apeluri telefonice. Datorita numarului mare de persoane care sunt online, exista intotdeauna aceia care nu stiu ce este un crawler deoarece acesta este primul pe care il vad. Aproape in fiecare zi primim un mesaj de genul 'V-ati uitat la foarte multe pagini din site-ul meu. Ce parere aveti despre el?'. Exista de asemenea unele persoane care nu au aflat de existenta protocolului de excluziune la roboti si se considera ca pagina lor ar trebui protejata impotriva unei indexari de genul 'Aceasta pagina este protejata si nu va fi indexata', care este dificil de inteles de crawler-ele web. De asemenea, din cauza cantitatii uriase de date implicate, lucruri neasteptate se pot intampla. De exemplu, sistemul nostru a incercat sa parcurga un joc online. Rezultatul a constat intr-o multime de mesaje iritante chiar in mijlocul jocului. Se pare ca aceasta a fost o problema usor de rezolvat. Dar aceasta problema nu aparuse pana in momentul in care am descarcat zeci de milioane de pagini. Datorita variatiei ridicate in paginile web si in servere, este practic imposibil sa testezi un crawler fara sa-l rulezi pe o parte considerabila a Internetului. Invariabil, apar sute de probleme obscure care se pot ivi pe o singura pagina din tot web-ul si pot cauza distrugerea crawler-ului sau mai rau, poate cauza o reactie imprevizibila sau incorecta. Sistemele care acceseaza parti mari din Internet trebuie sa fie foarte solide si testate cu multa atentie. Din moment ce sistemele complexe cum sunt crawler-ele vor duce in mod invariabil la aparitia problemelor, trebuie sa existe resurse semnificative dedicate citirii de e-mail-uri si rezolvarii problemelor din momentul in care acestea apar.

4.5 Cautarea

Scopul cautarii este acela de a oferi rezultate concludente in timp util. Multe dintre motoarele de cautare comerciale par sa fi facut progrese considerabile din punct de vedere al eficientei. De aceea, ne concentram mai mult pe calitate in cercetarea noastra, desi suntem de parere ca solutiile noastre se afla, cu putin mai mult efort, in progresie cu volumele comerciale. Procesul de evaluare al unei interogari Google este indicat de Figura 4.
Pentru marcarea unei limite a timpului de raspuns, odata ce un anumit numar de documente care se potrivesc cu interogarea (40.000 de obicei) este gasit, cel care a initiat cautarea poate merge direct la punctul 8 din Figura 4. Aceasta inseamna ca este posibil ca rezultate neconcludente sa fie oferite in schimb. In prezent, investigam alte metode pentru rezolvarea acestei probleme. In trecut, am sortat hit-urile in concordanta cu PageRank, lucru care pare sa fi imbunatatit situatia.

4.5.1 Sistemul de clasificare

Google pastreaza mult mai multe informatii despre documentele web decat motoarele tipice de cautare. Fiecare lista de hit-uri include pozitia, fontul si informatii despre tipul de litera folosit. In plus, luam in calcul hit-urile dupa textul link-ului si PageRank-ul documentului. Combinarea tuturor acestor informatii intr-un singur rezultat este dificila. Am conceput functia de ordonare astfel incat nici un factor particular sa nu aiba o influenta prea mare. Sa luam mai intai cazul cel mai simplu - o interogare cu un singur cuvant.
Pentru afisarea unui document folosind o interogare cu un singur cuvant, Google parcurge toate listele de hit-uri ale documentului pentru cuvantul respectiv. Google considera fiecare hit ca apartinand unuia dintre diversele tipuri (titlu, link, URL, fonturi mari si fonturi mici de text simplu etc.), fiecare dintre acestea avand grade diferite de importanta in functie de tipul din care face parte. Aceste grade de importanta formeaza un vector indexat in functie de tip. Google numara hit-urile fiecarui tip din lista de hit-uri. Apoi fiecare pozitie este reorganizata intr-un clasament in functie de importanta. Gradele de importanta cresc liniar in functie de primele pozitii, dar se reduc repede astfel incat este relevant numai un anume numar de aparitii. Noi preluam produsul scalar al vectorului de ponderi de aparitii impreuna cu vectorul de ponderi de tipuri pentru a calcula un scor IR al documentului. In final, scorul IR este combinat cu PageRank pentru a oferi un rezultat final al documentului.
Pentru o interogare alcatuita din mai multe cuvinte, situatia este si mai complicata. In acest caz, listele multiple de hit-uri trebuie parcurse simultan astfel incat hit-urile care sunt apropiate intr-un document sunt plasate pe pozitii superioare fata de cele care sunt departate unele de altele. Hit-urile din listele multiple sunt potrivite astfel incat hit-urile apropiate sunt puse impreuna. Pentru fiecare set de potriviri de hit-uri, se calculeaza o apropiere. Aceasta apropiere se bazeaza pe cat de departate sunt hit-urile in cadrul documentului (sau link-ului), dar este clasificata in 10 clase cu valori diferite, mergand de la o sintagma apropiata pana la 'nu foarte aproape'. Se fac contorizari nu numai pentru fiecare tip de hit, dar si pentru fiecare tip si apropiere. Fiecare pereche de tip si apropiere are o pondere tip-apropiere. Contorizarile sunt clasificate in functie de ponderile de aparitii si noi preluam produsul scalar pentru ponderile de aparitii si ponderile de tip-apropiere pentru realizarea unui scor IR. Toate aceste numere si matrice pot fi afisate odata cu rezultatele cautarii folosind o metoda speciala de corectare. Toate aceste afisari sunt de foarte mare ajutor in dezvoltarea sistemului de ordonare.

4.5.2 Scurta recapitulare

Functia de ordonare are multi parametri precum ponderile de tip si ponderile tip-apropiere. Stabilirea valorilor exacte pentru acesti parametri tine de domeniul magiei. Pentru a face acest lucru, avem un mecanism de feedback al utilizatorului in cadrul motorului de cautare. Un utilizator increzator poate evalua optional toate rezultatele care ii sunt returnate. Acest feedback este salvat. Apoi, cand modificam functia de ordonare, putem observa impactul acestei schimbari asupra cautarilor anterioare care au fost ordonate. Desi departe de perfectiune, acest lucru ne face sa observam cum o schimbare in functia de ordonare poate afecta rezultatele cautarii.

5. Rezultate si mod de functionare

Cea mai importanta caracteristica a unui motor de cautare este calitatea rezultatelor cautarii. In timp ce o evaluare completa a utilizatorului se afla dincolo de scopul acestei lucrari, experienta noastra personala cu Google a dovedit ca este posibil sa se obtina rezultate mult mai bune pentru majoritatea cautarilor decat ale celor mai importante motoare comerciale de cautare. Ca un exemplu ce ilustreaza utilizarea PageRank, a textului link-ului si a aproximarii, Figura 5 indica rezultatele Google pentru o cautare procesata pe termenul 'bill clinton'. Aceste rezultate evidentiaza cateva dintre trasaturile Google. Rezultatele sunt grupate de server. Acest lucru este de mare ajutor atunci cand examinam seturile de rezultate. O serie de rezultate sunt din domeniul whitehouse.gov, care reprezinta rezultatul asteptat pentru o cautare de acest gen. In mod obisnuit, majoritatea motoarelor de cautare comerciale nu ofera nici un rezultat din whitehouse.gov, cu atat mai putin pe cele corecte. Trebuie observat ca nici un titlu nu este afisat pentru primul rezultat, din cauza ca nu a fost parcurs. In schimb, Google s-a bazat pe textul link-ului pentru a hotari daca acesta era un raspuns potrivit pentru intrebare. In mod asemanator, al cincilea rezultat este o adresa de e-mail, care, bineinteles, nu poate fi parcursa (crawlable) si care este, de asemenea, un rezultat al textului link-ului.
Toate rezultatele sunt pagini cu un inalt nivel calitativ si, la o ultima verificare, nici una dintre ele nu este un link irelevant (broken). Acest lucru se intampla din cauza ca toate au un PageRank ridicat. PageRank-urile sunt marcate prin procentajele de culoare rosie. In concluzie, nu sunt rezultate despre un alt Bill in afara de Clinton sau despre un alt Clinton in afara de Bill si asta pentru ca acordam o importanta majora aproximarii sintagmelor in care apare un cuvant. Bineinteles ca un adevarat test al calitatii pentru un motor de cautare ar trebui sa implice si un studiu complet despre utilizator sau o analiza a rezultatelor pentru care noi nu avem loc in lucrarea de fata. In schimb, invitam cititorii sa incerce ei insisi Google la https://google.stanford.edu.

5.1 Parametri pentru stocare

In afara de calitatea cautarii, Google este proiectat sa masoare capacitatea Web-ului pe masura ce acesta se dezvolta. Un aspect al acestui fenomen il reprezinta modul eficient de stocare. Tabelul nr. 1 contine fragmente din cateva statistici si parametri de stocare ai Google. Datorita comprimarii, marimea totala a bibliotecii este de 53 GB, putin peste o treime din totalul de date pe care le contine. La preturile actuale ale discurilor biblioteca poate fi considerata o sursa ieftina de date. Ceea ce este mai important - totalul datelor folosite de motorul de cautare necesita un spatiu comparabil de stocare, adica in jur de 55 GB. Mai departe, un raspuns poate fi gasit pentru majoritatea interogarilor prin folosirea indexului complementar. Cu metode mai bune de codificare si de comprimare ale Document Index, un motor de cautare de calitate se poate incadra in 7 GB ai unui PC nou.

5.2 Modul de functionare a sistemului

Este important pentru un motor de cautare sa parcurga si sa indexeze eficient. Astfel, informatia poate fi permanent actualizata si modificarile majore aduse sistemului pot fi testate relativ repede. Pentru Google, operatiunile importante sunt Crawling (parcurgerea), Indexing (indexarea) si Sorting (sortarea). Este dificil de masurat cat a durat crawling-ul in total din cauza ca discurile au fost in intregime completate, numele serverelor nu mai sunt functionale sau din cauza oricarei probleme care putea determina oprirea sistemului. In total a durat cam 9 zile sa descarcam cele 26 milioane de pagini (inclusiv erorile). Totusi, din moment ce sistemul rula fluent si mai repede, am descarcat ultimele 11 milioane de pagini in doar 63 de ore, in medie 4 milioane de pagini pe zi sau 48,5 pagini pe secunda. Am rulat indexer si crawler simultan. Indexer a rulat mai repede decat crawler-ele. Aceasta s-a intamplat din cauza ca am petrecut destul timp pentru optimizarea indexer-ului astfel incat sa nu determine intarzierea dezvoltarii sistemului. Aceste optimizari au inclus o serie de updatari ale indexului documentului si plasarea structurilor precare de date pe un disc local. Indexer-ul ruleaza aproximativ 54 de pagini pe secunda. Sorter-ele pot fi rulate complet in paralel, utilizand 4 sisteme, intreg procesul de sortare durand in jur de 24 de ore.

5.3 Procesul de cautare

Imbunatatirea procesului de cautare nu a reprezentat punctul principal de interes al cercetarii noastre pana in acest moment. Versiunea curenta Google raspunde la cele mai multe din interogari intre 1 si 10 secunde. Acest interval este dominat in mare parte de IO-ul discului asupra NFS (din moment ce discurile sunt impartite pe sisteme diferite). Mai departe, Google nu are nici un fel de optimizare cum ar fi cache de cautari, subindici pe termeni comuni si alte optimizari obisnuite. Intentia noastra este de a mari considerabil viteza Google prin distributie si hardware, software si imbunatatiri algoritmice. Scopul nostru este acela de a putea raspunde la mai multe sute de interogari pe secunda. Tabelul nr. 2 contine cateva exemple de intervale de raspuns la interogari din versiunea curenta Google. Acestea sunt reluate pentru a reda performantele de viteza rezultate din cache-ul IO.

6. Concluzii

Google este proiectat sa fie un motor de cautare scalabil. Scopul principal este acela de a oferi rezultate de calitate pe fondul dezvoltarii rapide a World Wide Web. Google foloseste o serie de tehnici pentru ameliorarea calitatii cautarii incluzand page rank, textul link-ului si alte informatii apropiate. Mai departe, Google reprezinta o arhitectura completa pentru adunarea paginilor web, indexarea lor si efectuarea de interogari asupra lor.

6.1 Activitati viitoare

Un motor amplu de cautare este un sistem complex care ramane deschis completarilor. Scopurile noastre imediate sunt acelea de a imbunatati cautarea si de a afisa aproximativ 100 de milioane de pagini web. Cateva imbunatatiri simple aduse eficientei includ cache de interogari, alocare optimizata a discului si subindici. O alta sectiune care necesita o cercetare amanuntita este reprezentata de updatari. Trebuie sa avem algoritmi potriviti pentru a decide ce pagini mai vechi ar trebui reparcurse si ce pagini noi ar trebui parcurse. Munca in vederea atingerii acestui scop a fost facuta in [Cho 98]. O zona promitatoare de cercetare este aceea de a utiliza un cache proxy pentru construirea de baze de date cu scopul cautarii din moment ce acestea sunt influentate de cerere. Planuim sa adaugam trasaturi simple ce sunt suportate de motoarele comerciale de cautare cum ar fi operatorii de tip boolean, negatia si implicatia. Totusi, alte trasaturi cum ar fi feedback-ul relevantei si clustere (Google suporta in mod obisnuit clusterele bazate pe numele de domeniu) de-abia acum incep sa fie explorate. Intentionam de asemenea sa sustinem contextul de utilizator (cum ar fi locatia utilizatorului) si rezumarea rezultatelor. Ne preocupa si extinderea utilizarii structurii de link-uri si a textului link-ului. Experimentele simple indica faptul ca PageRank poate fi personalizat prin amplificarea ponderii homepage-ului unui utilizator sau a bookmark-urilor acestuia. In ceea ce priveste textul link-ului, experimentam utilizarea textului link-urilor invecinate alaturi de textul link-ului in sine. Un motor de cautare pe Web repezinta un mediu bogat pentru initiativele de cercetare.

6.2 Cautare la standarde inalte

Cea mai mare problema cu care se confrunta astazi utilizatorii de motoare de cautare o reprezinta calitatea rezultatelor pe care le primesc. Pe cand rezultatele sunt deseori amuzante si largesc orizontul utilizatorului, ele pot deveni si frustrante si pot consuma timp pretios. De exemplu, primul rezultat pentru o cautare 'Bill Clinton' pe unul dintre cele mai populare motoare de cautare comerciale a fost Bill Clinton Joke of the Day: April 14, 1997. Google este destinat sa ofere rezultate de o calitate superioara astfel incat Web-ul sa continue sa se dezvolte rapid, iar informatia sa poata fi gasita usor. Pentru a putea realiza acest lucru, Google utilizeaza frecvent informatia hipertextuala ce consta din structura de link-uri si din textul link-urilor. Google foloseste de asemenea aproximarea si informatia despre fonturi. In timp ce evaluarea unui motor de cautare este dificila, noi am aflat in mod intuitiv ca Google returneaza rezultate la un inalt nivel calitativ spre deosebire de motoarele comerciale de cautare. Analizarea structurii de link-uri prin PageRank permite Google sa evalueze calitatea paginilor web. Utilizarea textului link-ului ca o descriere a ceea ce indica link-ul contribuie la relevanta si, intr-o anumita masura, la inaltul standard calitativ al rezultatelor. In cele din urma, utilizarea unor informatii asemanatoare ajuta la marirea gradului de relevanta al multor interogari.

6.3 Arhitectura scalabila

In afara de calitatea cautarii, Google este destinat sa masoare. Trebuie sa dea dovada de eficienta atat in spatiu, cat si in timp, iar factorii constanti sunt foarte importanti atunci cand vorbim de Web. Prin implementarea Google, am observat intarzieri in CPU, accesarea memoriei, capacitatea memoriei, cautarile pe disc, continutul discului, capacitatea discului si IO de retea. Google a evoluat pentru a depasi o serie din aceste probleme prin intermediul unor operatiuni variate. Structurile majore de date ale Google utilizeaza in mod eficient spatiul de stocare. Mai departe, operatiunile de parcurgere, indexare si sortare sunt suficient de eficiente pentru a construi un index al unei parti substantiale a Web-ului - 24 de milioane de pagini in mai putin de o saptamana. Intentionam sa devenim capabili de a construi un index de 100 de milioane de pagini in mai putin de o luna.

6.4 Un instrument de cercetare
In afara de a fi un motor de cautare de calitate, Google este si un instrument de cercetare. Datele pe care Google le-a adunat au dus la aparitia multor lucrari prezentate la conferinte si multe altele sunt deja in curs de aparitie. Un studiu recent cum ar fi [Abiteboul 97] a indicat un numar de limitari ale cautarilor despre Web care pot fi raspunse fara ca Web-ul sa fie disponibil pe plan local. Aceasta inseamna ca Google (sau un sistem similar) nu reprezinta numai un instrument valoros de cercetare, dar si unul necesar pentru o serie larga de aplicatii. Speram ca Google va deveni o resursa pentru cautatorii si cercetatorii din lumea intreaga si ca va impulsiona generatia urmatoare de motoare de cautare.