Zachowanie Web crawlera jest wynikiem kombinacji polityk:
- polityka wyboru, która określa strony do pobrania,
- polityka ponownych odwiedzin, która określa kiedy sprawdzać zmiany na stronach,
- polityka uprzejmości, która określa jak unikać przeciążania stron internetowych.
- polityka paralelizacji, która określa jak koordynować rozproszone roboty indeksujące.
Polityka selekcjiEdit
Przy obecnym rozmiarze Sieci, nawet duże wyszukiwarki pokrywają tylko część publicznie dostępnej części. Badanie z 2009 roku wykazało, że nawet duże wyszukiwarki indeksują nie więcej niż 40-70% indeksowalnej sieci; poprzednie badanie przeprowadzone przez Steve’a Lawrence’a i Lee Gilesa wykazało, że żadna wyszukiwarka nie indeksowała więcej niż 16% sieci w 1999 roku. Ponieważ crawler zawsze pobiera tylko ułamek stron internetowych, bardzo pożądane jest, aby pobrany ułamek zawierał najbardziej istotne strony, a nie tylko losową próbkę sieci.
Wymaga to metryki ważności dla nadawania priorytetów stronom internetowym. Znaczenie strony jest funkcją jej wewnętrznej jakości, popularności pod względem linków lub odwiedzin, a nawet adresu URL (to ostatnie w przypadku wyszukiwarek pionowych ograniczonych do pojedynczej domeny najwyższego poziomu lub wyszukiwarek ograniczonych do ustalonej strony WWW). Zaprojektowanie dobrej polityki wyboru ma dodatkową trudność: musi ona pracować z częściową informacją, ponieważ kompletny zestaw stron internetowych nie jest znany podczas indeksowania.
Junghoo Cho et al. przeprowadzili pierwsze badania nad polityką harmonogramowania indeksowania. Ich zestaw danych to crawl 180,000 stron z domeny stanford.edu, w którym przeprowadzono symulację crawlowania przy użyciu różnych strategii. Testowane metryki porządkowania to breadth-first, liczenie backlinków i częściowe obliczanie PageRank. Jednym z wniosków było to, że jeśli crawler chce pobrać strony z wysokim Pagerank na początku procesu crawlowania, to lepsza jest strategia częściowego Pagerank, a następnie breadth-first i backlink-count. Jednakże, wyniki te dotyczą tylko jednej domeny. Cho napisał również pracę doktorską w Stanford na temat crawlingu.
Najork i Wiener przeprowadzili rzeczywisty crawl na 328 milionach stron, używając strategii breadth-first. Stwierdzili, że crawl typu breadth-first przechwytuje strony z wysokim Pagerank już na początku crawlowania (ale nie porównali tej strategii z innymi). Autorzy tłumaczą ten wynik tym, że „najważniejsze strony mają wiele linków do nich z wielu hostów, a te linki zostaną znalezione wcześnie, niezależnie od tego, z którego hosta lub strony pochodzi crawl.”
Abiteboul zaprojektował strategię crawlowania opartą na algorytmie zwanym OPIC (On-line Page Importance Computation). W OPIC każda strona otrzymuje początkową sumę „gotówki”, która jest równo rozdzielana pomiędzy strony, na które wskazuje. Jest to metoda podobna do obliczania PageRank, ale jest szybsza i wykonywana tylko w jednym kroku. Crawler OPIC pobiera w pierwszej kolejności te strony, które mają większą ilość „gotówki”. Eksperymenty przeprowadzono na liczącym 100 000 stron grafie syntetycznym z rozkładem power-law linków. Nie było jednak porównania z innymi strategiami ani eksperymentów w prawdziwej sieci.
Boldi et al. użyli symulacji na podzbiorach sieci 40 milionów stron z domeny .it i 100 milionów stron z crawla WebBase, testując strategię breadth-first przeciwko depth-first, losowemu porządkowaniu i strategii omniscient. Porównanie opierało się na tym, jak dobrze PageRank obliczony na podstawie częściowego crawlowania przybliża prawdziwą wartość PageRank. Zaskakująco, niektóre wizyty, które bardzo szybko akumulują PageRank (w szczególności, breadth-first i omniscient visit) dostarczają bardzo słabych progresywnych przybliżeń.
Baeza-Yates et al. zastosowali symulację na dwóch podzbiorach sieci Web składających się z 3 milionów stron z domen .gr i .cl, testując kilka strategii indeksowania. Wykazali, że zarówno strategia OPIC, jak i strategia wykorzystująca długość kolejek per-site są lepsze od strategii breadth-first crawling, a także, że bardzo efektywne jest wykorzystanie poprzedniego crawlowania, gdy jest ono dostępne, do kierowania bieżącym.
Daneshpajouh et al. zaprojektowali oparty na społeczności algorytm odkrywania dobrych nasion. Ich metoda indeksuje strony o wysokim PageRank z różnych społeczności w mniejszej ilości iteracji w porównaniu do indeksowania z losowych nasion. Za pomocą tej nowej metody można wyodrębnić dobre nasiona z wcześniej przeszukanego grafu WWW. Używając tych nasion, nowe przeszukiwanie może być bardzo efektywne.
Ograniczanie śledzonych linkówEdit
Czołgacz może chcieć wyszukiwać tylko strony HTML i unikać wszystkich innych typów MIME. Aby żądać tylko zasobów HTML, crawler może wykonać żądanie HTTP HEAD, aby określić typ MIME zasobu sieciowego, zanim zażąda całego zasobu za pomocą żądania GET. Aby uniknąć licznych żądań HEAD, crawler może zbadać URL i zażądać zasobu tylko wtedy, gdy URL kończy się określonymi znakami, takimi jak .html, .htm, .asp, .aspx, .php, .jsp, .jspx lub ukośnikiem. Strategia ta może spowodować niezamierzone pominięcie wielu zasobów HTML.
Niektóre roboty indeksujące mogą również unikać żądania zasobów, które mają w sobie „?” (są tworzone dynamicznie) w celu uniknięcia pułapek na pająki, które mogą spowodować, że robot indeksujący będzie pobierał nieskończoną liczbę adresów URL z witryny. Ta strategia jest zawodna, jeśli witryna używa przepisywania adresów URL w celu uproszczenia swoich adresów URL.
Normalizacja adresów URLEdit
Crawlery zazwyczaj wykonują pewien rodzaj normalizacji adresów URL, aby uniknąć indeksowania tego samego zasobu więcej niż raz. Termin normalizacja URL, zwany również kanonicznością URL, odnosi się do procesu modyfikacji i standaryzacji adresu URL w spójny sposób. Istnieje kilka rodzajów normalizacji, które mogą być wykonane, w tym konwersja adresów URL na małe litery, usuwanie segmentów „.” i „…” oraz dodawanie ukośników do niepustych elementów ścieżki.
Path-ascending crawlingEdit
Niektóre roboty indeksujące mają na celu pobranie/załadowanie jak największej ilości zasobów z danej strony internetowej. Dlatego wprowadzono crawlera, który będzie wchodził na każdą ścieżkę w każdym adresie URL, który ma zamiar przeszukać. Na przykład, gdy podany zostanie adres URL http://llama.org/hamster/monkey/page.html, będzie on próbował przeszukać /hamster/monkey/, /hamster/, i /. Cothey odkrył, że crawler wspinający się po ścieżkach był bardzo skuteczny w znajdowaniu odizolowanych zasobów, lub zasobów, dla których nie znaleziono by linków przychodzących w zwykłym crawlowaniu.
Focused crawlingEdit
Ważność strony dla crawlera może być również wyrażona jako funkcja podobieństwa strony do danego zapytania. Web crawlery, które próbują pobrać strony, które są podobne do siebie, nazywane są crawlerami ukierunkowanymi lub topicznymi. Koncepcje indeksowania topicznego i skoncentrowanego zostały po raz pierwszy wprowadzone przez Filippo Menczera oraz Soumen Chakrabarti et al.
Głównym problemem w indeksowaniu skoncentrowanym jest to, że w kontekście indeksowania sieciowego, chcielibyśmy być w stanie przewidzieć podobieństwo tekstu danej strony do zapytania przed faktycznym pobraniem strony. Możliwym predyktorem jest anchor text linków; takie podejście zostało zastosowane przez Pinkertona w pierwszym crawlerze we wczesnym okresie istnienia sieci. Diligenti et al. proponują wykorzystanie pełnej zawartości stron już odwiedzonych do wnioskowania o podobieństwie pomiędzy zapytaniem a stronami, które nie zostały jeszcze odwiedzone. Wydajność skoncentrowanego indeksowania zależy głównie od bogactwa linków w konkretnym temacie, a skoncentrowane indeksowanie zazwyczaj opiera się na ogólnej wyszukiwarce internetowej w celu dostarczenia punktów startowych.
Akademickie skoncentrowane indeksowanieEdit
Przykładem skoncentrowanego indeksowania są akademickie indeksatory, które przeszukują wolnodostępne dokumenty związane z nauką, takie jak citeseerxbot, który jest indeksatorem wyszukiwarki CiteSeerX. Inne wyszukiwarki akademickie to Google Scholar i Microsoft Academic Search itp. Ponieważ większość prac naukowych jest publikowana w formacie PDF, tego rodzaju crawler jest szczególnie zainteresowany crawlowaniem plików PDF, PostScript, Microsoft Word, w tym ich zzipowanych formatów. Z tego powodu, ogólne crawlery open source, takie jak Heritrix, muszą być dostosowane do filtrowania innych typów MIME, lub oprogramowanie pośrednie jest używane do wyodrębnienia tych dokumentów i importowania ich do bazy danych i repozytorium. Identyfikacja, czy te dokumenty są akademickie czy nie jest wyzwaniem i może dodać znaczny narzut do procesu indeksowania, więc jest to wykonywane jako proces post crawlingu przy użyciu uczenia maszynowego lub algorytmów wyrażeń regularnych. Dokumenty akademickie są zazwyczaj pozyskiwane z domowych stron wydziałów i studentów lub ze stron publikacji instytutów badawczych. Ponieważ dokumenty akademickie stanowią jedynie niewielki ułamek wszystkich stron internetowych, dobry wybór nasion jest ważny dla zwiększenia wydajności tych indeksatorów. Inne akademickie roboty indeksujące mogą pobierać pliki tekstowe i HTML, które zawierają metadane prac naukowych, takie jak tytuły, prace i abstrakty. Zwiększa to ogólną liczbę dokumentów, ale znaczna część z nich może nie zapewniać bezpłatnego pobierania plików PDF.
Semantycznie ukierunkowany crawlerEdit
Innym rodzajem crawlerów ukierunkowanych jest crawler semantyczny, który wykorzystuje ontologie domenowe do reprezentowania map tematycznych i łączenia stron internetowych z odpowiednimi koncepcjami ontologicznymi dla celów selekcji i kategoryzacji. Dodatkowo, ontologie mogą być automatycznie aktualizowane w procesie indeksowania. Dong et al. wprowadzili taki crawler oparty na uczeniu się ontologii, wykorzystujący maszynę wektorów wspierających do aktualizacji zawartości pojęć ontologicznych podczas przeszukiwania stron internetowych.
Re-visit policyEdit
Web ma bardzo dynamiczną naturę, a przeszukiwanie ułamka sieci może trwać tygodnie lub miesiące. Do czasu zakończenia przeszukiwania, wiele zdarzeń mogło się wydarzyć, w tym tworzenie, aktualizacje i usuwanie.
Z punktu widzenia wyszukiwarki, istnieje koszt związany z niewykryciem zdarzenia, a tym samym posiadanie nieaktualnej kopii zasobu. Najczęściej stosowanymi funkcjami kosztów są świeżość i wiek.
Świeżość: Jest to miara binarna, która wskazuje, czy lokalna kopia jest dokładna, czy nie. Świeżość strony p w repozytorium w czasie t definiuje się jako:
F p ( t ) = { 1 i f p i s e q u a l t o c a l c o p y a t t t i m e t 0 o t h e r w i s e {{p}(t)={{begin{cases}1&{\rm {if}}~p~{\rm {~is~equal~to~the~local~copy~at~time}}~t\\0&{\rm {otherwise}}\end{cases}}}
Age: Jest to miara, która wskazuje jak bardzo nieaktualna jest kopia lokalna. Wiek strony p w repozytorium, w czasie t jest zdefiniowany jako:
A p ( t ) = { 0 i if p i’s n o t m o d i f i e d a t i m e t – m o d i f i c a t i m e o n t i m e o of p o t h e r w i s e {{displaystyle A_{p}(t)={{begin{cases}0&{{{if}}~p~{is~not~modified~at~time}}~t}}{{{rm {modification~time~of}}~p& {{{rm {otherwise}} end{cases}}
Coffman i in. opracowali definicję celu crawlera sieciowego, która jest równoważna świeżości, ale używają innego sformułowania: proponują, aby crawler minimalizował ułamek czasu, w którym strony pozostają nieaktualne. Zauważyli oni również, że problem indeksowania stron internetowych może być modelowany jako system z wieloma kolejkami, z jednym serwerem, w którym indekser jest serwerem, a strony internetowe są kolejkami. Modyfikacje stron to przybycie klientów, a czasy przełączania to odstępy między kolejnymi wejściami na stronę w pojedynczej witrynie. W tym modelu, średni czas oczekiwania na klienta w systemie ankietowym jest równoważny średniemu wiekowi Web crawlera.
Celem crawlera jest utrzymanie średniej świeżości stron w jego kolekcji na jak najwyższym poziomie, lub utrzymanie średniego wieku stron na jak najniższym poziomie. Cele te nie są równoważne: w pierwszym przypadku crawlerowi chodzi tylko o to, ile stron jest nieaktualnych, w drugim zaś o to, ile lat mają lokalne kopie stron.
Dwie proste polityki ponownego odwiedzania były badane przez Cho i Garcia-Molina:
- Uniform policy: Polega ona na ponownym odwiedzaniu wszystkich stron w kolekcji z taką samą częstotliwością, niezależnie od tempa ich zmian.
- Polityka proporcjonalna: Polega na częstszym odwiedzaniu stron, które zmieniają się częściej. Częstotliwość odwiedzin jest wprost proporcjonalna do (szacowanej) częstotliwości zmian.
W obu przypadkach, powtarzana kolejność indeksowania stron może być wykonana w kolejności losowej lub stałej.
Cho i Garcia-Molina udowodnili zaskakujący wynik, że pod względem średniej świeżości, polityka jednolita przewyższa politykę proporcjonalną zarówno w symulowanej sieci, jak i w rzeczywistym indeksowaniu sieci. Intuicyjnie, rozumowanie jest takie, że ponieważ roboty indeksujące mają ograniczenie co do liczby stron, które mogą indeksować w danym przedziale czasowym, (1) będą alokować zbyt wiele nowych indeksów do szybko zmieniających się stron kosztem rzadziej aktualizowanych stron, oraz (2) świeżość szybko zmieniających się stron trwa krócej niż świeżość rzadziej zmieniających się stron. Innymi słowy, polityka proporcjonalna alokuje więcej zasobów do indeksowania często aktualizujących się stron, ale doświadcza mniej całkowitego czasu świeżości od nich.
Aby poprawić świeżość, crawler powinien karać elementy, które zmieniają się zbyt często. Optymalną polityką rewizyt nie jest ani polityka jednolita, ani polityka proporcjonalna. Optymalną metodą dla utrzymania średniej świeżości na wysokim poziomie jest ignorowanie stron, które zmieniają się zbyt często, a optymalną dla utrzymania średniego wieku na niskim poziomie jest stosowanie częstotliwości dostępu, które monotonicznie (i subliniowo) rosną wraz z tempem zmian każdej strony. W obu przypadkach optimum jest bliższe polityce równomiernej niż proporcjonalnej: jak zauważają Coffman et al. „aby zminimalizować oczekiwany czas przestarzałości, dostępy do poszczególnych stron powinny być możliwie równomiernie rozłożone”. Wyraźne formuły dla polityki ponownych odwiedzin nie są osiągalne w ogólności, ale można je uzyskać numerycznie, ponieważ zależą od rozkładu zmian stron. Cho i Garcia-Molina pokazują, że rozkład wykładniczy dobrze pasuje do opisu zmian stron, podczas gdy Ipeirotis et al. pokazują, jak używać narzędzi statystycznych do odkrywania parametrów, które wpływają na ten rozkład. Zauważ, że rozważane tutaj polityki ponownego odwiedzania traktują wszystkie strony jako jednorodne pod względem jakości („wszystkie strony w sieci są warte tyle samo”), co nie jest realistycznym scenariuszem, więc dalsze informacje o jakości stron internetowych powinny być uwzględnione w celu osiągnięcia lepszej polityki indeksowania.
Polityka uprzejmościEdit
Crawlery mogą pobierać dane znacznie szybciej i bardziej dogłębnie niż ludzkie wyszukiwarki, więc mogą mieć paraliżujący wpływ na wydajność witryny. Jeśli pojedynczy crawler wykonuje wiele żądań na sekundę i/lub pobiera duże pliki, serwer może mieć problem z nadążeniem za żądaniami od wielu crawlerów.
Jak zauważył Koster, użycie crawlerów jest przydatne w wielu zadaniach, ale ma swoją cenę dla ogółu społeczności. Koszty korzystania z crawlerów obejmują:
- zasoby sieciowe, ponieważ crawlery wymagają znacznej przepustowości i działają z dużym stopniem równoległości przez długi okres czasu;
- przeciążenie serwerów, zwłaszcza jeśli częstotliwość dostępu do danego serwera jest zbyt duża;
- słabo napisane crawlery, które mogą powodować awarie serwerów lub routerów, lub które pobierają strony, których nie są w stanie obsłużyć; oraz
- crawlery osobiste, które, jeśli zostaną wdrożone przez zbyt wielu użytkowników, mogą zakłócać pracę sieci i serwerów WWW.
Częściowym rozwiązaniem tych problemów jest protokół wykluczenia robotów, znany również jako protokół robots.txt, który jest standardem dla administratorów wskazującym, do których części ich serwerów WWW nie powinny mieć dostępu roboty indeksujące. Standard ten nie zawiera sugestii co do odstępu czasu pomiędzy wizytami na tym samym serwerze, mimo że odstęp ten jest najbardziej efektywnym sposobem uniknięcia przeciążenia serwera. Od niedawna komercyjne wyszukiwarki, takie jak Google, Ask Jeeves, MSN i Yahoo! Search, mogą korzystać z dodatkowego parametru „Crawl-delay:” w pliku robots.txt, aby wskazać liczbę sekund, które należy odłożyć między kolejnymi żądaniami.
Pierwszą proponowaną przerwą między kolejnymi odsłonami pageloads było 60 sekund. Jednakże, jeśli strony byłyby pobierane w tym tempie z witryny zawierającej ponad 100 000 stron przez idealne połączenie o zerowych opóźnieniach i nieskończonej przepustowości, pobranie całej witryny zajęłoby ponad 2 miesiące, a ponadto wykorzystany zostałby tylko ułamek zasobów tego serwera WWW. Nie wydaje się to akceptowalne.
Cho używa 10 sekund jako interwału dostępu, a WIRE używa 15 sekund jako wartości domyślnej. MercatorWeb stosuje adaptacyjną politykę uprzejmości: jeśli pobranie dokumentu z danego serwera zajęło t sekund, crawler czeka 10t sekund przed pobraniem następnej strony. Dill et al. używają 1 sekundy.
Dla tych, którzy używają crawlerów do celów badawczych, potrzebna jest bardziej szczegółowa analiza kosztów i korzyści, a przy podejmowaniu decyzji o tym, gdzie i jak szybko crawlować, należy wziąć pod uwagę względy etyczne.
Potwierdzone dowody z logów dostępu pokazują, że interwały dostępu znanych crawlerów wahają się od 20 sekund do 3-4 minut. Warto zauważyć, że nawet będąc bardzo uprzejmym i podejmując wszelkie środki ostrożności, aby nie przeciążać serwerów WWW, otrzymujemy pewne skargi od administratorów serwerów WWW. Brin i Page zauważają, że: „… uruchomienie crawlera, który łączy się z ponad pół milionem serwerów (…) generuje sporą ilość e-maili i telefonów. Ze względu na ogromną liczbę osób wchodzących na linię, zawsze znajdą się tacy, którzy nie wiedzą, czym jest crawler, ponieważ jest to pierwszy, jaki widzieli.”
Polityka równoległościEdit
Czołgacz równoległy to crawler, który uruchamia wiele procesów równolegle. Celem jest zmaksymalizowanie prędkości pobierania przy jednoczesnym zminimalizowaniu narzutu wynikającego z paralelizacji oraz uniknięcie wielokrotnego pobierania tej samej strony. Aby uniknąć pobierania tej samej strony więcej niż jeden raz, system indeksowania wymaga polityki przypisywania nowych adresów URL odkrytych podczas procesu indeksowania, ponieważ ten sam adres URL może zostać znaleziony przez dwa różne procesy indeksowania.