Introduction to Information
Retrieval

Konstrukcja indeksu

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

Podstawy hardware



Wiele decyzji projektowych w IR bazuje
charakterystykach hardware



Rozpoczniemy od przeglądu podstaw
hardware

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

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

Typowe parametry hardware



symbol statistic value



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

−3



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

−8



częstotliwość procesora 10

−1



p operacje niskiego poziomu 0.01 μs = 10

−8

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



pojemność pam. Głównej

kilka GB



pojemność dyskowa 1 TB lub wiecej

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

Dokument RCV1

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



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 #

did

enact

julius

caesar

was

killed

the

capitol

brutus

killed

let

with

caesar

the

noble

brutus

hath

told

you

caesar

was

ambitious

Introduction to Information
Retrieval

Term

Doc #

did

enact

julius

caesar

was

killed

the

capitol

brutus

killed

let

with

caesar

the

noble

brutus

hath

told

you

caesar

was

ambitious

Term

Doc #

ambitious

brutus

capitol

caesar

did

enact

hath

julius

killed

let

noble

the

told

you

was

with

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

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

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

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

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

N porównaniami,

jak długo to będzie trwać?

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

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

Jak łączyć posortowane ciągi?



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

10 = 4 poziomami.



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

Disk

Runs being
merged.

Merged run.

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

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

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

SPIMI-Invert



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

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

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

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

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

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

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

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

Inwertery



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



Sortuje i pisze listy wystąpień

Introduction to Information
Retrieval

Przepływ danych

splits

Parser

Master

a-f g-p q-z

Inverter

Postings

a-f

g-p

q-z

assign

Map
phase

Segment files

Reduce
phase

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

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

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

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

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

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

Łączenie logarytmiczne



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



Umieść najmniejszy (Z

) w pamięci



Większe (I

, I

, …) na dysku



Jeśli Z

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

jako I



Lub łącz z I

(jeśli I

już istnieje) jako Z



Lub wypisuj połączenie Z

na dysk jako I

(Jeśli

nie ma I

)



Lub łącz z I

formując Z



Itd..

Introduction to Information
Retrieval

Łączenie logarytmiczne



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

) 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

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

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

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?

Document Outline

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46

Sys Inf 03 Manning w 04

Document Outline