referat, referate , referat romana, referat istorie, referat geografie, referat fizica, referat engleza, referat chimie, referat franceza, referat biologie
 
Astronomie Istorie Marketing Matematica
Medicina Psihologie Religie Romana
Arte Plastice Spaniola Mecanica Informatica
Germana Biologie Chimie Diverse
Drept Economie Engleza Filozofie
Fizica Franceza Geografie Educatie Fizica
 

Proiect SCD - google

Categoria: Referat Informatica

Descriere:

Fiţi cât mai exact. Printr-o interogare precisă, se obţin mai puţine rezultate şi conţinutul relevant este mai uşor de găsit. De exemplu, dacă am căutat cuvântul lege, am obţinut aproximativ 3.580.000 de rezultate. Pentru căutarea lege drept autor am obţinut 12.000 de rezultate, în timp ce pentru fraza exactă "lege privind dreptul de autor" am obţinut 30 de rezultate...

Varianta Printabila 


1 Universitatea din Craiova





Facultatea de Automatică, Calculatoare şi Electronică





Proiect S.C.D.
Trasaturile, configuratia si modul de funtionare pentru Google








COORDONATOR:                         STUDENTĂ:

PROF.DR.ING. Matei Vnătoru                             Stănică Roxana
                                                                               Master - A.S.C











1. Google - Introducere    3
Căutarea n WEB    3
Cteva sfaturi pentru o căutare eficientă:    6
Utilizatori    7
Administraţie    8
Funcţionarea Google – pe scurt    8
Hardware    8
Cum manevrează Google cererile de căutare?    10
Sistemul PageRank    10
Googlebot-ul    11
Sistemul de fişiere Google    11
Scalabilitate:    12
1.1 Motoare de căutare – Evoluţie: 1994-2000    13
1.2 Google: Evoluţie concomitentă cu Web-ul    13
1.3 Caracteristici ale configuraţiei    14
1.3.1 Capacitate mbunătăţită de căutare    14
1.3.2. O cercetare academică a motorului de căutare    15
2. Trăsăturile sistemului    15
2.1 PageRank: Ordonarea Web-ului    16
2.1.1 Descrierea unui calcul PageRank    16
2.1.2 Explicarea intuitivă    17
2.2 Textul link-ului    17
2.3 Alte trăsături    18
3. Activităţi similare    18
3.1 Extragerea de informaţii    19
3.2 Diferenţe ntre Web şi colecţiile bine controlate    19
4. Configuraţia sistemului    20
4.1 Scurtă descriere a arhitecturii Google    21
4.2 Structuri majore de date    21
4.2.1 BigFiles    22
4.2.2 Biblioteca (Repository)    22
4.2.3 Indexul documentelor    22
4.2.4 Lexiconul    23
4.2.5 Listele de hit-uri (Hit Lists)    23
4.2.6 Indexul primar (Forward Index)    24
4.2.7 Indexul complementar    25
4.4 Indexarea Web-ului    25
4.5 Căutarea    27
4.5.1 Sistemul de clasificare    27
4.5.2 Scurta recapitulare    28
5. Rezultate şi mod de funcţionare    30
5.1 Parametri pentru stocare    30
5.2 Modul de funcţionare a sistemului    31
5.3 Procesul de căutare    31
6. Concluzii    32
6.1 Activităţi viitoare    32
6.2 Căutare la standarde nalte    32
6.3 Arhitectura scalabilă    33
Referinţe    34
1. Google - Introducere


Orict de imparţiali ncearcă jurnaliştii să fie, există o tendinţă clară n presă de a critica tot sau aproape tot ce face Microsoft şi de a reda ntr-o lumină placută şi optimistă realizările Google.
Este greu de spus cnd a nceput această modă şi care au fost motivele din spatele ei. Un ochi atent ar observa că pnă la urmă este vorba de doi giganţi din lumea IT care nu sunt att de diferiţi, factorul primar care face diferenţa ntre cei doi fiind vrsta.
Iniţial, Google a reprezentat un proiect de cercetare conceput n 1996 de Larry Page şi Sergey Brin, doi doctoranzi de la Stanford. Cei doi au plecat de la ipoteza că un motor de căutare care analizeazaă relaţiile dintre website-uri ar duce la obţinerea de rezultate mai bune dect cele furnizate de tehnicile folosite atunci, şi anume de cte ori se repetă cuvntul cheie pe pagină.
n martie 2001, Eric Schmidt a devenit membru al consiliului de directori, iar n august 2001, a fost numit CEO-ul companiei. Popularitatea noului motor de căutare s-a datorat design-ului aerisit, simplităţii şi acurateţii rezultatelor ntoarse, iar numărul de utilizatori a crescut exponenţial. n timp, după succesul motorului de căutare clasic, Google şi-a extins braţele virtuale şi peste imagini, video, ştiri, grupuri, mail, cumpărături, hărţi si multe altele. n plus, există zvonuri că Google ar plănui o reţea Internet proprie n Statele Unite, formată cu ajutorul kilometrilor ntregi de fibră optică rămaşi după boom-ul de la sfrşitul anilor '90. Această fibră optică, care străbate suprafeţe ntinse ale Statelor Unite poartă numele de "fibra ntunecată" (dark fiber).

Căutarea n WEB
Internetul poate fi considerat ca fiind cea mai mare bibliotecă disponibilă şi actualizată permanent. De aceea uneori găsirea informaţiei care ne este necesară poate fi dificilă.
World Wide Web (WWW sau Web) reflectă chiar prin numele sau trăsăturile sale esenţiale :
•    este destinat căutării informaţiei n ntregul Internet (world wide = n lumea ntreagă)
•    foloseşte hipertextul pentru organizarea informaţiei, ceea ce face ca aceasta să apară ca o pnză de păianjen (web) permiţnd navigarea cu uşurinţă de la o pagină la alta.

Pentru regăsirea informaţiei n Web se pot folosi următoarele instrumente:
•    serviciul de navigare – browserul, care permite accesarea informaţiilor prin introducerea adresei de web a paginii (numită URL - Uniform Resource Locator – identificator standard al locului n care se găseşte resursa), sau prin urmărirea unei hiperlegături (en. hyperlink) dintr-un alt document (care conţine URL-ul paginii respective)
•    serviciul de căutare automată – prin:
• instrumente de căutare (search tool)
• instrumente de indexare (indexing tool)
• motor de căutare (search engine)

Browserul permite, n general, efectuarea următoarelor operaţii:
•    navigarea printre paginile web şi vizualizarea lor.
•    urmărirea legăturilor dintre documente care conţin hiperlegături.
•    copierea informaţiilor din Internet pe propriul calculator.
•    căutarea informaţiei n Internet.
•    regăsirea rapidă a informaţiilor prin folosirea „semnelor de carte” („pagina favorită”) şi a istoricului.
•    accesarea altor servicii Internet: poşta electronică, mesagerie instantanee etc.

Aşadar, browserul integrează accesul la mai multe servicii din Internet printr-o interfaţă accesibilă şi uşor de utilizat.
O alternativă mai rapidă pentru „răsfoirea” paginilor web n căutarea informaţiei dorite este apelarea la un serviciu de căutare, adică un site web care conţine n general următoarele categorii de informaţii:
•    instrucţiuni care arată modul n care trebuie folosit serviciul
•    metoda prin care utilizatorul poate să propună un subiect pentru căutare

Portalurile sunt site-uri specializate care ndeplinesc funcţia cataloagelor dintr-o bibliotecă. Aceste site-uri aranjează pe categorii sau domenii diverse site-uri existente n Internet şi le ordonează n funcţie de anumite criterii n cadrul categoriilor stabilite (pe subiecte, după popularitate, etc.). De multe ori, portalurile oferă şi alte servicii pe lngă cel de căutare (poştă electronică, ştiri etc.).
 

Motoarele de căutare sunt site-uri care au rolul de a ajuta utilizatorul să găsească mai uşor şi mai direct informaţia n Internet. De cele mai multe ori, n cuprinsul unui site cu rol de căutare, se regăsesc ambele funcţionalităţi – indexare n catalog şi meniu de căutare. Motorul de căutare este n fapt o aplicaţie care „răsfoieşte” paginile web din Internet n căutarea cuvintelor sau frazelor cerute de utilizator. Pentru aceasta sunt folosite nişte programe automate care alcătuiesc liste de cuvinte din interiorul site-urilor. Rezultatele căutării sunt afişate n funcţie de relevanţa stabilită de motorul de căutare, utiliznd indexarea termenilor din aceste liste.
 

De aceea, termenii căutaţi trebuie să fie ct mai definitorii pentru subiectul n cauză (keywords – „cuvinte-cheie”).
Pentru a limita aria de căutare, se recomandă utilizarea modului de căutare avansată („advanced search”), care permite găsirea mai rapidă a informaţiei datorită criteriilor multiple de căutare.
De exemplu, Google afişează doar paginile care includ toţi termenii căutării. Nu este necesar să includem "and" ntre termeni. Pentru a rafina căutarea, se adaugă doar alţi termeni, iar rezultatele vor conţine un subset specific al paginilor ntoarse de către cererea originală.
Putetem exclude un cuvnt din căutare prin scrierea semnului minus ("-") imediat naintea termenului pe care vrem să l evităm. De asemenea, se pot căuta fraze prin includerea acesteia ntre ghilimele.
 

Cteva sfaturi pentru o căutare eficientă:
1.    Fiţi ct mai exact. Printr-o interogare precisă, se obţin mai puţine rezultate şi conţinutul relevant este mai uşor de găsit. De exemplu, dacă am căutat cuvntul lege, am obţinut aproximativ 3.580.000 de rezultate. Pentru căutarea lege drept autor am obţinut 12.000 de rezultate, n timp ce pentru fraza exactă "lege privind dreptul de autor" am obţinut 30 de rezultate.
2.    Nu folosiţi cuvinte uzuale. Utilizaţi cuvinte ct mai adecvate subiectului căutat, altfel utilitarul de căutare va returna zeci de pagini web cu informaţii irelevante pentru dumneavoastră. Vezi diferenţa ntre 5.570.000 rezultate pentru masă şi 4.960 pentru mijloace comunicare masă.
3.    nvăţaţi să adaptaţi interogarea. Dacă interogarea dumneavoastră returnează prea multe rezultate, restrngeţi aria de căutare. Dacă rezultatele returnate nu sunt suficiente, reformulaţi-o ntr-un mod mai general. Nu ntotdeauna primele cuvinte -cheie sunt şi cele mai bune.
4.    Folosiţi diferite forme ale cuvintelor. Puteţi utiliza diferite cuvinte care se referă la subiectul căutat pentru a obţine ct mai multe informaţii relevante pentru dumneavoastră.
5.    Folosiţi sinonimele. De exemplu, scrieţi şi „alergare” şi ”jogging”. Dacă folosiţi un utilitar de căutare care acceptă combinaţii de cuvinte - cheie, separaţi sinonimele prin cuvntul cheie OR
6.    Folosiţi citate ntre ghilimele. n cazul cnd căutaţi o anumită frază sau un titlu, plasaţile ntre ghilimele (de ex. „Internet pentru ncepători”) n formularul utilitarului de căutare.
7.    Folosiţi majuscule atunci cnd este necesar. Majoritatea directoarelor şi indexurilor de căutare fac diferenţa ntre literele mici şi literele mari din şirul de caractere căutat. Dacă textul introdus conţine numai litere mici, utilitarul de căutare va identifica numai textul scris fie cu litere mari, fie cu litere mici. n cazul n care scrieţi şi o litera mare, utilitarul de căutare presupune ca aceasta are o semnificaţie specială şi va afişa numai rezultatele care corespund exact şirului respectiv.
8.    Aflaţi secretele utilitarului de căutare folosit. Unele utilitare de căutare oferă facilităţi speciale prin care conţinutul relevant poate fi găsit mai uşor.

Google este cel mai mare motor de căutare şi datorită parteneriatelor sale cu Yahoo!, Netscape şi altele este capabil să răspundă la mult mai multe interogări dect orice alt serviciu online asemănător.
•   Interogări soluţionate n fiecare zi: peste 150 de milioane
•    Pagini web parcurse: peste 2,4 miliarde.
•    Tipuri de fişiere căutate
•    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 şi este folosit de oameni din lumea ntreagă

•    Media lunară a numărului de utilizatori: 55.6 milioane (Nilesen/NetRatings 5/02)
•    Gradul de utilizare att acasă, ct şi la birou: #4 (Nilesen/NetRatings 5/02)
•    Limbile pentru care Google asigură o interfaţă: 81
•    Limbile n care Google oferă rezultate: 35
•    Utilizatori: mai mult de jumătate din traficul Google.com provine din afara USA.

Administraţie

Personalul Google include profesionişti cu experienţă n domeniul tehnologiei, iar compania este susţinută de fonduri provenite de la două firme ce se ocupă cu investiţiile de risc.
•    Număr aproximativ de angajaţi: 400
•    Deţinători ai titlului de doctor: peste 50

Proiectarea unui motor de cătare este o provocare. Motoarele de căutare indexează zeci sau chiar sute de milioane de pagini web, implicnd un număr echivalent de termeni distincţi. Acestea raspund la zeci de milioane de ntrebări n fiecare zi. Deşi importanţa acestor motoare de căutare pe web este mare, totuşi ele nu au constituit subiectul unei cercetări academice amănunţite. n plus, datorită gradului rapid de avansare a tehnologiei şi dezvoltării continue a web-ului, metoda de creare a unui motor de căutare este foarte diferită de cea folosită acum trei ani. Această lucrare oferă o descriere amanunţită a motorului de cautare.
n afara problemelor de măsurare a capacităţii motoarelor tradiţionale de căutare pnă la a putea suporta o cantitate importantă de date, există noi provocări tehnice corelate cu utilizarea informaţiilor adiţionale prezente n hipertext, cu scopul producerii de rezultate mai bune. Lucrarea de faţa pune aceasta ntrebare, cum să construieşti un sistem practic de măsurare care poate folosi informaţia adiţională din hipertext. De asemenea, luăm n considerare modul de tratare efectiv al colecţiilor de hipertext, care nu pot fi n ntregime controlate şi unde fiecare este liber să publice ceea ce doreşte.

Funcţionarea Google – pe scurt

Hardware
Pentru a putea oferi capacitate suficientă de service, structura fizică a Google-lui este alcătuită din clustere şi computere situate peste tot n lume, cunoscute sub numele de ferme de servere. Aceste ferme de servere sunt alcătuite dintr-un număr mare de computere de nivel jos pe care rulează sisteme bazate pe Linux care operează cu GFS (Sistemul de fişiere Google), iar cele mai mari dintre aceste ferme au peste 1000 de noduri de stocare şi peste 300 de TB de spaţiu de stocare pe disk.
S-a speculat că Google are cel mai mare computer din lume. S-a estimat că Google are n jur de:
•899 de rack-uri
•79, 112 maşini
•158,244 Unităţi centrale de prelucrare (UCP)
•316,448 GHz putere de procesare
•158,224 Gb de RAM
•6,180 Tb de spaţiu pe Hard

Clustere-le sunt folosite pentru a face ca 2 sau mai multe calculatoare să apară ca unul singur pentru o comunitate de utilizatori. Custerele sunt folosite pentru a oferi fiabilitate crescută, şi/sau pentru a creşte performanţa de pe un singur calculator.
Un cluster este un grup de calculatoare legate ntre ele care lucrează mpreună ca un computer paralel. Una dintre cele mai populare implementări o reprezintă cluster-ul cu noduri pe care rulează Linux-ul ca şi sistem de operare şi software-ul Beowulf pentru a implementa paralelismul.
Microsistemele Sun şi-au lansat de asemenea un produs gen cluster numit Grid engine.
De asemenea denumită şi cluster de servere, fermă de computere sau ranch, o fermă de servere este un grup de servere legate prin reţea care sunt găzduite ntr-o singură locaţie. O fermă de servere modernizează procesele interne prin distribuirea lucrului ntre componentele individuale ale „ fermei” şi expediază procesele computaţionale prin folosirea puterii mai multor servere. „Ferma” se bazează pe software-ul „ load-balancing” care realizează sarcini cum ar fi urmărirea cererii pentru procesarea puterii de la diferite maşini, stabilind prioritatea temelor şi programndu-le şi reprogramnd-le n funcţie de prioritatea şi cererea pe care utilizatorii o pun pe reţea. Cnd un server din „ fermă” eşuează, un altul poate interveni ca şi back-up.
Un nod este un dispozitiv care este conectat ca şi parte a unei reţele de calculatoare. Nodurile pot fi computere, personal digital assistants (PDAuri), telefoane mobile sau variate dispozitive ale reţelei. Pe o reţea IP, un nod este orice dispozitiv cu o adresă IP. Nodurile sunt deseori conectate prin centrale, routere sau printr-un switch de reţea.
Linux-ul este un sistem de operare gratuit de tip Unix, creat cu originalitate de către Linus Torvalds cu ajutorul unor programatori din jurul lumii. Creat sub licenţa GNU General Public, codul sursă pentru Linux este disponibil gratuit pentru toată lumea.
Un rack de 19 inch este un sistem standard pentru ncărcarea unor module electronice variate ntr-o stivă sau un „ grilaj” , cu o lărgime de 19 inch.

Cum manevrează Google cererile de căutare?

Cnd un user introduce o ntrebare n căsuţa de căutare la Google.com, aceasta este transmisă n mod aleator la unul dintre clustere-le lui Google. ntrebarea va fi apoi manevrată n mod exclusiv de către cluster. Un echilibrator de ncărcare monitorizează cluster-ul, apoi mprăştie cererea către serverele din cluster ca să asigure că ncărcarea de pe hardware este egală.
Echilibratorul de ncărcare are nevoie de informaţii de profil pentru indica cum să re-mapeze procesele şi canalele de comunicare pentru a optimiza performaţa. Acesta va fi un ehilibrator-optimizator static care va lua informaţia din uneltele de profil şi va produce echilibrare de ncărcare pentru viitoarele rulări.

Căutarea propriu-zisă are loc n 2 faze:
•    n prima fază, cuvintele din cerere sunt verificate cu o listă din index-urile serverelor care conţin detaliile de potrivire ale documentelor. Sistemul PageRank este angajat ntr-un set relevant de documente, ce sunt identificate de trimiteri la alte referinţe ale cuvintelor şi  care vor determina scorul pentru fiecare document, dar la ntoarcere afectează poziţia documentului pe pagina rezutatelor.
•    Rezultatele de la serverele indexate sunt apoi trimise la servere de documente n formularul de identificatori de documente. Rezidentă n serverele document este o copie a lui World Wide Web, de unde se ia rezumatul conţinutului paginii web apoi le rentoarce către server. Rezultatul este apoi procesat şi este redat napoi ca un document HTML care poate fi afişat pe browser-ul user-ului ca pagină web.

Sistemul PageRank

PageRank, denumit astfel după Larry Page, care l-a inventat, este unul dintre modurile prin care Google determină importanţa paginii, care, la rentoarcere, va decide unde anume pe lista de rezulate va apărea rezultatul.
Algoritmul exact a lui PageRank, aşa cum este extras din “The Anatomy of a Large-Scale Hypertextual Web Search Engine” este n felul următor:
Presupunem că pagina A are paginile T1...Tn care pointează spre ea. Parametrul d este un factor, care poate fi setat ntre 0 şi 1. De obicei l punem pe d pe valoarea 0.85. Există mai multe detalii despre d n secţiunea următoare. De asemenea, C(A) este definit ca fiind numărul de link-uri care „ies” din pagina A. RankPage-ului paginii A este redat n felul următor:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

A se nota că PageRank-urile dintr-o probabilitate a distribuţiei peste paginile web este făcută astfel nct suma PageRank-urilor a tuturor paginilor web va fi una.

Googlebot-ul

Serverele Google sunt populate de către web crawler-urile Google-ului, Googlebot, care se mişcă de pe site pe site pe internet, făcnd download a unor copii a paginilor web şi salvndu-le n index-ul Google-ului (cunoscut sub numele de cache) pentru viitoarele refetinţe. Googlebot-ul nsăţi este rezident pe multe calculatoare care accesează simultan pe sute de pagini web. Acesta emulează un browser, aşa că, mulţi dintre webmasteri şi vor da seama că atunci cnd vizitează, acesta lasă un „marcaj” n secţiunea de browser a protocolului site-ului web mai degrabă dect n secţiunea de „păianjen” dect cele mai multe web crawler-uri care se nregistrază.
Un web crawler (cunoscut şi sub numele de web spider) este un program care deschide World Wide Web ntr-o manieră metodică, automată. Web crawlerii sunt n pricipal folosiţi pentru a crea o copie a tuturor paginilor web vizitate pentru procesări ulterioare de către un motor de căutare, care va indexa paginile download-ate pentru a oferi căutari mai rapide.
Există două metode pe care Googlebot le foloseţte pentru a găsi o pagină web: ori prin ajungerea la pagina web după ce „s-a trt” prin link-urile acesteia, ori ia pagina după ce a fost nscrisă de către webmaster. Prin nscrierea link-ului principal Googlebot va trece prin toate link-urile care se găsesc n indexul paginii şi n fiecare pagină următoare, pnă cnd ntregul site a fost indexat.

Sistemul de fişiere Google

Sistemul de fişiere Google este un sistem propriu de administrare a fişierelor dezvoltat de către Sanjay Ghemawat, Shun-Tak Leung şi Urs Holyle pentru Google, ca un mijloc de a manevra un număr masiv de cereri peste un număr mare de clustere ale serverelor.
Sistemul a fost creat la fel ca majoritatea celorlalte sisteme distribuite de fişiere, pentru performanţă maximă, pentru a face faţă unui număr mare de utilizatori, scalabilitate, pentru a fi capabil să manevreze expansiunile inevitabile, siguranţă, pentru a asigura maximul de uptime şi disponibilitate, pentru a asigura faptul că, toate calculatoarele sunt disponibile pentru a trata ntrebările.

Scalabilitate:
1. Cuvnt des folosit care se referă la felul n care un sistem hardware sau software se poate adapta pentru a creşte cererile.
2. Se referă la orice la care i se poate schimba mărimea
3. Cnd este folosit pentru a descrie un sistem al computerului, proprietatea de a rula mai mult de un procesor.
Uptime este o măsură a timpului de cnd un computer de sistem a fost pornit. A fost creat pentru a descrie antonimul cuvntului downtime, adică timpul ct un sistem a fost non-operaţional.
Disponibilitatea este o măsură a ct de mult timp o reţea sau o conexiune a rulat. n general, formula este: Timpul rulării/Timpul măsurat (timpul de rulare mpărţit la timpul măsurat). Deşi, dacă se măsoară ceva pentru 20 de minute şi acesta a fost disponibil doar 19 din acestea, disponibilitatea va fi de 95%.
Din cauza deciziei lui Google de a folosi un număr mare de computere de nivel jos n loc să folosească un număr mai mic de sisteme de tip server, sistemul de fişiere Google a trebuit să fie creat astfel nct să poată trata eşecurile sistemului, să efectueze monitorizarea constantă a sistemelor, detectarea de erori, toleranţa erorilor şi recuperarea automată.
Toleranţa erorilor este disponibilitatea unui sistem de a răspunde unui eşec neaşteptat a dispozitivelor hardware sau software. Există multe nivele de tolerare a erorilor, cel mai jos fiind amabilitatea de a continua operaţile n cazul unei căderi de tensiune. Multe dintre sistemele de computere care tolerează erorile monitorizează toate operaţiile, aceasta este n cazul n care, fiecare operaţie este efectuată pe două sau mai multe sisteme duplicate, aşa că n cazul n care unul dintre acestea eşuează celălalt poate prelua controlul.
Aceasta nsemna că, toate clustere-le ar trebui să reţină replici multiple a informaţiei create de web crawler-ii Google-lului. Aceasta este foarte relevant pentru Gmail care a fost recent implementat pe Google, unde email-ul personal al utilizatorilor trebuie să aibă backup pentru a preveni pierderea informaţiilor.
Din cauza mărimii bazei de date a Google-ului, sistemul a trebuit creat ca să poată trata fişiere enorme de mai mulţi giga-bytes totaliznd mulţi terabytes ca şi mărime. A fost creat astfel datorită faptului că stocarea fişierelor n kilobytes ar nsemna să existe miliarde de fişiere, care s-ar putea dovedi imposibil de manevrat. O altă metodă angajată să trateze fişiere de mărime enormă este că schimbările (cunoscute şi sub numele de mutaţii) sunt mai degrabă adăugate dect să aibă fişiere peste care s-a rescris, astfel se minimizează timpul de acces la fişiere.
GFS este un sistem propriu aşa că aplicaţiile software pot fi construite de obicei n jurul lui, asigurnd faptul că Google are control maxim asupra sistemului, n acelaşi timp permiţnd sistemului să rămnă flexibil.

Web-ul creează noi provocări pentru obţinerea de informaţii. Cantitatea de informaţii de pe web creşte ntr-un ritm alert, pe măsura numărului de noi utilizatori lipsiţi de experienţă n arta căutarii pe web. De obicei, oamenii navighează pe web folosind graficul acestuia de link-uri, adeseori ncepnd cu indici superiori calitativ, mentinuţi de intervenţia umană, cum ar fi Yahoo sau cu motoare de căutare. Listele unde intervine mintea umană acoperă subiecte diverse şi populare, dar sunt subiective, costisitoare de intreţinut şi menţinut, greu de imbunătăţit şi nu pot acoperi toate subiectele ce ţin de domenii specializate. Motoarele de căutare automate, care se bazează pe potrivirea de cuvinte-cheie, oferă, n mod obişnuit, prea multe rezultate neconcludente. Pentru a nrăutăţi situaţia, unii agenţi publicitari ncearcă să cstige atenţia prin diferite metode destinate să inducă n eroare motoarele automate de căutare. Ei au construit un motor de căutare pe scară largă care are răspuns pentru multe din problemele sistemului existent. Acesta utilizează, n special, structura adiţională din hipertext pentru a oferi rezultate concludente. Au numit acest sistem Google deoarece este un cuvnt asemănător cu googol sau 10100 şi corespunde cel mai bine intenţiei lor de a construi motoare de căutare pe scară largă.

1.1 Motoare de căutare – Evoluţie: 1994-2000

Tehnologia motoarelor de căutare a fost obligată să se reinventeze n mod constant pentru a putea ţine pasul cu expansiunea web-ului. n 1994, unul dintre primele motoare de căutare, World Wide Web Worm (WWWW), avea un index de 110,000 pagini web şi documente accesibile pe web. n noiembrie 1997, motoarele de căutare cele mai performante realizau indexarea de la 2 milioane (WebCrawler) pnă la 100 de milioane de documente web (din Search Engine Watch). Este previzibil că, pnă n anul 2000, un index complet al Web-ului să conţină peste un bilion de documente. n acelaşi timp, numărul interogărilor la care pot face faţă motoarele de căutare a crescut ntr-un ritm incredibil de rapid. n martie şi aprilie 1994, World Wide Web Worm primea n jur de 1500 de ntrebări pe zi. n noiembrie 1997, Altavista pretindea că rezolva aproximativ 20 de milioane de interogări pe zi. Odată cu creşterea numărului de utilizatori ai web-ului şi sistemelor automate care puneau ntrebări motoarelor de căutare, este posibil ca motoarele performante de căutare să poată raspunde la sute de milioane de ntrebări pe zi pănă n anul 2000. Scopul sistemului este să rezolve multe dintre aceste probleme, att din punct de vedere al calităţii, ct şi al scalabilităţii, coordonate introduse de tehnologia motoarelor de căutare care au atins cifre extraordinare.
1.2 Google: Evoluţie concomitentă cu Web-ul

Crearea unui motor de căutare care să ţină pasul cu web-ul zilelor noastre este subordonată multor provocări. Tehnologia rapidă de parcurgere este necesară pentru a ţine o evidenţă a documentelor web şi pentru a le actualiza n permanenţă. Spaţiul de stocare trebuie folosit n mod eficient pentru organizarea indicilor şi, opţional, chiar a documentelor. Sistemul de indexare trebuie să proceseze ct mai bine sute de gigabiţi de date. ntrebările trebuie să aibă un răspuns ntr-un interval ct mai scurt, la o rată de sute pnă la mii pe secundă.
Aceste sarcini devin din ce n ce mai dificile pe măsură ce Web-ul se dezvoltă. Totuşi, performanţele hardware şi costurile au crescut şi ele n mod constant pentru a rezolva parţial această problemă. Există, binenţeles, cteva excepţii importante de la acest progres cum ar fi timpul de căutare pe disc şi performanţele sistemului de operare. n proiectarea sistemului Google, s-au luat n considerare att rata de evoluţie a Web-ului, ct şi schimbările tehnologice. Google este construit n aşa fel nct să parcurgă eficient mari cantităţi de date. n acelaşi timp, Google utilizează eficient spaţiul de stocare pentru organizarea indexului. Structurile sale informaţionale sunt optimizate pentru accesul rapid şi concludent (vezi secţiunea 4.2). Se speră că preţul indexării şi stocării de text sau HTML să devină n cele din urmă mai mic n raport cu cantitatea de date ce va fi disponibilă. Acest lucru va genera caracteristici mai performante de organizare pentru sistemele centralizate ca Google.

1.3 Caracteristici ale configuraţiei
1.3.1 Capacitate mbunătăţită de căutare

Scopul principal a fost acela de a mbunătăţi calitatea motoarelor de căutare. n 1994, existau păreri că un index complet de căutare va face posibilă găsirea rapidă a oricărui răspuns. n opinia Best of the Web 1994 – Navigators, “Cel mai bun sistem de navigare ar trebui să faciliteze găsirea unui răspuns la aproape orice ntrebare pe Web (din momentul introducerii datelor)”. Totuşi, Web-ul anului 1997 este diferit. Oricine a utilizat recent un motor de căutare, poate oricnd să spună că nu complexitatea indexului este singurul factor care asigură calitatea rezultatelor căutării. Rezultatele neconcludente (junk results) estompează de obicei relevanţa rezultatelor de care un utilizator este ntr-adevar interesat. De fapt, din noiembrie 1997, numai unul dintre cele 4 motoare de căutare comerciale şi menţionează numele (returnează pagina proprie de căutare ca răspuns la numele sau n topul primelor 10 rezultate). Una dintre principalele cauze ale acestei probleme este aceea că numărul documentelor din indici a crescut progresiv acoperind diferitele grade de importanţă, n timp ce modul de percepere al utilizatorului asupra acestor documente nu s-a schimbat. Oamenii manifestă n continuare interes doar pentru primele 10 rezultate. Din acest motiv, pe măsura ce colecţia de date se măreşte, este nevoie de instrumente cu un grad ridicat de precizie (adică număr de documente relevante returnate, de exemplu n topul primelor 10 rezultate). ntr-adevar, se vrea ca noţiunea de “relevant” să includă caracteristica de cel mai important ignornd chiar căutarea n sine (numărul total de documente relevante pe care sistemul este capabil să le ofere. Există chiar un sentiment de optimism care se referă la utilizarea mai multor informaţii hipertextuale ce pot contribui la mbunătăţirea căutării şi la alte aplicaţii. n particular, structura şi textul link-ului oferă multe informaţii pentru efectuarea de analize relevante şi filtrări de calitate. Google foloseşte att structura link-ului ct şi textul acestuia (vezi sectiunile 2.1 si 2.2).

1.3.2. O cercetare academică a motorului de căutare

n afară de o creştere considerabilă, Web-ul a adoptat şi o caracteristică comercială de-a lungul timpului. n 1993, 1,5% din serverele web erau pe domenii .com. Numărul acestora a atins 60 de procente n 1997. n acelaşi timp, motoarele de căutare au părăsit academicul n favoarea comercialului. Pnă n prezent dezvoltarea majorităţii motoarelor de căutare a fost efectuată de companii care aveau prea puţin de-a face cu detaliile tehnice. Acest fenomen a determinat rămnerea n umbră a tehnologiei motoarelor de căutare şi orientarea acestora către comercial. Cu Google, scopul este acela de a orienta dezvoltarea şi perceperea acestora către sfera academicului.
O altă trăsătură importantă a acestei configuraţii era construirea de sisteme pe care mulţi oameni să le poată utiliza. Modul de utilizare era important pentru deoarece unele dintre cele mai interesante cercetări implică manipularea unei vaste cantităţi de informaţii care sunt disponibile pe sistemele web moderne. De exemplu, zilnic sunt iniţiate zeci de milioane de căutari. Totuşi, toate aceste date sunt foarte dificil de obţinut, n special pentru că se consideră că au valoare comercială.
Scopul final al acestei configuraţii era realizarea unei arhitecturi care să poată susţine activităţi inedite de căutare pe scară largă a informaţiei pe web. Pentru a sprijini aceste activităţi de căutare, Google stochează toate documentele n format comprimat pe care le parcurge. Unul dintre scopurile principale ale configuraţiei Google a fost acela de a stabili un mediu unde ceilalţi căutători puteau intra repede, de a procesa secţiuni considerabile ale web-ului şi oferi rezultate interesante care ar fi fost greu de oferit prin adoptarea unei alte metode. n intervalul scurt de timp n care sistemul a fost construit, existau deja cteva lucrări care foloseau bazele de date oferite de Google şi multe altele sunt realizate acum. O altă este aceea de a constitui un mediu asemănător cu un laborator spaţial unde cercetătorii sau chiar studenţii să poată propune şi chiar executa experimente interesante folosind informaţiile complexe ale web-ului.
2. Trăsăturile sistemului

Motorul de căutare Google este caracterizat de două trăsături importante care ajută la producerea de rezultate cu un grad ridicat de precizie. n primul rnd, Google se foloseşte de structura de link-uri a Web-ului pentru a calcula un indice calitativ al fiecarei pagini web. Această estimare a nivelului calitativ se numeşte PageRank n al doilea rnd, Google utilizează link-urile pentru a mbunătăţi rezultatele căutării.


1 2.1 PageRank: Ordonarea Web-ului

Graficul de link-uri al web-ului este o resursă importantă care a rămas n mare parte neutilizată de motoarele de căutare. S-au realizat hărţi conţinnd nu mai puţin de 518 milioane din aceste hyperlink-uri, o mostră semnificativă a totalului. Aceste hărţi permit calcularea rapidă a PageRank-ului unei pagini web, o măsura obiectivă a importanţei link-urilor care corespunde cu ideea subiectivă de importanţă a oamenilor. Datorită acestei corespondenţe, PageRank reprezintă o metodă excelentă de stabilire a gradului de importanţă a rezultatelor căutărilor bazate pe cuvinte cheie. Pentru cele mai populare subiecte, un text simplu care se potriveşte cu căutarea şi care este limitat la titluri ale paginii web este foarte bine reprezentat atunci cnd PageRank stabileşte importanţa rezultatelor (demonstraţie disponibilă la google.stanford.edu). Pentru căutările ce au la bază un text integral n 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 raportată la web, n general prin numerotarea link-urilor sau backlink-urilor unei pagini date. Acest lucru stabileşte cu aproximaţie importantă sau calitatea unei pagini. PageRank extinde această idee nu prin efectuarea unei numerotări a link-urilor din toate paginile, ci prin stabilirea numărului de link-uri dintr-o pagină. PageRank este definit după cum urmează:
Presupunem că pagina A este formată din paginile T1…Tn care se referă la aceasta (adică sunt link-uri). Parametrul d este un factor de nivelare care se află ntre 0 şi 1. De obicei, stabilim valoarea 0.85 pentru acest factor. Mai multe detalii despre d sunt oferite n secţiunea următoare. De asemenea, C(A) este definit ca un număr de link-uri care nu fac parte din pagina A. PageRank-ul paginii A este după cum urmează:
PR(A) = (1-d) +d(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))
Trebuie reţinut că PageRank formează o distribuţie a probabilităţii paginilor web, astfel că suma tuturor paginilor web ce ţin de PageRank este 1.
PageRank sau PR(A) poate fi calculat utiliznd un simplu algoritm repetabil şi 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 n cteva ore ntr-un punct de lucru de mărime medie. Există multe alte detalii care depăşesc intenţia acestei lucrări.

2.1.2 Explicarea intuitivă

PageRank poate fi considerat un model al comportamentului utilizatorului. Să presupunem că există un navigator oarecare care vizitează o pagină web aleasă la ntamplare şi care accesează link-urile, fără a reveni la pagina iniţială: n cele din urmă se va plictisi şi se va orienta spre altă pagină web aleasă la ntmplare. Probabilitatea că acest navigator să viziteze o pagină este reprezentată de PageRank. Iar d, factorul de nivelare, reprezintă probabilitatea ca navigatorul să se plictisească la fiecare pagină accesată şi să continue căutarea paginilor la ntamplare. O variaţie importantă este aceea de a adaugă doar factorul de nivelare d unei singure pagini sau unui grup de pagini. Acest lucru permite personalizarea şi poate face aproape imposibilă inducerea deliberată n eroare a sistemului pentru obţinerea unui calificativ superior. Pentru mai multe referiri la PageRank.
O altă explicaţie intuitivă este că o pagină poate avea un PageRank ridicat dacă există mai multe pagini care fac referire la aceasta sau dacă există cteva pagini care au un PageRank ridicat şi care o recomandă. n mod intuitiv, paginile la care se face referire din multe colţuri ale web-ului sunt considerate importante. De asemenea, paginile care probabil au o singură referire de la gazda Yahoo-ului sunt considerate importante. Dacă o pagina nu are un nivel calitativ ridicat sau are un link insuficient, este mai mult dect probabil ca pagina gazdă a Yahoo-ului nu va avea nici un link pentru aceasta. PageRank face faţă ambelor situaţii şi chiar mai mult de att prin propagarea recursivă a gradului de importanţă n ntreaga structură de link-uri a web-ului.

2.2 Textul link-ului

Textul link-ului este tratat ntr-un mod cu totul special de motorul de căutare. Majoritatea motoarelor de căutare asociază textul link-ului cu pagina de care se leagă. n plus, se asociază cu pagina pe care link-ul respectiv o indică. Acest sistem prezintă mai multe avantaje. n primul rand, link-urile oferă deseori descrieri mai precise ale paginilor web dect o fac paginile respective. n al doilea rnd, link-urile pot face referire la documente care nu pot fi indexate de un motor de căutare bazat pe text, cum ar fi: imagini, programe sau baze de date. Acest lucru face posibilă returnarea paginilor web care nici macăr nu au fost parcurse. Trebuie reţinut că paginile care nu au fost parcurse pot cauza probleme din moment ce nu le-a fost niciodată verificată validitatea nainte de a fi oferite utilizatorului. n acest caz, motorul de căutare poate oferi o pagină care nu a existat niciodată cu adevarat, dar care are hyperlink-uri care fac referire la ea. Totuşi, este posibil ca rezultatele să fie sortate, astfel ca această problemă apare rareori.
Ideea corelării textului link-ului cu pagina web la care se referă a fost implementată n World Wide Web Worm, n special pentru că ajută la căutarea informaţiei de tip non-text şi mareşte aria de acoperire a căutarii prin numărul mai redus de documente descărcate. Se foloseşte propagarea de link-uri deoarece textul link-ului poate contribui la oferirea de rezultate mai bune. Utilizarea eficientă a text-ului link-ului este dificilă din punct de vedere tehnic din cauza cantităţilor mari de date care trebuie procesate. n procesul de parcurgere a 24 milioane de pagini, s-au indexat peste 259 de milioane de link-uri.

2.3 Alte trăsături

n afară de PageRank şi de utilizarea textului link-ului, Google are şi alte trăsături. Prima este aceea că are informaţii de bază pentru toate căutarile şi astfel utilizează, n mod frecvent, proximitatea n procesul de căutare. A doua se referă la faptul că Google are n vedere detaliile vizuale ale prezentării cum ar fi mărimea fonturilor. Cuvintele scrise cu un font mai mare sau cu caractere ngroşate sunt percepute altfel dect celelalte cuvinte. A treia trăsătură este aceea că se ţine o evidenţă a ntregului şir al paginilor HTML.


3. Activităţi similare

Cercetarea navigarii pe web are o istorie scurtă şi concisă. World Wide Web Worm (WWWW) a fost unul dintre primele motoare de căutare. Acesta a fost ulterior urmat de alte cteva motoare de căutare academice, dintre care multe sunt acum companii publice. Comparativ cu dezvoltarea Web-ului şi importanţa motoarelor de căutare, există puţine documente valoroase refe-ritoare la motoarele de căutare recente. Conform lui Michael Mauldin (cercetător la Lycos Inc) “serviciile variate (inclusiv Lycos) urmăresc ndeaproape detaliile acestor baze de date”. Totuşi, există studii despre trăsăturile specifice ale motoarelor de căutare. Un studiu bine realizat este acela care duce la obţinerea de rezultate prin procesarea ulterioară a rezultatelor motoarelor de căutare comerciale sau la producerea, la scară redusă, de motoare de căutare individualizate. Cercetări amanunţite au fost făcute pe sistemele care se ocupă cu extragerea de informaţii, n special pe colecţiile bine controlate. n următoarele două secţiuni, se va discuta despre zone unde această cercetare trebuie extinsă pentru a se putea lucra mult mai bine pe web.

3.1 Extragerea de informaţii

Cercetarea sistemelor care se ocupă cu extragerea de informaţii a fost iniţiată acum mulţi ani şi este acum bine dezvoltată. Totuşi, majoritatea cercetărilor asupra acestor sisteme se concentrează pe colecţiile omogene şi bine ntretinute cum ar fi: colecţiile de lucrări stiintifice sau articole despre un subiect apropiat. ntr-adevăr, prototipul extragerii de informaţii, The Text Retrie-val Conference foloseşte pentru teste colecţii mici dar bine controlate. Testul “Very Large Corpus” are doar 20 GB n comparaţie cu 147 GB ai celor 24 de milioane de pagini web. Tot ce funcţionează bine pe TREC nu oferă de obicei rezultate satisfăcătoare pe web. De exemplu, modelul de vector spaţial standard ncearcă sa returneze documentele care se apropie cel mai mult de interogare, ţinnd seama de faptul că att interogarea ct şi documentul sunt vectori definiţi de ocurenţa cuvintelor lor. Pe web, această strategie oferă de obicei documente scurte care conţin interogarea şi cteva cuvinte n plus. De exemplu, s-a observat că un motor important de căutare returnează o pagina conţinnd doar “Bill Clinton Sucks” şi o fotografie dintr-o interogare referitoare la Bill Clinton. Unii sunt de părere că, pe web, utilizatorii ar trebui să specifice cu mai multă acurateţe ceea ce doresc să afle şi să adauge mai multe cuvinte ntrebării respective. Dacă un utilizator formulează o interogare de tipul “Bill Clinton” ar trebui să primească rezultate concludente din moment ce există o cantitate considerabilă de informaţii valoroase disponibile pentru acest subiect. Prin aceste exemple procesul standard de extragere de informaţii trebuie extins pentru a putea utiliza web-ul n mod eficient.
3.2 Diferenţe ntre Web şi colecţiile bine controlate

Web-ul reprezintă o colecţie vastă de documente eterogene. Documentele de pe web sunt caracterizate printr-o variaţie internă constantă a documentelor şi de asemenea prin meta informaţie externă care poate să fie disponibilă. De exemplu, documentele diferă din punct de vedere intern prin limbaj (att uman, ct şi de programare), vocabular (adrese de e-mail, link-uri, coduri zip, numere de telefon, numere de producţie), tip de format (text, HTML, PDF, imagini, sunete) şi pot fi generate chiar de sistem (fişiere jurnal sau extrase din baza de date). Pe de altă parte, definim meta informaţia externă ca informaţia care poate fi dedusă despre un document, dar care nu este conţinută de acesta. Exemple de meta informaţie externă includ aspecte precum reputaţia sursei, frecvenţa actualizării, calitatea, popularitatea sau uzajul si link-urile. Nu numai că sursele posibile ale meta informaţiei externe sunt variate, dar lucrurile care sunt măsurate variază de asemenea din punct de vedere al gradelor de importanţa. De exemplu, dacă se compară informaţia uzuală de pe o pagină gazdă importantă ca Yahoo, care primeşte zilnic milioane de accesări de pagini, cu un articol istoric obscur care poate fi accesat o dată la zece ani. n mod evident, aceste două aspecte trebuie tratate n mod diferit de un motor de căutare.
O altă diferenţă majoră ntre web şi colecţiile tradiţionale este aceea că, practic, nu există nici un control asupra a ceea ce pot publica oamenii pe web. Corelnd această flexibilitate de a putea publica orice cu influenţa considerabilă a motoarelor de căutare care pot afecta traficul (şi există diverse companii care manipulează deliberat motoarele de căutare pentru a obţine profit), ajungem la o problemă serioasă. Această problemă nu a fost pusă n cazul sistemelor tradiţionale de extragere de informaţii. De asemenea, este interesant de observat că eforturile depuse n cazul metadatelor au eşuat n cazul motoarelor de căutare, deoarece orice text de pe pagină care nu este direct oferit utilizatorului este supus manipulării efectuate de motoarele de căutare. Există chiar numeroase companii care s-au specializat n manipularea motoarelor de căutare n vederea obţinerii de profit.


4. Configuraţia sistemului

4.1 Scurtă descriere a arhitecturii Google

n această sectiune va fi o descriere despre modul de funcţionare al sistemului. n secţiunile următoare se va discuta despre aplicaţiile şi structurile de date care nu vor fi menţionate n această secţiune. Cea mai mare parte din Google este realizată n C sau C++ pentru eficienţă şi poate rula att n Solaris, ct şi n Linux.
n Google parcurgerea web-ului (descărcarea de pagini) este făcută de mai multe crawlere diferite. Există un server URL care trimite listele de URL-uri ce trebuie găsite de crawlere. Paginile web care sunt găsite sunt apoi returnate serverului de stocare, care le memorează. Acesta comprimă paginile şi le depune ntr-o bibliotecă. Orice pagină web are un număr de identificare numit docID, care este oferit ori de cte ori un nou URL este analizat şi extras dintr-o pagină web. Funcţia de indexare este realizată de indexer şi de sorter. Indexer-ul indeplineşte o serie de funcţii. Citeşte documentele din bibliotecă, decomprimă documentele şi le analizează. Fiecare document este convertit ntr-o serie de asocieri de cuvinte numite hit-uri. Acestea nregistrează cuvantul şi poziţia sa n document, aproximează dimensiunea fontului şi tipurile de litere folosite. Indexer-ul distribuie aceste hit-uri ntr-o serie de categorii, crend un index parţial dezvoltat de sortare. Indexer-ul mai ndeplineşte şi o altă funcţie importantă. Analizează toate link-urile din fiecare pagina web şi stochează informaţii importante despre acestea ntr-un fişier de link-uri. Acest fişier conţine informaţii suficiente pentru a stabili unde ne ndreaptă link-ul respectiv, precum şi textul link-ului.
Sistemul de analizare a URL-urilor citeşte fişierul de link-uri şi converteşte URL-urile relative n URL-uri absolute şi, respectiv, n docID-uri. Plasează textul link-ului n indexul iniţial care este asociat cu docID-ul la care se referă link-ul. Acesta generează de asemenea o bază de date de link-uri care nu sunt altceva dect corespondentele docID-urilor. Această bază de link-uri este folosită pentru calcularea PageRank-urilor pentru toate documentele.
Sorter-ul preia categoriile care sunt sortate de docID şi le clasifică după wordID pentru a forma un index complementar (inverted index). Un program numit DumpLexicon preia această listă mpreună cu lexiconul produs de indexer şi formează un lexicon nou care poate fi utilizat de searcher. Searcher-ul este rulat de un server şi foloseşte lexiconul construit de DumpLexicon mpreună cu indexul complementar şi PageRank pentru a răspunde ntrebărilor.




4.2 Structuri majore de date

Structurile de date ale Google sunt optimizate astfel nct o colecţie amplă de documente poate fi parcursă şi indexată cu puţin efort. Deşi CPU-urile şi majoritatea ratelor de input output s-au mbunătăţit de-a lungul anilor o simplă căutare pe disc tot necesită 10 ms pentru a fi realizată. Google este proiectat să evite acest gen de căutări de cte ori este posibil, iar acest lucru a avut o influenţă considerabilă asupra formatului structurilor de date.

4.2.1 BigFiles

BigFiles reprezintă fişiere virtuale care parcurg multiple fişiere de sistem şi care sunt operaţionale cu 64 de biţi integrali. mpărţirea ntre multiplele fişiere de sistem este realizată n mod automat. Aceste fişiere suportă de asemenea alocarea şi dealocarea descriptorilor de fişiere, din moment ce sistemele de operare nu oferă destul pentru ceea ce avem noi nevoie. BigFiles suportă şi opţiuni simple de comprimare.

4.2.2 Biblioteca (Repository)

Biblioteca conţine HTML-ul integral al fiecarei pagini web. Fiecare pagină este comprimată prin folosirea zlib. Optarea pentru o tehnică de compresie reprezintă echilibrul ntre viteză şi proporţia comprimării. S-a ales viteza zlib dintr-o serie de mbunătăţiri semnificative aduse comprimării de bzip. Rata compresiei bzip era de aproximativ 4 la 1 n bibliotecă, n comparaţie cu zlib care oferea o rată de 3 la 1. n bibliotecă, documentele sunt stocate unul după altul şi sunt prefixate de docID, precizndu-li-se lungimea şi URL-ul. Biblioteca nu solicită alte structuri de date care să fie folosite pentru ca aceasta să fie accesată. Acest lucru contribuie la consistenţa informaţiei uşurnd dezvoltarea; se poate reconstrui toate celelalte structuri de date doar din bibliotecă şi dintr-un fişier care listează erorile crawler-ului.

4.2.3 Indexul documentelor

Indexul documentelor păstrează informaţii despre fiecare document. Acesta este un index ISAM (Index sequential access mode) cu o lăţime fixă, ordonat de un docID. Informaţia conţinută de fiecare scurtă introducere include statutul curent al documentului, un indicator către bibliotecă, o evidenţă a documentului şi statistici variate. Dacă documentul a fost parcurs atunci conţine un indicator către un fiţier cu multe variabile numit docinfo şi care cuprinde URL-ul şi titlul documentului. n caz contrar, indicatorul se ndreaptă către lista URL-urilor care cuprinde numai URL-uri. Această hotărare de design a fost luată n conformitate cu dorinţa de a avea o structură compactă de date, precum şi cu abilitatea de stabili un record de accesare unică a discului n timpul unei căutări.
n plus, există un fişier care este folosit n convertirea URL-urilor n docID-uri. Acesta conţine o lista cu URL-uri mpreuna cu docID-ul corespunzător şi este sortat de sumă de control. Pentru a găsi docID-ul unui anume URL, suma de control a URL-ului este calculată şi o căutare binară este realizată pe fişierul de sume de control pentru identificarea docID-ului. URL-urile pot fi convertite n docID-uri lund mai multe simultan prin alipirea la acest fişier. Aceasta este tehnica pe care cel ce soluţionează URL-uri o foloseşte pentru a transforma URL-urile n docID-uri. Această metodă de abordare este importantă pentru că altfel trebuie să efectuam o căutare pentru fiecare link care, ţinnd cont de disc, ar dura mai mult de o lună pentru baza de 322 milioane de link-uri.

4.2.4 Lexiconul

Lexiconul are mai multe forme diferite. O modificare esenţiala adusă, spre deosebire de sistemele anterioare, este ca lexiconul să poate ajusta memoria la un preţ rezonabil. n implementarea actuală putem păstra lexiconul n memorie ntr-un sistem cu 256 MB de memorie. Lexiconul actual conţine 14 milioane de cuvinte (deşi cteva cuvinte rare nu au fost adăugate). Lexiconul are două parti: o listă de cuvinte (nşiruite mpreună, dar separate de zerouri) şi o serie de indicatori. Pentru a ndeplini diverse funcţii, lista de cuvinte are informaţii auxiliare care se aflş nsă dincolo de scopul acestei lucrări.

4.2.5 Listele de hit-uri (Hit Lists)

O listă de hit-uri corespunde unei liste de apariţii ale unui anumit cuvnt ntr-un document, incluznd informaţii despre poziţia, fontul şi tipul de literă folosit. Listele de hit-uri explică cea mai mare parte a spaţiului utilizat att n indicele primar (forward index), ct şi n indicele complementar (inverted index).
Din această cauză, este important să fie reprezente ct mai eficient posibil. Am luat n calcul mai multe alternative pentru poziţia de codificare, font şi tipul de literă – codificarea simplă (un grup de trei numere inetgrale), codificarea compactă (o serie de biţi optimizaţi manual) şi codificarea Huffmann. n final, am ales codificarea compactă optimizată manual deoarece necesită de departe mai putin spaţiu decat codificarea simplă şi mult mai puţină manipulare a biţilor dect codificarea Huffmann. Detalii despre aceste hit-uri sunt arătate.
Codificarea compactă foloseşte doi biţi pentru fiecare hit. Există două tipuri de hit-uri: hit-uri complexe (fancy hits) şi hit-uri simple (plain hits). Hit-urile complexe includ apariţia hit-urilor ntr-un URL, titlu, textul link-ului sau meta tag. Hit-urile simple includ restul. Un hit simplu constă dintr-un bit referitor la tipul de literă, marimea fontului şi 12 biţi de poziţii ale cuvntului ntr-un document (toate poziţiile ce depăşesc 4095 sunt catalogate 4096). Mărimea fontului este reprezentată relativ faţă de restul documentului utiliznd 3 biţi (doar 7 valori sunt de fapt folosite deoarece 111 este simbolul care semnalează apariţia unui hit complex). Un hit complex constă ntr-un bit referitor la tipul de literă, mărimea fontului este setată la 7 pentru a indica că este vorba de un hit complex, 4 biţi pentru codificarea tipului de hit complex şi 8 biţi de poziţie. Pentru hit-urile de tip anchor, cei 8 biţi ai poziţiei sunt mpărţiţi n 4 biţi pentru poziţie n link şi 4 biţi pentru conţinutul docID-ului n care link-ul apare. Aceasta ne oferă o sintagma redusă de căutare din moment ce nu există multe link-uri pentru un anumit cuvnt. Trebuie să se actualizeze metoda de stocare a hit-urilor anchor pentru permiterea unei rezoluţii mai mari n cadrul poziţiei şi cmpurilor de docID-uri. Se va folosi mărimea fontului n legătură cu restul documentului deoarece, atunci cnd căutam, nu dorim listarea diferită a unor documente identice doar pentru că unul din documente este scris cu un font mai mare.
Lungimea unei liste de hit-uri este stocată nainte chiar de hit-urile n sine. Pentru a economisi spaţiu, lungimea listei de hit-uri este combinată cu wordID-ul n indexul primar şi cu docID-ul n indexul complementar. Acest lucru o limitează la 8 şi respectiv 5 biţi (există o serie de trucuri care permit ca 8 biţi să fie imprumutaţi din wordID). Dacă lungimea este mai mare şi nu se poate ncadra n respectivii biţi, atunci un cod de rezervă este folosit n aceşti biţi, iar următorii 2 biţi vor conţine lungimea actuală.

4.2.6 Indexul primar (Forward Index)

Indexul primar este deja parţial sortat şi este stocat ntr-o serie de categorii (s-au folosit 64). Fiecare categorie conţine o serie de wordID-uri. Dacă un document conţine cuvinte care ţin de un anumit barrel, docID-ul este intregistrat n categorie urmat de o listă de wordID-uri cu liste de hit-uri care corespund cuvintelor respective. Această schemă necesită mai mult spaţiu de stocare din cauza docID-urilor duplicate, dar diferenţa este foarte mică pentru un număr considerabil de categorii şi economiseşte timp şi complexitate de codificare n faza finală de indexare făcută de sorter. Mergnd mai departe, n loc de a stoca wordID-urile actuale, se stochează fiecare wordID ca o diferenţă relativă de la wordID-ul minim care se găseşte n categoria n care se află şi wordID-ul. Astfel, se pot folosi 24 biţi pentru wordID-uri n categorii nesortate, lasnd 8 biţi pentru lungimea listelor de hit-uri.

4.2.7 Indexul complementar

Indexul complementar constă din aceleaşi categorii ca şi indexul primar, cu diferenţa că acestea au fost procesate de sorter. Pentru fiecare wordID valid, lexiconul conţine un indicator către categoria n care wordID-ul este inclus. Acest indicator se referă la o listă de docID-uri luate mpreună cu listele de hit-uri corespunzatoare. Această listă reprezintă toate apariţiile acelui cuvnt n toate documentele.

4.4 Indexarea Web-ului

— Analiza: orice sistem de analizare care este destinat să ruleze pe ntreg Web-ul trebuie să facă faţă unei mari cantităţi de erori posibile. Acestea se pot ntinde de la mici greşeli n sintagmele HTML pnă la kilobiţi de zerouri n mijlocul unei sintagme, caractere non-ASCII, sintagme HTML depozitate n interior şi o mare varietate de alte greşeli care pot provoca imaginaţia oricui pentru a-l determina să apară cu altele noi. Pentru viteza maximă, n loc să se folosească YACC pentru a genera un sistem CFG de analiză, se foloseşte un cablu electric pentru iniţierea unui analizator lexical which care se dotează cu propria informaţie. Dezvoltarea acestui sistem de analiză care rulează cu o viteză rezonabilă şi care este foarte solid a nsemnat un timp ndelungat de muncă continuă.
— Indexarea documentelor n categorii: după ce fiecare document este analizat, este codificat ntr-o serie de categorii. Fiecare cuvnt este convertit ntr-un wordID utiliznd un conţinut de tip in-memory (lexiconul). Adăugările care se fac conţinutului lexiconului sunt consemnate ntr-un fişier. Din momentul n care cuvintele sunt convertite n wordID-uri, apariţiile lor n documentul curent sunt traduse n liste de hit-uri şi sunt scrise n categoriile primare. Principala dificultate cu simultaneitatea fazei de indexare este aceea că lexiconul trebuie mpărţit. n loc de mpărţirea lexiconului, se scrie un logaritm pentru toate cuvintele auxiliare care nu se aflau n lexiconul de bază, care s-a fixat la 14 milioane de cuvinte. n acest fel, indexer-ele multiple pot rula n paralel şi apoi fişierul 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 primară şi o sortează după wordID pentru a produce o categorie complementară pentru titlu şi hit-urile de tip anchor şi o categorie complementară de text integral. Acest proces se ntmplă cu fiecare categorie n parte, necesitnd astfel un spaţiu mic de stocare temporară. De asemenea, se compară faza de sortare pentru a utiliza ct mai multe sisteme posibile prin simpla rulare de sorter-e multiple, care pot procesa categorii diferite n acelaşi timp. Din moment ce categoriile nu sunt compatibile cu memoria principală, sorter-ul le subdivide mai departe n subcategorii care se potrivesc cu memoria bazată pe word ID şi docID. Apoi, sorter-ul ncarcă fiecare subcategorie n memorie, o sortează şi i transcrie conţinutul n categorii complementare mici şi n categorii complementare detaliate.O altă caracteristică importantă o reprezintă ordinea n care docID-urile trebuie să apară n listă. O soluţie simplă este să fie stocate n funcţie de docID. Acest lucru permite fuzionarea rapidă a diferitelor liste pentru ntrebările cu multe cuvinte. O altă posibilitate este să fie stocate n funcţie de apariţia cuvntului n fiecare document. Acest lucru implică lipsa de valoare a răspunsurilor la ntrebările alcătuite dintr-un singur cuvnt şi face posibil faptul că răspunsurile la ntrebările cu multe cuvinte să se afle chiar la nceput. Totuşi, fuzionarea este cu mult mai dificilă. De asemenea, acest lucru face ca dezvoltarea să devină mult mai dificilă, n sensul că o schimbare n funcţia de ordonare necesită o reconstruire a indexului. S-a ales un compromis ntre aceste opţiuni, prin păstrarea a două serii de categorii complementare - o serie pentru listele de hit-uri care include titlul sau link-ul şi o altă serie pentru toate listele de hit-uri. n acest fel, se verifică primul set de categorii şi dacă nu se găsesc destule potriviri n cadrul acestora se verifică şi cele mai mari.
Rularea unui crawler web reprezintă o provocare. Există acţiuni riscante şi subiecte sigure şi, mult mai important, există subiecte sociale. Parcurgerea (crawling) reprezintă cea mai fragilă aplicaţie din moment ce implică interacţiunea cu sute de mii de servere web şi nume de servere diverse care se află 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 oferă liste de URL-uri unui număr de crawlers (n general se folosesc n jur de 3). Att server-ul URL, ct şi crawler-ele sunt realizate n Python. Fiecare crawler ţine n jur de 300 de conexiuni (connections) deschise simultan. Acest lucru este necesar pentru regăsirea paginilor web la o viteza suficient de rapidă. La viteze mari sistemul poate să parcurgă peste 100 de pagini pe secundă utiliznd 4 crawlere. Acesta se ridică la aproximativ 600K de date pe secundă. O acţiune importantă este reprezentată de verificarea DNS. Fiecare crawler menţine un cache DNS propriu, astfel că nu este nevoie să se facă un control DNS nainte de parcurgerea fiecărui document. Fiecare dintre sutele de conexiuni se poate afla n stadii diverse: verificarea DNS, conectarea la gazdă, transmiterea solicitărilor şi primirea răspunsurilor. Aceşti factori fac din crawler o componentă complexă a sistemului. Acesta foloseşte IO asincron pentru a face faţă solicitărilor şi un număr de secvenţe pentru mutarea preluărilor de pagini din secţiune n secţiune.
Se adevereşte astfel că rularea unui crawler care se conectează la mai mult de jumătate de milion de servere şi care generează zeci de milioane de fişiere jurnal implică o cantitate considerabilă de e-mailuri şi apeluri telefonice. Datorită numărului mare de persoane care sunt online, există ntotdeauna aceia care nu ştiu ce este un crawler deoarece acesta este primul pe care l văd. Aproape n fiecare zi primim un mesaj de genul ‘V-aţi uitat la foarte multe pagini din site-ul meu. Ce parere aveţi despre el?'. Există de asemenea unele persoane care nu au aflat de existenţa protocolului de excluziune la roboţi şi se consideră că pagina lor ar trebui protejată mpotriva unei indexari de genul ‘Această pagina este protejată şi nu va fi indexată‘, care este dificil de nteles de crawler-ele web. De asemenea, din cauza cantităţii uriaşe de date implicate, lucruri neaşteptate se pot ntampla.
De exemplu, sistemul a ncercat să parcurgă un joc online.
Rezultatul a constat ntr-o mulţime de mesaje iritante chiar n mijlocul jocului. Se pare că aceasta a fost o problemă uşor de rezolvat. Dar această problemş nu aparuse pnă n momentul n care s-au descărcat zeci de milioane de pagini. Datorită variaţiei ridicate n paginile web şi n servere, este practic imposibil să testezi un crawler fără să-l rulezi pe o parte considerabilă a Internetului. Invariabil, apar sute de probleme obscure care se pot ivi pe o singură pagină din tot web-ul şi pot cauza distrugerea crawler-ului sau mai rău, poate cauza o reacţie imprevizibilă sau incorectă. Sistemele care accesează parţi mari din Internet trebuie să fie foarte solide şi testate cu multă atenţie. Din moment ce sistemele complexe cum sunt crawler-ele vor duce n mod invariabil la apariţia problemelor, trebuie să existe resurse semnificative dedicate citirii de e-mail-uri şi rezolvării problemelor din momentul n care acestea apar.

4.5 Căutarea

Scopul căutarii este acela de a oferi rezultate concludente n timp util. Multe dintre motoarele de căutare comerciale par să fi facut progrese considerabile din punct de vedere al eficienţei. De aceea, se pune accentul mai mult pe calitate.
Pentru marcarea unei limite a timpului de răspuns, odată ce un anumit număr de documente care se potrivesc cu interogarea (40.000 de obicei) este găsit, cel care a iniţiat căutarea poate accesa paginile.
Aceasta nseamna că este posibil ca rezultate neconcludente să fie oferite n schimb. n prezent, se investighează alte metode pentru rezolvarea acestei probleme. n trecut, s-au sortat hit-urile n concordanţă cu PageRank, lucru care pare să fi imbunătăţit situaţia.
4.5.1 Sistemul de clasificare

Google păstreaza mult mai multe informaţii despre documentele web dect motoarele tipice de căutare. Fiecare listă de hit-uri include poziţia, fontul şi informaţii despre tipul de literă folosit. n plus, se iau n calcul hit-urile după textul link-ului şi PageRank-ul documentului. Combinarea tuturor acestor informaţii ntr-un singur rezultat este dificilă. S-a conceput funcţia de ordonare astfel nct nici un factor particular să nu aibă o influenţă prea mare. Se iamai nti cazul cel mai simplu - o interogare cu un singur cuvnt.
Pentru afişarea unui document folosind o interogare cu un singur cuvnt, Google parcurge toate listele de hit-uri ale documentului pentru cuvntul respectiv. Google consideră fiecare hit ca aparţinnd unuia dintre diversele tipuri (titlu, link, URL, fonturi mari şi fonturi mici de text simplu etc.), fiecare dintre acestea avnd grade diferite de importanţă n funcţie de tipul din care face parte. Aceste grade de importanţă formează un vector indexat n funcţie de tip. Google numară hit-urile fiecărui tip din lista de hit-uri. Apoi fiecare poziţie este reorganizată ntr-un clasament n funcţie de importanţă. Gradele de importanţă cresc liniar n funcţie de primele poziţii, dar se reduc repede astfel nct este relevant numai un anume număr de apariţii. Se preia produsul scalar al vectorului de ponderi de apariţii mpreună cu vectorul de ponderi de tipuri pentru a calcula un scor IR al documentului. n final, scorul IR este combinat cu PageRank pentru a oferi un rezultat final al documentului.
Pentru o interogare alcatuită din mai multe cuvinte, situaţia este şi mai complicată. n acest caz, listele multiple de hit-uri trebuie parcurse simultan astfel nct hit-urile care sunt apropiate ntr-un document sunt plasate pe poziţii superioare faţă 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 calculează o apropiere. Această apropiere se bazează pe ct de departate sunt hit-urile n cadrul documentului (sau link-ului), dar este clasificată n 10 clase cu valori diferite, mergnd de la o sintagmă apropiata pnă la ‘nu foarte aproape'. Se fac contorizări nu numai pentru fiecare tip de hit, dar şi pentru fiecare tip şi apropiere. Fiecare pereche de tip şi apropiere are o pondere tip-apropiere. Contorizările sunt clasificate n funcţie de ponderile de apariţii şi se preia produsul scalar pentru ponderile de apariţii şi ponderile de tip-apropiere pentru realizarea unui scor IR. Toate aceste numere şi matrice pot fi afişate odată cu rezultatele căutării folosind o metodă specială de corectare. Toate aceste afişări sunt de foarte mare ajutor n dezvoltarea sistemului de ordonare.

4.5.2 Scurta recapitulare

Funcţia de ordonare are mulţi parametri precum ponderile de tip şi ponderile tip-apropiere. Stabilirea valorilor exacte pentru aceşti parametri ţine de domeniul magiei. Pentru a face acest lucru, există un mecanism de feedback al utilizatorului n cadrul motorului de căutare. Un utilizator ncrezător poate evalua opţional toate rezultatele care i sunt returnate. Acest feedback este salvat. Apoi, cnd se modifică funcţia de ordonare, se observă impactul acestei schimbări asupra căutarilor anterioare care au fost ordonate. Deţi departe de perfecţiune, acest lucru ne face sa observăm cum o schimbare n funcţia de ordonare poate afecta rezultatele căutării.



5. Rezultate şi mod de funcţionare

Cea mai importantă caracteristică a unui motor de căutare este calitatea rezultatelor căutării. n timp ce o evaluare completă a utilizatorului se află dincolo de scopul acestei lucrări, experienţa cu Google a dovedit că este posibil sa se obţina rezultate mult mai bune pentru majoritatea căutărilor dect ale celor mai importante motoare comerciale de căutare. Dacă se caută ‘bill clinton' se obţin rezultate ce evidenţiază cteva dintre trăsăturile Google. Rezultatele sunt grupate de server. Acest lucru este de mare ajutor atunci cnd se examinează seturile de rezultate. O serie de rezultate sunt din domeniul whitehouse.gov, care reprezintă rezultatul aşteptat pentru o căutare de acest gen. n mod obişnuit, majoritatea motoarelor de căutare comerciale nu oferă nici un rezultat din whitehouse.gov, cu att mai puţin pe cele corecte. Trebuie observat că nici un titlu nu este afişat pentru primul rezultat, din cauză că nu a fost parcurs. n schimb, Google s-a bazat pe textul link-ului pentru a hotăr dacă acesta era un răspuns potrivit pentru ntrebare. n mod asemănător, al cincilea rezultat este o adresă de e-mail, care, binenţeles, nu poate fi parcursă (crawlable) şi care este, de asemenea, un rezultat al textului link-ului.
Toate rezultatele sunt pagini cu un nalt nivel calitativ şi, la o ultimă verificare, nici una dintre ele nu este un link irelevant (broken). Acest lucru se ntmplă din cauză că toate au un PageRank ridicat. PageRank-urile sunt marcate prin procentajele de culoare roşie. n concluzie, nu sunt rezultate despre un alt Bill n afara de Clinton sau despre un alt Clinton n afară de Bill şi asta pentru că se acordă o importanţă majoră aproximării sintagmelor n care apare un cuvnt. Binenţeles că un adevărat test al calităţii pentru un motor de căutare ar trebui să implice şi un studiu complet despre utilizator sau o analiză a rezultatelor.

5.1 Parametri pentru stocare

n afară de calitatea căutării, Google este proiectat să măsoare capacitatea Web-ului pe măsuă ce acesta se dezvoltă. Un aspect al acestui fenomen l reprezintă modul eficient de stocare. Datorită comprimării, mărimea totală a bibliotecii este de 53 GB, puţin peste o treime din totalul de date pe care le conţine. La preţurile actuale ale discurilor biblioteca poate fi considerată o sursă ieftină de date. Ceea ce este mai important - totalul datelor folosite de motorul de căutare necesitaă un spaţiu comparabil de stocare, adică n jur de 55 GB. Mai departe, un răspuns poate fi găsit pentru majoritatea interogarilor prin folosirea indexului complementar.




5.2 Modul de funcţionare a sistemului

Este important pentru un motor de căutare să parcurgaă şi să indexeze eficient. Astfel, informaţia poate fi permanent actualizată şi modificările majore aduse sistemului pot fi testate relativ repede. Pentru Google, operaţiunile importante sunt Crawling (parcurgerea), Indexing (indexarea) si Sorting (sortarea). Este dificil de măsurat ct a durat crawling-ul n total din cauză că discurile au fost n ntregime completate, numele serverelor nu mai sunt funcţionale sau din cauza oricărei probleme care putea determina oprirea sistemului. n total a durat cam 9 zile să se descarce cele 26 milioane de pagini (inclusiv erorile). Totuşi, din moment ce sistemul rula fluent şi mai repede, s-au descărcat ultimele 11 milioane de pagini n doar 63 de ore, n medie 4 milioane de pagini pe zi sau 48,5 pagini pe secundă. S-au rulat indexer şi crawler simultan. Indexer-ul a rulat mai repede dect crawler-ele. Aceasta s-a ntmplat din cauză că s-a petrecut destul timp pentru optimizarea indexer-ului astfel nct să nu determine ntrzierea dezvoltării sistemului. Aceste optimizări au inclus o serie de updatări ale indexului documentului şi plasarea structurilor precare de date pe un disc local. Indexer-ul rulează aproximativ 54 de pagini pe secundă. Sorter-ele pot fi rulate complet n paralel, utiliznd 4 sisteme, ntreg procesul de sortare durnd n jur de 24 de ore.

5.3 Procesul de căutare

mbunătăţirea procesului de căutare nu a reprezentat punctul principal de interes al cercetării al realizatorilor Google-ului pnă n acest moment. Versiunea curentă Google răspunde la cele mai multe din interogări ntre 1 şi 10 secunde. Acest interval este dominat n mare parte de IO-ul discului asupra NFS (din moment ce discurile sunt mpărţite pe sisteme diferite). Mai departe, Google nu are nici un fel de optimizare cum ar fi cache de căutări, subindici pe termeni comuni şi alte optimizări obişnuite. Intenţia lor este de a mări considerabil viteza Google prin distribuţie şi hardware, software şi mbunătăţiri algoritmice. Scopul este acela de a putea răspunde la mai multe sute de interogări pe secundă.







6. Concluzii

Google este proiectat să fie un motor de căutare scalabil. Scopul principal este acela de a oferi rezultate de calitate pe fondul dezvoltării rapide a World Wide Web. Google foloseşte o serie de tehnici pentru ameliorarea calităţii căutării incluznd page rank, textul link-ului şi alte informaţii apropiate. Mai departe, Google reprezintă o arhitectură completă pentru adunarea paginilor web, indexarea lor şi efectuarea de interogări asupra lor.

6.1 Activităţi viitoare

Un motor amplu de căutare este un sistem complex care rămne deschis completărilor. Scopurile noastre imediate sunt acelea de a imbunătăţi căutarea şi de a afişa aproximativ 100 de milioane de pagini web. Cteva mbunătăţiri simple aduse eficienţei includ cache de interogări, alocare optimizată a discului şi subindici. O altă secţiune care necesita o cercetare amanunţită este reprezentată de updatări. Trebuie să avem algoritmi potriviţi pentru a decide ce pagini mai vechi ar trebui reparcurse şi ce pagini noi ar trebui parcurse. O zonă promiţătoare de cercetare este aceea de a utiliza un cache proxy pentru construirea de baze de date cu scopul căutării din moment ce acestea sunt influenţate de cerere. Se plănuieşte adăugara de trăsături simple ce sunt suportate de motoarele comerciale de căutare cum ar fi operatorii de tip boolean, negaţia şi implicaţia. Totuşi, alte trăsături cum ar fi feedback-ul relevanţei şi clustere (Google suportă n mod obişnuit clusterele bazate pe numele de domeniu) de-abia acum ncep să fie explorate. Se intenţionează de asemenea susţinerea contextul de utilizator (cum ar fi locaţia utilizatorului) şi rezumarea rezultatelor. Apare şi preocuparea extinderii utilizării structurii de link-uri şi a textului link-ului. Experimentele simple indică faptul că PageRank poate fi personalizat prin amplificarea ponderii homepage-ului unui utilizator sau a bookmark-urilor acestuia. n ceea ce priveşte textul link-ului, se experimentează utilizarea textului link-urilor nvecinate alături de textul link-ului n sine. Un motor de căutare pe Web repezintă un mediu bogat pentru iniţiativele de cercetare.

6.2 Căutare la standarde nalte

Cea mai mare problemă cu care se confruntă astăzi utilizatorii de motoare de căutare o reprezintă calitatea rezultatelor pe care le primesc. Pe cnd rezultatele sunt deseori amuzante şi lărgesc orizontul utilizatorului, ele pot deveni şi frustrante şi pot consuma timp pretios. De exemplu, primul rezultat pentru o căutare ‘Bill Clinton' pe unul dintre cele mai populare motoare de căutare comerciale a fost Bill Clinton Joke of the Day: April 14, 1997. Google este destinat să ofere rezultate de o calitate superioară astfel ncat Web-ul să continue să se dezvolte rapid, iar informaţia să poata fi gasită uşor. Pentru a putea realiza acest lucru, Google utilizează frecvent informaţia hipertextuală ce constă din structura de link-uri şi din textul link-urilor. Google foloseşte de asemenea aproximarea şi informaţia despre fonturi. n timp ce evaluarea unui motor de căutare este dificilă, s-a aflat n mod intuitiv că Google returnează rezultate la un nalt nivel calitativ spre deosebire de motoarele comerciale de căutare. Analizarea structurii de link-uri prin PageRank permite Google să evalueze calitatea paginilor web. Utilizarea textului link-ului ca o descriere a ceea ce indică link-ul contribuie la relevanţă şi, ntr-o anumită măsură, la naltul standard calitativ al rezultatelor. n cele din urmă, utilizarea unor informaţii asemănătoare ajută la mărirea gradului de relevanţă al multor interogări.

6.3 Arhitectura scalabilă

n afară de calitatea căutării, Google este destinat să măsoare. Trebuie să dea dovadă de eficienţă att n spaţiu, ct şi n timp, iar factorii constanţi sunt foarte importanţi atunci cnd vorbim de Web. Prin implementarea Google, s-au observat ntrzieri n CPU, accesarea memoriei, capacitatea memoriei, căutările pe disc, conţinutul discului, capacitatea discului şi IO de reţea. Google a evoluat pentru a depăşi o serie din aceste probleme prin intermediul unor operaţiuni variate. Structurile majore de date ale Google utilizează n mod eficient spaţiul de stocare. Mai departe, operaţiunile de parcurgere, indexare şi sortare sunt suficient de eficiente pentru a construi un index al unei părţi substanţiale a Web-ului – 24 de milioane de pagini n mai puţin de o săptămnă.



Referinţe

Google Guide (2003) “How Google Works” Google Guide Retrieved 8 Sept, 2004 from: googleguide.com
Sullivan, R., (2004) “Google and Googlebot Information” searchengineposition.com Retrieved 8 Sept, 2004 from: searchengineposition.com
Brin, S., Page, L. (2000) “The Anatomy of a Large-Scale Hypertextual Web Search Engine” Retrieved 8 Sept, 2004 from: stanford.edu
Barroso, L. A., Dean, J., Hlzle, U. (2003) “Web search for a planet: The Google cluster architecture” Micro, IEEE, Volume: 23 , Issue: 2, pp.22-28 Ghemawat, S., Gobioff, H., and Leung, S. T., (2003) “The Google File System” SOSP’03, October 19–22
Traducere de pe pagina: http://wiki.media-culture.org.au/index.php/Google- How_It_Works.
Referat oferit de www.ReferateOk.ro
Home : Despre Noi : Contact : Parteneri  
Horoscop
Copyright(c) 2008 - 2012 Referate Ok
referate, referat, referate romana, referate istorie, referate franceza, referat romana, referate engleza, fizica