Søkemotorindeksering - Search engine indexing

Søkemotorindeksering er innsamling, analyse og lagring av data for å lette rask og nøyaktig informasjonsinnhenting . Indeksdesign inneholder tverrfaglige begreper fra lingvistikk, kognitiv psykologi, matematikk, informatikk og informatikk. Et alternativt navn på prosessen, i sammenheng med søkemotorer designet for å finne websider på Internett, er webindeksering . Eller bare indeksering.

Populære motorer fokuserer på fulltekstindeksering av dokumenter på naturlig språk. Medietyper som video, lyd og grafikk er også søkbare.

Meta søkemotorer gjenbruker indeksene til andre tjenester og lagrer ikke en lokal indeks, mens hurtigbaserte søkemotorer lagrer indeksen permanent sammen med korpuset . I motsetning til fulltekstindekser, begrenser delteksttjenester dybden som indekseres for å redusere indeksstørrelsen. Større tjenester utfører vanligvis indeksering på et forhåndsbestemt tidsintervall på grunn av nødvendig tid og behandlingskostnader, mens agentbaserte søkemotorer indekserer i sanntid .

Indeksering

Hensikten med å lagre en indeks er å optimalisere hastighet og ytelse ved å finne relevante dokumenter for et søk. Uten indeks ville søkemotoren skanne alle dokumenter i korpuset , noe som ville kreve betydelig tid og datakraft. For eksempel, mens en indeks på 10 000 dokumenter kan spørres innen millisekunder, kan en sekvensiell skanning av hvert ord i 10 000 store dokumenter ta timer. Den ekstra datamaskinlagringen som kreves for å lagre indeksen, samt den betydelige økningen i tiden som kreves for at en oppdatering skal finne sted, byttes ut for tiden som spares under informasjonsinnhenting.

Indeksdesignfaktorer

Viktige faktorer ved utformingen av en søkemotors arkitektur inkluderer:

Slå sammen faktorer
Hvordan data kommer inn i indeksen, eller hvordan ord eller emnefunksjoner legges til i indeksen under tekstkorpusoverføring, og om flere indeksatorer kan fungere asynkront. Indekseringen må først kontrollere om den oppdaterer gammelt innhold eller legger til nytt innhold. Traversal korrelerer vanligvis med retningslinjene for datainnsamling . Søkemotorindeksfusjonering ligner i konseptet på SQL Merge -kommandoen og andre flettealgoritmer.
Lagringsteknikker
Hvordan du lagrer indeksen data , det vil si om informasjonen skal data komprimeres eller filtrert.
Indeksstørrelse
Hvor mye datamaskinlagring er nødvendig for å støtte indeksen.
Oppslagshastighet
Hvor raskt et ord kan bli funnet i den inverterte indeksen . Hastigheten på å finne en oppføring i en datastruktur, sammenlignet med hvor raskt den kan oppdateres eller fjernes, er et sentralt fokus for datavitenskap.
Vedlikehold
Hvordan indeksen opprettholdes over tid.
Feiltoleranse
Hvor viktig det er for tjenesten å være pålitelig. Problemer inkluderer håndtering av indekskorrupsjon, avgjøre om dårlige data kan behandles isolert, håndtere dårlig maskinvare, partisjonering og ordninger som hashbasert eller sammensatt partisjonering, samt replikering .

Indeksere datastrukturer

Søkemotorarkitekturer varierer i hvordan indeksering utføres og i metoder for indekslagring for å møte de forskjellige designfaktorene.

Suffiks -tre
Figurativt strukturert som et tre, støtter lineær tidsoppslag. Bygget ved å lagre suffikser av ord. Endetreet er en type trie . Prøver støtter utvidbar hashing , noe som er viktig for indeksering av søkemotorer. Brukes til å søke etter mønstre i DNA -sekvenser og klynger. En stor ulempe er at lagring av et ord i treet kan kreve plass utover det som kreves for å lagre selve ordet. En alternativ representasjon er et suffiksarray , som anses å kreve mindre virtuelt minne og støtter datakomprimering, for eksempel BWT -algoritmen.
Omvendt indeks
Lagrer en liste over forekomster av hvert atomkriterium, vanligvis i form av en hashtabell eller et binært tre .
Sitasjonsindeks
Lagrer sitater eller hyperkoblinger mellom dokumenter for å støtte sitatanalyse, et emne for bibliometri .
n -gram indeks
Lagrer sekvenser av datalengde for å støtte andre typer gjenfinning eller tekstgruvedrift .
Dokument-siktmatrise
Brukt i latent semantisk analyse, lagrer forekomster av ord i dokumenter i en todimensjonal sparsom matrise .

Utfordringer i parallellisme

En stor utfordring i utformingen av søkemotorer er styringen av serielle databehandlingsprosesser. Det er mange muligheter for løpsforhold og sammenhengende feil. For eksempel legges et nytt dokument til i korpuset og indeksen må oppdateres, men indeksen må samtidig fortsette å svare på søk. Dette er en kollisjon mellom to konkurrerende oppgaver. Tenk på at forfattere er produsenter av informasjon, og en webcrawler er forbrukeren av denne informasjonen, tar tak i teksten og lagrer den i en cache (eller korpus ). Fremoverindeksen er forbrukeren av informasjonen som produseres av korpuset, og den inverterte indeksen er forbrukeren av informasjon produsert av fremoverindeksen. Dette blir ofte referert til som en produsent-forbruker-modell . Indekseringen er produsenten av søkbar informasjon, og brukerne er forbrukerne som trenger å søke. Utfordringen forsterkes når du arbeider med distribuert lagring og distribuert behandling. I et forsøk på å skalere med større mengder indeksert informasjon, kan søkemotorens arkitektur innebære distribuert databehandling , der søkemotoren består av flere maskiner som fungerer i fellesskap. Dette øker mulighetene for usammenheng og gjør det vanskeligere å opprettholde en fullt synkronisert, distribuert, parallell arkitektur.

Omvendte indekser

Hovedartikkel: Omvendt indeks

Mange søkemotorer har en omvendt indeks når de vurderer et søk for å raskt finne dokumenter som inneholder ordene i en spørring, og deretter rangere disse dokumentene etter relevans. Fordi den inverterte indeksen lagrer en liste over dokumentene som inneholder hvert ord, kan søkemotoren bruke direkte tilgang til å finne dokumentene som er knyttet til hvert ord i spørringen for å kunne hente de matchende dokumentene raskt. Følgende er en forenklet illustrasjon av en omvendt indeks:

Omvendt indeks
Ord Dokumenter
de Dokument 1, Dokument 3, Dokument 4, Dokument 5, Dokument 7
ku Dokument 2, Dokument 3, Dokument 4
sier Dokument 5
mø Dokument 7

Denne indeksen kan bare avgjøre om det finnes et ord i et bestemt dokument, siden det ikke lagrer informasjon om ordets frekvens og posisjon; det regnes derfor som en boolsk indeks. En slik indeks bestemmer hvilke dokumenter som samsvarer med en forespørsel, men rangerer ikke samsvarende dokumenter. I noen design inneholder indeksen tilleggsinformasjon, for eksempel frekvensen av hvert ord i hvert dokument eller posisjonene til et ord i hvert dokument. Posisjonsinformasjon gjør at søkealgoritmen kan identifisere ordnærhet for å støtte søk etter setninger; frekvens kan brukes til å rangere relevansen av dokumenter for søket. Slike temaer er det sentrale forskningsfokuset for informasjonsinnhenting .

Den omvendte indeksen er en sparsom matrise , siden ikke alle ord er tilstede i hvert dokument. For å redusere krav til datamaskinlagring , lagres det annerledes enn en todimensjonal matrise . Indeksen ligner på begrepet dokumentmatriser brukt ved latent semantisk analyse . Den omvendte indeksen kan betraktes som en form for en hashtabell. I noen tilfeller er indeksen en form for et binært tre , som krever ekstra lagring, men kan redusere oppslagstiden. I større indekser er arkitekturen vanligvis et distribuert hash -bord .

Indeksfusjon

Den omvendte indeksen fylles ut via en sammenslåing eller gjenoppbygging. En ombygging ligner på en sammenslåing, men sletter først innholdet i den inverterte indeksen. Arkitekturen kan være utformet for å støtte inkrementell indeksering, der en sammenslåing identifiserer dokumentet eller dokumentene som skal legges til eller oppdateres og deretter analyserer hvert dokument i ord. For teknisk nøyaktighet kombinerer en fletting nylig indekserte dokumenter, vanligvis i virtuelt minne, med indeksbufferen på en eller flere harddisker.

Etter analysering legger indekseren til det refererte dokumentet i dokumentlisten for de riktige ordene. I en større søkemotor kan prosessen med å finne hvert ord i den inverterte indeksen (for å rapportere at det skjedde i et dokument) være for tidkrevende, og derfor er denne prosessen vanligvis delt opp i to deler, utviklingen av en fremoverindeks og en prosess som sorterer innholdet i fremoverindeksen i den inverterte indeksen. Den inverterte indeksen er så navngitt fordi den er en inversjon av fremoverindeksen.

Fremoverindeksen

Fremoverindeksen lagrer en liste med ord for hvert dokument. Følgende er en forenklet form av fremoverindeksen:

Fremoverindeks
Dokument Ord
Dokument 1 den, ku, sier, moo
Dokument 2 hatten, katten og hatten
Dokument 3 den, parabolen, løp, bort, med, den, skjeen

Begrunnelsen for å utvikle en fremoverindeks er at ettersom dokumenter blir analysert, er det bedre å lagre ordene per dokument i mellomtiden. Avgrensningen muliggjør asynkron system behandling, noe som delvis omgår den inverterte indeks oppdatering flaskehals . Fremoverindeksen er sortert for å transformere den til en invertert indeks. Fremoverindeksen er i hovedsak en liste over par som består av et dokument og et ord, samlet av dokumentet. Å konvertere fremoverindeksen til en invertert indeks er bare et spørsmål om å sortere parene etter ordene. I denne forbindelse er den inverterte indeksen en ordsortert fremoverindeks.

Komprimering

Å generere eller vedlikeholde en storstilt søkemotorindeks representerer en betydelig lagrings- og behandlingsutfordring. Mange søkemotorer bruker en form for komprimering for å redusere størrelsen på indeksene på disken . Vurder følgende scenario for en fulltekst, søkemotor på Internett.

Gitt dette scenariet, vil en ukomprimert indeks (forutsatt en ikke- sammensatt , enkel indeks) for 2 milliarder nettsider måtte lagre 500 milliarder ordoppføringer. Med 1 byte per tegn, eller 5 byte per ord, krever dette 2500 gigabyte lagringsplass alene. Dette plassbehovet kan være enda større for en feiltolerant distribuert lagringsarkitektur. Avhengig av valgt komprimeringsteknikk, kan indeksen reduseres til en brøkdel av denne størrelsen. Avregningen er tiden og prosessorkraften som kreves for å utføre komprimering og dekomprimering.

Spesielt inneholder store søkemotordesign både lagringskostnader og strømkostnader for å drive lagringen. Således er komprimering et mål på kostnad.

Dokumentanalyse

Dokumentanalyse bryter komponentene (ord) i et dokument eller annen form for media for å settes inn i de fremadrettede og inverterte indeksene. Ordene som er funnet kalles tokens , og i forbindelse med søkemotorindeksering og behandling av naturlig språk blir parsing mer ofte referert til som tokenisering . Det er også noen ganger kalt ordgrense disambiguering , tagging , tekst segmentering , innholdsanalyse , tekstanalyse, tekst gruvedrift , konkordans generasjon, tale segmentering , Lexing , eller leksikalsk analyse . Begrepene 'indeksering', 'analysering' og 'tokenisering' brukes om hverandre i bedriftsslang.

Naturlig språkbehandling er gjenstand for kontinuerlig forskning og teknologisk forbedring. Tokenisering byr på mange utfordringer med å trekke ut nødvendig informasjon fra dokumenter for indeksering for å støtte kvalitetssøk. Tokenisering for indeksering innebærer flere teknologier, som implementering ofte blir holdt som bedriftshemmeligheter.

Utfordringer i naturlig språkbehandling

Ordgrense uklarhet
Native engelsktalende kan ved første vurdere tokenization å være en grei oppgave, men dette er ikke tilfelle med å utforme en flerspråklig indekser. I digital form representerer tekstene til andre språk som kinesisk , japansk eller arabisk en større utfordring, ettersom ord ikke er tydelig avgrenset av mellomrom . Målet under tokenisering er å identifisere ord som brukerne vil søke etter. Språkspesifikk logikk brukes for å skikkelig identifisere grensen til ord, som ofte er begrunnelsen for å designe en parser for hvert språk som støttes (eller for grupper av språk med lignende grensemarkører og syntaks).
Språk tvetydighet
For å hjelpe til med riktig rangering av matchende dokumenter, samler mange søkemotorer tilleggsinformasjon om hvert ord, for eksempel språk eller leksikalsk kategori ( del av talen ). Disse teknikkene er språkavhengige, ettersom syntaksen varierer mellom språk. Dokumenter identifiserer ikke alltid klart språket i dokumentet eller representerer det nøyaktig. Ved å symbolisere dokumentet prøver noen søkemotorer å automatisk identifisere språket i dokumentet.
Ulike filformater
For å kunne identifisere hvilke byte i et dokument som representerer tegn, må filformatet håndteres riktig. Søkemotorer som støtter flere filformater, må kunne åpne og få tilgang til dokumentet på riktig måte og kunne symbolisere tegnene i dokumentet.
Feil lagring
Kvaliteten på de naturlige språkdataene er kanskje ikke alltid perfekt. Et uspesifisert antall dokumenter, spesielt på Internett, følger ikke nøye riktig filprotokoll. Binære tegn kan være feilkodet i forskjellige deler av et dokument. Uten anerkjennelse av disse tegnene og passende håndtering kan indekskvaliteten eller indekserytelsen forringes.

Tokenisering

I motsetning til lesefulle mennesker, forstår ikke datamaskiner strukturen i et naturspråklig dokument og kan ikke automatisk gjenkjenne ord og setninger. For en datamaskin er et dokument bare en sekvens av byte. Datamaskiner 'vet ikke' at et mellomromstegn skiller ord i et dokument. I stedet må mennesker programmere datamaskinen for å identifisere hva som utgjør et individuelt eller tydelig ord referert til som et tegn. Et slikt program kalles vanligvis en tokenizer eller parser eller lexer . Mange søkemotorer, så vel som annen programvare for naturlig språkbehandling, inneholder spesialiserte programmer for analyse, for eksempel YACC eller Lex .

Under tokenisering identifiserer parseren sekvenser av tegn som representerer ord og andre elementer, for eksempel tegnsetting, som er representert med numeriske koder, hvorav noen er kontrolltegn som ikke skrives ut. Parseren kan også identifisere enheter som e -postadresser, telefonnumre og nettadresser . Når du identifiserer hvert token, kan flere egenskaper lagres, for eksempel symbolets bokstav (øvre, nedre, blandede, riktige), språk eller koding, leksikalsk kategori (del av talen, som 'substantiv' eller 'verb'), posisjon, setning nummer, setningsposisjon, lengde og linjenummer.

Språkgjenkjenning

Hvis søkemotoren støtter flere språk, er et vanlig første trinn under tokenisering å identifisere hvert dokuments språk; mange av de påfølgende trinnene er språkavhengige (for eksempel stemming og del av talemerking). Språkgjenkjenning er prosessen der et dataprogram prøver å automatisk identifisere eller kategorisere språket i et dokument. Andre navn for språkgjenkjenning inkluderer språkklassifisering, språkanalyse, språkidentifikasjon og språkmerking. Automatisert språkgjenkjenning er gjenstand for pågående forskning innen behandling av naturspråk . Å finne hvilket språk ordene tilhører, kan innebære bruk av et språkgjenkjenningskart .

Formatanalyse

Hvis søkemotoren støtter flere dokumentformater , må dokumenter forberedes for tokenisering. Utfordringen er at mange dokumentformater inneholder formateringsinformasjon i tillegg til tekstinnhold. For eksempel inneholder HTML -dokumenter HTML -koder, som angir formateringsinformasjon, for eksempel ny linjestart, fet utheving og skriftstørrelse eller stil . Hvis søkemotoren ignorerer forskjellen mellom innhold og "markup", vil ekstern informasjon bli inkludert i indeksen, noe som fører til dårlige søkeresultater. Formatanalyse er identifisering og håndtering av formateringsinnholdet som er innebygd i dokumenter som styrer måten dokumentet gjengis på en dataskjerm eller tolkes av et program. Formatanalyse blir også referert til som strukturanalyse, formatparing, tagstripping, formatstripping, tekstnormalisering, tekstrensing og tekstforberedelse. Utfordringen med formatanalyse blir ytterligere komplisert av forviklingene i forskjellige filformater. Enkelte filformater er proprietære med svært lite informasjon avslørt, mens andre er godt dokumentert. Vanlige, veldokumenterte filformater som mange søkemotorer støtter inkluderer:

Alternativer for å håndtere forskjellige formater inkluderer bruk av et offentlig tilgjengelig kommersielt analyseringsverktøy som tilbys av organisasjonen som utviklet, vedlikeholder eller eier formatet, og skriver en tilpasset parser .

Noen søkemotorer støtter inspeksjon av filer som er lagret i et komprimert eller kryptert filformat. Når du arbeider med et komprimert format, dekomprimerer indekseren først dokumentet; dette trinnet kan resultere i en eller flere filer, som hver må indekseres separat. Vanligvis støttede komprimerte filformater inkluderer:

  • ZIP - ZIP -arkivfil
  • RAR - Roshal AR -arkivfil
  • CAB - Microsoft Windows -kabinettfil
  • Gzip - Fil komprimert med gzip
  • BZIP - Fil komprimert ved hjelp av bzip2
  • Tape ARchive (TAR) , Unix arkivfil, ikke (selv) komprimert
  • TAR.Z, TAR.GZ eller TAR.BZ2 - Unix arkivfiler komprimert med Compress, GZIP eller BZIP2

Formatanalyse kan innebære metoder for kvalitetsforbedring for å unngå å inkludere 'dårlig informasjon' i indeksen. Innhold kan manipulere formateringsinformasjonen for å inkludere tilleggsinnhold. Eksempler på misbruk av dokumentformatering for spamdexing :

  • Inkludert hundrevis eller tusenvis av ord i en seksjon som er skjult for visning på dataskjermen, men synlig for indekseren, ved bruk av formatering (f.eks. Skjult "div" -tag i HTML , som kan inkludere bruk av CSS eller JavaScript for å gjøre så).
  • Angir skriftfargen på forgrunnen til ord på samme måte som bakgrunnsfargen, gjør ord skjult på dataskjermen for en person som ser på dokumentet, men ikke skjult for indekseren.

Seksjonsgjenkjenning

Noen søkemotorer inkluderer seksjonsgjenkjenning, identifisering av store deler av et dokument før tokenisering. Ikke alle dokumentene i et korpus leste som en velskrevet bok, delt inn i organiserte kapitler og sider. Mange dokumenter på nettet , for eksempel nyhetsbrev og bedriftsrapporter, inneholder feilaktig innhold og sideseksjoner som ikke inneholder hovedmateriale (det som dokumentet handler om). Denne artikkelen viser for eksempel en sidemeny med lenker til andre websider. Noen filformater, som HTML eller PDF, tillater at innhold vises i kolonner. Selv om innholdet vises eller gjengis i forskjellige områder av visningen, kan råmarkeringsinnholdet lagre denne informasjonen sekvensielt. Ord som vises sekvensielt i råkildeinnholdet, indekseres sekvensielt, selv om disse setningene og avsnittene gjengis i forskjellige deler av dataskjermen. Hvis søkemotorer indekserer dette innholdet som om det var normalt innhold, kan kvaliteten på indeksen og søkekvaliteten bli forringet på grunn av blandet innhold og feil ordnærhet. To hovedproblemer er notert:

  • Innhold i forskjellige seksjoner behandles som relatert i indeksen, når det i virkeligheten ikke er det
  • Organisatorisk «sidelinje» -innhold er inkludert i indeksen, men sidelinjens innhold bidrar ikke til betydningen av dokumentet, og indeksen er fylt med en dårlig representasjon av dokumentene.

Seksjonsanalyse kan kreve at søkemotoren implementerer gjengivelseslogikken for hvert dokument, i hovedsak en abstrakt fremstilling av det faktiske dokumentet, og deretter indekserer representasjonen i stedet. For eksempel gjengis noe innhold på Internett via JavaScript. Hvis søkemotoren ikke gjengir siden og vurderer JavaScript på siden, ville den ikke 'se' dette innholdet på samme måte og indeksere dokumentet feil. Gitt at noen søkemotorer ikke bryr seg om gjengivelsesproblemer, unngår mange webdesignere å vise innhold via JavaScript eller bruke Noscript -taggen for å sikre at nettsiden er indeksert riktig. Samtidig kan dette faktum også utnyttes for å få søkemotorindekseren til å 'se' annet innhold enn betrakteren.

HTML prioritetssystem

Indeksering må ofte gjenkjenne HTML -taggene for å organisere prioritet. Indeksering av lav prioritet til høy margin til etiketter som sterk og lenke for å optimalisere prioritetsrekkefølgen hvis disse etikettene er i begynnelsen av teksten, kan ikke vise seg å være relevant. Noen indeksører som Google og Bing sørger for at søkemotoren ikke tar de store tekstene som relevant kilde på grunn av sterk systemkompatibilitet .

Metakodeindeksering

Spesifikke dokumenter inneholder ofte innebygd metainformasjon som forfatter, søkeord, beskrivelse og språk. For HTML -sider inneholder metakoden søkeord som også er inkludert i indeksen. Tidligere Internett -søkemotorteknologi ville bare indeksere søkeordene i metakodene for fremoverindeksen; hele dokumentet vil ikke bli analysert. På den tiden var fulltekstindeksering ikke like godt etablert, og maskinvare kunne heller ikke støtte slik teknologi. Utformingen av HTML -kodespråket inkluderte i utgangspunktet støtte for metakoder med det formål å bli ordentlig og enkelt indeksert, uten å kreve tokenisering.

Etter hvert som Internett vokste gjennom 1990-tallet, gikk mange selskaper i murstein og mørtel "online" og etablerte bedriftsnettsteder. Søkeordene som brukes til å beskrive nettsider (hvorav mange var bedriftsorienterte nettsider som ligner produktbrosjyrer) endret seg fra beskrivende til markedsføringsorienterte søkeord som er designet for å øke salget ved å plassere nettsiden høyt i søkeresultatene for spesifikke søk. Det faktum at disse søkeordene var subjektivt spesifisert, førte til spamdexing , noe som fikk mange søkemotorer til å ta i bruk fulltekstindekseringsteknologi på 1990-tallet. Søkemotordesignere og -selskaper kunne bare plassere så mange "markedsføringssøkeord" i innholdet på en webside før de tappet all interessant og nyttig informasjon. Gitt den interessekonflikten med forretningsmålet om å designe brukerorienterte nettsteder som var "klissete", ble verdiligningen for kundens levetid endret for å inkludere mer nyttig innhold på nettstedet i håp om å beholde den besøkende. I denne forstand var indeksering av fulltekst mer objektiv og økte kvaliteten på søkemotorresultater, ettersom det var enda et skritt unna subjektiv kontroll med søkemotorresultatplassering, noe som igjen forsket på fulltekstindekseringsteknologi.

I desktop -søk inneholder mange løsninger metakoder for å gi forfatterne en måte å tilpasse hvordan søkemotoren vil indeksere innhold fra forskjellige filer som ikke fremgår av filinnholdet. Desktop -søk er mer under kontroll av brukeren, mens Internett -søkemotorer må fokusere mer på fulltekstindeksen.

Se også

Referanser

Videre lesning

  • R. Bayer og E. McCreight. Organisering og vedlikehold av store bestilte indekser. Acta Informatica, 173-189, 1972.
  • Donald E. Knuth . The Art of Computer Programming , bind 1 (3. utgave): grunnleggende algoritmer, Addison Wesley Longman Publishing Co. Redwood City, CA, 1997.
  • Donald E. Knuth . The computer of computer programming, volume 3: (2nd ed.) Sorting and search, Addison Wesley Longman Publishing Co. Redwood City, CA, 1998.
  • Gerald Salton . Automatisk tekstbehandling, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988.
  • Gerard Salton . Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986.
  • Gerard Salton . Lesk, ME: Datavurdering av indeksering og tekstbehandling. Journal of the ACM. Januar 1968.
  • Gerard Salton . SMART Retrieval System - Eksperimenter i automatisk dokumentbehandling. Prentice Hall Inc., Englewood Cliffs, 1971.
  • Gerard Salton . Transformasjon, analyse og henting av informasjon etter datamaskin, Addison-Wesley, Reading, Mass., 1989.
  • Baeza-Yates, R., Ribeiro-Neto, B .: Moderne informasjonsinnhenting. Kapittel 8. ACM Press 1999.
  • GK Zipf. Menneskelig atferd og prinsippet om minst innsats. Addison-Wesley, 1949.
  • Adelson-Velskii, GM, Landis, EM: En algoritme for informasjonsorganisasjon. DANSSSR, 146, 263-266 (1962).
  • Edward H. Sussenguth Jr. , Bruk av trestrukturer for behandling av filer, Communications of the ACM, v.6 n.5, s. 272-279, mai 1963
  • Harman, DK, et al .: Inverterte filer. In Information Retrieval: Data Structures and Algorithms, Prentice-Hall, s. 28–43, 1992.
  • Lim, L., et al .: Characterizing Web Document Change, LNCS 2118, 133–146, 2001.
  • Lim, L., et al .: Dynamisk vedlikehold av webindekser ved bruk av landemerker. Proc. av den 12. W3 -konferansen, 2003.
  • Moffat, A., Zobel, J .: Selvindeksering av inverterte filer for rask teksthenting. ACM TIS, 349–379, oktober 1996, bind 14, nummer 4.
  • Mehlhorn, K .: Datastrukturer og effektive algoritmer, Springer Verlag, EATCS Monographs, 1984.
  • Mehlhorn, K. , Overmars, MH : Optimal dynamisering av nedbrytbare søkeproblemer. IPL 12, 93–98, 1981.
  • Mehlhorn, K .: Lavere grenser for effektiviteten ved å omdanne statiske datastrukturer til dynamiske datastrukturer. Matte. Systemteori 15, 1–16, 1981.
  • Koster, M .: ALIWEB: Archie-Like indexing in the Web. Datanettverk og ISDN -systemer, vol. 27, nr. 2 (1994) 175-182 (se også Proc. First Int'l World Wide Web Conf., Elsevier Science, Amsterdam, 1994, s. 175–182)
  • Serge Abiteboul og Victor Vianu . Forespørsler og beregning på nettet . Prosedyrer fra den internasjonale konferansen om databaseteori. Delphi, Hellas 1997.
  • Ian H Witten, Alistair Moffat og Timothy C. Bell. Administrere gigabyte: Komprimere og indeksere dokumenter og bilder. New York: Van Nostrand Reinhold, 1994.
  • A. Emtage og P. Deutsch, "Archie-En elektronisk katalogtjeneste for Internett." Proc. Usenix Winter 1992 Tech. Conf., Usenix Assoc., Berkeley, California, 1992, s. 93–110.
  • M. Gray, World Wide Web Wanderer .
  • D. Cutting og J. Pedersen. "Optimaliseringer for dynamisk vedlikehold av invertert indeks." Proceedings of the 13th International Conference on Research and Development in Information Retrieval, s. 405–411, september 1990.
  • Stefan Büttcher, Charles LA Clarke og Gordon V. Cormack. Informasjonsinnhenting: Implementering og evaluering av søkemotorer . MIT Press, Cambridge, Mass., 2010.