Sys Inf 03 Manning w 19

background image

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

background image

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

background image

Wyniki

algorytmicz

ne

Wyszuk

i-wanie

płatne

3

background image

Postawy wyszukiwania
webowego

The Web

Ad indexes

Web spider

Indexer

Indeksy

Search

Użytko-

wnik

4

background image

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

background image

Jak dużo ludzie przeglądają
wyników?

(Source:

iprospect.com

WhitePaper_2006_SearchEngineUserBehavior.pdf)

6

background image

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

background image

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

background image

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

background image

Spam

(Optymizacja silników
wyszukiwawczych)

10

background image

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

background image

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 (

www.webmasterworld.com

)

Search engine specific tricks

Dyskusje na temat artykułów akademickich 

12

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

http://airweb.cse.lehigh.edu/

18

background image

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

background image

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

background image

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

background image

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

background image

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

background image

Metody statystyczne
badaniach Web

Podejście 1

Losowe pytania

Losowe wyszukiwania

Podejście 2

Losowe adresy IP

Błądzenie przypadkowe

24

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

“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

background image

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

background image

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

background image

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

background image

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

background image

Comparing Signatures

Signature Matrix S

Rows = Hash Functions

Columns = Columns

Entries = Signatures

Can compute

– Pair-wise similarity of

any pair of signature columns

53

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
Sys Inf 03 Manning w 06
Sys Inf 03 Manning w 02
Sys Inf 03 Manning w 07
Sys Inf 03 Manning w 03
Sys Inf 03 Manning w 21
Sys Inf 03 Manning w 20
Sys Inf 03 Manning w 09
Sys Inf 03 Manning w 01
Sys Inf 03 Manning w 04
Sys Inf 03 Manning w 08
Sys Inf 03 Manning w 05
Sys Inf 03 Manning w 06
Sys Inf 03 Manning w 02
Sys Inf 03 Manning w 07
Sys Inf Manning w
opracowane pytania MSI (1), Studia Zarządzanie PWR, Zarządzanie PWR I Stopień, V Semestr, Modelowani
ei 03 2002 s 19 21
abc projekt sys.inf, szkola, projekt II

więcej podobnych podstron