Byl bych rad, kdyby se vic rozebraly veci kolem prohledavani. Protoze vim jenom neco, ptam se tech, kteri vedi vic.
Gatherer (smatrac v obsahu serveru) stahuje data a uklada je na disky podle urcitych pravidel (napr. nemusi stahovat zdaleka vsechen text). Kazda webovska stranka je v gathereru nejak prezentovana (provazne indexovane male soubory s ruznymi informacemi).
Pokud se takhle stahne 500 milionu stranek (dejme tomu, ze na kazdou padne po ostrouhani zbytecnych informaci a rozdeleni do nekolika malych souboru v prumeru 5 KB), pak gatherer na ulozeni potrebuje 2,500 GB, tedy 2,5 TB. Po stazeni dat z Inetu nastava stavba indexu brokeru. Jaka je jeho vysledna velikost pri pouziti ruznych postupu, nevim. Ale vim, ze muze byt i priblizne stejna, jako rozsah nasmatranych dat (i pri pouziti hashingu).
Moje prvni otazka zni - pro Page Rank se pripravuje pole uz v gathereru (coz bych docela predpokladal) a pak se z gathereru nasledne vytahuji data pro Page Rank (coby mezifaze), nebo se vsechno pusti az na sestaveny index brokeru, nebo jinak?
Druha otazka - jak dlouho muze trvat prevedeni onech nejakych 2,5 TB nasmatranych dat do indexu, bezicim na spouste diskovych poli? Podotykam, ze vim, ze doba stavby indexu treba ze 4 GB muze trvat nekolik hodin na stredne rychlem pocitaci se SCSI.
Zpracovavani dat je vyhodne delat co nejvic davkove - tedy vzdy pro co nejvic dat najednou. Z toho duvodu pouzivaji mne zname vyhledavace postup, ze nejdriv vse stahnou, pak vse zpracuji.
K prvni otazce: Podle me je vhodne generovat databaze s linkovou strukturou uz za behu crawleru (gathereru), protoze crawler ji ke svemu behu beztak potrebuje. A PageRank bych pocital az nakonec, stejne jako reverzni databaze.
A k druhe: Stavba indexu (pokud myslite to, cemu rikam reverzni databaze, tedy prirazeni jednotlivym slovum seznam dokumentu) je take vec pomerne jednoducha a muzete pouzit stejny postup vypoctu jako ja v clanku: 4GB se prectou z disku za 4 minuty, pak totez musite zapsat, a nejspis bude vypocet tak na 2 pruchody, vynasobite tremi aby se nereklo... dohromady to podle me bude asi pulhodina. (diskove pole jsem neresil, vyse uvedene se tyka spis mensiho indexu, napr. ceskeho).
Pokud mate na mysli stavbu indexu s obri RAM (tedy s mensim naporem na vypocty na disku), pak budiz. Bez takove RAM je vsechno ponekud jinak (muj priklad se 4 GB dat se tykal cca 128 MB RAM, coz jsem zapomnel uvest).
Je tady nekdo, kdo by neco rekl k rozdelovani nasmatranych dat do indexu s velkym poctem diskovym poli?
Muj vypocet nejake obri velikosti RAM nevyzadoval, pro prakticke vyuziti tak 256MB a vic.
Pouzitim diskovych poli se podle me nic nezmeni. Pod unixy si jednotlive pocitace namapujete jako NFS a pristupujete k nim jako k jedinemu. Rozlozit databazi na vic souboru jste musel i v prikladu s 4GB (protoze FS mivaji omezeni na 2GB na soubor), takze kdyz nektere z rozlozenym souboru budou symlinky na uplne jiny stroj, algoritmus to ani nepozna.
Jak pise autor, lze jednu iteraci provest relativne rychle a protoze je to pasova ridka matice, dava vetsina metod rychlejsi vysledky nez u hustych matic - pokud ale konverguji. Prilis se touhle oblasti nezabyvam a nevim, jake metody se pouzivaji (to by byla jiste zajimava otazka, odpoved na ni ale asi bude soucasti "vyrobniho" tajemstvi vyhledavace) ale u vetsiny iteracnich metod pro reseni soustav jsou dany striktni podminky, za nichz lze ocekavat konvergenci a kdy metody konverguji dobre ci spatne. Urcite je dulezita regularita matice, pro metody je pak vetsinou vyznamna predevsim podminenost matice vyjadrena pomerem min. a max. vlastniho cisla. Muze to pak mit i vliv na rychlost - je sice hezke, ze mi jeden cyklus probehne dosti rychle, ale kdyz je matice spatne podminena tak potrebuji cyklu velmi mnoho, abych se dostal na pozadovanou uroven presnosti (nebo se na ni nikdy nemusim dostat). Protoze jsou tyto parametry nezname (tedy - urcite mne, ale asi i autorovi), je cela diskuse nad rychlosti atp. relativne bezpredmetna - chtelo by to nejakou solidni teorii, ktera by o takto vzniklych maticich dokazala zakladni predpokady pro pouziti iteracnich metod, aby bylo mozno pouzit ty opravdu nejrychlejsi a predikovat tak rychlost konvergence.
Existuje?
Mozna ze ano, mozna ze by bylo zajimave o tom neco napsat.
Fakt je, ze empiricke poznatky jsou takove, ze ve vetsine pripadu to funguje pekne a tak se to pouziva, i kdyz podminky metod neni mozne zarucit - coz je ostatne relativne obvykly postup v praxi numericke matematiky.
Je dokazano, ze rovnice pouzivana PageRankem konverguje, pokud je graf silne propojeny (existuje cesta z kazdeho uzlu do kterehokoliv jineho). Tato podminka neni u www splnena, ale ve stredu webu existuje velka silne propojena komponenta, takze to nevadi.
Otazka na pocet iteraci je spravna. Vemte to takto: Po prvni iteraci mame stejny vysledek, jako bychom pocitali pocet odkazu, ktere na danou stranku smeruji. To samo o sobe je docela uzitecna informace. Po druhe iteraci bude vysledek znatelne lepsi. Po 3-4 uz mate neco, co vykazuje vsechny charakteristiky PageRanku. Google tusim udaval kdysi 20 iteraci, ted (se zvetsujicim se indexem) bude asi pouzivat min.
Diky za informaci. Neni mi ale jasne, jak se vybiraji ty "silne propojene" body (pokud se vubec vybiraji), aby byla konvergence zarucena - domnivam se, ze se nevybiraji (jak by se pak mohlo vyhledavat na vsech strankach, kdyby u nejakych chybel PageRank, ze...), ale diky tomu, ze cele reseni zaplatpanbuh nevykazuje znaky nestability (doslova - to tezko asi nekdo jiny ovlivni 8^)), neprojevuji se chyby nejakymi drastickymi divergencemi. Je to asi zpusobeno tim, ze ty uzly, ktere maji ve vypoctu vetsi vahu jsou prave ty "vice propojene", ktere zarucuju "zestabilnovani" metody... Je to krasne, jak ta priroda funguje!!!
Presne tak, v silne propojene casti grafu jsou vyssi PageRanky, ty pak ovlivnuji zbytek grafu. Ty uzly (stranky), z kterych nevedou zadne odkazy ven, pusobi ale trochu problem - u Googleu tomu rikaji "rank sink" (neco jako vylevka) a optimalizuji algoritmus tak, ze tyto stranky pri prvnim vypoctu z grafu uplne vyhodi.
Nicmene, kdyz tuto optimalizaci neprovedete, nic hrozneho se nestane, akorat nemate zajistenou konvergenci...
ČLÁNKY DO MAILU