Veb-indekser () je internet robot koji sistematski pretražuje veb, uglavnom u svrhe indeksiranja veb-lokacija. Takođe je poznat i kao program tragač ili pretraživač veb-lokacija. U daljem tekstu će se koristiti pojam tragač.
Pretraživači veba i neki sajtovi koriste tragače da ažuriraju veb-sadržaj ili indekse sadržaja drugih veb-sajtova. Programi tragači mogu da iskopiraju sve strane koje posete radi kasnijeg procesiranja od strane pretraživača veba koji indeksira stranice koje su preuzete, tako da bi ih korisnici brže pronalazili.
Programi tragači mogu da izvrše validaciju hiperveza i -{HTML}- koda. Takođe se mogu koristiti za ekstrakciju podataka sa veba.
Način rada programa tragača Tragač rad otpočinje sa nizom veb-adresa koje treba posetiti. Te adrese se nazivaju semena. Kako program tragač posećuje te veb-adrese, on prepoznaje sve hiperveze koje se nalaze na toj stranici i dodaje ih na listu veb-adresa koje treba posetiti, koja se naziva granica traganja. Kasnije se te stranice rekurzivno posećuju prema skupu politika posećivanja.
Velika količina veb-stranica povlači kao posledicu da tragač može da preuzme samo određeni broj veb-stranica u zadatom vremenskom roku, tako da je prioritet preuzimanja stranica jako bitan. Veliki broj promena povlači činjenicu da su stranice možda promenjene ili čak izbrisane.
Broj stranica za posećivanje koje generiše serverski softver, takođe otežava tragačima da izbegnu preuzimanje duplikata sadržaja. Postoji bezbroj kombinacija -{HTTP GET}- parametara, od kojih će samo mali broj vratiti jedinstven sadržaj. Na primer, uzmimo najprostiju on-lajn (eng. on-line) galeriju slika koja nudi tri opcije korisnicima, navedene pomoću HTTP GET parametara u veb-adresi. Ako postoji četiri načina da se sortiraju slike, tri izbora za velicinu ikonica, dva formata podataka, i opcija da onemogućimo sadržaj koji pruža korisnik, onda istom sadržaju možemo da pristupimo sa 48 različitih adresa, sve nastale od onog sto se može povezati na sajtu. Ova matematička kombinacija stvara problem tragačima, jer oni moraju da sortiraju kroz bezbroj kombinacija relativno malih promena da bi došli do jedinstvenog sadržaja.
Kao što su Edwards i saradnici naveli : "Uzevši u obzir to da opseg za rad tragača nije beskonačan, i ima svoju cenu, neophodno je da pretraživanje veba bude ne samo skalabilno, već i efikasno, ako želimo da održimo neku razumnu meru kvaliteta i svežine." Tragač mora pri svakom koraku pažljivo da bira koju će sledeću stranicu da poseti.
Ponašanje programa tragača je rezultat sledeće kombinacije politika: politika odabira, koja navodi koje stranice treba preuzeti, politika ponovnog posećivanja, koja navodi kada proveriti da li je došlo do promene stranice, politika „lepog ponašanja“, koja navodi načine za izbegavanje preopterećenje sajtova, politika paralelizacije, koja navodi kako upravljati distibuiranim tragačima.
Politike programa tragača Politika odabira Uzevši u obzir trenutnu veličinu veba, čak i veliki pretraživači veba pokrivaju samo udeo od dela dostupnog javnosti. Istraživanjaa sprovedena 2005. godine pokazala je da pretraživači veba velikih razmera ne indeksiraju više od 40% — 70% indeksablinog veba; prethodna istraživanja od strane Stiva Lorensa i Lija Džilsa pokazale su da ni jedan pretraživač veba nije indeksirao više od 16% veba 1999. godine. Pošto tragač uvek preuzima samo frakciju veb-stranice, veoma je poželjno da preuzeta frakcija sadrži najvažnije stranice, a ne samo nasumične uzorke veba.
Ovo zahteva jedinicu važnosti da bi se odredio prioritet veb-stranica. Vrednost stranice je funkcija njenog unutrašnjeg kvaliteta, njene popularnosti u pogledu hiperveza ili posećenosti, čak i njene veb-adrese. (Ovo drugo se odnosi na slučaj vertikalnih veb-pretraživača, ograničenih na jedinstveni internet domen najvišeg nivoa. Dizajniranje dobre politike odabira otežava još i činjenica da mora da radi sa delimičnim informacijama, kako kompletni skup veb-stranica nije poznat tokom rada programa tragača.
Janghu Čo i saradnici su sproveli prvo istraživanje o politikama za planiranje pretrage lokacija po vebu. Njihov skup podataka je bio 180.000 stranica sa domena -{stanford.edu}-, na kom su sprovedene simulacije nad tragačima sa različitim strategijama. Testirane mere za redosled su bile pretraga u širinu, -{backlink-count}- strategija i delimične -{PageRank}- kalkulacije.(-{PageRank}- je algoritam koji koristi Guglov pretraživač veba.) Jedan od zaključaka je bio da je, ako tragač želi da preuzme stranice sa visokim -{PageRank}- prioritetom ranije u toku svog rada, bolje primeniti delimične -{PageRank}- kalkulacije, zatim pretragu u širinu i -{backlink-count}- strategiju. Međutim, ovi rezultati su bili u okviru samo jednog domena. Čo je takođe napisao doktorsku disertaciju na Stanfordu vezanu za programe tragače.
Najork i Viner su sproveli indeksiranje lokacija na 328 miliona stranica, koristeći pretragu u širinu.Marc Najork & Janet L. Wiener (5. 2001). . Elsevier Science. Hong Kong. стр. 114—118 Otkrili su da ovom metodom program tragač preuzima stranice sa visokim -{PageRank}- prioritetom ranije tokom svoga rada (ali oni nisu uporedili ovu strategiju sa drugim strategijama). Objašnjenje dato od strane autora za ovakav rezultat bilo je da najvažnije stranice imaju mnogo hiperveza od strane brojnih hostova prema njima, i da takve hiperveze budu najranije pronađene, bez obzira na to sa kog hosta ili stranice počinje indeksiranje lokacija.
Abitbul je dizajirao strategiju zasnovanu na algoritmu -{OPIC}- (). U -{OPIC}- algoritmu svakoj stranici je data početna suma „novca”, koja se podjednako distribuira između stranica na koje pokazuje. To je slično -{PageRank}- izračunavanjima, ali je bilo brže i bilo je rađeno u jednom koraku. Tragač zasnovan na -{OPIC}- algoritmu prvo preuzima stranice u granici traganja koje imaju veću svotu novca. Eksperimenti su izvedeni na sintetičkom grafu od 100.000 stranica, sa stepenim zakonom raspodele unutrašnjih hiperveza. Međutim, nije sprovedeno ni jedno upoređivanje sa ostalim strategijama, niti eksperimentisanje na pravom vebu.
Paolo Boldi i saradnici su sproveli simulaciju na podskupu veba koja je sadržala 40 miliona stranica sa .it domena i 100 miliona stranica sa -{WebBase}--a, testirajući pretragu u širinu protiv pretrage u dubinu, nasumičnog poretka i sveznajuće strategije. Poređenje je zasnivano na tome koliko je -{PageRank}- dobijen na delimičnom indeksiranju lokacija približan pravoj vrednosti. Iznenađujuće, neke strategije koje nagomilavaju -{PageRank}- veoma brzo (pre svega, pretraga u širinu i sveznajuća strategija), pružaju veoma loša progresivna izračunavanja.
Baeza-Jejts i saradnici koristili su simulaciju na dva podskupa veba koji se sastojao od 3 miliona stranica sa .gr i .cl domena, testirajući nekoliko strategija.Baeza-Yates, R.; Castillo, C.; Marin, M.; Rodriguez, A. . Crawling a Country: Better Strategies than Breadth-First for Web Page Ordering. In Proceedings of the Industrial and Practical Experience track of the 14th conference on World Wide Web. Chiba, Japan. ACM Press. (2005). стр. 864—872. Pokazali su da i -{OPIC}- strategija i strategija koja koristi -{per-site}- red bolja od strategije koja koristi pretragu u širinu, i da je takođe, kada je to moguće, veoma efikasno koristiti prethodno indeksiranje lokacija kao smernicu za trenutno.
Šervin Danešpedžoh je dizajnirao algoritam zasnovan na zajednici, koji pronalazi dobra semena. Ovaj metod indeksira lokacije sa visokim -{PageRank}- prioritetom iz drugih zajednica u manje iteracija nego indeksiranje lokacija koje počinje nasumičnim semenima. Ovako se, koristeći ovu metodu, dobro seme može izvući iz veb-grafa koji je ranije korišćen. Pomoću ovih semena novo indeksiranje lokacija moze biti veoma efikasno.
Politika ponovnog posećivanja Veb je vrlo dinamične prirode, tako da indeksiranje njegove frakcije može da potraje nedeljama ili mesecima. Dok tragač završi svoje indeksiranje lokacija, mnogi događaji bi mogli da se dese, uključujući dodavanja, ažuriranja i brisanja sadržaja.
Iz tačke gledišta pretraživača veba, postoji cena koja je vezana za događaj koji se desio, a time za posledicu ima zastarelu kopiju resursa. Najkorišćenije funkcije troškova su svežina i starost.
Svežina — Ovo je binarna jedinica koja označava da li je lokalna kopija precizna ili nije. Svežina stranice u skladištu za dato vreme se definiše kao:
(ako je lokalna kopija jednaka u trenutku ) ili kao
(uobičajeno).
Starost — Ovo je jedinica koja pokazuje koliko je zastarela lokalna kopija. Starost stranice u skladištu, za dato vreme se definiše kao:
(ako nije modifikovana u trenutku ) ili kao
(uobičajeno).
Edvard Kofman je radio sa definicijom cilja tragača koja je ekvivalentna svežini, ali je to drugačije formulisao; on je predlagao da tragač mora da minimalizuje frakciju vremena za koju je stranica zastarela. On je takođe primetio da se indeksiranje lokacija može modelovati pomoću biračkog sistema sa više redova, a jedinstvenim serverom u kom je tragač server, a veb-sajtovi su redovi. Modifikacije stranica su dolasci birača, a prelazna vremena su intervali između pristupa stranica jednog veb-sajta. U ovom modelu, međuvreme koje se provodi u čekanju na birača je u biračkom sistemu je ekvivalentno prosečnoj starosti za program tragač.
Cilj tragača je da održi stranice u svojoj kolekciji što je moguće svežijim, ili da održava prosečnu starost stranica što je moguće nižom. Ovi ciljevi nisu ekvivalentni: u prvom slučaju tragača samo zanima broj stranica koje su zastarele, dok u drugom slučaju program tragač samo brine o starosti lokalnih kopija stranica.
Čo i Garsija-Molina su proučavali dve proste politike ponovnog posećivanja: Uniformna politika — Ovo podrazumeva posećivanje svih stranica istom učestalošću, bez obzira na njihovu brzinu promena. Proporcionalna politika — Ovo podrazumeva češće posećivanje onih stranica koje se brže menjaju. Učestalost posećivanja je direktno proporcionalna (procenjenoj) brzini promena.
(U oba slučaja, ponovljeni redosled indeksiranja se može izvšiti u nasumičnom ili fiksnom redosledu.)
Čo i Garsija-Molina su pokazali iznenađujuće rezultate po kojima — u smislu prosečne svežine — uniformna politika prevazilazi proporcionalnu politiku u indeksiranju, kako na simulaciji veba, tako i na pravom vebu.
Intuitivno, obrazloženje je to da, pošto tragači imaju ograničen broj stranica koji mogu da indeksiraju za određeno vreme, treba u obzir uzeti sledeće: alocirati previše novih indeksiranja na stranice koje se brzo menjaju, po cenu smanjenja učestalosti ažuriranja stranica i svežina stranica koje se brzo menjaju traje manje od svežine stranica koje se ne menjaju toliko često.
Drugim rečima, proporcionalna politika alocira više resursa da bi indeksirala stranice koje se češće menjaju, ali dobija manju ukupnu svežinu stranica od njih.