Title

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!

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

Potrzeby użytkownika



Potrzeby [Brod02, RL04]



Informacyjne – chcemy

dowiedzieć się

o czymś (~40% /

65%)



Nawigacyjne – chcemy

dostać się

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

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

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 …”

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

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

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 

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

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, …”

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?

SPAM

Real

Doc

Cloaking

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

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

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/

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ść.

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.

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, ...

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





Każdy test

wymaga:

(i) Próbkowania (ii)

Checking

Względny rozmiar wynikający
z pokrywania się silników A i B

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)

Metody statystyczne
badaniach Web



Podejście 1



Losowe pytania



Losowe wyszukiwania



Podejście 2



Losowe adresy IP



Błądzenie przypadkowe

Losowe URLe z losowych pytań



Generowanie losowego pytania: jak?



Leksykon

400,000+ słowa z webcrawlera



Koniunkcyjne pytania: w

i w

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

) / W(SE

) ~ |SE

| / |SE

Nie słownik
angielski

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?

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.

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ą

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)

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



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

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ę

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%

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)

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

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

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

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

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

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)

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

Zbiór n-gramów
A

szkic A

Doc

Zbiór n-gramów
B

szkic B

Jaccard

Szkic dokumentu



Twórz “wektor szkicu” (rozmiar ~200) dla
każdego dokumentu



Dokumenty dla których pokrywa się

≥

(powiedzmy 80%) odpowiadających są

prawie duplikatami



Dla dokumentu D, szkic

[ i ] jest

następujący:



Niech f mapuje wszystkie szkice w uniwersum
0..2

(np.: f = odciski palców)



Niech 

będzie losową permutacją na 0..2



Pobierz MIN {

(f(s))} na wszystkich szkicach s w

Obliczanie Szkic[i] dla Doc1

dokument1

Start z 64-bitową f(n-gramów)

Permutować na osi liczbowej
z rozkładem



Pobierz min wartość

Testowanie czy Doc1.Szkic[i] =
Doc2.Szkic[i]

Dokument 1

Dokument 2

Czy są równe?

Testuj dla

200

losowych permutacji:



, 

,…



200

Jednak…

Dokument 1

Dokument 2

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

Dlaczego?

Podobieństwo zbiorów C

, C



Przedstawmy zbiory jako macierze kolumnowe A;
jeden wiersz dla każdego elementu w uniwersum.
a

= 1 wskazuje obecność jednostki i w zbiorze j



Przykład

)

Jaccard(C







0 1

1 0
1 1 Jaccard(C

) = 2/5 = 0.4

  0    0
  1    1
  0    1

Istotna obserwacja



Dla kolumn C

, C

są cztery typy wierszy

1 1

1 0

0 1

0 0



Notacja obciążenia:

A = # (liczba) wierszy

typu A



Twierdzenie

)

Jaccard(C





“Min” Haszing



Losowo

permutuj

wiersze



Haszuj

h(C

) = indeks pierwszego wiersza

jako 1 w kolumnie C



Zaskakująca własność



Dlaczego?



Oba są

A/(A+B+C)



Przeglądaj w dół kolumny

, C

aż do

pierwszego wiersza

Typu-nie-D



h(C

) = h(C

)  Wiersz typu A









Jaccard

)

h(C

)

h(C



Szkice Min-Hash



Pobierz

losowo wiersz permutacji



Szkic MinHash

Sketch

= lista

indeksów pierwszych wierszy z

1 w kolumnie z C



Podobieństwo sygnatur



Niech

sim[szkic(C

),szkic(C

)]

= ułamek

permutacji, gdzie wartości MinHash się zgadzają



Zaobserwowano

E[sim(sig(C

),sig(C

))]

Jaccard(C

)

Przykład

1 0 1

0 1 1

1 0 0

1 0 1

0 1 0

Sygnatury

Permutacja 1 = (12345)

1 2

Permutacja 2 = (54321)

4 5

Permutacja 3 = (34512)

3 5

Podobieństwa

1-2 1-3 2-3

Kol-Kol

0.00 0.50 0.25

Sig-Sig

0.00 0.67 0.00

Trik implementacyjny



Permuting

universe

even once is prohibitive



Row Hashing



Pick

P hash functions

: {1,…,n}{1,…,O(n)}



Ordering

under h

gives random permutation of

rows



One-pass Implementation



For each

and

, keep “

slot

” for min-hash value



Initialize

all slot(C

) to

infinity



Scan rows

in arbitrary order looking for 1’s



Suppose row R

has 1 in column C



For each h



if h

(j) < slot(C

), then slot(C

)  h

(j)

Example

1 0

0 1

1 1

1 0

0 1

h(x) = x mod 5
g(x) = 2x+1 mod 5

h(1) = 1

g(1) = 3

h(2) = 2

g(2) = 0

h(3) = 3

g(3) = 2

h(4) = 4

g(4) = 4

h(5) = 0

g(5) = 1

slots

Comparing Signatures



Signature Matrix S



Rows = Hash Functions



Columns = Columns



Entries = Signatures



Can compute

– Pair-wise similarity of

any pair of signature columns

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

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)

Document Outline