Systémy pro stahování dat z webu

Systémy pro stahování dat z webu Leo Galamboš Ústav bezpečnostních technologií a inženýrství, FD ČVUT v Praze Konviktská 20, 110 00 Praha 1 [email protected]

Procházení a stahování dat z webu je dnes samostatnou disciplínou, která vychází z řady teoretických i empirických poznatků a úzce souvisí s praktickou konstrukcí odpovídajících nástrojů. Webové crawlery jsou pak programy určené pro procházení a dávkové stahování webových stránek1, tzv. crawling. Využití nalézají především v systémech webových vyhledávačů, ale slouží i pro archivování nebo monitorování webu, případně jsou používány jako nedílná součást systémů pro dolování dat (informací) z webu. Ve velkých webových vyhledávačích opatřují data pro indexátor. Zajišťují, že je indexovaný obsah co nejvěrnější kopií aktuální podoby webu. Ve vertikálních vyhledávačích se specializují pouze na specifický obsah, například stránky zaměřené na zpravodajství, technické články, e-shopy apod. U „Business Intelligence“ systémů se rovněž zajímají jen o malou část webu, v tomto případě vymezenou například klíčovými slovy (čísla patentů, označení copyrightů, názvy firem) nebo obecnými zájmovými oblastmi, například letectvím nebo vojenskou technikou. Důvod existence crawlerů je zřejmý. Na webu je k nalezení mnoho informací, ale dopředu nevíme, kde přesně jsou. K jejich lokalizaci tedy nepřímo slouží crawlery, které zájmové oblasti stáhnou a předají k dalšímu zpracování. Tento článek by měl odpovědět na následující základní otázky:  Jaká je obvyklá architektura crawleru?  Jaké lze dosáhnout skutečné výkony stahování a co je ovlivňuje?  Jaké operace lze požadovat po crawleru, a jak to ovlivňuje kvalitu získávaných dat?  Jaké jsou otevřené problémy a směry vývoje? Osobně se často setkávám s představou „prostě ten web nějak stáhnu“ nebo „vezmu nějaký program a ono mi to stáhne, co potřebuji za 2 dny“. Bohužel, realita je často jiná. Mnoho zajímavého obsahu nelze obecně dostatečně efektivně stahovat, nebo jej nelze stahovat v takovém formátu, jak bychom chtěli. Například webové diskuze ve formě svodek, mnohé JavaScriptové nebo AJAX aplikace, HTML5 prezentace, atd. Vše je dáno tím, že crawler je silně optimalizovaný systém, který nemůže provádět složité výpočty a uvažování jak pokračovat dále. Navíc „vidí“ jen malý výhled, nemá ihned k dispozici celý zajištěný obsah a už vůbec nad ním nemůže spouštět komplikované dotazy nebo výpočty. To samozřejmě souvisí i s prostorem, ve kterém se musí crawlery pohybovat. Webový prostor Web není centrálně spravované úložiště, ale skládá se z miliónů nezávislých poskytovatelů obsahu. Jeho zpracování vyžaduje agregaci. Jsou možné dvě základní strategie: pull - data se stahují k agregátoru; a push - obsah je dodáván pomocí speciálních protokolů od 1

Stránkou v tomto článku chápeme datový obsah umístěný na konkrétním URL.

J. Genči, P. Šaloun (eds.), DATAKON 2012, Mikulov, 14-16.10.2012.

Systémy pro stahování dat z webu

poskytovatelů obsahu k agregátoru. V praxi se osvědčil pull model, který dal za vznik crawlerům. Jejich architektura je silně závislá na dynamice webu, zvláště pokud musí zajišťovat aktuální obsah. Kvůli pull přístupu totiž postrádají informace o tom, co se kde v jaký čas přesně změnilo. Existuje mnoho studií, které se dynamice webu věnují, vyjděme jen z několika základních informací [1, 11, 14, 15, 17]:  Nové stránky vznikají s 8% přírůstkem za týden, nové odkazy s 25%.  Během týdne se změní 33% stránek.  Za rok zmizí 80% stránek, stejně jako odkazů.  Až 90% nových stránek lze získat monitoringem malého počtu "starých stránek", zbytek (10%) se získává mnohem obtížněji.  Události změn stránek jsou pokryty Poissonovým procesem, tj. změny probíhají náhodně a nezávisle, alespoň u stránek modifikovaných denně. Z konstrukčního pohledu jsou pak ještě zajímavá i tato zjištění:  Změny stránek lze rozdělit do několika značně silných vrstev stránek modifikovaných: do hodiny, hodinově, denně, týdně, měsíčně, ročně. Z tohoto poznatku vyplývá, že není nutné zjišťovat přesnou frekvenci změn, postačí nám vytvoření několika málo priorit pro stahované stránky.  Frekvence změn je stabilní v čase, takže předchozí frekvence změny určuje i budoucí. Opět, není nutné sledovat kompletní historii změn, stačí několik málo posledních časových údajů o změně. Dobrý crawler by měl být schopen posoudit i dopad změny. Mnoho stránek obsahuje například reklamní poutače, které se mění při každé návštěvě. Kvůli takovým stránkám není nutné zvyšovat frekvenci návštěv a zbytečně bychom se ochuzovali o stahování hodnotnějšího dynamického obsahu. S efektivním průchodem webu souvisí i schopnost crawleru stahovat nejdříve zajímavý obsah. Jeho hodnota může být dána například známým PageRankem. Z pohledu crawleru to ale představuje určitý problém, neboť PageRank se počítá iterativně a není k dispozici „okamžitě“. Proto se hledaly různé aproximace. Jedna z nich vychází ze vstupního stupně (indeg) uzlu webového grafu. Tuto hodnotu může crawler velice snadno počítat. Je však otázka, zda podobnost distribuce hodnot indeg a PageRank (Obr. 3.1) znamenají, že uzly s velkým indeg mají i velký PageRank.

Obr. 3.1: Indeg a PageRank v doméně mff.cuni.cz. Negativní odpověď dává pro malé webové oblasti hned několik prací [4, 22]. Naopak u větších grafů se tato hypotéza zdá být pravdivou [30].

Tutoriál

Celkový závěr je proto nejasný. Většinou se dnes ale stahují velké webové oblasti, a proto mohou mnohé současné crawlery tuto aproximaci bez obav uplatnit. Crawlery Základní algoritmus, na kterém crawler pracuje, je jednoduchý. Stáhnou se všechny stránky na známých URL, z nich se vyextrahují další URL, a tento postup se může libovolně-krát opakovat. Algoritmus však naráží na několik praktických problémů. Web je velký, neustále se mění, a proto je obtížné stáhnout všechny známé URL. Velké pokrytí a čerstvost vyžadují obrovský datový průtok, což je příčinou mnoha implementačních problémů. Nezbytnou podmínkou pro provoz crawleru je jeho slušnost (zdvořilost), tj. nemělo by docházet k přetěžování cílů velkým počtem připojení nebo žádostí o stránky. Postupem doby byl vytvořen neoficiální standard robots.txt2. Ten umožňuje, aby sám cíl (zdroj stránek) specifikoval, které stránky může crawler procházet a jakou frekvenci návštěv má volit. Příslušné specifikace jsou potom přístupné na URL adresách tvaru http://servername/robots.txt ve formě textového souboru. Před přístupem k serveru zdvořilý crawler tuto specifikaci stáhne a posoudí, zda jsou jeho požadavky v souladu s přáním navštíveného serveru. Zde se liší více a méně sofistikované crawlery. Konstrukčně jednodušší systémy si tyto specifikace stahují vždy před přístupem k danému serveru (například seznambot/3.0), profesionální systémy je naopak kešují a stahují je například jen jednou za 24 hodin (například googlebot/2.x), což je pochopitelně efektivnější. Pro průchod webovým grafem je možné použít dvě základní strategie: do šířky, kdy se známé URL organizují do FIFO front, a do hloubky, kdy jsou fronty organizované pomocí LIFO. Organizování front pomocí FIFO je rozumné, pokud disponujeme vhodnou množinou výchozích URL a naším cílem je se držet v okolí. Druhá varianta (LIFO) se v praxi nepoužívá, neboť hrozí pád crawleru do pasti. Past na crawler je obecně nekonečný počet (většinou dynamicky generovaných) provázaných stránek. Vzniká tak cesta libovolné délky. Podobná situace nemusí vzniknout záměrně. Past vznikne i cyklickým zanořením nějakého webového adresáře, především chybou v konfiguraci WWW serveru. V praxi se můžeme na webu potkat i s tzv. SPAMem. Jedná se o stránky, které obsahují falešný nebo matoucí obsah. Jejich cíl je typicky buď oklamat uživatele, nebo přinejmenším velké webové vyhledávače a jejich vyhodnocovací funkce. Do této kategorie spadá jak linkSPAM (vytváření umělých klik a HUBů s cílem navýšit váhu stránek), tak i podvržení oblíbených klíčových slov. Tuto kategorii SPAMu žádný veřejně známý crawler neřeší, je to součást až návazných komponent nebo administrace příslušného vyhledávacího systému. Existuje ještě další kategorie SPAMu – cloaking. Ten je založen na tom, že se obsah stránky mění dle User-agent položky HTTP žádostí. Crawlery tak mohou obdržet zcela jiný obsah než webový prohlížeč nějakého uživatele. S tímto problémem si dokáží poradit sofistikované crawlery, které nejen používají vhodnou User-agent identifikaci, ale rovnou maskují svůj průchod „simulací“ živého uživatele jako to dokáže systém Akula, představovaný v sekci 3.5. Dokáží tak získat reálný obsah stránek, i když je to vykoupeno větší náročností implementace v plánovacím algoritmu crawleru. Efektivitu crawleru ovlivňuje vhodné využití dostupných zdrojů, vyhnutí se crawlovacím pastem a duplicitnímu obsahu, tzv. zrcadlům. Jinými slovy, dobrý crawler se nesnaží stáhnout vše a mít vše aktuální, ale zaměřuje se primárně na hodnotný obsah. Je jen věcí konkrétní implementace, zda se zaměří na procházení s cílem získat co největší

2

http://www.robotstxt.org/


pokrytí, nebo na co největší čerstvost, nebo na kombinaci obojího. Z toho pak vyplývají mnohé problémy a zásadní rozdíly ve schopnostech jednotlivých crawlerů. Deep-web Zdaleka ne všechny stránky jsou přístupné procházením všech dostupných odkazů. Někdy je zapotřebí aktivní činnost na straně crawleru, například vyplnění formuláře nebo provedení JavaScriptu (typicky u technologií typu AJAX). V této oblasti, označované jako deep-web, je pak několik problémů. Crawler musí být schopen analyzovat kontext vstupního formuláře, provést smysluplné vyplnění, a nakonec zanalyzovat odpověď. V případě JavaScriptu je situace ještě komplikovanější, neboť by mělo dojít k analýze JavaScriptového kódu, detekci stavů aplikace a následně systematickému krokování a stahování dat. Tyto oblasti jsou stále předmětem výzkumu [18, 24]. V konkrétních případech se můžeme obejít i bez komplikovaných nástrojů. Například ČVUT zpřístupňuje mnoho údajů v deep-web oblastech. Ukažme si na příkladu, jak taková data strojově získat. Naším cílem je seznam e-mailových adres studentů FIT ČVUT, prakticky bychom si ale mohli vybrat libovolnou cílovou skupinu (fakultu, zaměstnance, apod.). Fronty crawleru nahradíme pouhými UNIXovými rourami. Finální podobu kódu obsahuje Program 3.1. echo –e 'facultyProfile=FIT&ctuRelation=STUDENT&firstname=adam\n---' | lynx -dump -listonly -post_data https://usermap.cvut.cz/search/advanced | grep usermap.cvut.cz/profile | cut -c 7- | xargs -I '{}' -n 1 lynx -dump -listonly '{}' | grep mailto | cut -f 2 -d':' | grep '@' | sort -u

Program 3.1: One-liner hack na získání emailových adres z adresáře ČVUT. Program zašle šifrovaným spojením vyplněný formulář „vyhledávání osob“ s hodnotami pro vyhledání mezi studenty v rámci FIT ČVUT. Jméno hledaného studenta je „adam“. V praxi bychom pochopitelně zaslali celou sérii dotazů na všechna předpokládaná jména. Z výsledného seznamu výsledků získáme seznam „domácích“ profilových stránek každého z nalezených studentů a všechny tyto stránky rovněž stáhneme (via xargs/lynx příkaz). V takto stažených stránkách se již snadno najdou odkazy „mailto“, ze kterých nakonec vyextrahujeme požadované emailové adresy a seřadíme je, abychom se zbavili všech duplicitních. Je snadné rozšířit program tak, aby se choval jako zdvořilý crawler a stahoval například jen jednu stránku za sekundu. Podstatnější je ovšem poznatek, že ruční nebo poloautomatické stahování dat z deep-webu není obtížné. Pro strojové stahování je ovšem problémem pochopit sémantiku položek formuláře a strukturu výsledku. Stroj je většinou odkázán jen na několik pokusů, ze kterých se snaží pochopit funkci neznámého formuláře. Z toho plyne i myšlenka spolupracujících crawlerů, z nichž každý vyzkouší své postupy a centrální crawler potom pouze zvolí nejvhodnější z nich, respektive pokračuje odkazy, které mu rozkryl úspěšný z crawlerů. K tomuto postupu se ještě vrátíme později v hlavní části článku, v sekci 3.5. Popsaný přístup má však několik technických úskalí. Především průchod do deep-webu může automaticky iniciovat nastavení cookies. Jedná se o hodnoty, které by měl webový prohlížeč (v našem případě crawler) posílat spolu s dalšími žádostmi o stránku. Pokud je

Tutoriál

nepošle, nebo pokud vyprší jejich platnost, je nutné znovu projít do deep-webu a příslušné cookie obnovit. Těmto technickým detailům se podrobněji nebudeme věnovat, pouze musíme mít na zřeteli, že centrální crawler nemůže být jen běžným crawlerem a musí s takovými eventualitami počítat. To vše pak komplikuje jeho implementaci. Efektivitu práce crawlerů deep-webu je vhodné posuzovat s ohledem na počet žádostí, které potřebují na získání určitého množství informací. Prakticky není reálné zkoušet všechny možnosti vstupu, neboť by to vyvolalo nechtěnou reakci cíle, typicky omezení přístupu. Proto se uplatňují metody, které vedou k rozdělení vstupních parametrů na skutečné a formátovací [24] a prohledávaný prostor formulářových šablon se tak výrazně omezí. V neposlední řadě je zajímavé i srovnání deep-webu s jeho povrchovým protějškem. Podle studie brightplanet.com jsou deep-web stránky v průměru o 27% menší. Na druhou stranu jich existuje přibližně 500x více jak stránek v povrchových oblastech. Struktura této kapitoly Z úvodních poznatků vyplývají dva hlavní požadavky na crawler. Zaprvé, musí být schopen obejít pasti a být zdvořilý. Zadruhé, měl by být distribuovaný s možností téměř lineárního růstu vůči počtu výpočetních uzlů, resp. dostupné šířky pásma, dále by měl podporovat priority stahování stránek podle důležitosti (záměru uživatele) a měl by být dostatečné modulární. V sekci 3.1 diskutujeme základní architekturu takového crawleru, zmíníme kritická místa a zavedeme některé pojmy z oblasti distribuovaných crawlerů. Teoretické poznatky o webu, které mají vliv na konstrukci crawleru, obsahuje sekce 3.2. Implementační problematice je věnována sekce 3.3 a aktuální směry vývoje představuje sekce 3.4. Zkušenosti z implementace a provozu prototypového systému Akula jsou pak obsahem sekce 3.5. 3.1

Architektura a klasifikace crawlerů

První z veřejně dostupných vzorových architektur crawleru bylo řešení systému Mercator (Compaq) [20]. Výchozím bodem je seznam známých URL adres, ze kterého selektor vybírá URL určené ke stahování. Jakmile se podaří opatřit příslušnou stránku, je získán seznam obsažených URL adres. Tyto seznamy projdou eliminací jak již známých URL, tak i duplicitních URL (eliminace zrcadel) a dostanou se do výchozího seznamu (nyní) známých URL. V případě distribuovaného systému popsaný algoritmus pracuje na každém zúčastněném uzlu, přičemž prochází jen určitou vymezenou oblast webu přidělenou právě danému konkrétnímu uzlu. Proto je možné seznam nalezených URL snadno distribuovat, a transformovat jednouzlové řešení na poměrně dobře škálovatelný distribuovaný systém (Obr. 3.2).


Seznam stahovaných URL adres

Eliminace duplicitních

Seznam známých URL adres

Selektor

Stahování

Eliminace známých

Redistribuce mezi zúčastněnými uzly

Seznam nalezených URL adres

Parsování

Obr. 3.2: Základní architektura crawleru. V takto popsané architektuře existuje několik kritických míst, které mají přímý dopad na výsledný výkon crawleru: 1. Externí datová struktura pro ověření, zda je URL známé, tzv. URL-seen test (UST). 2. Proces odstranění duplicitních URL, tzv. duplicate URL eliminator (DUE). 3. Datové struktury (typicky fronty) obsluhující seznam známých URL adres. 4. Zajištění vhodného časování, aby nedocházelo k vypršení cookies. Způsob jejich zvládnutí se liší podle typu crawleru, přičemž rozlišujeme dvě základní kategorie: dávkový a inkrementální crawler. Pro obě tyto kategorie lze postavit odpovídající implementace nad zmíněnou architekturou. Dávkový crawler Dávkový crawler slouží k vytvoření jednoho nebo více statických snímků webové oblasti. Prochází odkazy od iniciálních bodů, přičemž (ve většině implementací) neprovádí opakované návštěvy v rámci sběru jednoho snímku. Typický dávkový crawler vybere množinu známých URL adres, které ještě v rámci pořizovaného snímku nestáhl, a pošle ji stahovacím jednotkám. Vznikne seznam nově objevených URL, který se ale v rámci pořizování jednoho snímku nemusí okamžitě slévat se seznamem (dosud) známých URL adres. Proces se opakuje do té doby, dokud nevyprší čas nebo není sesbíráno určité množství stránek. Při tomto typu sběru je výhodné začít s dostatečně velkou množinou iniciálních bodů. Typicky se jedná o seznam URL z nějakého webového katalogu, například DMOZ Open Directory. Je rovněž možné použít URL adresy z předchozího snímku, včetně nově objevených. Celkově je tento typ crawleru robustní, a zároveň i jednoduchý. Proces eliminace známých URL (za pomoci UST) může probíhat až úplně na závěr, čímž se výrazně šetří nároky na zatřiďování nových adres. Stejně tak je možné provádět eliminace duplicitních URL až po skončení sběru jednoho snímku, a před startem nového. To vše zjednodušuje vnitřní strukturu crawleru. Na druhou stranu je nutné, aby byla množina známých URL adres dostatečně veliká a operace restartování snímku kvůli tomu nemusela nastávat příliš často. To je jeden z hlavních důvodů, proč dávkové crawlery nestartují z malé množiny iniciálních URL.

Tutoriál

Je výhodné, pokud lze před startem sběru jednoho snímku uspořádat množinu URL adres podle vhodného kvalitativního faktoru. Poté je snadné dosáhnout poměrně efektivního sběru, například s ohledem na co největší sumu PageRanku nebo indeg sebraných stránek. Inkrementální crawler Inkrementální crawler nevytváří oddělitelné snímky, neboť kromě stahování nových URL zároveň provádí i obnovování (aktualizaci) již stažených stránek. Tento postup je výhodnější, neboť crawler nemusí čekat, až dokončí celý snímek a může pak provádět snímkování různých částí webu odlišnou frekvencí. Z jiného pohledu se jedná o crawler, který dovoluje znovu navštěvování každé ze stránek s proměnným intervalem. Tím dochází k zajištění jak dostatečného pokrytí, ale i čerstvosti staženého obsahu. Zmíněný kvalitativní posun je vykoupen větší technickou náročností. UST musí podporovat operaci „vymazání“ (například kvůli návratovým HTTP hodnotám 4xx). Zpracovaná URL mohou opakovaně vstupovat do plánovacích front, pokaždé s jinou prioritou. Její hodnota může záviset od počtu změn od posledního stažení, ale ta může být mylná kvůli silně dynamickému SPAMu. V rámci DUE naopak hrozí, že v určitém čase preferovaná unikátní množina (jedno ze zrcadel) zmizí, a je nutné co nejrychleji detekovat novou unikátní množinu. Z technického hlediska nastávají problémy s frontami URL adres ke stažení. Obslužná datová struktura musí být uchovávána na disku (URL adres je obrovské množství), a reorganizace front s ohledem na definované priority není levnou operací. Pokud bychom například museli při zařazení jednoho URL provést operaci seek (tj. cca 8ms), pak bychom mohli zařadit nejvýše 125 URL/s. Při zpracování jedné stránky však můžeme získat cca 20 nových URL, což znamená, že bychom mohli stahovat rychlostí přibližně 6 URL/s. V neposlední řadě musí crawler řešit filosofické dilema. Buď navštíví novou stránku, a vylepší tím pokrytí, anebo věnuje čas na stažení staré stránky, což zlepší čerstvost a může přinést aktuálnější a zajímavější odkazy. Naštěstí lze tento problém přenést na uživatele, který musí nadefinovat, v jakém poměru mají být tyto dva pohledy preferovány. Distribuovaný crawler Architektura z Obr. 3.2 dovoluje poměrně snadný přechod z jednouzlového systému na distribuovaný. V těchto velkých systémech se ukazuje, že je výhodné použít kešování častých (známých) URL. Při keši o 50000 položkách má UST ulehčenou práci až o 80% [9], což se příznivě projevuje i na snížení mezi-uzlové komunikace. Podle způsobu přidělování webových oblastí na zúčastněné uzly (ZU) lze rozlišovat tři základní typy distribuovaných crawlerů:  nezávislý, ve kterém neprobíhá žádná koordinace mezi jednotlivými ZU,  dynamický, kde centrální koordinátor dynamicky rozděluje web na menší části pro jednotlivé ZU,  a statický, který má před startem jasně definované rozdělení, například pevně danou hešovací funkcí. Samotné přidělování a rozdělení webu mezi ZU je lépe systematizované pro libovolně paralelizované crawlery a jejich módy činnosti:  firewallový mód, ve kterém se ignorují odkazy mezi přidělenými oblastmi mezi ZU,  překryvný mód, ve kterém ZU následuje i odkazy do dalších oddílů,  a výměnný, který zajišťuje předávání nových URL příslušnému ZU.


Z testů vyplývá [12], že firewallový mód je výhodný při malém počtu ZU (méně než čtyři), pokud stahujeme velkou část webu. Výměnný mód je dnes nejpoužívanější. Je výhodný pro větší počty ZU. Při vhodném uplatnění kešovacích strategií [9] pak činí komunikace mezi ZU zanedbatelných 1% datových toků. 3.2

Teorie

Pro konstrukci a provoz crawleru má rovněž význam ještě několik teoretických zjištění. Dle provedených výzkumů se předpokládá, že webová struktura stránek a jejich odkazů připomíná vázanku [8]. Zjednodušenou podobu prezentuje Obr. 3.3. Centrální jádro je silně spojitou komponentou a obsahuje přibližně 30% stránek. Další dvě významné komponenty na něj navazují. První (levá) z nich je taková, že obsahuje stránky, ze kterých je možné se dostat do centrálního jádra. Druhá (pravá) je naopak dosažitelná z jádra, avšak ne naopak. Kromě toho existují i další komponenty. Například výhonky začínající v levé nebo pravé komponentě, tunely mezi levou a pravou komponentou, případně úplně oddělené oblasti (webový graf nemusí být nutně souvislý).

23,4%

29,8%

23,4%

Obr. 3.3: Předpokládaná podoba webového grafu. Toto zjištění má vliv i na crawlery. Vyplývá z něj, že nelze jen stahovat do hloubky N (BFS, breadth-first-search) a domnívat se, že stáhneme celý web nebo jeho zásadní část. Zároveň je patrné, že volba startovacích URL ovlivňuje zásadním způsobem získanou množinu stránek. Proto je nutné vybírat startovací body uvážlivě a mít jich raději větší množství. Jaká strategie průchodu je nejvýhodnější? V minulosti byly zkoumány především strategie BFS a procházení s ohledem na aktuálně dostupný PageRank (PRK). Jako alternativa posledně zmíněného přístupu existuje i indeg strategie, která má z pohledu crawleru menší provozní nároky. Hledaly se i další možnosti, lepší jak BFS a přitom méně náročné jak PRK. Jedna z možných strategií je preference velkých serverů [2]. Její implementace je velice snadná, neboť stačí známé URL roztřídit do front podle cílového serveru a preferovat delší fronty. Ve velkých vyhledávačích se mohou uplatnit i techniky, které využívají zpětné vazby. Lze předpokládat, že pokud uživatel zvolil nějaký odkaz ve výsledkové listině, tak ho pravděpodobně něco zaujalo a je vhodné danou oblast stáhnout ve větším okolí.

Tutoriál

Pro podobné účely lze rovněž využít různých klasifikačních algoritmů (KA) nebo jednoduchých heuristik. Lze tak snadno přisuzovat prioritu nalézaným odkazům: je-li zdrojová stránka zajímavá z pohledu KA, potom získají nalezené odkazy vyšší prioritu. Tento způsob procházení webu dal za vznik systémům na principu FISH/SHARK [19] nebo přímo konstrukci tematicky zaměřených crawlerů [25]. Z teoretického pohledu je zajímavá i studie alokace dostupného pásma s ohledem na čerstvost shromažďovaných stránek [13]. Vyplývá z ní, že rovnoměrné rozdělení zdrojů je vhodnější než proporční, zvláště pokud mají stránky stejnou hodnotovou váhu pro uživatele. Pokud budeme posuzovat aktuálnost jen v intencích ano/ne, bez udání významnosti změny nebo jejího stáří, tak se nevyplatí plýtvat zdroji na opětovné návštěvy často se měnících stránek. Takové stránky by dokonce nemusely být vůbec stahovány. Na druhou stranu, pokud vyžadujeme, aby stránky nemohly být až „nekonečně staré“ (dlouhodobě neaktuální), tak je výhodné přidělovat pásmo proporčně, tj. často se měnící stránky navštěvovat častěji. Nakonec, ne však v poslední řadě, jsou důležité i poznatky týkající se eliminace duplicitního obsahu. Důležitost tohoto problému podtrhuje zjištěný fakt na kolekci 30 miliónů stránek [7], že téměř jedna třetina stránek je víc jak z poloviny podobná jiným, z čehož přibližně jedna desetina jsou přímé kopie. Bohužel, dokonalá eliminace zrcadel se dotýká získané množiny stránek jako celku. Je samozřejmě možné zablokovat následování odkazů ze stránek se známým obsahem. K tomu by postačovaly bloom filtry nad číselnou hodnotou textového obsahu. Jak ale naložit s univerzálními stránkami typu „zde tento dokument není, následujte prosím tento odkaz“? Text těchto stránek je univerzální, přesměrování nemusí obsahovat jedinečné URI, a za této situace nezbývá než posuzovat celý kontext takové stránky. Jisté řešení mohou skýtat techniky, které eliminují URL bez nutnosti analýzy obsahu [3]. Jejich myšlenkou je nalezení kanonizačních pravidel pro URL, které vedou k eliminaci duplicitního obsahu. Celkově ovšem není chybou ani ex-post analýza duplicit mimo vlastní proces crawleru. Odhalené množiny URL duplicitního obsahu potom mohou být odstraněny nebo zablokovány snížením jejich priority. Snížení priority můžeme uplatnit i v situacích, kdy nedisponujeme externím procesem a dané URL budí podezření z duplicity (obsahu). Cena za toto zjednodušení je zvýšený průtok skrze crawler a větší možnost pádu do webové pasti. Na druhou stranu existují systémy, u kterých je naopak žádoucí stahovat i duplicitní obsah. Jako příklad je možné uvést studentské projekty nad systémem Egothor2 [16]. Jejich cílem bylo vyhledávání duplicitního obsahu (plagiátů) a je tedy logické, že nedisponují žádným DUE modulem. Je na uživateli crawleru, aby sám určil, jakou míru eliminace duplikátů od systému požaduje. Obecně jsou ovšem možnosti crawleru v této oblasti značně omezené, a je výhodnější spoléhat na externí post-procesy. Někdy postačuje šalamounské řešení, kdy potencionální duplicitní obsah získává v rámci plánování menší prioritu. Deep-Web Reálný provoz deep-web crawlerů otevřel několik teoretických otázek, které se týkaly především analýzy vstupních formulářů a přípustných hodnot. Diskutované formuláře jsou typicky vícepoložkové, dostupné přes několik málo odkazů z titulních stránek serverů. Jejich celkový počet se odhaduje v řádu miliónů [10]. Z toho vyplývá, že správný deep-web crawler musí pracovat velmi efektivně a cíleně. Jeden z prvních systémů HiWE [28] nabídl řešení založené na LVS (label, value, set) tabulce. LVS tabulka přiřazovala konkrétním detekovaným položkám (návěštím položek)


konkrétní hodnoty, které mohly být potencionálním vstupem. V praxi se ukázalo, že návěští může být závislé od kontextu formuláře. Rovněž byly odhaleny formuláře, které obsahovaly vzájemně závislá pole. Jejich chybné vyplnění nebylo produktivní, například je zbytečné vyplňovat souběžně položky „město“ a „stát“ hodnotami „Velké Nedvězí“ a „Demokratická republika Kongo“. Od autorů HiWE proto vzešlo doporučení využívat vícero specificky zaměřených deep-web crawlerů, respektive využít tematicky zaměřený crawler, který nás udrží v konkrétní tematické oblasti a tím i množině přípustných hodnot. Existují i novější řešení, například deeppeep.org, což je akademický projekt monitorující 13000 formulářů v sedmi doménách. Tento projekt podrobněji rozpracoval problémy kategorizace formulářů a extrakce návěští. Z provedených studií vyplývá, že lze úspěšně kategorizovat formuláře na základě textového obsahu okolí formulářů. K samotné charakterizaci nepostačuje text uvnitř formuláře, je nutné využít text celé stránky, na které se formulář nachází [5]. Studie byla provedena na formulářích leteckých společností, hudebních nakladatelství apod. Je otázkou, nakolik to reflektuje i případ formuláře z úvodní ukázky deep-web crawleru (Program 3.1). Dalším teoreticky rozpracovaným problémem byla extrakce návěští políček formulářů. V praxi se zjistilo, že mnoho formulářů neodpovídá klasické představě o těsném kontextu návěští a vstupního prvku. Například vznikají problémy s dvousloupcovými formuláři, kde se návěští nachází jen nad vstupním prvkem v prvním sloupci a druhý sloupec je toliko odsazen, přestože má přímý vztah k danému návěští. HiWE používal rozmisťovací algoritmus, který kalkuloval vzdálenost v pixelech a následně použil heuristiky. Jejich vstupem byly parametry jako souřadnice, počet slov, velikost fontu, apod. Tato technika se na zmíněných formulářích ukázala jako neúčinná. Jedno z možných řešení představují techniky na principu učícího se klasifikátoru [26], které jsou právě součástí systému deeppeep.org. 3.3

Implementace

Problémy v implementační rovině souvisí s reálnou situací na webu. Náš systém například v roce 2012 odhalil na českém webu následující základní parametry. V jedné stažené stránce lze nalézt v průměru 7 dalších (dosud neznámých) URL adres. Celkově je ale nalezeno až 20 unikátních URL adres v jedné stránce. Jaké má tento empirický poznatek dopady? URL-seen test Přímý dopad je v UST. Tato rutina musí pracovat s datovou strukturou, která je perzistentní. Při stahování 1000 URL/s musí obsloužit 20000 testů, z nichž 7000 vede ke vložení nově testovaného URL. Je pochopitelné, že daný objem není zvládnutelný běžnou datovou strukturou na principu stromu (B+ apod.) – situace by vedla k mnoha drahým seek operacím. Určitým řešením může být bitové pole nebo bloom filtr, případně hešovací tabulka. Tyto způsoby počítají s určitým faktorem kolizí, ale jako základní struktura by je bylo možné použít. Pokud by se zjistilo, že je URL skutečně nové, muselo by se navíc zapsat do pomocného souboru. Z něj by se bitové pole mohlo reinicializovat při restartech crawleru. Velkou výhodou je i možnost efektivní distribuce tohoto pole – každý uzel distribuovaného crawleru by měl své vlastní,, pro jemu přidělenou webovou oblast. V případě hešování lze dále ušetřit kompresí URL adres (řádově desítky až stovky znaků), případně jejich převodem na položky pevné délky (MD5 apod.). Tyto techniky však často vedou k rozbití lokality přístupu v datové struktuře nebo do keší, a proto bývají doplňovány o prefixování

Tutoriál

dle jména serveru v URL adrese. Tím je zajištěno, že budou redukované položky z téhož serveru opět dosažitelné poblíž sebe. Z našich dalších testů vyplývá, že například hešovací tabulka (položky jsou MD5 hodnoty známých URL) realizovaná v PostgreSQL zvládá přibližně 3000 testů za sekundu. Crawler, který by pak takovou strukturu použil, dosáhne na českém internetu rychlosti přibližně 150 URL/s. Dalším řešením UST problému je udržování seřazeného seznamu všech známých URL. Nově získaná URL je pak možné slévat ve větších dávkách, a všechny skutečně nové položky (až poté) posílat do front crawleru. Tento postup amortizuje snadný, i když zdlouhavý, proces slévání. Na druhou stranu se do crawleru mohou dostat nová URL se značným zpožděním. Na začátku, když je v crawleru málo známých URL adres, je tento aspekt zanedbatelný. Později může být patrný a mohl by brzdit crawler, který by tak neměl dostatek kandidátů ke stahování. Praxe ukazuje, že to nehrozí, neboť případné volné kapacity (pokud je crawler vůbec má) lze využít na aktualizaci již získaného obsahu. V neposlední řadě je možné operaci slévání distribuovat přes celý dostupný crawlovací cluster, což její náročnost významně zmenší. Z reálných implementací je technika slévání využita v Mercatoru i IRLbotu (budou ještě zmíněny později) [20,23]. Mercator používá dávky, které se vejdou do RAM, IRLbot využívá slévání na disku s o mnoho větším počtem prvků v jedné dávce. Správa front Počet URL v systému není nebezpečím pouze pro UST. Plánovací fronty s URL záznamy rostou velmi rychle a přitom musí velmi efektivně podporovat operace insert a delete. Z tohoto důvodu se často používají cyklická pole. Je rovněž možné využít systém několika souborů – segmentů fronty, který usnadňuje umazávání začátku fronty (po vyčerpání segmentu se může celý smazat). Ve všech těchto variantách je ale velice obtížné zajistit přeuspořádání již existující fronty, zejména s ohledem na počet prvků a trvalý přísun nových. S frontami souvisí i praktická omezení. Crawler se musí chovat dostatečně zdvořile, tj. žádosti o stránky prokládat určitou pauzou, v opačném případě mu hrozí zablokování přístupu. Jaký to má vliv na fronty crawleru? Uvažujme příklad BFS strategie s FIFO frontami, které nelze přeuspořádávat. Dále uvažme, že procházíme dva servery. Každý z nich obsahuje stránky s 200 odkazy sám na sebe. Stáhneme-li stránku z prvního serveru, získáme 200 odkazů na ten samý server a ty pošleme do fronty. Přibližně v tu samou chvíli stáhneme stránku z druhého serveru a opět pošleme 200 URL do fronty. Na začátku fronty nyní vidíme URL z prvního serveru a za ním ještě 199 URL na tentýž server. Pokud se budeme chovat zdvořile a použijeme pauzu 5 sekund mezi žádostmi do téhož serveru, dostaneme se k URL druhého serveru až za 1000 sekund, přestože bychom je mohli stahovat souběžně. Tento problém musí každý crawler řešit dostatečně efektivně, aby nedocházelo k popsaným „zbytečným“ prodlevám. Crawler může využít i jinou politiku, kdy je čekání odvozeno od doby nutné pro stažení poslední stránky z daného serveru. Pro rychlé, pravděpodobně nezatížené, servery je pauza malá, pro pomalejší větší. Popsaná politika pak způsobuje, že dopředu nemůžeme říct, kolik stránek lze z daného serveru v aktuální chvíli stáhnout, a předchozí problém se tak ještě prohloubí.


Kanonizace Dalším faktorem, který ovlivňuje kvalitu crawleru je nakládání s URL adresami a eliminace duplicitních části webového grafu. Každý crawler převádí nalezená URL na základní, kanonický tvar. Typicky doplňuje číslo portu, eliminuje fragmenty ./ a ../, apod. Bohužel, ne všechny tyto úpravy jsou korektní. Například, u virtuálních serverů je (díky jejich konfiguraci) často rozdíl, žádá-li crawler o dokument z virtuálního webu „www.firma.cz“ nebo „www.firma.cz:80“ (HTTP položka „Host“). Stejně tak nemusí být korektní transformace z www.firma.cz/ na www.firma.cz/index.html (ev. naopak). Naproti tomu, pokud se podaří najít vhodná transformační pravidla, může to znamenat, že nedochází ke zbytečnému stahování duplicitního obsahu a časové sloty jsou volné pro stahování jiného obsahu. IRLbot raději volí kompromisní strategii. Pokud se zdá být určitá část webu duplicitní, sníží ji pouze prioritu. Efektivita crawleru Obecně lze říct, že neefektivní crawler je typicky ten, který zbytečně čeká. Podívejme se proto podrobněji na jednotlivé části crawleru a jaké činnosti lze paralelizovat. Například první verze Mercatoru odhalila velkou neefektivitu v paralelním řešení DNS dotazů na platformě Java [20]. Oprava přinesla několikanásobné zrychlení. Crawler čeká, ne z vlastní vůle, v následujících akcích:  řešení DNS dotazů,  připojování se k cíli,  a při stahování dat z cíle. Objektivní odpověď na míru čekaní v těchto akcích můžeme získat analýzou crawleru, který je součástí systému Egothor2 [16]. Jeho architektura je zachycena v Obr. 3.4.

Obr. 3.4: JavaSpace-like architektura crawleru Egothor2. Tento crawler používá několik oddělených vláken, označených velkým T. Mezi nimi putuje proud URL adres, které se stahují. Adresy jsou předávány skrze synchronizovaná cyklická pole, s jedním producentem (vlevo) a jedním konzumentem (vpravo). Nulté

Tutoriál

vlákno řídí přísun URL adres. První vlákno řeší pouze DNS dotazy, třetí vlákno HTTP stahování formou asynchronního přístupu, a páté vlákno zajišťuje finální zpracování získané stránky (extrakce odkazů, tvorba indexu, apod.). V této architektuře, odpovídající technologii JavaSpace (resp. GigaSpace) lze snadno nahlédnout, kde nastává nechtěná prodleva.

Obr. 3.5: Průměrné čekací doby při připojování a stahování z cíle. Operace připojení k cíli (v rámci třetího vlákna) vyžaduje přibližně 14-15ms a samotné stahování 280ms (Obr. 3.5) v prostředí sítě CESNET při stahování dokumentů z české národní domény.

Obr. 3.6: Aktuální zátěž jednotlivých front v crawleru architektury Egothor2. Z pohledu na celkové zaplnění front vyplývá (Obr. 3.6), že třetí vlákno označené v obrázku jako „WWW“, nedosahuje zdaleka maximálního naplnění (800 objektů cyklického pole). Vlákno řešící DNS dotazy je po celou dobu dokonce na nule, z čehož je zřejmé, že současná velikost DNS keší i implementace DNS klientů je na plně postačující úrovni. DNS problém systému Mercator se tedy na současné Java platformě již dále nevyskytuje. Zároveň je vidět, že je páté vlákno (Mutex) dlouhodobě saturováno. V tomto vlákně se odehrávají všechny podstatné operace UST a DUE, vyjma práce s frontami – ty má na starost nulté vlákno. Z uvedeného rozboru vyplývá, že nejpodstatnější dopad na kapacitu crawleru mají především operace UST a DUE. Dokonce řádově větší jak nároky spojené se samotným stahováním stránek.


Map-Reduce styl Poměrně přirozeným řešením pro implementaci crawleru by mohlo být využití MapReduce (MR) infrastruktury, zejména v systémech, které ji dále využívají pro zpracování obsahu. Bohužel, samotná implementace není snadná: MR pracuje dobře, pokud jsou jednotlivé operace nad klíč-hodnotou nezávislé od ostatních. Při zdvořilém stahování tato základní premisa neplatí. Na druhou stranu, MR může být vhodný prostředek pro další zpracování dat, například jako podpora UST a DUE. Ovšem ne všechny datové struktury je vhodné spravovat MR stylem, neboť to přináší mnohé problémy:  kvůli MR principům neexistuje centrální datová oblast a programovací model je poměrně restriktivní,  spojení vícero datových množin je pomalé, neexistují indexy, data se musí ve velkém množství kopírovat během zpracování, což může v některých případech vést až k problémům s datovou propustností,  přestože se jedná o řešení pro Share-Nothing architekturu, nadále obsahuje single-master uzel, který vyžaduje větší péči a může být příčinou výkonnostních problémů,  problémy jsou i s řízením toku dat, zvláště pokud je nutné ukládat mezivýsledky operací (datových toků), například z důvodů optimalizace a eliminování již zpracovaných (mezi)výsledků,  řízení a správa clusteru je obtížná - například správné stanovení počtu jednotlivých procesů typu mappers/reducers, stanovení paměťových limitů, apod. Projekt Hadoop (respektive Nutch) aktivně hledá řešení těchto konkrétních nedostatků a je možné, že se je podaří najít. Při syntetických testech dokázal jejich plánovač pracovat na výkonu téměř 900 URL/s (zdroj zprávy - A. Bialecki, autor tohoto plánovače) – je ovšem otázka nakolik suché testy reflektují reálnou situaci. Mnoho uživatelů tohoto projektu má, dle zpráv z mailové konference projektu Nutch, problém udržet i řádově nižší výkon svých instalací. Zatím lze tedy pouze konstatovat, že plánovač má dostatečnou kapacitu a případné propady výkonu jsou způsobeny buď chybnou konfigurací na straně uživatelů, nebo chybami v některých dalších částech architektury. Konkrétní produkty Mercator Mercator byl původně nedistribuovaný crawler, který používal blokované API pro přístup k síťovým službám. Jeho poslední (veřejně známá) verze je již distribuovaná a celková modulární architektura dovoluje postavit crawler s libovolnými funkcemi. Jeho architekturu jádra lze snadno adaptovat pro implementaci inkrementálních i dávkových crawlerů, nebo různých tematických crawlerů. Distribuovaná verze (kódové označení Atrax) je založena na architektuře z Obr. 3.2, v níž dochází k přirozenému propojení jedno-uzlových crawlerů (Mercators). Pro výměnu URL adres mezi zúčastněnými uzly (ZU) se uplatňuje režim „bez překryvu“. Problémem je tak výpadek jednoho z uzlů nebo snaha o modifikaci počtu ZU. V těchto případech může nastat problém v DUE. Naopak UST nečiní problém. Každý ze ZU má k dispozici svoji část UST struktury, a proto není ve své vlastní činnosti omezen. Práce s UST strukturami probíhá dávkově.

Tutoriál

Fronta

Prioritizér

Halda

Mini fronta cíle

Vyvažovací Selektor

...

Router

...

Fronta

Mini fronta cíle

První řada front

Druhá řada front

Selektor

Obr. 3.7: Správa front Mercator.

Principiálně se ale i tak jedná o centralizovaný crawler, který vyžaduje rychlé disky pro své datové struktury, zejména pro podporu UST a DUE. Systém front využívá dvě vrstvy k zajištění zdvořilosti a saturace s ohledem na definované priority (Obr. 3.7). Nové URL adresy přicházejí do první řady front, kde je každá z nich alokována pro jednu konkrétní prioritu. Vyvažovací selektor potom vybírá frontu, ze které přenese plánovaná URL dál. Volba reflektuje priority, tj. častěji je volena fronta s vyšší prioritou. Přenesená URL vstupují do druhé řady front. Jedná se o fronty, které jsou přiřazeny konkrétním serverům (klíčem je hostname). Zde čekají, až je další selektor vybere ke stahování s ohledem na zvolenou politiku zdvořilosti. Fakticky celý proces pracuje v obráceném pořadí. Druhá řada front je požádána o další URL ke stahování. Pokud je má k dispozici, vydá je pouze z front druhé řady. Pokud jimi nedisponuje, požádá fronty první řady o doplnění zásoby URL ke stahování. Z toho plyne, že první řada uplatňuje politiku priorit, druhá řada pak dohlíží pouze na zdvořilost přístupu k cílům. Front druhé řady je daleko více než stahovacích vláken: z praktického provozu vyplývá, že je jich zapotřebí až 3x více. Reálný výkon uváděný autory činí 891M stránek za 17 dní na 4 uzlech. Z objektivního hlediska ovšem musíme počítat pouze se 473M stránek. Zbylé stránky byly v daném testu ne-HTML formátu, a proto neměly žádný vliv na UST nebo DUE, případně zátěž v externích frontách. Polybot Zajímavé architektonické řešení představuje crawler Polybot [29]. Celý systém je rozdělen na klientskou aplikaci, která úkoluje stahovací manager, a ten dále stahovací procesy. Získané stránky jsou doručovány zpět aplikaci, takže je možné zaintegrovat crawler do různých produktů. Systém dále definuje některá základní rozhraní, jejichž implementace lze následně distribuovat. Oproti Mercator realizuje zdvořilost tak, že prodlevy činí nikoliv vůči cílovým IP adresám, ale proti hostname. V případě, kdy je na jedné IP adrese provozováno několik virtuálních webových hostů, může dojít k přetížení stylem DoS. Při praktickém testování se ovšem tato obava nepotvrdila. Tento zajímavý poznatek zjednodušuje implementaci „zdvořilosti“, neboť není potřeba provádět DNS dotazování před tím, než padne rozhodnutí o stažení stránky.


Samotná implementace využívá dvě haldy s aktivními a čekajícími servery a podle toho (a priorit konkrétních URL) volí stránky ke stažení. UST pracuje v dávkovém režimu přímo na disku. Pro doručování stránek mezi komponentami slouží NFS. Reálný výkon činí 120M stránek za 18 dní na 3-5 uzlech (počet uzlů se v průběhu publikovaného testu měnil). Heritrix Heritrix je crawler používaný k archivaci internetových stránek neziskovou společností Internet Archive. Konstrukčně se jedná o architekturu Mercator s využitím bloom filtrů k detekci známých URL (tzv. UST). WebFountain (IBM) Jedná se o korporátní implementaci crawleru architektury Mercator v jazyce C++ a s podporou MPI. Tento crawler je inkrementální, jeho crawlovací proces nikdy nekončí. URL jsou organizovány ve skupinách dle cílového hostname, a každá tato skupina je přiřazena jednomu stroji. Neexistuje tedy centrální fronta nebo seznam URL. Směrování URL provádí controller. Ten je kontaktován jednotlivými uzly s množinami URL, které nespadají do jejich působnosti. Hlavní vlastností tohoto crawleru je schopnost adaptace na změny stránek tak, aby dokázal udržovat jejich co nejčerstvější podobu [15]. UbiCrawler (Trovatore) Jedná se o univerzitní crawler, který je plně distribuovaný s řídícím procesem monitorujícím správnou funkci všech komponent. Pro distribuci URL využívá konzistentní hešování. Jeho základem je technika, která dovoluje každému ze zúčastněných uzlů určit, který uzel je za stahování daného URL zodpovědný [6]. IRLbot IRLbot je ryze jednouzlový crawler. Jeho autoři tvrdí, že distribuovaná verze bude růst lineárně, neboť se využije redistribuce v rámci výměnného módu [23]. Toto tvrzení nemusí být vždy platné, zejména u některých algoritmů obsluhujících DUE. Systém představil vlastní nízkonákladové externí datové struktury pro UST, DUE a správu front. Výsledné řešení bylo testováno na čtyřprocesorovém systému Opteron 2.6GHz, RAM 16GB, disk RAID-5 (24 disků). Tato aparatura dokázala za 41 dní získat 6400M stránek, což činí 1800 URL/s. Jako další zajímavý výsledek tohoto experimentu je potvrzení předpokladu, že BFS strategie nemusí být nejvhodnější pro velmi rozsáhlá stahování [23]. XCrawler Systém XCrawler [21] je jednoduše rozšiřitelný crawler, který stahuje webové stránky a pak je podle filtrů směřuje k cílovým aplikacím. Jeho obdobu lze spatřovat v proudových nebo paralelních databázích. Další ekvivalenci lze nalézt v publish-subscribe systémech jako jsou Gryphon, Siena, Elvin nebo LeSubscribe. Architektonicky nejblíže má asi k produktu Cobra, což je distribuovaný systém stahující RSS a vyhodnocující uživatelské filtry.

Tutoriál

3.4

Některé směry vývoje

Primární otázkou existence crawleru je otázka „co je cílem?“. Rozhodně tím nemusí být stažení veškerého webového obsahu. Ostatně, web je natolik veliký, že by se tento cíl nemuselo vůbec podařit naplnit. Konkrétnější cíle si stanovily mnohé komerční systémy (Alta Vista, Google, ad.). Jejich primárním cílem je získání stránek, které mají tak zajímavou váhu, že se pravděpodobně dostanou do výsledkových listin vyhledávání. Zpravodajské portály naopak preferují často aktualizované stránky, oborové portály se zase budou primárně zajímat o tematické stahování konkrétního tématu. Architektura takových crawlerů je již ověřena praxí. Jediné, co ještě může rozhodovat je nalezení jiných typů preferenčních strategií, resp. strategií, jejichž implementace přinese významné úspory a posílení výkonu. Touto cestou se vydal například IRLbot. Novým směrem se proto v oblasti stahování webu stala především dosud málo prozkoumaná oblast deep-webu. Deep-web Problematiku deep-webu lze rozdělit na dvě základní oblasti zájmu. Jednak jde o indexování JavaScript/AJAX aplikací, a rovněž o přístup k datovým záznamům za formuláři. První oblast je obecně obtížná, neboť ji lze chápat jako zpětnou analýzu chování Turingova stroje, stanovení stavů a přechodů mezi nimi. Je otázka, zda lze nalézt rozumný, dostatečně praktický přístup. Určité zjednodušující postupy existují, například návrh na spolupráci autorů obsahu a crawlerů skrze standardizační návrh stahování AJAX aplikací 3. V druhé oblasti je předmětem zájmu určení přípustných hodnot a jak efektivně odlišit podstatné vstupní položky od prezentačních. Tento problém je poměrně složitý a nemusí platit, že se výsledek liší vzhledem a nikoliv obsahem [18]. Samotné zpracování formulářů již bylo integrováno do Google [24]. Využívají se šablony, které poskytují dostatečně charakteristický výstup, tj. nejedná se o chybové hlášení a nejedná se ani o modifikaci v prezentační rovině. Uvedené šablony se vyplňují ve volných textových polích, přičemž se může využít iterativní postup pro získání příslušných hodnot. Startuje se například z množiny slov uvedených ve formuláři a přidávají se slova z výsledkových stránek formuláře. Celou situaci komplikují formuláře se závislými hodnotami a strojové odhalování těchto závislostí. Jedná se o poměrně nové metody a celá problematika deep-webu tak zůstává v těchto směrech otevřenou oblastí. 3.5

Projekt Akula

Na procházení webu lze nahlížet jako na diskrétní simulaci akcí. Při tomto pohledu se základní technická problematika transformuje na systém, který je schopen plánovat velké množství úkolů a efektivně je doručovat na prováděcí jednotky. Na rozdíl od běžných crawlerů musíme počítat s tím, že neuskutečnění nějaké akce může vyvolat další aktivity (snížení priority daného úkolu, přeplánování akcí, apod.). Kromě toho si musíme být vědomi toho, že v takovém distribuovaném systému se může stát, že nějakou úlohu nejenom splníme nebo nesplníme, ale i jen „možná splníme“ (pouze se o tom kvůli výpadku nedovíme včas). V popisovaných crawlerech nevyvolávalo nesplnění nějaké akce žádné zásadní operace, jednoduše se počkalo, až bude k dispozici 3

https://developers.google.com/webmasters/ajax-crawling/docs/getting-started


dostatek zdrojů a akce se provedla. Nová situace odpovídá stavu, kdy by se úlohy z druhé řady front vracely zpět do první řady front, a při tom by mohlo ještě dojít k přeplánování některých dalších úloh (Obr. 3.7, první a druhá řada front). Tyto úvahy nás postupně dovedly k realizaci projektu Akula. Jedná se o distribuovaný systém pro procházení webu, resp. jakýchkoliv organizovaných struktur (v podobě grafu) přístupných libovolným protokolem. Výsledná architektura je založena na spolupracujících službách. Tím je zajištěno, že výpadek nějaké služby může být nahrazen jinou službou se shodnou funkcionalitou – dochází tak k implicitní ochraně proti výpadku, což je důležitý aspekt pro dlouhodobě běžící systémy. Zmíněnou vlastnost lze použít i pro posílení výkonu. Libovolnou službu můžeme klonovat, odmigrovat ji v rámci distribuovaného systému na zvolené místo a tím posílit výkon. Ze systému by se tak mohl stát živý software, který na základě vlastní telemetrie, heuristik a zkušeností z provozu sám řídí své rozmístění. Vrátíme-li se do kontextu crawlerů, pak takový systém bude fungovat jako jednouzlový, pokud se mu to bude zdát efektivní. Jakmile se rozhodne, že je nutné posílit výkon (např. rychlost nárůstu front je větší než lze zvládnout), odmigruje svůj klon, rozdělí datové struktury, vloží adaptér pro distribuovaný crawler (Obr. 3.2, blok „Redistribuce mezi…“), a to vše za plného provozu. Nastíněná vize je v běžně dostupných technologiích jen obtížně realizovatelná, a proto jsme se rozhodli vytvořit specifický middleware. Prototyp je pak složen ze dvou vrstev: podkladového middleware J5M a vlastní crawlovací platformy. Výsledná platforma je založena na principech diskrétní simulace a dovoluje využití nejenom pro implementaci různých webových crawlerů, ale například i pro simulaci pohybu virtuálních osob po webovém prostoru. Základem systému jsou čtyři základní rozhraní: BaseSystem představuje správce front; Coordinator povoluje přístup k cílům v daném čase; Service implementuje uživatelskou operaci, která je spouštěna nějakou naplánovanou událostí (například stažení stránky, odeslání formuláře, apod.); a nakonec Cabinet, přes který je možné uložit nestrukturovaná data k dalšímu zpracování. Jeden z možných příkladů vazeb představuje Obr. 3.8. Coordinator je vždy svázán s nějakým BaseSystem, který musí být omezován při využívání Service. V obrázku je rovněž naznačen BaseSystem, rozdělený na dva jiné. Takové rozhraní pracuje jako proxy s vnitřním řízením a podle parametrů přeposílá volání jednomu nebo druhému podřízenému BaseSystemu. Úkoly již nejsou jednoznačně identifikovatelné pomocí URL. Úkol je vymezen časovým úsekem, ve kterém může být proveden, požadovanou operací a nakonec parametrem. Například: „v čase od-do provést stažení stránky s kontrolou robots.txt s parametrem konkrétní URL“. Úkoly jsou organizované do stromové struktury, jeden úkol tak může založit několik svých podúkolů. Nadřazeným úkolem může být „začni procházet web jako crawler XYZ“, a podřízenými úkoly jednotlivé kroky daného crawleru. S tímto přístupem je následně možné v rámci jednoho BaseSystem provozovat libovolný počet nezávislých crawlerů. Všechna znázorněná rozhraní (čtverce a obdélníky) představují služby, které mohou běžet v několika instancích. Pokud vypadnou, nahradí je (polo)automaticky jiná instance a systém jako celek pracuje dál.

Tutoriál

BaseSystem splitter Large/Images Coordinator Global

BaseSystem Service

BaseSystem

BaseSystem

Large-scale

Imagebot

FormAnalysis

Persons Coordinator PersonalLife

Service Lurker

BaseSystem Service

Deep-web

PoliteFetch

Coordinator Global2

Service DataExtraction

Cabinet

Cabinet

Cabinet

Workgroup WebAnalytics

Workgroup Multimedia

Workgroup UnstructData

Obr. 3.8: Příklad rozmístění celého systému crawlerů. Stejným stylem je navržen i samotný BaseSystem, Obr. 3.9. Ten spolupracuje s normalizátorem, kterým procházejí všechny nové úlohy (operace „push“). Po normalizaci (kanonizace úlohy, příp. DUE) se úloha dostává do systému externích front (CylinderSet). Odtud se s ohledem na priority a plánovací algoritmus fronty (PriorityQueue) přesune do vnitřní paměti (Flux). Odtud vyzvedává úlohy plánovač pro služby (Service), které se mu přihlásí. Možnost provést úlohu konzultuje s koordinátorem přístupů k cílům (Coordinator), a pokud je aktuálně neproveditelná, vrací ji zpět do vnitřní paměti. V opačném případě se dostává příslušné službě, která ji zpracuje. V rámci zpracování může emitovat nové úlohy pro tentýž nebo i jiný BaseSystem. Po dokončení zpracování využije Service operaci „popAndPush“, která slouží buď pro definitivní vyřazení daného úkolu, nebo jeho přeplánování. V obou případech je zkontrolováno, zda se tato úloha stále nachází ve vnitřní paměti. Pokud ano, implicitní transakce vztažená k dané úloze se uzavře. V opačném případě je možné provést opravné kroky de-facto vyvolané tím, že byla daná úloha mezitím vytlačena zpět z vnitřní paměti do externích front. Všechna popsaná rozhraní jsou robustní, lze je vyměňovat za běhu systému a systém jako celek není ohrožen, pokud alespoň jedna instance daného rozhraní pracuje. Systém dovoluje i různé prakticky orientované varianty. Například lze bez problémů implementovat dva oddělené BaseSystem, do kterých se on-line registruje stejná služba stahování webové stránky. První ze systémů obsahuje úkoly na stažení nových URL, druhý obsluhuje stahování již navštívených URL. Pak je možné používat pro každou tuto množinu jinou plánovací strategii a lépe vyvažovat stahování nových stránek a obnovování již získaného obsahu. Při porovnání s architekturou Mercator bychom našli některé styčné body. BaseSystem, který je pouhým rozdělovačem nad několika jinými BaseSystem, je vlastně adaptérem pro distribuovaný crawler (Obr. 3.2, „Redistribuce mezi…“). Výhodou našeho návrhu je jeho otevřenost a snadná adaptibilita dle specifických potřeb pro procházení webu.


lazy greedy

Normalizer

BaseSystem push

popAndPush

PriorityQueue CylinderSet

Cabinet Planner

Service

Flux Recrawl policy

Filtry Cylinder Cylinder ...

...

Cabinet

Aktivní úlohy Coordinator Pasivní úlohy

Obr. 3.9: Hlavní procesy a rozhraní Akula. Srovnání s architekturou Mercator Náš systém je založen na obecnějších principech než běžný crawler. Principiálně však zajišťuje obdobnou funkcionalitu jako Mercator, a proto můžeme popsat jednotlivé styčné body a zavedené odchylky. Cylinder je jedna z našich externích front. Je rozdělena pomocí definovaných filtrů na povolené a zakázané úlohy, přičemž pouze povolené úlohy mohou být dále zpracovávány. Filtrem může být například sada specifikací robots.txt. Filtr může sloužit i k rozdělení úkolů do skupin s tím, že jsou pak tyto skupiny postupně povolovány a zpracovávány (například jako vrstvy stromu v BFS). Mercator tuto funkcionalitu standardně nenabízí. CylinderSet spravuje jednotlivé Cylindery. Jejich počet je neomezený a mohou v čase přibývat nebo naopak mizet. Tyto operace řídí fronta (PriorityQueue) tak, aby Cylindery nebyly příliš veliké a bylo je možné dostatečně efektivně přeuspořádávat. Mercator nabízí ve svých externích frontách více staticky orientovanou implementaci. Větší dynamiku nevyžaduje, neboť nepotřebuje zajišťovat přeplánování jednotlivých úloh. Flux má naopak obdobu v mini-frontách Mercatoru. Naše implementace je komplikovanější v tom, že Service je z našeho pohledu nekontrolovaný kód a může předané úlohy „ztratit“. Flux musí tento problém řešit pomocí implicitních transakcí (vydaná úloha musí být ze strany Service potvrzena jako dokončená nebo přeplánovaná). Plánovač (Planner) je komponenta, kterou Mercator nedisponuje. V našem systému slouží buď v režimu pull nebo push (z pohledu Service), přičemž může směrovat úlohy na Service, které jsou méně zatížené. Z praktického pohledu může rovněž zajistit, aby se úkol procházení webu prováděl vždy z jedné IP adresy (tj. z konkrétní Service). Service je služba, která dokáže realizovat konkrétní úkoly. V tomto rozhraní je typicky implementován uživatelský kód pro stahování webu. Výhodou je, že lze příslušné instance dynamicky připojovat, zabíjet a tedy i vyměňovat za plného provozu. Kromě toho se Service registruje do všech dostupných plánovačů všech BaseSystem (není-li limitována nastavením), a proto je snadné implementovat několik funkčně totožných BaseSystem ale s například jiným algoritmem plánování front.

Tutoriál

J5M Velká část zajímavých vlastností je pokryta schopnostmi podkladového middleware. V této části popíšeme některé z nich a ukážeme, jaká je cena za jejich realizaci. J5M řeší problémy takřka libovolného rozmístění zúčastněných služeb a potažmo stability. Toto dynamické prostředí má nejblíže k Java technologii JINI, avšak J5M dovoluje stromovou strukturu jmen hnízděných objektů a jejich dynamické parametry. Těmito parametry může Service například deklarovat jakými IP adresami pro stahování disponuje. Kromě tohoto rozdílu jsou klientské a serverové objekty hostované v rámci tzv. Nuggetů. Nuggety nabízejí některé ze základních služeb: vyhledání instance požadovaného rozhraní, přístup k zásobníku spojů do databáze apod. Rovněž sledují, které instance rozhraní jsou rychlé a ty potom preferují při operaci vyhledávání instancí. Další činností je sledování spojů mezi klientskými a serverovými objekty (instancemi). Pokud serverový objekt vypadne, Nugget nabídne alternativní, a klientský objekt může pokračovat ve své činnosti dál. Nugget je navíc plně zodpovědný za to, jaký protokol bude zvolen pro komunikaci mezi klientem a serverem. V případě, že se oba objekty nacházejí v témže JVM procesu, probíhají volání přímo, v ostatních případech skrze Java RMI. V rámci testování jsme ověřovali, nakolik profilování spoje zpomaluje samotnou komunikaci mezi klientem a serverem. Implementovali jsme serverový objekt se třemi metodami. První byla zcela bez parametrů, druhá měla jediný parametr přenášející jeden objekt (Task), a třetí akceptovala pole objektů. Klientský objekt prováděl řádově desítky tisíc volání zmíněných metod. Naše testy srovnávaly POJO versus J5M (v jedné JVM) a RMI versus J5M (mezi JVM přes localhost). Rozdíly byly nepatrné, v řádu promile až (nejvýše) 1%. Z toho vyplývá, že monitoring ze strany J5M neprodražuje volání oproti přímé a nativní implementaci v Java. Všechny tyto funkce jsou vykoupeny striktnějším protokolem hnízdění hostovaných objektů, než jaký požaduje JINI. Na druhou stranu, naše řešení umožňuje profilování komunikace klient-server a migrace (některých) instancí mezi jednotlivými JVM, což je s ohledem na zamýšlené cíle přínosná vlastnost. Vyhodnocení prototypové implementace crawleru Výsledná implementace crawleru byla testována jak v syntetickém, tak i reálném prostředí. Syntetické prostředí využívalo implementaci rozhraní Service, které simulovalo procházení webového grafu. Simulace byla úplná, včetně syntetického generování robots.txt. Stránky obsahovaly nejvýše 50 odkazů. Každý z 500 serverů disponoval 5 tisíci stránek. Výsledek tohoto testu se čtyřmi Service instancemi ukazuje Obr. 3.10. Je patrné, že crawler zvládá lineární nárůst počtu úkolů. Při větších syntetických testech jsme ověřili, že je možné zpracovat 24M úkolů za den (277 úkolů/s) na jednom procesoru. Při praktickém nasazení jsme pak využili virtuální stanici v prostředí vmWare (1CPU, 4GB RAM). Rychlost stahování činila přibližně 80 úkolů/s. Náš systém je univerzální a dokáže místo crawleru realizovat i pohyb uživatele (virtuální identity) po webovém grafu. Vyjdeme-li z výše uvedených měření, pak je možné v syntetickém prostředí obsloužit tým 1000 identit (16 úkonů za minutu na jednu identitu). V reálném prostředí se tento počet snižuje na 250 identit. Pro lepší zasazení těchto empirických hodnot do reálného kontextu připomeňme, že v roce 2010 poptávala americká administrativa systém pro řádově stovky virtuálních identit. Implementace diskrétního plánovače v rozsahu úkolů webového crawleru je náročnější úkol než implementace běžného crawleru. Na druhou stranu výsledek přináší několik


zajímavých vlastností. V rámci jednoho systému může probíhat několik oddělených stahovacích procesů (crawlerů). Zároveň s nimi může probíhat i navigace virtuálních identit. Protože je naše architektura blízká jedné z nejčastěji používaných architektur (Mercator), mělo by být rovněž snadné integrovat postupy umožňující běh tematických nebo deep-web crawlerů. Robot (4 service objekty) 600000

500000

400000

300000

200000

100000

0 Base system

Priority queue

Obr. 3.10: Propustnost jedné jednotky BaseSystem (30min). Jako celek tak dokáže tento systém zajistit jednotnou platformu pro všechny uvažované varianty aplikací pro procházení webu. Lze tak běžným crawlerem monitorovat povrchový web a odhalovat vstupy do deep-webu. Okamžitě je možné startovat tematické nebo deepweb crawlery, případně povolávat virtuální identity schopné provádět nejrůznější aktivní činnosti. Přínos podkladového J5M nejlépe dokládá jeden z nechtěných testů. Omylem došlo k vysunutí síťového kabelu, čímž všechny uzly našeho clusteru najednou ztratily přístup ke sdíleným diskům s frontami úloh a veškerými daty. Tato situace vedla k úplnému rozpojení běžícího systému. Avšak po opětovném zapojení sítě se systém sám do několika minut „sestavil“ a pokračoval ve své činnosti bez jakýchkoliv známek poruchy. 3.6

Závěr

Tento článek představil postupy, techniky a konkrétní implementace několika veřejně publikovaných crawlerů. Je patrné, že crawlery se stále více přesouvají do dříve nepřístupných webových oblastí tzv. deep-webu. Představili jsme rovněž náš prototypový systém, který pracuje na principu diskrétní simulace událostí. Dokáže proto pracovat nejen jako klasický crawler, ale má schopnost

Tutoriál

simulovat pohyby virtuálních identit po webovém prostoru. Ukázali jsme, jaká podkladová platforma nám dovolila postavit robustní a otevřený systém, který je možné považovat za vhodnou platformu pro další aplikace v oblasti procházení webového prostoru.

Literatura 1.

2.

3.

4. 5.

6. 7.

8.

9.

10. 11.

12.

13.

Adar, E., Teevan, J., Dumais, S. T., Elsas, J. L.: The web changes everything: Understanding the dynamics of web content. In: Proceedings of the Second ACM International Conference on Web Search and Data Mining. WSDM ’09. ACM, New York (2009), 282–291. Yates, R. B., Castillo, C., Marin, M., Rodr guez, A.: Crawling a country: Better strategies than Breadth-First for web page ordering. In: Proceedings of the 14th international conference on World Wide Web / Industrial and Practical Experience Track. ACM Press, Chiba (2005), 864–872. Bar-Yossef, Z., Keidar, I., Schonfeld, U.: Do not crawl in the dust: different urls with similar text. In: Proceedings of the 16th international conference on World Wide Web, ACM New York (2007), 111-120. Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286 (5439), (1999), 509–512. Barbosa, L., Freire, J., Silva, A.: Organizing hidden-web databases by clustering visible web documents. ICDE 2007. IEEE 23rd International Conference on Data Engineering (2007), 326-335. Boldi, P., Codenotti, B., Santini, M., Vigna, S.: Ubicrawler: A scalable fully distributed web crawler. Software: Practice & Experience 34(8), (2004), 721–726. Broder, A. Z., Glassman, S. C., Manasse, M. S., Zweig, G.: Syntactic clustering of the web. In: Selected papers from the sixth international conference on World Wide Web. Vol. 29. Elsevier Science Publishers Ltd., Essex, UK (1997), 1157–1166. Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Computer Networks 33 (1-6), (2000) 309–320. Broder, A., Najork, M., Wiener, J.: Efficient URL caching for World Wide Web crawling. In: Proceedings of the 12th international conference on World Wide Web, Budapest, Hungary (2003), 679 – 689. Chang, K.C.C., He, B., Li, C., Patel, M., Zhang, Z.: Structured databases on the web: observations and implications. SIGMOD Rec. 33, 3 (September 2004), 61-70. Cho, J., Garcia-Molina, H.: The Evolution of the Web and Implications for an Incremental Crawler. In: Proceedings of the 26th International Conference on Very Large Data Bases (VLDB '00), Amr El Abbadi, Michael L. Brodie, Sharma Chakravarthy, Umeshwar Dayal, Nabil Kamel, Gunter Schlageter, and Kyu-Young Whang (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2000), 200-209. Cho, J., Molina, H. G.: Parallel crawlers. In: Proceedings of the 11th international conference on World Wide Web (WWW '02). ACM, New York, NY, USA (2002), 124135. Cho, J., Garcia-Molina, H.: Effective page refresh policies for Web crawlers. ACM Trans. Database Syst. 28, 4 (December 2003), 390-426.


14. Dasgupta, A., Ghosh, A., Kumar, R., Olston, C., Pandey, S., Tomkins, A.: The discoverability of the web. In: Proceedings of the 16th international conference on World Wide Web (WWW '07). ACM, New York, NY, USA (2007), 421-430. 15. Edwards, J., Mccurley, K. S., Tomlin, J. A.: An adaptive model for optimizing performance of an incremental web crawler. In: Proceedings of the 10th international conference on World Wide Web (WWW '01). ACM, New York, NY, USA (2001), 106113. 16. Galambos, L.: Egothor2. WWW http://www.egothor.org/. 17. Fetterly, D., Manasse, M., Najork, M., Wiener, J.: A large-scale study of the evolution of web pages. In: Proceedings of the 12th international conference on World Wide Web (WWW '03). ACM, New York, NY, USA (2003), 669-678. 18. He, Y., Xin, D., Ganti, V., Rajaraman, S., Shah, N.: Crawling Deep-web Entity Pages. In submission. 19. Hersovici, M., Jacovi, M., Maarek, Y.S., Pelleg, D., Shtalhaim, M., Ur, S.: The sharksearch algorithm. An application: tailored Web site mapping. In: Proceedings of the seventh international conference on World Wide Web 7 (WWW7), Philip H. Enslow, Jr. and Allen Ellis (Eds.). Elsevier Science Publishers B. V., Amsterdam, The Netherlands, The Netherlands (1998), 317-326. 20. Heydon, A., Najork, M.: Mercator: A scalable, extensible Web crawler. World Wide Web 2, 4 (April 1999), 219-229. 21. Hsieh, J.M., Gribble, S.D., Levy, H.M.: The architecture and implementation of an extensible web crawler. In: Proceedings of the 7th USENIX conference on Networked systems design and implementation (NSDI'10). USENIX Association, Berkeley, CA, USA (2010), 22-22. 22. Kleinberg, J.M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.S.: The web as a graph: measurements, models, and methods. In: Proceedings of the 5th annual international conference on Computing and combinatorics (COCOON'99), Takao Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, and Takeshi Tokuyama (Eds.). Springer-Verlag, Berlin, Heidelberg (1999), 1-17. 23. Lee, H. T., Leonard, D., Wang, X., Loguinov, D.: IRLbot: scaling to 6 billion pages and beyond. In: Proceedings of the 17th international conference on World Wide Web (WWW '08). ACM, New York, NY, USA (2008), 427-436. 24. Madhavan, J., Ko, D., Kot, Ł., Ganapathy, V., Rasmussen, A., Halevy, A.: Google's Deep Web crawl. Proc. VLDB Endow. 1, 2 (August 2008), 1241-1252. 25. Menczer, F.: ARACHNID: Adaptive Retrieval Agents Choosing Heuristic Neighborhoods for Information Discovery. In: Proceedings of the 14th International Conference on Machine Learning (ICML97), D. Fisher (ed.), Morgan Kaufmann (1997), 227-235. 26. Nguyen, H., Nguyen, T., Freire, J.: Learning to extract form labels. In: Proc. VLDB Endow. 1, 1 (August 2008), 684-694. 27. Ntoulas, A., Cho, J., Olston, C.: What's new on the web?: the evolution of the web from a search engine perspective. In: Proceedings of the 13th international conference on World Wide Web (WWW '04). ACM, New York, NY, USA (2004), 1-12. 28. Raghavan, S., Garcia-Molina, H.: Crawling the Hidden Web. In: Proceedings of the 27th International Conference on Very Large Data Bases (VLDB '01), Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and

Tutoriál

Richard Thomas Snodgrass (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2001), 129-138. 29. Shkapenyuk, V., Suel, T.: Design and Implementation of a High-Performance Distributed Web Crawler. In: Proceedings of the 18th International Conference on Data Engineering (ICDE '02). IEEE Computer Society, Washington, DC, USA (2002), 357-368. 30. Upstill, T., Craswell, N., Hawking, D.: Predicting fame and fortune: PageRank or indegree?. In: Proc. 8th Australasian Document Computing Symposium, Canberra, Australia (2003), 31-40.

Systémy pro stahování dat z webu

Recommend Documents