Cum functioneaza Google? (partea 1)

Acest articol deoarece era prea mare l-am impartitit in doua. Prima parte cuprinde pe langa un interviu cu Larry Page, co-fondator si presedinte, divizia de Produse, si multe alte lucruri interesante despre modul de functionare a principalului motor de cautare Google.

Interviu cu Larry Page, co-fondator si presedinte, divizia de Produse
Fondatorii Google
Google pe scurt
SCURT ISTORIC GOOGLE
Anatomia unui mega-motor de cautare hipertext pentru Web

Interviu cu Larry Page, co-fondator si presedinte, divizia de Produse

Internet Magazin: Google ocupa o parte din ce in ce mai mare din piata motoarelor de cautare. Va exista un moment in care veti dezvolta alte proiecte, si in ce directie s-ar incadra acestea?

Larry Page: In cadrul firmei Google, scopul nostru este sa ne perfectionam tehnologia de cautare si sa imbunatatim si extindem experienta cautarii pe Internet, pentru utilizatorii nostri. Pentru aceasta, am dezvoltat mai multe produse legate de cautare, cum ar fi Google Image Search, Google Catalog Search, Google News Search si altele. Desi am avansat foarte mult in aceasta industrie, mai avem inca multe de realizat. Dorim sa devenim motorul de cautare absolut, care intelege exact ce doriti si va intoarce exact rezultatele de care aveti nevoie.

IM: Aveti in cadrul companiei si specialisti romani?

LP: La Google sunt angajati oameni din toate rasele si de toate formatiile, iar multi dintre specialistii nostri vin din tari europene. Avem mai multi angajati din Romania, care contribuie la perfectionarea tehnologiei de cautare si la dezvoltarea unor produse inovatoare.

IM: In aceasta perioada de criza pentru afacerile bazate pe Internet, Google continua sa prospere, in timp ce alte afaceri au falimentat. Care este explicatia pentru succesul crescand al lui Google?

LP: Google a ramas concentrat exclusiv pe progresul tehnologiei de cautare, si suntem in continuare credinciosi misiunii companiei noastre, aceea de a organiza informatia mondiala si de a o face universal accesibila si utila. Noi punem interesele utilizatorilor nostri pe primul plan, iar acestia continua sa ramana fideli lui Google.

IM: Ce sfaturi dati dotcom-urilor din Romania (unde Internetul este inca tanar si in crestere), pentru a evita eventuale prabusiri similare celor din SUA?

LP: Ramaneti concentrati pe misiunea companiei voastre, angajati oameni talentati si nu creati o afacere doar pentru a face bani. Ideile mari si o echipa remarcabila pot propulsa puternic o companie.

IM: Veti dezvolta un site Google in Romania, asa cum ati facut si in alte tari?

LP: Google continua sa isi extinda domeniile specifice de tari, si speram ca in viitor sa includem si Romania, ca si alte tari.

IM: In prezent indexati peste 2 miliarde de pagini Web. Cum veti aborda in viitor continutul in alte limbi?

LP: Google va continua sa isi extinda continutul international, adaugand din ce in ce mai multe interfete de limba, domenii specifice de tari si restrictii de limba. In acest moment, Google are cel mai bogat continut international dintre motoarele de cautare orientate catre consumatori; avem suport pentru 82 interfete de limba, 34 domenii specifice de tari si 35 restrictii de limba.

IM: Ce este serviciul Google Answers? Cum va fi el dezvoltat pentru partea de Web in alte limbi?

LP: Google Answers este o alte extensie a ofertei noastre si este in prezent in faza de beta-testare. Este vorba despre un serviciu platit, in care utilizatorii pot primi raspunsuri la intrebari, de la un cautator pe Web profesionist. Timpul de raspuns variaza in functie de dificultatea intrebarii. Deoarece Google Answers se afla inca in faza de beta-testare, vom continua sa evaluam feedback-ul utilizatorilor pentru a determina etapele urmatoare ale acestui serviciu; in viitor, vom avea in vedere si localizarea acestui produs, pe baza de limba sau pe baza de tara.

Fondatorii Google

Sergey Brin Sergey Brin
Co-fondator & Presedinte, Tehnologie
Sergey Brin (28 ani), originar din Moscova, a primit titlul de licenþiat in stiinþe cu merite deosebite in matematica si informatica la Universitatea din Maryland, la College Park. In prezent, este aproape de terminarea studiilor de doctorat in informatica la Universitatea Stanford, unde a primit si diploma de masterat. Brin este membru al National Science Foundation Graduate Fellowship. La Stanford l-a cunoscut pe Larry Page, alaturi de care a lucrat la proiectul care, mai tarziu, a devenit Google. Impreuna au fondat Google Inc. in 1998, iar Brin a continuat sa imparta responsabilitaþile operaþiunilor zilnice cu Larry Page si Eric Schmidt.
Printre subiectele asupra carora Brin a efectuat cercetari se numara motoarele de cautare, extragerea de informaþii din surse nestructurate si analiza colecþiilor ample de text si date stiinþifice. A publicat mai mult de o duzina de lucrari academice, printre care Extracting Patterns and Relations from the World Wide Web; Dynamic Data Mining: A New Architecture for Data with high Dimensionality, pe care a publicat-o impreuna cu Larry Page; Scalable Techniques for Mining Casual Structures; Dynamic Itemset Counting and Implication Rules for Market Basket Data si Beyond Market Baskets: Generalizing Association Rules to Correlations.

Lawrence Page Larry Page
Co-fondator & Presedinte, Produse
Larry Page (29 ani) este CEO fondator al Google si a contribuit la dezvoltarea profitabilitaþii companiei prin angajarea a peste 200 de oameni, inainte de numirea sa ca presedinte al segmentului de Produse in aprilie 2001. In prezent, continua sa imparta responsabilitaþile operaþiunilor zilnice cu Eric Schmidt si Sergey Brin.
Ca fiu al profesorului de informatica de la Universitatea din Michigan, Dr. Carl Victor Page, pasiunea lui Page pentru computere a inceput la varsta de 6 ani. Calcand pe urmele tatalui sau, Page a absolvit cu merite deosebite Universitatea din Michigan, unde a primit diploma de licenþiat in inginerie, accentul fiind pus pe ingineria informatica. In intervalul petrecut la Ann Arbor, Page a primit numeroase premii pentru eforturile depuse in vederea imbunataþirii Colegiului de Inginerie, a fost presedintele Eta Kappa Nu Honor Society din cadrul universitaþii si a construit un plotter programabil si o imprimanta pe jet de cerneala din piese LegoTM.
In timpul studiilor de doctorat in informatica la Universitatea Stanford, Page il intalneste pe Sergey Brin si impreuna dezvolta Google, care devine operaþional in 1998. Dupa primirea diplomei de master Page paraseste Stanford. Inainte de Google, Page a fost dezvoltator de software la Advanced Management Systems din Washington, D.C. si CogniTek din Evanston, Ill.

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 soluþionate in fiecare zi: peste 150 de milioane
 Pagini web parcurse: peste 2,4 miliarde
 Tipuri de fisiere cautate:
 HyperText Markup Language (html)
 Adobe Portable Document Format (pdf)
 Adobe PostScript (ps)
 Lotus 1-2-3 (wk1, wk2, wk3, wk4, wk5, wki, wks, wku)
 Lotus WordPro (lwp)
 MacWrite (mw)
 Microsoft Excel (xls)
 Microsoft PowerPoint (ppt)
 Microsoft Word (doc)
 Microsoft Works (wks, wps, wdb)
 Microsoft Write (wri)
 Rich Text Format (rtf)
 Text (ans, txt)
 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 interfaþa: 81
 Limbile in care Google ofera rezultate: 35
 Utilizatori: Mai mult de jumatate din traficul Google.com provine din afara USA

Administraþie
Personalul Google include profesionisti cu experienþa in domeniul tehnologiei, iar compania este susþinuta de fonduri provenite de la doua firme ce se ocupa cu investiþiile de risc.
 Numar aproximativ de angajaþi: 400
 Deþinatori 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 inþelegeau 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 soluþiona una dintre cele mai mari provocari legate de domeniul computerelor: extragerea unor informaþii 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 capacitaþii 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 reputaþiei motorului BackRub printre cei care mai vazusera aceasta tehnologie.

1998
Ianuarie-Iulie 1998
Larry si Sergey continua sa perfecþioneze tehnologia de cautare Google. Urmand aceesi concepþie care va deveni o parte esenþiala a metodei Google, ei ofera un terabyte de spaþii de stocare la preþuri 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 incurajaþi de unul dintre fondatorii Yahoo! si coleg de universitate, David Filo. Filo a aprobat eficienþa 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 atenþia portalurilor importante, Sergey si Larry concep un plan de afaceri si, avand doar un bagaj de cunostinþe, 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 potenþialul 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 angajaþi. 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 angajaþi 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 angajaþi. Virgilio, portalul online leader in Italia, alege Google sa ofere servicii WebSearchTM. Google castiga o serie de premii in mai puþin de 4 luni, printre care: Technical Excellence Award oferit de PC Magazine pentru inovatii in dezvoltarea aplicaþiilor 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 iniþiaza 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 conþinand 1 bilion de URL-uri. Yahoo! selecteaza Google ca suport informaþional 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! anunþa un parteneriat care asigura reputaþia companiei nu doar ca agent ce asigura tehnologie, dar si ca o afacere substanþiala 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 informaþii pe orice pagina de pe intregul web. PC Magazine din Anglia recompenseaza Google cu premiul pentru cea mai buna inovaþie de pe Internet.

2001
Ianuarie-Februarie 2001
Google raspunde la mai mult de 100 de milioane de cautari pe zi. Google achiziþioneaza 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 conþine 300 de site-uri), Vodaphone si MarthaStewart.com. Google anunþa 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 conþinea 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 promoþionale Google atrag mai mult de 350 de sponsori si mii de agenþi 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, Franþa, Italia, Elveþia, Canada, Japonia si Coreea. Utilizatorii pot selecta interfaþa Google in aproape 40 de limbi in afara de engleza. Opþiunea 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 presedinþi. 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 corporaþiilor Sony. Noul index Google Image Search, cu 250 de milioane de imagini si cautare de informaþii, devine disponibil prin pagina avansata de cautare Google. Sistemele de cautare, tendinþele si noutaþile 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 Select™.
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 http://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.

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.
Autor: Sergey Brin, Larry Page
Sursa http://www.internet-magazin.ro

Ce sa nu faca webdesigner-ul pentru a creea un site optimizat? Cum functioneaza Google? (partea 2)

Comentarii