Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Konstrukcja indeksu

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Index construction



How do we construct an index?



What strategies can we use with limited 
main memory?

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Podstawy hardware



Wiele decyzji projektowych w IR bazuje 
charakterystykach hardware



Rozpoczniemy od przeglądu podstaw 
hardware

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Podstawy hardware



Dostęp do danych w pamięci jest znacznie 
szybszy w pamięci niż dostęp do danych na 
dysku.



Szukanie na dysku: nie ma transferu podczas 
pozycjonowania głowicy.



Dlatego: przesyłanie jednego dużego fragmentu 
danych z dysku do pamięci jest szybsze niż 
transfer wielu małych fragmentów.



I/O dla dysku jest oparte na blokach: czytanie i 
pisanie całych bloków(zamiast małych 
fragmentów).



Rozmiary bloków: 8KB do 256 KB.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Podstawy hardware



Serwery używane w systemach IR obecnie 
typowo mają kilka GB pamięci operacyjnej, 
czasami dziesiątki  GB. 



Dostępna przestrzeń dyskowa jest kilka (2–
3) rzędów większa.



Odporność na uszkodzenia jest bardzo 
droga: Znacznie taniej jest użyć wiele 
zwykłych maszyn niż jedną bardzo 
niezawodną.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Typowe parametry hardware 



symbol  statistic  value



s średni czas dostępu 5 ms = 5 x 10

−3

 s



b  czas transferu na bajt    0.02 μs = 2 x 10

−8

 

s



       częstotliwość procesora   10

9

 s

−1



p operacje niskiego poziomu 0.01 μs = 10

−8

 s

          (np.: porównanie i wymiana słów)



       pojemność pam. Głównej 

kilka GB



       pojemność dyskowa   1 TB lub wiecej

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

RCV1: Nasza kolekcja do tego 
wykładu



Zebrane dzieła Shakespeare są zbyt małe aby 
zademonstrować wiele punktów z tego kursu.



Kolekcja która będzie użyta też wystarczająco 
duża, ale jest publicznie dostępna i co 
najmniej bardzo przekonywującym 
przykładem.



Jako przykład dla zastosowania skalowalnego 
algorytmu budowy indeksu, użyjemy kolekcji 
Reuters RCV1.



Jest to jeden rok depesz Reutera(część 1995 
roku i 1996)

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Dokument RCV1

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Statystyki dla Reuters RCV1 
(przybliżone dla przykładu)



symbol statystyka wartość



N  dokumenty   800,000



L  avg. # tokens per doc  200



M termy (= word types)  400,000



                 avg. # bytes per token  6

                    (incl. spaces/punct.)



                 avg. # bytes per token4.5

            

(without spaces/punct.)



                 avg. # bytes per term 7.5



                 nie pozycyjne wystąpienia 
100,000,000

4.5 bajtów na token słowa token ale 7.5 bajtów na word 
type: dlaczego?

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 



Dokumenty są parsowane aby wybrać 

słowa i te słowa są pamiętane z ID 

dokumentu.

I did enact Julius
Caesar I was killed 
i' the Capitol; 
Brutus killed me.

Doc 1

So let it be with
Caesar. The noble
Brutus hath told you
Caesar was ambitious

Doc 2

Przypomnienie 
konstrukcji indeksu 

Term

Doc #

I

1

did

1

enact 

1

julius

1

caesar

1

I

1

was

1

killed

1

i'

1

the

1

capitol

1

brutus

1

killed

1

me

1

so

2

let

2

it

2

be

2

with

2

caesar

2

the

2

noble 

2

brutus

2

hath 

2

told 

2

you

2

caesar 

2

was

2

ambitious

2

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Term

Doc #

I

1

did

1

enact 

1

julius

1

caesar

1

I

1

was

1

killed

1

i'

1

the

1

capitol

1

brutus

1

killed

1

me

1

so

2

let

2

it

2

be

2

with

2

caesar

2

the

2

noble 

2

brutus

2

hath 

2

told 

2

you

2

caesar 

2

was

2

ambitious

2

Term

Doc #

ambitious

2

be

2

brutus

1

brutus 

2

capitol

1

caesar

1

caesar

2

caesar

2

did

1

enact

1

hath

1

I

1

I 

1

i'

1

it

2

julius

1

killed

1

killed

1

let

2

me

1

noble

2

so

2

the

1

the 

2

told

2

you

2

was

1

was

2

with

2

 Kluczowy krok



Po parsowaniu wszystkich 
dokumentów, indeks 
inversyjny jest sortowany 
wg termów. 

Rozpatrujemy ten krok 
sortowania.
Mamy 100M jednostek do 
sortowania.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Konstrukcja skalowanego 
indeksu



Konstrukcja indeksu w pamięci nie 
zmniejsza go.



Jak mamy budować indeks dla bardzo 
dużych kolekcji?



Biorąc pod uwagę ograniczenia hardware 
myślimy o…



PO, dyskach, prędkości itd.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Konstrukcja indeksu oparta na 
sortowaniu



W trakcie budowy indeksu parsujemy dokumenty po 
jednym.



W trakcie budowy indeksu nie można łatwo 
kompresować  

 (możemy, ale jest to bardzo złożone)



Ostateczny zbiór wystąpień dla jakiegoś termu jest 
nieznany aż do końca.



Dla  12 bajtów na  wejście do niepozycyjnego 
wystąpienia (term, doc, częstość), potrzeba dużo 
pamięci dla dużych kolekcji.



T = 100,000,000 w przypadku RCV1



To mamy w pamięci dla 2009, ale typowe kolekcje są 
znacznie większe.  Np.: New York Times ma indeks dla 
>150 lat depesz



Więc: musimy trzymać wyniki pośrednie na dysku.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Czy używać dla dysku?



Czy możemy użyć ten sam algorytm 
budowy indeksu do większych kolekcji, ale 
przez użycie dysku zamiast pamięci?



Nie: Sortowanie T = 100,000,000  
rekordów na dysku jest zbyt wolne – zbyt 
dużo pobrań z dysku.



Potrzebujemy zewnętrzny algorytm 
sortowania.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Wąskie gardło



Parsuj i twórz wejścia wystąpień dla 
jednego dokumentu za jednym razem



Sortuj wystąpienia wg termów (następnie 
wg dokumentów dla termów)



Wykonywanie tego dla losowego szukania 
na dysku jest zbyt wolne T=100M 
(milionów)rekordów

Jeśli każde porównanie wymaga 2 pobrań z dysku,
 i N elementów ma być sortowane z  N log

2

N porównaniami,

 jak długo to będzie trwać?

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

BSBI: Blocked sort-based 
Indexing (Sortowanie z min. 
pobrań z dysku)



12-bajtowe (4+4+4) rekordy (term, doc, freq).



Są one generowane podczas parsowania 
dokumentów.



Musimy teraz sortować 100M takich 12-
bajtowych rekordów na term.



Zdefiniuj Block ~ 10M  takich rekordów



Możemy łatwo umieścić kilka w pamięci.



Będziemy mieli 10 takich bloków na starcie.



Podstawowa idea algorytmu:



Zbieraj wystąpienia dla każdego bloku, sortuj, pisz 
na disk.



Wtedy łącz bloki w jeden długi posortowany ciąg.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Sortowanie 10 bloków po 10M 
rekordów



Najpierw czytaj każdy blok i sortuj 
wewnętrznie: 



Quicksort wymaga 2N ln N spodziewanych 
kroków



W naszym przypadku 2 x (10M ln 10M) kroków



10 razy tyle daje 10  przejść  sortowania  
dla  10M rekordów każde.



Wykonanie bezpośrednie wymaga  2 kopii 
danych na dysku



Ale możemy to optymalizować

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Jak łączyć posortowane ciągi? 



Można łączyć binarnie, za pomocą drzewa z 
log

2

10 = 4 poziomami.



Dla każdej warstwy, czytaj do pamięci ciągi w 
blokach 10M, łącz i pisz na dysk

.

Disk

1

3

4

2

2

1

4

3

Runs being
merged.

Merged run.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Jak łączyć posortowane ciągi?



Ale istnieje bardziej efektywne n-łączenie, gdzie 
czytamy ze wszystkich bloków jednocześnie



Po zastosowaniu czytania odpowiednich 
rozmiarowo części każdego bloku do pamięci i 
wypisywaniu odpowiednich rozmiarowo 
wyjściowych części bloków, dostępy do dysku nie 
zniszczą zalet algorytmu

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Pozostały problem z 
algorytmem opartym na 
sortowaniu



Zakładaliśmy: możemy trzymać słownik w 
pamięci.



Potrzebujemy słownik (który rośnie 
dynamicznie) aby implementować 
odwzorowanie term do termID .



Aktualnie możemy pracować z odwołaniami 
term,docID  zamiast z odwołaniami termID, 
docID  . . .



. . . Ale wtedy zbiory pośredniczące stają się 
bardzo duże. (Wtedy możemy skończyć ze 
skalowalną, ale bardzo wolną metodą budowy 
indeksu.)

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

SPIMI: 
Single-pass in-memory indexing



Ważna zasada 1: generuj oddzielne słowniki 
dla każdego bloku – nie ma potrzeby 
utrzymywania  term-termID odwzorowania 
miedzy blokami.



Ważna zasada 2: Nie sortuj. Gromadź 
wystąpienia w listach wystąpień tak jak się 
pojawiały.



Te zasady pozwolą wygenerować kompletny 
indeks odwrotny dla każdego bloku.



Te oddzielne indeksy mogą być łączone w 
jeden duży indeks.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

SPIMI-Invert



Łączenie bloków jest analogiczne jak dla BSBI.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

SPIMI: Kompresia



Kompresja powoduje, że SPIMI jest jeszcze 
efektywniejszy.



Kompresja termów



Kompresja wystąpień



Będzie na następnym wykładzie

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Indeksowanie rozproszone



Dla indeksowania w skali webowej:

Musimy użyć rozproszony klaster komputerów



Pojedyncze maszyny są zbyt zawodne



Mogą nagle spowolnić przetwarzanie lub ulec 
awarii



Jak możemy eksploatować taki zbiór 
maszyn?

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Centra danych Google



Centra danych Google zawierają głównie 
maszyny profesjonalne.



Centra danych są rozproszone po całym 
świecie.



W przybliżeniu: w całości 1 milion serwerów, 
3 miliony procesorów/rdzeni (Gartner 2007)



W przybliżeniu: Google instaluje 100,000 
serwerów na kwartał.



Wymaga to  200–250 milionów dolarów na rok



To może być 10% mocy obliczeniowej 
świata!?!

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Centra danych Google



Jeśli niezawodna maszyna ma 1000 
węzłów, każdy z niezawodnością 99.9% , 
jaka jest niezawodność całego systemu?



Answer: 63%



Wiele serwerów jest uszkodzonych w 
każdej minucie dla instalacji z 1 miliona 
serwerów.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Indeksowanie rozproszone



Utrzymuj maszynę master  zarządzającą 
indeksowaniem – traktowaną jako 
„bezpieczna”.



Podziel indeksowanie na zbiory 
(równoległych) zadań.



Maszyna master przypisuje każde zadanie 
do wolnej maszyny z systemu.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Równoległe zadania



Używa się dwa zbiory równoległych zadań



Parsery



Inwertery



Dzieli się wejściową kolekcję dokumentów 
na części



Każda część jest podzbiorem dokumentów  
(odpowiadającym blokom w BSBI/SPIMI)

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Parsery



Master przypisuje część do wolnej 
maszyny parsera



Parser czyta po jednym dokumencie i 
tworzy pary (term, doc) 



Parser zapisuje pary do  j partycji



Każda partycja jest dla zakresu pierwszych 
liter termów



(np.: a-f, g-p, q-z) – tutaj j = 3.



Następnie wykonuj inwersję indeksu

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Inwertery



Inwerter zbiera wszystkie pary (term,doc) 
pairs (= wystąpienia) do partycji jednego 
termu.



Sortuje i pisze listy wystąpień

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Przepływ danych

splits

Parser

Parser

Parser

Master

a-f g-p q-z

a-f g-p q-z

a-f g-p q-z

Inverter

Inverter

Inverter

Postings

a-f

g-p

q-z

assign

assign

Map
phase

Segment files

Reduce
phase

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Odwzorowanie redukujące 
(MapReduce)



Opisany właśnie algorytm budowy indeksu 
jest instancją MapReduce.



MapReduce (Dean and Ghemawat 2004) jest 
solidnym i koncepcyjnie prostym 
frameworkiem dla przetwarzania 
rozproszonego …



… bez pisania kodu dla części rozproszenia.



Opisują oni system indeksujący Google  (ca. 
2002) jako składający się z pewnej liczby faz 
zaimplementowanych w MapReduce.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

MapReduce



Konstrukcja indeksu była właśnie jedną fazą.



Inna faza: przekształcenie indeksu 
podzielonego na termy w indeks podzielony na 
dokumenty.



Term-partitioned: jedna maszyna obsługuje 
podzakres termów



Document-partitioned: jedna maszyna obsługuje 
podzakres dokumentów



Jak będzie powiedziane w części webowej 
wykładu – większość wyszukiwarek  używa 
indeksu dzielonego na dokumenty … lepsze 
zrównoważenie obciążenia itd.

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Schemat dla konstrukcji 
indeksu w  MapReduce



Schema of map and reduce functions



map: input → list(k, v)     reduce: (k,list(v)) → output



Instantiation of the schema for index 
construction



map: web collection → list(termID, docID)



reduce: (<termID1, list(docID)>, <termID2, 
list(docID)>, …) → (postings list1, postings list2, …)



Example for index construction



map: d2 : C died. d1 : C came, C c’ed. → (<C, d2>, 
<died,d2>, <C,d1>, <came,d1>, <C,d1>, <c’ed, d1>



reduce: (<C,(d2,d1,d1)>, <died,(d2)>, <came,(d1)>, 
<c’ed,(d1)>)  →  (<C,(d1:2,d2:1)>, <died,(d2:1)>, 
<came,(d1:1)>, <c’ed,(d1:1)>)

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Indeksowanie dynamiczne



Do tej pory zakładaliśmy, że kolekcja jest 
statyczna.



Rzadko tak bywa: 



Dokumenty przybywają z czasem i muszą być 
wstawiane.



Dokumenty są skreślane i modyfikowane.



To oznacza, że słownik i listy wystąpień 
muszą być modyfikowane:



Wystąpienia aktualizuje się dla termów 
będących już w słowniku



Nowe termy są dodawane do słownika

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Najprostsze podejście



Utrzymuj  “duży” główny indeks



Nowe dokumenty idą do “małego” 
dodatkowego indeksu



Przeszukuj obydwa i łącz wyniki



Skreślenia



Wektor bitowy błędów dla skreślonych 
dokumentów



Filtruj wyjściowe wyniki wyszukiwania tym 
wektorem bitowym błędów



Okresowo re-indeksuj aby uzyskać dobry 
indeks główny

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Problemy z głównym i 
dodatkowymi indeksami



Problem częstego łączenia – zbyt często przerabiamy



Mała wydajność w czasie łączenia



Aktualnie:



Łączenie dodatkowego indeksu do głównego indeksu jest 
efektywne jeśli utrzymujemy oddzielne pliki dla każdej listy 
odwołań.



Łączenie jest tym samym co proste append.



Ale wtedy musimy użyć wielu zbiorów – nieefektywne dla O/S.



Założenie dla reszty wykładu: indeks jest jednym 
dużym zbiorem.



W rzeczywistości: Używa się pośrednich rozwiązań 
(np.: podział bardzo dużych list odwołań, zbieranie list 
odwołań o długości  1 w jeden zbiór itd.)

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Łączenie logarytmiczne



Utrzymuj ciąg indeksów, każdy dwa razy większy 
od poprzedniego.



Umieść najmniejszy (Z

0

) w pamięci



Większe (I

0

, I

1

, …) na dysku



Jeśli  Z

0

 staje się zbyt duży (> n), pisz na dysk 

jako I

0



Lub łącz z I

0

 (jeśli I

0

 już istnieje) jako Z

1



Lub wypisuj połączenie Z

1

 na dysk jako I

1

 (Jeśli 

nie ma I

1

)



Lub łącz z  I

1

 formując Z

2



Itd..

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Łączenie logarytmiczne



Dodatkowy i główny indeks: czas konstrukcji 
jest  O(T

2

) ponieważ każde wystąpienie jest 

używane w każdym łączeniu.



Łączenie logarytmiczne: Każde wystąpienie jest 
łączone O(log T) razy, więc złożoność jest O(T 
log T)



Więc łączenie logarytmiczne znacznie 
efektywniejsze  dla konstrukcji indeksu



Ale przetwarzanie pytania teraz wymaga 
łączenia O(log T) indeksów



Podczas gdy jest  O(1) jeśli mamy główny i 
dodatkowy indeks

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Dalsze problemy z 
wielokrotnymi indeksami



Statystyki dla całych kolekcji są trudne do 
utrzymywania



Np.: gdy mówimy o korekcie spellingu: którą 
alternatywę mamy zaprezentować 
użytkownikowi?



Mówimy, weź ten z największymi trafieniami



Jak pamiętać ten najlepszy dla wielokrotnych 
indeksów i wektorów bitowych błędów?



Jedyna możliwość: ignoruj wszystko poza głównym 
indeksem przy porządkowaniu



Omówimy więcej takich statystyk używanych 
do rankingu wyników

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Dynamiczne indeksowanie w 
silnikach wyszukiwawczych



Wszystkie duże silniki wyszukiwawcze 
obecnie stosują dynamiczne indeksowanie



Ich indeksy mają częste zmiany ilościowe



Nowe obiekty, blogi, nowe tematyczne strony 
webowe



Sarah Palin, …



Ale (czasami/typowo) one również 
okresowo rekonstruują indeks z kopii



Przetwarzanie pytań jest wtedy przełączane na 
nowy indeks, a stary indeks jest kasowany

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Introduction to Information 
Retrieval

Introduction to Information 
Retrieval

 

 

 

 

Inne rodzaje indeksów



Indeksy pozycyjne



Pewne problemy z sortowaniem… są większe



Budowa indeksów z n-gramów znaków:



Gdy tekst jest parsowany, utwórz n-gramy.



Dla każdego  n-gramu, potrzebne wskaźniki do 
wszystkich termów słownika zawierających go –  
“wystąpienia”.



Zauważmy, że te same “wejścia wystąpień” będą 
przybywać powtarzalnie w parsowanych dokumentach 
– potrzebny efektywny haszing aby pamiętać ich ślad.



Np.: taki trigram uou występuje termie deciduous będzie 
odkryty w każdym tekstowym wystąpieniu deciduous



Potrzebujemy przetworzyć każdy term raz

dlaczego?