Resource Discovery is een populaire kreet. De eerste Index van het Web die als commerciële databank werkt is al gesignaleerd. Moeten we bang zijn voor robots en spinnen? Caches moeten de overbelasting van het net bestrijden.

LRU URL

Informatie zoeken en bewaren in het World-Wide Web

Sommige mensen, op zoek naar het Internet, bellen de PTT inlichtingendienst. Die gaf in zo'n geval het telefoonnummer van XS4ALL; tegenwoordig wordt de klant met het eigen Planet Internet doorverbonden. U hoeft echter alleen 'ping internic.net' in te voeren; als u een antwoord terug krijgt, dan zit u op het net. Het opzoeken van IP nummers gaat automatisch met de Domain Name Service. Het World-Wide Web lijkt eerder gemaakt om in te verdwalen dan om gericht naar informatie te zoeken. Een groeiend aantal indexen probeert de gebruiker te helpen. De explosieve groei van WWW heeft tot overbelaste servers geleid, zoals de NASA site die afgelopen jaar opnamen van de Shoemaker-Levi komeet vertoonde.

zoekmethoden

De voornaamste manier om het Web te gebruiken is nog steeds het 'surfen' over hypertekst links naar pagina's met aanverwante informatie. Als startpunt kan een Home Page dienen, een lijstje met Bookmarks van eerder bezochte sites of een op onderwerp of geografische lokatie gerangschikte zoekboom. In dat geval heeft een verzamelaar min-of-meer bekende ingangen op een rij gezet. Het is natuurlijk ook mogelijk het tegen betaling uit laten zoeken.

Programmeurs hebben diverse zgn. robots gemaakt, die zelfstandig het Web afzoekt. In de eenvoudigste vorm gaat het om een toevoeging aan een browser, die zoekt op een trefwoord i.p.v. een URL adres, zoals EMACS-WWW of Fish Search. Die vragen alle pagina's op waarnaar wordt verwezen in het huidige document en volgen dan alle links in de opgevraagde documenten enz. tot voldoende 'hits' zijn gescoord of de tijdslimiet verstreken is of de recursielimiet bereikt.

De meeste robots verzamelen hun informatie batchgewijs en slaan die op in een grote database; ze hebben hun eigen home page waar vragen kunnen worden gesteld en beantwoord. Zo is de World Wide Web Worm een vrij primitief schepsel dat achter elkaar pagina's opvraagt en die met de titelregel of anchor tekst in de database opslaat. Op deze 'brute force' manier zijn uiteindelijk grote delen van het Web in kaart gebracht.

World Wide Web Worm

De term 'worm' staat eigenlijk voor een programma dat zichzelf vermenigvuldigt als een virus, maar dan via een netwerk. WWWW en consorten blijven op hun plaats maar vuren hun vragen op verschillende servers af. Ook dit soort netbewoners is niet overal welkom, vooral als ze snel achtereen grote hoeveelheden data opvragen. Om misbruik te voorkomen geven lang niet alle auteurs hun code vrij. Aan de andere kant besparen robots de gebruiker tijd en het net bandbreedte. Martijn Koster heeft een gedragscode opgesteld die door de meeste betrokkenen wordt onderschreven; robots zijn immers moeilijk van gewone gebruikers te onderscheiden. Zijn voorstel komt erop neer dat servers een file '/robots.txt' opnemen die voor verschillende robot programma's aangeeft welke directories voor hun verboden gebied zijn, zoals de /tmp directory.

Met behulp van een depth-first search algoritme kan snel een groot aantal sites worden bestreken, terwijl breadth-first search meer op volledigheid gericht is. In beide gevallen moeten duplicaten worden geëimineerd, wat niet onproblematisch is omdat verschillende URLs naar hetzelfde object kunnen verwijzen en één URL naar meerdere objecten.

Fish Search

Het Fish Search algoritme probeert snel specifieke informatie te zoeken in plaast van het hele Web in kaart te brengen. Als een opgevraagd document relevante informatie bevat, dan worden de links daarin vooraan de te doorzoeken lijst gezet, wat neerkomt op depth first search. De links in irrelevante documenten komen helemaal achteraan de lijst te staan, wat neerkomt op breadth first search. Om een goed overzicht te krijgen, worden zoveel mogelijk verschillende sites bezocht en daarvan slechts enkele pagina's opgevraagd. Van sites met een trage verbinding worden weinig documenten opgevraagd.

WebCrawler

De WebCrawler kent zowel een batch modus om de index bij te werken en een interactieve modus om gericht te zoeken. In het eerste geval wordt een variant op breadth-first search gebruikt waarin van iedere server enkele documenten worden opgevraagd. In de interactieve modus worden eerst een aantal relevante documenten in de index opgezocht en vandaaruit wordt verder gewerkt als bij Fish Search. Om het netwerk te ontzien laat Fish Search zijn vissen één voor één los terwijl de WebCrawler het werk door maximaal 13 agents of loopjongens tegelijk laat doen.

NOG NIET CONTENT?

Om nuttig te zijn moet een database meer doen dan enkel een grote hoeveelheid data vergaren. Omdat een titel alleen weinig houvast biedt, is het beter ook de inhoud van de documenten te indexeren. Onderstaand voorbeeld van het resultaat van een query op de commerciële Infoseek database demonstreert hoe zoeken op een enkel trefwoord onverwachte resultaten oplevert.
BAZAR LATINO
Red Latinoamericana de Informacion en Europa. In samenwerking met de Digitale Stad (DDS), Amsterdam. Recepcion. De receptie van het gebouw / Recepcao / Reception. Sala de Exposiciones. Expositie ruimte / Sala de Exposicoes / ...
--- [694] http://www.dds.nl/~noticias/index.html (1K)
Eventos
Palestras e seminarios. Short Course: Dynamics of Turbulence and Numerical Implementation. Local: Sala 856L. Data: Dia 19/05/95 as 12:00h. Professor: Carlos A. Thompson. Contato: depto@mat.puc-rio.br. Seminarios de ...
--- [693] http://www.puc-rio.br/portugues/eventos.html (1K)
Sala Communications Publishers
Founded in 1983, Sala Communications is a medium sized trade magazine publisher with in-house advertising sales, editorial, preproduction, support functions and specialised in computer related publications covering the Dutch and Dutch speaking ...
--- [692] http://net.info.nl/sala/promous.html (4K)
Biblioteca
Sala Porfirio Diaz y Colecciones especiales. En la Sala Porfirio Diaz, se encuentra informacion acerca de los archivos personales de Miguel Covarrubias, Robert Barlow, Pablo Herrera Carrillo, Jose Miguel Quintana y del Gral. Porfirio Diaz, ...
--- [678] http://info.pue.udlap.mx/udla/biblioteca/ (1K)

Voor opslag van de complete teksten zijn vele gigabytes nodig; multimedia datatypen worden doorgaans overgeslagen. Om trefwoorden in teksten op te zoeken zijn er Unix utilities als fgrep (Boyer-Moore algoritme), egrep (zoeken met wildcards) en agrep (fuzzy search: zoeken naar strings die ongeveer met trefwoorden overeenkomen), maar die zijn alle te tijdrovend voor dergelijke grote databases.

indexen

Daarom zijn er efficiënte indexen ontwikkeld. Voor het Harvest projekt is de Glimpse index ontwikkeld die een te indexeren tekst opbreekt in losse woorden. De hoofdindex bestaat uit een lijst van woorden, die met agrep doorzocht kan worden. Ieder gevonden woord levert dan een pointer op naar een lijst van lokaties waar het betreffende woord voorkomt. Vooralsnog wordt de lokatie niet nauwkeuriger aangegeven dan de filenaam. Een voorbeeld index van informatica literatuur beslaat slechts 270 MB waar WAIS 9 GB nodig zou hebben. Firma's als Verity, Square en Nexial leveren ook search engines die aan Web servers gekoppeld kunnen worden.

Harvest bezit nog een alternatieve index, Nebula, die een query kan beperken tot een bepaald vakgebied, om valse treffers als in bovenstaand voorbeeld te voorkomen. Zoekdomeinen kunnen hiërarchisch gestruktureerd worden, bijv. Windows Databases als deelgebied van PC software.

De beste resultaten worden waarschijnlijk bereikt door met de hand trefwoorden of samenvattingen in te voeren, maar dat is veelal te bewerkelijk en bovendien foutgevoelig. Het Harvest projekt stelt flexibiliteit voorop omdat elke toepassing eigen eisen stelt. Er is een centraal meldpunt waar alle Harvest Servers zich kunnen laten registreren. Het Essence systeem dat wordt gebruikt om informatie te extraheren kan worden aangepast aan zeer uiteenlopende datatypen. Zo kunnen de titel en auteur uit LaTeX documenten worden gehaald of routine namen en copyright strings uit binaries. De systeembeheerder kiest of volledige teksten of samenvattingen worden geïnxeerd. Speciale methoden voor bijv. Postscript files en compressed tar archives zijn mogelijk en ook handmatig ingevoerde meta-informatie kan worden meegenomen. Door de Gatherer software op de zelfde machine als de te indexeren informatie te installeren kan de belasting van het net sterk worden teruggebracht.

WIE WAT BEWAART

Om zich te beveiligen tegen hackers en andere indringers hebben veel sites hun lokale netwerk afgeschermd van het Internet d.m.v. een firewall. Om van binnenuit toegang te krijgen tot externe servers zijn zgn. Proxies ingevoerd, met als schoolvoorbeeld de CERN httpd server en de daarop gebaseerde Netscape-servers.

De proxy heeft zowel een verbinding met binnen als buiten. HTTP clients zijn meestal al op het werken via een proxy tussenpersoon voorbereid. Zij sturen de gewenste URL naar de proxy. Die stuurt het verzoek door naar een host met zijn eigen adres als afzender en retourneert het resultaat door de opening in de firewall.

De soms matige performance van het Web bleek te kunnen worden verbeterd door de proxy van een cache te voorzien; verschillende browsers hebben hun privé-cache, maar die werkt vooral als de gebruiker Go back aanklikt. Httpd kan eveneens lokale files serveren aan touristen. Proxies worden sindsdien ook als cache gebruikt door wie zich niet in een firewall bevindt. Als de netwerkverbinding uitvalt is de bewaarde informatie nog bruikbaar.

Een probleem met caching is hoe te zorgen dat de kijker geen verouderde informatie uit de cache krijgt voorgeschoteld. In principe kan de bron zelf doorgeven welke pagina's gewijzigd zijn (Cache invalidation), maar dit is niet erg praktisch. De andere mogelijkheid is dat de cache verzoekt om een pagina te sturen indien die gewijzigd is sinds de vorige keer. Voor korte pagina's duurt uitwisseling van een statusbericht net zo lang als verzending van het hele document.

Anders dan een goede database kiest Internet voor performance boven gegarandeerde correctheid. Als de gebruiker op de Reload knop drukt krijgt ze wé een vers exemplaar. De gebruikelijke benadering is om documenten van een uiterste houdbaarheidsdatum te voorzien. Als die niet op het etiket is vermeld moet de webmaster (systeembeheerder) vuistregels gebruiken. Een andere strategie is om eerst de kortste levenduur te kiezen. Iedere keer als die verlopen is wordt het document opnieuw opgevraagd en als het nog het zelfde is, de levensduur verdubbeld. Helaas moet dat eens fout gaan. Afgezien van eenmalige objecten blijft het gemiddelde WWW document 44 dagen onveranderd.

De Eindhovenaren hebben naast de Fish Searcher ook de Lagoon cache ontwikkeld. De één zoekt informatie bij voorbaat op, terwijl de ander ze bewaart voor een volgende keer. De semi-handmatige Fish is selektiever dan een allesvretende robot. Integratie ligt dan ook in het verschiet.

SAMEN DELEN

Er dreigt nu een hele hoop dubbelop te worden gedaan. Vandaar zijn er voorzieningen om caches samen te laten werken. Als een cache een page mist laat ze verzoeken uitgaan naar de eigenlijke lokatie en een aantal soortgenoten en wacht op de eerste reactie.

Het Harvest projekt wil een optimale performance bereiken met grote aantallen Brokers, die ieder een replica van de database bezitten. Hun Flood-d protocol is geïnspireerd door Usenet News, dat goede responstijden haalt op een artikelenbestand van meerdere gigabytes, doordat elke site kopiën van alle relevante nieuwsberichten bijhoudt. Flood-d lijkt een beetje op het flood-fill algoritme, dat wordt gebruikt om een figuur (gesloten veelhoek) in te kleuren: begin bij een willekeurig punt en kleur alle omringende punten in die niet tot de rand behoren en vervolgens de buren van de juist bereikte punten. Volgens het inductieprincipe wordt zo uiteindelijk elk punt bereikt.

Flood-d verspreidt informatie via een virtuele topologie, die los staat van de fysieke bekabeling; met behulp van ping kan worden vastgesteld welke node het snelst reageert danwel de hoogste bandbreedte heeft. De zo gevonden logische topologie wijkt niet veel af van de feitelijke netwerkstruktuur en wordt dynamisch aangepast bij storingen. Nodes die volgens de logische topologie buren zijn werken hun databases onderling bij. De indeling wordt zo gekozen dat tussen elk paar nodes steeds ten minste twee of drie verbindingen bestaan, die tegelijk moeten uitvallen voordat delen van het net elkaar niet meer kunnen bereiken. Om ook heel grote netten in de hand te houden worden de nodes ingedeeld in groepen. Nodes houden kopieën bij van alle leden van hun groep en enkele leden zijn aangewezen om met vertegenwoordigers van andere groepen te overleggen.

De berekende logische topologie is niet optimaal, maar de bepaling van het optimum zou erg veel rekentijd vergen en bovendien snel verouderen. In plaats daarvan wordt een willekeurige geschikte oplossing gekozen, die met simulated annealing enigszins wordt verbeterd. De zo gekozen topologie ligt meestal vrij dicht bij het optimum.

Flood-d gebruikt het Timestamped Anti-Entropy protocol (TSAE), dat weliswaar niet garandeert dat alle klanten steeds dezelfde informatie zien en ook niet dat alle berichten van verschillende bronnen overal in dezelfde volgorde worden ontvangen, maar wel dat alle deelnemers alle berichten uiteindelijk korrekt zullen ontvangen, zwakke consistentie genoemd; ook worden ze wel als epidemische replicatie protocollen aangeduid. Het grootste voordeel is dat de service beschikbaar blijft als een verbinding uitvalt. Het TSAE protocol is ook bruikbaar voor in filesystemen van draagbare computers; er kan gewoon met lokale data worden doorgewerkt, maar af en toe worden wijzigingen met een andere machine gesynchroniseerd. Een ander voordeel is het efficiënt gebruik van netwerkcapaciteit. Gemiddeld genomen worden berichten snel verspreid en blijft de inconsistentie beperkt.

Als een replica een boodschap wil verzenden (om een verandering in de database door te geven) schrijft het die in een log-file en markeert het het tijdstip. De inhoud van de log wordt geacht server crashes te overleven. Van tijd tot tijd kiest een replica een ander replica uit om elkaars log-files te synchroniseren in een zgn. anti-entropie sessie door elkaar alle boodschappen in hun logboek te sturen die de ander nog niet had. Daarbij worden boodschappen van een afzender steeds in chronologische volgorde verwerkt.

Een voorbeeld van een anti-entropie sessie is te zien in de figuur. Bovenin zijn de log-files van A en B weergegeven waarin staat welke berichten A en B reeds hebben gezien. A en B zenden elkaar eerst via een betrouwbaar protocol de nummers van de meest recente boodschappen in hun log-file afkomstig van A, B en C. Daaruit kan worden afgeleid dat de gearceerde berichten moeten worden uitgewisseld. Alleen boodschap nr. 5 wordt twee keer verzonden. Als dat is gebeurd kunnen berichten die iedereen heeft gezien uit de log-file worden verwijderd en gebruikt om de permanente database bij te werken. Synchronisatie is mogelijk door met elk bericht de lokale tijd mee te zenden. Als een bericht wordt ontvangen met een later klokstempel dan de lokale klok, moet de laatste vooruit worden gezet.

Verbetering van de toegankelijkheid van het Web is een terrein dat nog niet uitontwikkeld is. De nu beschikbare sites kampen met een overmatige belangstelling. Wellicht zal de gebruiker voortaan voor zijn informatie moeten gaan betalen.

    GRAUWE GIDS
  1. http://www.cs.colorado.edu/home/mcbryan/WWWW.html
  2. http://web.nexor.co.uk/mak/doc/robots/robots.html
  3. http://www.win.tue.nl/win/cs/is/reinpost/www94/www94.html
  4. http://www.biotech.washington.edu/WebCrawler/WebQuery.html
  5. http://www.infoseek.com/Home
  6. ftp://cs.arizona.edu
  7. http://harvest.cs.colorado.edu
Daniel von Asmuth