\documentclass[twoside,12pt]{article} \usepackage{graphics,latexsym,a4wide} \usepackage[bf,centerlast]{subfigure} \usepackage{graphicx} \usepackage{amsmath} \usepackage[latin2]{inputenc} \usepackage{t1enc} \usepackage[magyar]{babel} \usepackage{hyperref} \selectlanguage{magyar} \DeclareGraphicsRule{.png}{eps}{.bb}{`bmeps -p3 -c -er8f #1} \newenvironment{proof}{\noindent{\bf Bizonyítás:}}{\qed\bigskip} \newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip} \newtheorem{thm}{Tétel} \newtheorem{corollary}{Következmény} \newtheorem{lemma}{Lemma} \newtheorem{claim}{Állítás} \newtheorem{definition}{Definíció} \newtheorem{example}{Példa} \newtheorem{algorithm}{Algoritmus} \newtheorem{note}{Megjegyzés} \newcommand{\qed}{$\Box$} \newcommand{\eloadas}[2]{ %\pagestyle{myheadings}[Hálózatok és a World Wide Web matematikája][#1 \hfill #2] \thispagestyle{empty} \noindent \begin{center}\framebox{ \vbox{ \hbox to 5.875in { {Hálózatok és a World Wide Web matematikája \hfill 2003/2004 I. félév} } \vspace{4mm} \hbox to 5.875in {\hfill {\Large #1} \hfill #2} \vspace{2mm} \hbox to 5.875in { {\it Előadó: Benczúr András\quad \texttt{benczur@sztaki.hu} \hfill } } \hbox to 5.875in { {\it Jegyzetíró: Takács Bálint\quad \texttt{takbal@elte.hu}} \hfill } }}\end{center} \vspace*{4mm} } \begin{document} \eloadas{Tizedik előadás}{2003. dec. 18.} \section{Földrajzi helyzet megtalálása ad-hoc mobil hálózatokban} Ismétlésként: az ad-hoc mobil hálózatok olyan mobil eszközökből (állomásokból, egységekből) spontán szerveződő csomagkapcsolt hálózatok, ahol nincs semmilyen központi infrastruktúra vagy szolgáltatás (maximum a földrajzi információhoz lehet hozzáférni). A fő feladat itt két tetszőleges állomás közötti kommunikáció megoldása a többi eszköz közreműködésével. Ebben a hálózatban minden eszköz egyúttal egy útvonalválasztó (router) is. Ha ismerjük az eszközök fizikai helyzetét, akkor könnyű megadni egy csomagtovábbítási eljárást, amellyel a kommunikáció lebonyolítható: mindenki annak a szomszédjának küldi tovább a csomagot, amely fizikailag a legközelebb van a csomagban megjelölt célállomáshoz, ha pedig nincs ilyen, hibaüzenetet küld a feladónak ugyanazon az útvonalon, amelyen a csomag érkezett. Ez az algoritmus nem tudja okosan elkerülni a hálózatban meglevő ,,lyukak'' miatt keletkező zsákutcákat. A problémára léteznek megoldási javaslatok, de most egyszerűen tegyük fel, hogy az eszközök elég sűrűn helyezkednek el. Sajnos az üzenet megfogalmazásakor a legritkább esetben tudjuk a cél konkrét földrajzi helyzetét. A címzettet inkább valamilyen azonosító (pl. egy telefonszám) alapján szeretnénk megtalálni. Az ismertetendő algoritmus célja egy \emph{,,Location Service''} létrehozása, amivel központi infrastruktúra nélkül lehetséges megtalálni kevés (kb. $log(n)$) lépésben egy azonosító alapján valaki földrajzi helyzetét. Az algoritmus skálázható abban az értelemben, hogy (a) egyik eszköz sem képez szűk keresztmetszetet, az adminisztrációs teher várhatóan egyenletesen oszlik el az egyes eszközök között, (b) egy állomás kiesése nem túl sok más állomás elérhetőségét befolyásolja, (c) lokális abban az értelemben, hogy egy közeli állomás megtalálása nem igényel egészen távoli állomásokkal történő kommunikációt, (d) nincs szüksége túl sok erőforrásra.\footnote{A (d) pont kivételével ezek a tulajdonságok nem teljesülnek a triviális megoldásra, azaz ha rögzített földrajzi pozíciójú központi szerverekkel próbálnánk megoldani a szolgáltatást.} \subsection{Az algoritmus leírása} Tegyük fel, hogy minden eszköz tudja a saját földrajzi pozícióját, pl. GPS segítségével. Tegyük fel azt is, hogy az egységek szomszédjaikhoz elég közel vannak ahhoz, hogy közvetlen tudnak kommunikálni. A szomszédok rendszeresen tudatják egymással földrajzi pozícióikat és azonosítójukat ,,beköszönő'' üzenetek váltásával. Minden egységnek kiosztunk egy azonosító számot. Ez a gyakorlatban lehet pl. telefonszám vagy IP cím, itt az egyszerűség kedvéért kétjegyű számokat fogunk használni. Az algoritmus lényege, hogy minden állomás ,,toboroz'' néhány másik egységet, és folyamatosan tudatja vele a földrajzi helyzetét. Ezen állomásokat az adott egységhez rendelt \emph{location server}-nek, magyarul \emph{diszpécsernek} fogjuk hívni. Természetesen minden egységből lehet diszpécser, sőt, minden egység várhatóan igen sok másiknak lesz diszpécsere. Tegyük fel, hogy előre rögzítjük a világ egy négyzeteken alapuló felbontását (\ref{fig:alg}. ábra). A teljes világot egy nagy négyzetnek tekintve azt négy egyforma négyzetre vágjuk, és a keletkező négyzetekben ezt az eljárást $k$ alkalommal megismételjük. A kiinduló négyzet oldalait így $2^k$ részre partícionáljuk. A felosztás során kapott nagyobb négyzeteket is a felosztás részeként ,,tartjuk fejben'' (hasonlóan a ,,quad-tree'' néven ismert felbontáshoz). Tegyük fel, hogy a legkisebb négyzetek mindegyike már olyan kicsi, hogy az ezen belül elhelyezkedő mobil eszközök szomszédosak. Ekkor igazából nincs miért megkülönböztetni ezeket az egységeket a hálózat szempontjából, hiszen köztük teljes a kommunikáció, ezért a példában feltesszük, hogy a legkisebb cellákban csak egy egység van, illetve megengedjük azt is, hogy egy cella üres legyen. \begin{figure} \subfigure[A B jelzésű (17-es azonosítójú) egység diszpécserei] { \includegraphics[width=8cm]{first.png} \label{fig:alg:locservs} } \subfigure[Egy teljes hálózat diszpécserei illetve két példa-lekérdezés útvonala] { \includegraphics[width=8cm]{second.png} \label{fig:alg:locservs2} } \caption{\textbf{A diszpécserek kiosztása illetve az algoritmus működése.} Az \ref{fig:alg:locservs}. ábrán a kettős széllel rajzolt négyzetek azok, amelyekben a B állomás diszpécsereket keres. A diszpécserek a bekarikázott azonosítókkal rendelkező egységek lesznek. A \ref{fig:alg:locservs2}. ábrán a négyzetekben szereplő nagyobb szám az adott cellában tartózkodó egység azonosítója, a bal felső sarok felsorolása pedig azon egységek azonosítói, amelyek földrajzi pozícióját a cellában tartózkodó egység ismeri. Az ábrába be lett rajzolva két, az A jelű állomások (90 és 76) által végrehajtott B-re vonatkozó példa-lekérdezés útvonala.} \label{fig:alg} \end{figure} Minden egységhez a következő módon rendelünk diszpécsereket: tekintsük a felosztás összes tetszőleges méretű négyzetét, amelyek területén tartózkodik az illető E egység. Minden ilyen négyzetnek három szomszédja van az őt befoglaló nagyobb négyzetben. Válasszunk minden ilyen szomszédos négyzetben egy diszpécsert E-hez: keressük meg azt, amelynek a sorszáma a legkisebb az E sorszámánál nagyobb sorszámok közül ebben a négyzetben. Természetesen technikai okokból ez a reláció ,,átfordul'' a maximális azonosítószámnál, mert különben pl. a maximális azonosítószámú egységhez nem tudnánk diszpécsert rendelni. Egy példa látható a \ref{fig:alg:locservs}. ábrán. A \ref{fig:alg:locservs2}. ábrán láthatjuk egy konkrét esetben az összes kiosztott diszpécsert. Nézzük, hogyan kérdezhetjük le valaki földrajzi helyzetét a diszpécserek segítségével. A lekérdezés algoritmusa tulajdonképp a diszpécserek kijelölésére szolgáló algoritmus fordítottja: ha valamely A egység keresi B-t, akkor A elküldi a kérdést egy olyan egységnek, amely az általa nyilvántartott egységek listájában (azaz amelyeknek ő diszpécsere) a legkisebb, B azonosítójánál nagyobb egyenlő azonosítóval rendelkezik. Ezt megteheti, hiszen definíció szerint diszpécser mivoltából következően tudja a fizikai pozícióját. Ezzel reményeink szerint előbb-utóbb direkt B-hez jutunk, aki -- feltéve, hogy a kérés tartalmazza A földrajzi helyzetét -- a saját pozícióját már el tudja küldeni A-nak a bevezetőben leírt útvonalválasztó eljárással. Két példa látható erre az eljárásra a \ref{fig:alg:locservs2}. ábrán. Miért működik az algoritmus? Tekintsük a négyzeteknek azt a sorozatát, amelyek minden tagja tartalmazza az eredetileg lekérdező egységet valamint az aktuális lépést követő egységet, és a legkisebb az ilyen négyzetek közül. Ez a sorozat biztos, hogy növekvő négyzeteket tartalmaz, "legrosszabb" esetben ezen négyzetek mindegyike csak eggyel nagyobb rendű, mint az előző. Elég azt belátni, hogy a lekérdezések során minden lépésben megtaláljuk a sorozat következő négyzetén belül azt az egységet, amely a legjobb abban az értelemben, hogy az azonosítója a legkisebb a keresett egység azonosítójánál nagyobb egyenlő azonosítók közül. Nyilván a négyzetek méretének növekedésével előbb-utóbb belekerül a célállomás is egy ilyen négyzetbe, és ha az állítás igaz, akkor neki kell lenni a legjobbnak abban a négyzetben, tehát ebben a lépésben már rá is találtunk. Az állítást legkönnyebb egy példán keresztül belátni. Nézzük meg a \ref{fig:alg:locservs2}. ábrán azt az példát, amikor a 76-os egység szeretné megtalálni a 17-est. A 76-os nyilván a legjobb saját magán belül. A második lépésben a 2x2-es befoglaló négyzetben nyilván a legjobb azonosítójúhoz jutunk (ez most a 21), hiszen 76 minden szomszédjának diszpécsere, ez itt most véletlen. A harmadik lépés az érdekes. Tudjuk, hogy a 21-et tartalmazó 2x2-es négyzetben a 21 a legjobb a keresett 17-esre nézve. Ha most az eggyel nagyobb rendű 4x4-es négyzetben létezik egy 21-estől eltérő másik, jobb azonosító, akkor ez nagyobb egyenlő mint 17, viszont kisebb mint 21. Jelölje ezt X. Ebben az esetben X-nek 21 mindenképp diszpécsere, hiszen X-nek kellett egy diszpécsert választania a 2x2-esben is, és ott már tudjuk, hogy a legjobb 17-re és így X-re nézve is a 21. Tehát a 21-es diszpécsere minden egységnek, amely 17 nél nagyobb egyenlő, kisebb mint 21 és a 4x4-es négyzetben helyezkedik el, így a következő lépésben a lekérdezés ezzel az egységgel fog folytatódni. Esetünkben egy ilyen azonosító van, ez a 20-as, és ő ugyanabban a 8x8-as négyzetben van, mint a keresett 17, tehát ő már egyenesen oda irányítja a lekérdezést. Ha úgy tekintjük, hogy minden egység diszpécsere önmagának, akkor általánosabban is fogalmazhatunk: \begin{claim} Ha C a keresett egység azonosítója, akkor minden négyzetben a legkisebb C-nél nagyobb azonosítójú X egység diszpécsere az eggyel nagyobb rendű négyzetbeli, a legkisebb C-nél nem nagyobb azonosítójúnak. \end{claim} Világos, hogy a lekérdező algoritmus legfeljebb annyi lépést igényel, mint ahányadik rendű négyzetig eljutunk a keresés során, így a lépések száma a világ fizikai méretével logaritmikusan skálázódik. Természetesen egy-egy lépés során el kell juttatnunk egy csomagot az adott rendű négyzet egy másik pontjára, tehát közben a leírt útvonalválasztó algoritmus szintjén viszont sok apró lépést kell tennünk. Jogos kérdés, hogy miként lehet a diszpécserek kijelölését a gyakorlatban megoldani, hiszen valamely E egység nem tud távolból ,,kijelölni'' senkit: ehhez nem tudja sem a földrajzi pozíciójukat, sem azt, hogy kik vannak egy adott négyzetben. Valójában erre nincs is szükség. Tegyük fel, hogy E valamelyik négyzetben szeretne egy diszpécsert szerezni. Ilyenkor egyszerűen küld egy, a saját helyzetét tartalmazó csomagot azon négyzet tetszőleges pontjára egy speciális jelöléssel (a koordinátákat ismeri, hiszen a világ felosztását előre rögzítettük). Az első ottani egység megkapva ezt a csomagot, elindít egy ugyanolyan keresést E irányába, mint amikor az előbb A kereste B-t, de most egy speciális jelöléssel, B helyzetével és a négyzet paramétereivel. Az utolsó olyan egység, amely a szóbanforgó négyzetből kifelé akarná továbbítani a csomagot, egyszerűen nem küldi tovább, hanem ő lesz B diszpécsere. Egyszerűbben fogalmazva, egy újonnan belépő egység megpróbál magának üzenetet küldeni valamelyik négyzeten keresztül, és akinek már nem sikerül továbbküldenie az adott négyzetben, az automatikusan diszpécserévé válik. Tehát valójában senki sem tudja, kik az ő diszpécserei: a diszpécserség csak egyirányú kapcsolatot jelent. Belátható, hogy ezzel az eljárással a diszpécserek rendszere a ,,nulláról'' felépíthető: ha a négyzetes felbontás $k.$ szintjén már minden egység diszpécsereit kijelöltük, akkor ez elegendő a $k+1$. szint diszpécsereinek kijelöléséhez stb. A leírt rendszerben még sok gyakorlati probléma vár megoldásra. Például mi történik, ha az egyik egység cellát vált? Vagy pl. hogyan áll helyre a hálózat, ha valaki kikapcsolódik? \section{Internetes keresők felépítése} \begin{figure} \includegraphics[width=16cm]{abra.eps} \caption{\textbf{Keresőrendszer felépítése és működése}} \label{fig:kereso} \end{figure} Egy általános keresőrendszer vázlatos felépítését mutatja a \ref{fig:kereso}. ábra. Elöljáróban megállapíthatunk pár egyszerű dolgot: a) valahogy be kell járnunk a hálózatot, b) a letöltött dokumentumok formátumát értelmezni kell (html, pdf, ps, avi, stb.), valamint c) szükségünk lesz a bejárt dokumentumok egy tárolt változatára illetve a találatok környezetére vonatkozó információkra, ha az erre vonatkozó kérdéseket is meg szeretnénk engedni. Szükség lesz még egy jó rangsorra is, ehhez tárolnunk kell a dokumentumok pontszámát. Ennek kialakításához a linkstruktúra tárolása sokat segíthet. Szükség lehet még a dokumentumtípusok, a bejárási dátum, a domainnév stb. tárolására is. Nem fogjuk tárgyalni a párhuzamosítás kérdéseit. Érdekességképp megemlítjük, hogy a Google például kb. 30000 számítógépen működik. Az adatbázisok mérete is igen nagy: példaként említhetjük, hogy a nagyjából 10 millió magyar oldal szövege 10 GB-ot foglal el tömörítés nélkül. Tehát az adatbázishoz történő hozzáférés megoldása sem egyszerű, sok számítógép együttes munkáját kell hozzá összehangolni. \subsection{Robotok} A robot feladata a dokumentumok begyűjtése a kereső számára. A gyűjtés során egy böngésző emberhez hasonlóan jár el: kap néhány kiindulópontot, aztán innen kiindulva valamilyen szabály szerint a megtalált dokumentum linkjei közül egyet vagy többet követ az előzetesen megadott szabályának megfelelően. Az alábbiakban megvizsgálunk pár robotokra vonatkozó kérdést. \subsubsection{Etika, udvariasság} Speciális képességeikből -- egy robot nagyon gyorsan tud kattintani -- és funkciójukból adódóan a dokumentum eredeti tulajdonosa korlátozhatja a robotok viselkedését, akár robottípustól függően. Ezeket a szabályokat érdemes betartani, különben a robot IP-je gyorsan tiltólistákon találhatja magát. A korlátozások néhány módja: \begin{itemize} \item a site gyökerében elhelyezett ,,robots.txt'' fájlban explicit letöltési szabályok helyezhetők el, \item megadhatók a dokumentumokban ,,robot-meta'' tagok, amelyek rögzítik, hogy az oldalt le szabad-e tölteni, szabad-e másolatot tárolni az oldalról, szabad-e a dokumentum linkjeit követni vagy például szabad-e az oldal médiatartalmait letölteni, \item kötelező a terhelés korlátozása is: egy robotnak kb. 30-60 másodpercet várnia kell két letöltés között egy adott IP címről. Ez szabály komoly gátja a web robotos bejárásának, mert általában a nagy site-ok egy IP címről üzemelnek, így ezeknek a site-oknak csak nagyon lassan jutunk el a ,,mélyére''. \end{itemize} \subsubsection{Letöltési stratégiák} Néhány lehetséges szempont a letöltési stratégiák osztályozásához: \begin{itemize} \item lehet valamilyen \emph{fókuszunk} a letöltésekre nézve. Mondjuk csak a magyar nyelvű oldalakra vagyunk kíváncsiak. Nagyjából 300000 magyar nyelvű oldal létezik a .hu domain-en kívül, ezek bejárása során egy ilyen fókuszt kell használnunk, \item törekedhetünk arra, hogy minél \emph{több} oldalunk legyen, illetve célként tűzhetjük ki, hogy minél \emph{frissebb} oldalakat töltsünk le, \item a letöltés lehet \emph{elindít/leáll} típusú, ahol például egy hétig gyűjtök, aztán elérhetővé teszem a gyűjtést, illetve lehet \emph{inkrementális}, ahol folyamatosan frissítem az adatbázist. A kettő kombinációja is hasznos lehet, pl. a kis site-okat folyamatosan frissítem, míg a nagyokat csak időnként nézem át. \end{itemize} Milyen frissítési stratégiát érdemes követni? Az optimális döntéshez szükségünk van egy modellre a változások módjáról. Tekintsük valószínűségi változónak azt az időpontot, amikor a dokumentum megváltozik, jelölje ezt $t$. A legegyszerűbb azt feltenni, hogy a változások exponenciális eloszlás szerint történnek, azaz $t$ sűrűségfüggvénye $f(t)=\lambda e^{-\lambda t}$ alakú, ahol $\lambda$ a várható élettartam. A gyakorlati tesztek szerint ez nagyjából teljesül, de vannak ettől eltérő vélemények is. Az biztos, hogy sok egyéb meghatározó faktor is létezik, például a napszak nagyon fontos -- az oldalak általában munkaidőben változnak, hírek napközben jönnek stb. Kis kitérő: egyáltalán nem biztos, hogy könnyű eldönteni, hogy egy adott dokumentum megváltozott. Ha az oldal például tartalmaz egy számlálót, minden leolvasásnál más lesz a tartalom. Sok site direkt újnak tünteti fel az oldalt, például folyamatosan cserélgetnek egy véletlen számot a dokumentumban. Néhány megoldás: a legegyszerűbb csak a szöveg változását vizsgálni, illetve a szöveget szétvágni néhány (10-20) darabra, valamilyen hash értéket rendelni a darabokhoz, és ha csak kevés hash érték változik meg, akkor nem tekintjük újnak a szöveget. Külön problémát jelentenek a dinamikus oldalak, pl. a hírportálok, ahol a hír köré folyamatosan új reklámok, linkek szerveződnek. Sokan foglalkoznak azzal, hogy miként lehet egy ilyen dinamikus oldalból a lényeget kiemelni. Hogyan lehet a fenti egyszerű modell alapján meghatározni egy jó letöltési stratégiát? Sokféle célfüggvényre lehet optimalizálni, más szavakkal, sokféleképp számolhatjuk az adatbázis aktuális összértékét. Az egyik lehetőség, hogy összeadjuk az adatbázisban tárolt, az eredetinek pillanatnyilag teljesen megfelelő oldalak értékét. Sajnos általában közvetlenül nincs információnk a megváltozásról, viszont ha a modellünk jó, akkor nem tévedünk nagyot, ha a tárolt oldalak értékét a megváltozásuk valószínűségével súlyozzuk. Azaz keressük azt a stratégiát, amivel a \begin{eqnarray*} \sum_{i~\text{URL}~\in DB} \text{érték}(i) \Pr(i~\text{a letöltés óta nem változott}) \end{eqnarray*} kifejezés maximális lesz. Érték alatt itt tekinthetjük a PageRank-ot, illetve ha elég régóta működik a keresőnk, akkor hasznos lehet figyelembe venni azt is, hogy a felhasználók hányszor klikkeltek erre a linkre. Itt felhasználhatjuk az előző modellt a megváltozás gyakoriságára, amivel a \begin{eqnarray*} \sum_{i~\text{URL}~\in DB} \text{érték}(i) (1-\int_0^{\text{kor}(i)} \lambda_i e^{-\lambda_i t} dt)= \sum_{i~\text{URL}~\in DB} \text{érték}(i) e^{-\lambda_i \text{kor}(i)} \end{eqnarray*} kifejezést kapjuk. Itt most feltettük, hogy minden oldal különböző élettartammal rendelkezik, amiket statisztikai módszerekkel lehet becsülni. Milyen letöltési stratégiát tudunk ez alapján mondani? Elméletben a fenti célfüggvény Lagrange-multiplikátoros optimalizációjával minden oldalhoz hozzá lehet rendelni egy letöltési gyakoriságot. Ezt csak numerikusan lehet kiszámolni és gyakorlatban kevéssé használható, mert mindig le kell töltenem a megadott időben az oldalt. Ez a hálózati sebességek miatt többnyire kivitelezhetetlen. Egy egyszerűbb megoldás az, hogy megpróbáljuk azt az oldalt letölteni következőként, amely a legtöbbel járul hozzá az adatbázis értékéhez. Az $i$-edik oldal hozzájárulása a letöltése előtt $\text{érték}(i) e^{-\lambda_i \text{kor}(i)}$ volt, utána $\text{érték}(i)$ lesz, tehát a megváltozás $\text{érték}(i) (1-e^{-\lambda_i \text{kor}(i)})$. Tehát egy ügyes stratégia, ha azokat az oldalakat töltjük le, ahol ez a kifejezés a legnagyobb. Vegyük észre, hogy ezek a stratégiák egyszerre próbálnak optimalizálni értékre és korra. Ha például az adatbázisban minden URL kora végtelen, mert például nagyon régi az adatbázis, még nincs letöltött dokumentumunk vagy nem érdekel minket a dokumentumok kora, akkor a legnagyobb értékű oldalt fogjuk letölteni. Léteznek ennek a stratégiának olyan kibővítései is, amely figyelembe veszi, hogy a felhasználók mit mennyire keresnek, bekerül-e az oldal a felhasználó találati listájába, ha bekerül, akkor szokott-e rá klikkelni stb. Egy másik további egyszerűsítési lehetőség, hogy a letöltésre egyszerű szélességi keresést használunk. A tapasztalat szerint ez ,,elég jó'', viszonylag magas PageRank-ű oldalakat fog találni, ezt kísérleti adatok bizonyítják. \subsection{Az adatbázis felépítése} Nagyon sokféle igényünk lehet egy adatbázissal szemben. Mi itt csak a legegyszerűbb problémát fogjuk röviden tárgyalni, azaz hogy beadott kulcsszavak alapján hogyan keressük meg azokat oldalakat, amelyek tartalmazzák az illető kulcsszót. Ez a könyvtárak kapcsán már elég régen megfogalmazott probléma az \emph{information retrieval} témájához tartozik. A feladathoz az \emph{indexből} indulunk ki, amely minden dokumentumhoz felsorolja a benne előforduló szavakat. A felsorolásban a dokumentumok és a szavak egyedi azonosítóval rendelkeznek. Az indexet képzelhetjük egy hatalmas mátrixnak, amelynek a sorainak a dokumentumok, oszlopainak a szavak illetve azonosítójuk felel meg. A megközelítés előnye, hogy így a szavakhoz lehet tárolni az előfordulási gyakoriságukat is az illető dokumentumban. Az \emph{invertált index} ezen mátrix transzponáltja: azt olvashatjuk le belőle, hogy adott szó milyen dokumentumokban fordul elő. A keresés ez alapján nagyon egyszerű: ha egy szót keresünk, az invertált index megfelelő sorát megnézve találati listát készítünk, ha pedig több kulcsszó van egy keresésben logikai kifejezéssel összekapcsolva, akkor a találati listákat egyszerűen össze kell fésülni a logikai kifejezésnek megfelelően. A dolog egyszerűnek látszik, de a gyakorlatban problémák sora merül fel. A webes kereséssel foglalkozók gyakran egészen más megközelítést alkalmaznak, mint a klasszikus módszerek; ezen megoldások használhatósága gyakran vitatott pro és kontra. Ha egy szót keresünk, akkor a listánk nagyon hosszú lehet. Ebből minket csak az első (pl. a ,,top 10'') találat érdekel. Nagyon jó lenne az is, ha a listák egyből PageRank szerint rendezettek lennének. Egy lehetséges megoldás kihasználni a szélességi keresés fentebb említett tulajdonságát: ha a dokumentumok azonosítóit egy ilyen bejárás sorrendjében jelöljük ki, akkor elég jó PageRank-ű oldalak lesznek a lista elején. Nagyon fontos a szó előfordulásának típusa is. Egy szó a dokumentum szempontjából kiemelten fontos lehet, ha az alábbiak valamelyikében fordul elő: \begin{itemize} \item a domain-ben -- ez talán a legnehezebben manipulálható és így a legértékesebb információ, \item az URL-ben, ezt is relatíve nehezen lehet megváltoztatni, \item az oldal címében (\emph{title} tag), headerekben, különböző kiemelésekben (pl. bold, más betűméret), \item létezik egy HTML elem a kulcsszavak megadására is (\emph{meta keyword}), amit inkább büntetni szokás, mert tipikusan szemetet lehet itt találni (ez például egy olyan pont, ahol a webes keresgélés nagyon eltér a könyvtáritól), \item nagyon hasznos még az \emph{anchor} szöveg, azaz az a szöveg, ami az oldalra mutató linkek alatt van. \end{itemize} Lényeges lehet a szó darabszáma is, ezt nyilván valamilyen logaritmikus skálán érdemes tárolni. Ezeket az információkat valahogy össze kellene fésülni a PageRank-kel, és ezen együttes értékelés sorrendjében mutatni a találatokat a felhasználó felé. Egy lehetséges stratégia az, hogy az azonosítókat a fent említett módon szélességi keresés szerint rendezzük, és egy-egy keresésnél a legelsőket, pl. az első pár ezer darabot újra rendezzük az összetettebb értékelés szerint. Ez valamennyire több szóra is felhasználható stratégia, gond csak akkor lép fel, ha ÉS kapcsolatban áll egy gyakori és egy kevéssé gyakori szó, mert ilyenkor a gyakori szó találati listájából igencsak sokat kell olvasni. További problémákat jelentenek a több szóból álló \emph{kifejezésre történő keresések}. Ehhez a problémához hasonló a NEAR operátorral történő lekérdezések problémája, hiszen a kifejezést tekinthetjük NEAR 0 vagy NEAR 1 operátorral megadott kereséseknek. Ilyen keresések lehetővé tételéhez mindenképp tárolni kell a szavak dokumentumon belüli pozícióját, azaz a szavak nem aggregálhatók egy dokumentumon belül. Ez jelentősen megnöveli az index méretét. A pozíciót muszáj az indexben tárolnunk, mert a dokumentumok túl nagyok ahhoz, hogy minden kereséshez akár több ezer oldalt elővegyünk és ott helyben keressük ki a szavak pozícióját. Megoldási javaslatok: (i) bevezethetünk egy külön indexet a folytatásra, azaz minden szóhoz tároljuk el, milyen szóval folytatódik, (ii) indexelhetünk szavak helyett szópárokat is stb. Tovább növelheti a létrehozott indexek számát, hogy agglutináló nyelvekben, például a magyarban bizonyos feladatoknál szükség van szótövezésre, bizonyosakban nem. Milyen adatstruktúrát használjunk az indexek tárolására? Ez a műveletektől függ. Inkrementális robotok esetén beszúrni és törölni szeretnénk, emellett gyorsan keresni. Nem árt figyelembe venni azt sem, hogy az adatbázis nem fog beleférni a memóriába. Példaképp említhetjük, hogy a magyar web indexei egy konkrét implementációban kb. 5 GB helyet foglaltak el. A konkrét megvalósítások számára leggyakrabban B-fákat szoktak javasolni, de létezik olyan open source-os megoldás is, amely hashelést használ. \end{document}