Krótka (nie techniczna)
historia wyszukiwań
webowych
Pierwsze silniki bazujące na słowach
kluczowych około 1995-1997
Altavista, Excite, Infoseek, Inktomi, Lycos
Płatne szukanie z rankingiem: Goto
(przekształcone w Overture.com
Yahoo!)
Twój ranking zależy od opłaty
Aukcja dla słów kluczowych: casino było
drogie!
1
Krótka (nie techniczna)
historia wyszukiwań
webowych
1998+: Oparty na linkach pionierski ranking Google
Wymiótł wszystkie poprzednie silniki zostawiając Inktomi
Duże doświadczenie użytkowników w wyszukiwaniach dla
biznesu
W międzyczasie Goto/Overture roczne dochody były ok. 1
miliard $
Rezultat: Google dodał płatne szukanie “ads” do
strony niezależnie od wyników wyszukiwania
Yahoo postąpił podobnie, nabywając Overture (jako płatne) i
Inktomi (do szukania)
2005+: Google wzmocnił swój udział, dominując w
Europie a najbardziej w Ameryce Północnej
2009: Yahoo! i Microsoft zaproponowały złożone oferty
płatnego szukania
2
Wyniki
algorytmicz
ne
Wyszuk
i-wanie
płatne
3
Postawy wyszukiwania
webowego
The Web
Ad indexes
Web spider
Indexer
Indeksy
Search
Użytko-
wnik
4
Potrzeby użytkownika
Potrzeby [Brod02, RL04]
Informacyjne – chcemy
dowiedzieć się
o czymś (~40% /
65%)
Nawigacyjne – chcemy
dostać się
na
pewną stronę (~25% /
15%)
Transakcyjne – chcemy
zrobić coś
(za pośrednictwem web)
(~35% / 20%)
Dostęp do serwisu
Pobrać obiekty
Zakupy
Szare strefy
Znaleźć dobry hub
Szukanie odkrywcze “patrzymy co tam jest”
Low hemoglobin
United Airlines
Seattle weather
Mars surface images
Canon S410
Car rental Brasil
5
Jak dużo ludzie przeglądają
wyników?
(Source:
WhitePaper_2006_SearchEngineUserBehavior.pdf)
6
Empiryczna ocena wyników przez
użytkownika
Jakość stron jest bardzo różna
Relewancja nie jest wystarczającą miarą
Inne ważne oceny (nie IR!!)
Zawartość: Wiarygodność, rozproszenie, brak duplikatów, czy dobrze
utrzymane
Czytelność webowa: poprawne wyświetlanie & szybkie
Nie działa na nerwy: pojawianie się nieoczekiwanych informacji, etc
Precyzja vs. kompletność
W wyszukiwaniach webowych, kompletność rzadko ma znaczenie
Co ma znaczenie
Precyzja dla jednego 1? Precyzja powyżej pewnego poziomu?
Wszechstronność – musi sobie radzić z niejasnymi pytaniami
Kompletność ma znaczenie gdy liczba trafień jest bardzo mała
Postrzeganie przez użytkownika może nie być
naukowe, ale jest bardzo znaczące dla dużych
populacji
7
Empiryczna ocena silników przez
użytkowników
Relewancja i ważność wyników
UI – Prostota, nie bałaganiarski, odporny na błędy
Zaufanie – Wyniki są obiektywne
Dostarczanie wyników na niejednoznaczne pytania
Udostępnianie narzędzi dla pre/post przetwarzania
Zmniejszanie błędów użytkownika (automatyczna kontrola
spellingu, wspomaganie szukania,…)
Jawnie: Szukaj w wynikach, podobne do tych, rozwiń ...
Przewidująco: podobne szukania
Radzenie sobie z dziwnymi pytaniami
Specyficzne słownictwo webowe
Wpływ na stemming, sprawdzanie spellingu, etc
Adresy webowe wpisywane do skrzynki wyszukiwawczej
“Pierwszy i ostatni to najlepszy i najgorszy …”
8
Kolekcja dokumentów
webowych
Brak projektu/koordynacji
Rozproszone tworzenie treści, linki,
demokratyczne publikowanie
Treści zawierają prawdę, kłamstwa,
przestarzałe informacje,
sprzeczności …
Niestrukturalne (text, html, …),
semistrukturalne (XML, annotated
photos), strukturalne (Databases)…
Skala znacznie większa niż
poprzednie kolekcje tekstowe … ale
inne zapisy też doganiają
Wzrost – zwolnił w porównaniu z
początkowym “podwajaniem
objętości w ciągu kilku miesięcy” ale
ciągle trwa
Treść może być tworzona
dynamicznie
The Web
9
Spam
(Optymizacja silników
wyszukiwawczych)
10
Kłopoty z płaceniem za
reklamowanie się w sieci …
Kosztuje pieniądze. Co jest alternatywą?
Optymizacja silnika:
“strojenie” twojej strony webowej, aby zwiększyć
page rank dla algorytmicznego wyszukiwania
wybranych słów kluczowych
Alternatywa dla płacenia za umiejscowienie
To bardzo ważna funkcja marketingu
Dostarczana przez kompanie, webmasterów i
konsultantów (“Optymizatory silników”) dla
ich klientów
Niektóre perfekcyjne, inne bardzo podejrzane
11
Optymizacja silnika (Spam)
Motywy
Komercyjne, polityczne, religijne, lobbing
Promocja finansowana przez budżet reklam
Operatorzy
Wykonawca (Optymizatory silników) dla lobbystów, dla firm
Webmasterzy
Usługi hostingowe
Fora
Np.: Web master world (
)
Search engine specific tricks
Dyskusje na temat artykułów akademickich
12
Najprostsze formy
Pierwsza generacja silników opierała się głównie na
tf/idf
Najwyższe w rankingu dokumenty dla pytanie maui
resort były te zawierające najwięcej maui i resort
SEO (Search Engine Optimization) odpowiadali
częstym powtarzaniem wybranych termów
Np.: maui resort maui resort maui resort
Często powtórzenia były tego samego koloru co tło strony
webowej
Powtarzające się termy były indeksowane przez pająki
Ale niebyły widziane przez ludzi w wyszukiwarkach
Czysta gęstość słów nie
budzi zaufania jako
sygnał do wyszukania
dokumentu
13
Warianty wstawiania słów
kluczowych
Mylące meta-tagi, nadmierna
powtarzalność
Ukryte kolorami teksty, triki w
arkuszach styli, etc.
Meta-Tags =
“… London hotels, hotel, holiday inn, hilton,
discount, booking, reservation, sex, mp3, britney
spears, viagra, …”
14
Zakrywanie
Podawanie fałszywych treści dla pająków
sieciowych
Zakrywanie DNS: Przełączanie adresów IP.
Podszywanie się za kogoś.
Is this a Search
Engine spider?
Y
N
SPAM
Real
Doc
Cloaking
15
Inne techniki spamerskie
Strony wejściowe
Strony optymizowane dla pojedynczego słowa
kluczowego, które kierują na prawdziwą stronę
docelową
Linki typu spam
Towarzystwa wzajemnej adoracji, linki ukryte,
nagrody – później będzie więcej
Domain flooding: liczne domeny, które pokazują
lub kierują na stronę docelową
Roboty
Strumień fałszywych pytań – do programów
ustawiających ranking
“Dopasowanie” do programów rankingu silników
Miliony zgłoszeń przez Add-Url
16
Walka ze spamem
Oznaki jakości –
Preferowanie
autoryzowanych stron na
podstawie:
Głosy od autorów (sygnały o
linkach)
Głosy od użytkowników (sygnały
użycia)
Polityka dostarczania URL-I
Testy anty- robotowe
Limity na meta-słowa
kluczowe
Analiza siły linków
Ignorowanie statystycznie
dziwnych linków (lub tekstów)
Użycie analizy linków do
wykrywania spamerów (wina
przez skojarzenie)
Rozpoznawanie
spamu przez uczenie
maszynowe
Zbiór treningowy oparty
na rozpoznanym spamie
Filtry przyjazne
rodzinie
Analiza lingwistyczna,
ogólne techniki
klasyfikacji etc.
Dla obrazów: flesh tone
detectors, analiza tekstów
źródłowych etc.
Interwencja edytorska
Blacklists (czarne listy)
Badanie częstych pytań
Badanie skarg
Detekcja spodziewanych
wzorców
17
Więcej o spamie
Silniki wyszukiwania webowego mają
strategię na działania SEO tolerują/blokują
http://help.yahoo.com/help/us/ysearch/index.html
http://www.google.com/intl/en/webmasters/
Wyszukiwanie reklam: niekończąca się
wojna (techniczna) między SEO’s i
silnikami webowymi
Badania
18
Jaki jest rozmiar Web?
Problemy
Web jest w rzeczywistości nieskończony
Dynamiczna treść, np.: kalendarz
Soft 404: www.yahoo.com/<
cokolwiek
> to prawidłowa
strona
Statyczny Web zawiera syntaktyczne duplikaty,
głównie przez mirroring (~30%)
Pewne serwery są rzadko podłączane
Kto jest zainteresowany?
Media, a w konsekwencji użytkownik
Projektanci silników wyszukiwawczych
Strategie silników pająków. Wpływ na
kompletność.
19
Co możemy próbować
mierzyć?
Względne rozmiary silników
wyszukiwawczych
Pojęcie strony, która jest indeksowana jest
ciągle rozsądnie zdefiniowane.
Jednak są problemy
Poszerzenia dokumentów: np.: silniki indeksują strony
nie przechodząc całości, ale przez indeksowanie
kluczowego tekstu.
Ograniczenia dokumentów: Wszystkie silniki
ograniczają to co jest indeksowane (pierwsze n słów,
tylko relewantne słowa, etc.)
Pokrycie danego silnika
wyszukiwawczego w stosunku do innego
szczególnego procesu crawlingu.
20
Nowe definicje?
Statystycznie indeksowany Web jest
w pewnym sensie dość trudną
podstawą wyszukiwań.
Różne silniki mają różne preferencje
maksymalna głębokość url, max liczba/host,
anti-spamowe reguły, reguły priorytetu, etc.
Różne silniki indeksują różne rzeczy dla
tych samych URL:
frames, meta-keywords, document restrictions,
document extensions, ...
21
A B = (1/2) * Rozmiar A
A B = (1/6) * Rozmiar B
(1/2)*Roz.A = (1/6)*Roz.B
ize A / Size B =
(1/6)/(1/2) = 1/3
Próbka
losowa
URLi z A
Sprawdź
czy jest
zawarta w B i
na odwrót
A
B
Każdy test
wymaga:
(i) Próbkowania (ii)
Checking
Względny rozmiar wynikający
z pokrywania się silników A i B
22
Próbkowanie URLi
Idealna strategia: Generuj losowy URL i
sprawdź czy zawarty jest każdym indeksie.
Problem:
Losowe URLe są trudne do
znalezienia! Wystarczy wygenerować losowy
URL zawarty w danym silniku.
Podejście 1: Generuj losowy URL zawarty w
danym silniku
Wystarczające do estymacji względnego rozmiaru
Podejście 2: Błądzenie przypadkowe/ adresy IP
W teorii: może dać prawdziwą estymację rozmiaru Web
(inaczej niż dla ciągle względnych rozmiarów indeksów)
23
Metody statystyczne
badaniach Web
Podejście 1
Losowe pytania
Losowe wyszukiwania
Podejście 2
Losowe adresy IP
Błądzenie przypadkowe
24
Losowe URLe z losowych pytań
Generowanie losowego pytania: jak?
Leksykon
:
400,000+ słowa z webcrawlera
Koniunkcyjne pytania: w
1
i w
2
np.: vocalists AND rsi
Weź 100 wynikowych URLi z silnika A
Wybierz losowo URL jako kandydata do
sprawdzenia na obecność w silniku B
Ten rozkład daje wagę prawdopodobieństwa
W(p) dla każdej strony.
Hipoteza: W(SE
A
) / W(SE
B
) ~ |SE
A
| / |SE
B
|
Nie słownik
angielski
25
Sprawdzanie bazujące na
pytaniach
Mocne pytanie aby sprawdzić czy silnik B ma
dokument D:
Pobierz D. Weź listę słów.
Użyj 8 najmniej częstych słów jako pytanie AND
do B
Sprawdź czy D jest obecny w zbiorze wynikowym.
Problemy:
Bliskie duplikaty
Sformułowania
Przekierowania
Time-out silników
Czy pytanie z 8-słów jest wystarczająco dobre?
26
Cd: Zalety & wady
Statystycznie poprawne dla odpowiednich wag.
Problemy powodowane przez losowe pytania
Tendencyjność pytań:
Faworyzują strony o bogatej zawartości
w językach leksykonu
Tendencyjność rankingu:
Rozwiązanie: Użycie
koniunkcyjnych pytań & podaj wszystko
Tendencyjne sprawdzanie:
Duplikaty, ubogie strony są
omijane
Elementy restrykcyjne dla dokumentów lub pytań:
silnik
może źle funkcjonować z
8 słowowymi pytaniami koniunkcyjnymi
Elementy złośliwości:
sabotowanie przez silniki
Problemy operacyjne:
Time-outs, uszkodzenia, różnice w
budowie silników, modyfikacja indeksu.
27
Szukania losowe
Wybierz losowe wyszukiwania ze logów
serwera [Lawrence & Giles 97] lub zbuduj
“losowe szukania”
Użyj tylko pytania z małymi zbiorami wyników.
Policz znormalizowane URLe w zbiorach
wynikowych.
Zastosuj analizę statystyczną
28
Cd: Zalety & wady
Zaleta
Może dać lepszą interpretację na ludzką
ocenę pokrywania tematu
Problemy
Próbki są skorelowane ze źródłami logów
Duplikaty
Techniczne problemy statystyczne (muszą
być niezerowe wyniki, wyniki średnie nie są
statystycznie pewne)
29
Cd: Szukania losowe
575 & 1050 pytań z logów pracowniczych NEC RI
6 silników w 1998, 11 w 1999
Implementacja:
Ograniczone do pytań z < 600 wyników w
całości
Zliczanie URLi z każdego silnika po weryfikacji
trafień pytania
Obliczanie rozmiarów & nakładania się dla
indywidualnych pytań
Przybliżanie rozmiaru indeksu & nakładania się
przez uśrednienie po wszystkich pytaniach
30
adaptive access control
neighborhood preservation
topographic
hamiltonian structures
right linear grammar
pulse width modulation
neural
unbalanced prior
probabilities
ranked assignment method
internet explorer favourites
importing
karvel thornber
zili liu
Cd: Pytania z badań Lawrence and
Giles
softmax activation function
bose multidimensional
system theory
gamma mlp
dvi2pdf
john oliensis
rieke spikes exploring
neural
video watermarking
counterpropagation
network
fat shattering dimension
abelson amorphous
computing
31
Losowe adresy IP
Generuj losowe adresy IP
Znajdź serwer webowy o takim adresie
Jeśli taki istnieje
Pobierz wszystkie strony z serwera
Z tego zbioru wybierz losowo stronę
32
Cd: losowe adresy IP
Żądania HTTP do losowych adresów IP
Ignorujemy: puste lub wymagające autoryzacji lub
wyłączone
[Lawr99] około 2.8 million IP adresów przechodząc
dostepne dla crawlera serwery webowe (16 million w
całości) z badanych 2500 serwerów.
OCLC stosując próbkowanie IP znalazł 8.7 M hostów w
2001
Netcraft [Netc02] dotarł do 37.2 milionów hostów w lipcu 2002
[Lawr99] wyczerpująco „crawled” 2500
serwerów i ekstrapolował
Przybliżony rozmiar Web jako 800 milionów stron
Przybliżone użycie deskryptorów metadanych:
Meta tagi (słowa kluczowe, opisy) na 34% stronach domowych,
Dublin core metadata na 0.3%
33
Cd: Zalety & wady
Zalety
Prawidłowa statystyka
Niezależność od strategii crawlera
Wady
Nie zwraca uwagi na duplikaty
Wiele hostów może dzielić jeden IP, lub nie przyjmować
żądań
Nie ma gwarancji, że wszystkie strony są do strony
domowej.
Np.: strony pracowników
Prawo potęgowe dla # stron/hostów wykazuje tendencję
w kierunku witryn małą liczbą stron.
Ale tendencja może, być dokładnie określona jeśli znamy rozkład
Potencjalne zagrożenie spamem (wiele serwerów unika
bloków IP)
34
Błądzenie przypadkowe
Rozpatrujemy Web jako graf skierowany
Buduj błądzenie przypadkowe na tym grafie
Zawiera zmienne zasady “skoków” do już
odwiedzonych stron
Nie utknij w pułapce na pająki sieciowe!
Można przejść wszystkie linki!
Jest zbieżny do rozkładu stacjonarnego
Musimy założyć, że graf jest skończony i niezależny of
błądzenia.
Założenia nie są spełnione (cookie crumbs, zatapianie)
Czas potrzebny dla uzyskania zbieżności nie jest rzeczywiście
znany
Próbki z rozkładu stacjonarnego błądzenia
Użyj metodę “mocnego pytania” do sprawdzenia
pokrywania przez SE
35
Cd: Zalety & wady
Zalety
“Statystycznie poprawna” metoda co najmniej
w teorii!
Może działać nawet dla nieskończonego Web
(zakładając zbieżność) dla określonych metryk.
Wady
Lista ziaren początkowych jest problemem.
Praktyczna aproksymacja może być
nieprawidłowa.
Nie ma znormalizowanego rozkładu
Może służyć spamu linków
36
Wnioski
Żadna metoda próbkowania nie jest
idealna.
Wiele nowych idei ...
....ale problem jest coraz trudniejszy
Ilościowe badania są fascynującym i
dobrym problemem badawczym
37
Duplikaty dokumentów
Web jest pełen dublujących się treści
Wykrywanie dokładnego dublowania się
= dokładne dopasowanie
Nie jest to częste
Ale bardzo wiele przypadków to prawie
duplikaty
Np.: ostatnio modyfikowana data może
być jedyną różnicą między dwiema
kopiami strony
38
Detekcja Duplikatów/Prawie
duplikatów
Duplikat: Dokładne dopasowanie może być
łatwo wykryte
Prawie duplikat: Przybliżone dopasowanie
przegląd
Oblicz syntaktyczne podobieństwo za pomocą
miary odległości edycyjnej
Użyj progu podobieństwa do wykrycia prawie
duplikatów
Np.: Podobieństwo > 80% => Dokumenty są
„prawie duplikatami”
Nie jest to przechodnia własność chociaż czasami
używana jako przechodnia
39
Obliczanie podobieństwa
Cechy:
Segmenty dokumentów (naturalne lub sztucznie
podzielone)
Tabliczki (N-gramy słów)
a rose is a rose is a rose →
a_rose_is_a
rose_is_a_rose
is_a_rose_is
a_rose_is_a
Miara podobieństwa między dwoma dokumentami (=
zbiory tabliczek)
Przecięcie zbiorów
Specyficznie (Rozmiar_Przecięcia/ Rozmiar_Unii)
40
Tabliczki + Przecięcie zbiorów
Obliczenie
dokładnego zbioru przecięcia
między wszystkimi parami dokumentów
jest drogie/niewykonalne
Przybliżenie używa odpowiednio dobrany
podzbiór n-gramów z każdego (szkic)
estymacja
(rozmiar_przcięcia/rozmiar_unii)
oparta na
krótkich szkicach
Doc
A
Doc
A
Zbiór n-gramów
A
szkic A
Doc
B
Doc
B
Zbiór n-gramów
B
szkic B
Jaccard
41
Szkic dokumentu
Twórz “wektor szkicu” (rozmiar ~200) dla
każdego dokumentu
Dokumenty dla których pokrywa się
≥
t
(powiedzmy 80%) odpowiadających są
prawie duplikatami
Dla dokumentu D, szkic
D
[ i ] jest
następujący:
Niech f mapuje wszystkie szkice w uniwersum
0..2
m
(np.: f = odciski palców)
Niech
i
będzie losową permutacją na 0..2
m
Pobierz MIN {
i
(f(s))} na wszystkich szkicach s w
D
42
Obliczanie Szkic[i] dla Doc1
dokument1
2
64
2
64
2
64
2
64
Start z 64-bitową f(n-gramów)
Permutować na osi liczbowej
z rozkładem
i
Pobierz min wartość
43
Testowanie czy Doc1.Szkic[i] =
Doc2.Szkic[i]
Dokument 1
Dokument 2
2
64
2
64
2
64
2
64
2
64
2
64
2
64
2
64
Czy są równe?
Testuj dla
200
losowych permutacji:
1
,
2
,…
200
A
B
44
Jednak…
Dokument 1
Dokument 2
2
64
2
64
2
64
2
64
2
64
2
64
2
64
2
64
A = B iff określony n-gram z MIN wartością w unii
Doc1 and Doc2 jest wspólny dla obu (tzn.: leży w
przecięciu)
Twierdzenie: To nastąpi z prawdopodob.
Rozmiar_przecięcia/Rozmiar_unii
B
A
Dlaczego?
45
Podobieństwo zbiorów C
i
, C
j
Przedstawmy zbiory jako macierze kolumnowe A;
jeden wiersz dla każdego elementu w uniwersum.
a
ij
= 1 wskazuje obecność jednostki i w zbiorze j
Przykład
j
i
j
i
j
i
C
C
C
C
)
C
,
Jaccard(C
C
1
C
2
0 1
1 0
1 1 Jaccard(C
1
,C
2
) = 2/5 = 0.4
0 0
1 1
0 1
46
Istotna obserwacja
Dla kolumn C
i
, C
j
,
są cztery typy wierszy
C
i
C
j
A
1 1
B
1 0
C
0 1
D
0 0
Notacja obciążenia:
A = # (liczba) wierszy
typu A
Twierdzenie
C
B
A
A
)
C
,
Jaccard(C
j
i
47
“Min” Haszing
Losowo
permutuj
wiersze
Haszuj
h(C
i
) = indeks pierwszego wiersza
jako 1 w kolumnie C
i
Zaskakująca własność
Dlaczego?
Oba są
A/(A+B+C)
Przeglądaj w dół kolumny
C
i
, C
j
aż do
pierwszego wiersza
Typu-nie-D
h(C
i
) = h(C
j
) Wiersz typu A
j
i
j
i
C
,
C
Jaccard
)
h(C
)
h(C
P
48
Szkice Min-Hash
Pobierz
P
losowo wiersz permutacji
Szkic MinHash
Sketch
D
= lista
P
indeksów pierwszych wierszy z
1 w kolumnie z C
Podobieństwo sygnatur
Niech
sim[szkic(C
i
),szkic(C
j
)]
= ułamek
permutacji, gdzie wartości MinHash się zgadzają
Zaobserwowano
E[sim(sig(C
i
),sig(C
j
))]
=
Jaccard(C
i
,C
j
)
49
Przykład
K
1
K
2
K
3
W
1
1 0 1
W
2
0 1 1
W
3
1 0 0
W
4
1 0 1
W
5
0 1 0
Sygnatury
S
1
S
2
S
3
Permutacja 1 = (12345)
1 2
1
Permutacja 2 = (54321)
4 5
4
Permutacja 3 = (34512)
3 5
4
Podobieństwa
1-2 1-3 2-3
Kol-Kol
0.00 0.50 0.25
Sig-Sig
0.00 0.67 0.00
50
Trik implementacyjny
Permuting
universe
even once is prohibitive
Row Hashing
Pick
P hash functions
h
k
: {1,…,n}{1,…,O(n)}
Ordering
under h
k
gives random permutation of
rows
One-pass Implementation
For each
C
i
and
h
k
, keep “
slot
” for min-hash value
Initialize
all slot(C
i
,h
k
) to
infinity
Scan rows
in arbitrary order looking for 1’s
Suppose row R
j
has 1 in column C
i
For each h
k
,
if h
k
(j) < slot(C
i
,h
k
), then slot(C
i
,h
k
) h
k
(j)
51
Example
C
1
C
2
R
1
1 0
R
2
0 1
R
3
1 1
R
4
1 0
R
5
0 1
h(x) = x mod 5
g(x) = 2x+1 mod 5
h(1) = 1
1
-
g(1) = 3
3
-
h(2) = 2
1
2
g(2) = 0
3
0
h(3) = 3
1
2
g(3) = 2
2
0
h(4) = 4
1
2
g(4) = 4
2
0
h(5) = 0
1
0
g(5) = 1
2
0
C
1
slots
C
2
slots
52
Comparing Signatures
Signature Matrix S
Rows = Hash Functions
Columns = Columns
Entries = Signatures
Can compute
– Pair-wise similarity of
any pair of signature columns
53
Wszystkie pary sygnatur
Powyższe rozważania pokazują, że mamy
ekstremalnie efektywną metodę do estymacji
współczynnika Jaccard dla pojedynczej pary
dokumentów.
Ale ciągle musimy estymować N
2
współczynników gdzie N jest liczbą stron
webowych.
Ciągle b. wolno
Jedno z rozwiązań: locality sensitive hashing
(LSH)
Inne rozwiązanie: sortowanie (Henzinger 2006)
54