Pod maską Google'a

[pneuma]

Chip.pl napisał:

Pod maską Google'a

Najpopularniejsza wyszukiwarka świata jest przykładem na to, jak można zdobyć prymat nie marketingiem, ale technologią. A ta jest w Google'u imponująca.

Co jest główną zaletą Internetu? To oczywiste: ogrom informacji, do których mamy dostęp na każde nasze życzenie. A co jest główną wadą Internetu? To także jasne: ogrom informacji, z których nie zawsze potrafimy szybko i sprawnie wyłowić to, co jest nam potrzebne. Właśnie ten problem próbują rozwiązać Larry Page i Sergey Brin, twórcy wyszukiwarki internetowej Google. 

      Obecnie w swoich bazach Google (nazwa usługi pochodzi od angielskiego słowa googol, które oznacza liczbę 10100) przechowuje informacje o 6 miliardach obiektów, w tym 4,3 miliarda stron WWW, 880 milionów obrazków oraz 850 milionów wiadomości z grup dyskusyjnych. Wszystkie te liczby robią wrażanie, a dodając do tego nowatorski i skuteczny system sortowania informacji, otrzymujemy odpowiedź, dlaczego Google jest obecnie najbardziej popularnym wśród internautów serwisem wyszukiwawczym.

Rys. 1. Szybkie i sprawne działanie Google zawdzięcza specyficznej architekturze. System został zrównoleglony i poszczególne zadania przypisano różnym grupom komputerów. Szczegółowy opis: patrz tekst obok ("Google pod mikroskopem")

Liczy się pomysł 

W ostatnich kilku latach wraz z rozwojem Internetu rozrastały się też wyszukiwarki internetowe. Wystarczy porównać następujące wielkości: pierwsza usługa tego typu z 1994 r. (World Wide Web Worm) w swojej bazie przechowywała informacje o 110 tysiącach stron. W roku 1997 najlepsza ówcześnie wyszukiwarka (Web-Crawler) zawierała już wyrazy z 2 milionów dokumentów. Równocześnie drastycznie wzrastała liczba zapytań. W 1994 wynosiła ona 1500 na dobę, a w 1997 AltaVista obsługiwała około 20 milionów pytań dziennie. Dzisiaj liczba ta przekracza setki milionów! 

      Wydaje się, że znalezienie czegokolwiek w tak potężnej bazie danych powinno zajmować co najmniej kilka minut. Jednak nic bardziej błędnego. Google zwraca nam rezultat każdego wyszukiwania w czasie krótszym niż sekunda! Zaprojektowanie tak wydajnego systemu jest dużym wyzwaniem. Wystarczy uświadomić sobie, jak ogromna jest to masa danych oraz ile zapytań do bazy będzie generowanych w każdej minucie działania systemu. Jak Google radzi sobie w tych warunkach? 

      Najważniejszym problemem jest jednak sortowanie wyników wyszukiwania. Przeciętnie użytkownik zwraca uwagę tylko na pierwsze dziesięć odsyłaczy, pomijając pozostałe. Właśnie dlatego tak ważne jest, żeby informacja, do której chcemy dotrzeć, pojawiała się jako pierwsza, a dodatkowo żeby była to informacja dla nas wartościowa. Tutaj pojawia się odkrywcza myśl twórców Google'a. Zauważyli oni mianowicie, że o tym, czy dana strona jest cenna oraz czy warto ją promować, świadczą m.in. odsyłacze prowadzące do niej z innych stron WWW. W ten sposób stworzyli algorytm PageRank, który nadawał odpowiedni priorytet wynikom wyszukiwania. Im więcej odnośników do danego dokumentu istnieje w Internecie, tym wyższy priorytet on otrzyma. PageRank dla strony 

A można obliczyć, stosując następujący wzór: 

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

Zakładamy, że do pliku A prowadzą odsyłacze ze stron od T1 do Tn, d to współczynnik, który może przyjmować wartości od 0 do 1, zazwyczaj ustawiany jest na 0,85, a C(A) to liczba odnośników prowadzących z dokumentu A. Skąd wziąć wartości PR dla stron składowych? Gdybyśmy chcieli je obliczyć, otrzymamy układ 4,3 mld równań z 4,3 mld niewiadomych. Jego rozwiązanie jest oczywiście niemożliwe. Dlatego nie da się precyzyjnie określić wartości PageRanku dla wszystkich dokumentów. Nie ma jednak takiej potrzeby. Internet bowiem cały czas się zmienia. Problem rozwiązano następująco: na początku wszystkim dokumentom nadano identyczne wartości PR, później na tej podstawie obliczono współczynniki i... zaczęto obliczanie od nowa. W ten krokowy sposób można uzyskać współczynniki bliskie rzeczywistości.

Rys. 2. Jednym z ciekawszych serwisów Googl'a jest Froogle - narzędzie do wyszukiwania ofert sklepów internetowych

tabela parametrów

a reszta materiału jest

cześci - 2 - 3 - 4

[michal]

a tu naprawde jak dziala technologia Google https://www.google.com/technology/pigeonrank.html

[Yrek]

hahaha.

Isn't it cruel to keep pigeons penned up in tiny data coops?

Google exceeds all international standards for the ethical treatment of its pigeon personnel. Not only are they given free range of the coop and its window ledges, special break rooms have been set up for their convenience. These rooms are stocked with an assortment of delectable seeds and grains and feature the finest in European statuary for roosting.