Přibližné metrickéindexování / vyhledávání

Jan Dědek

2

Hlavní téma

Michael E. Houle, Jun Sakuma:

Fast Approximate Similarity Search in Extremely High-Dimensional Data Sets

Proceedings of the 21st International Conference on Data Engineering (ICDE 2005, April 5-8)

3

Obsah

• Kvalita přibližného vyhledávání

• Přehled existujících indexačních metod

• SASH– Datová struktura a algoritmy– Časová, prostorová složitost– Experimentální výsledky– Výhody a nevýhody

4

Kvalita přibližného vyhledávání 1

• Míra podobnosti dist– dist : D × D → R+

– metrika:• reflexivita, pozitivita, symetrie, trojúhelníková nerovnost

• Typy dotazů– query-by-example

• rozsahový dotaz – práh r

• k nejbližších sousedů – k-NN (k-nearest-neighbor)

5

Kvalita přibližného vyhledávání 2

• k přibližně nejbližších sousedů (k-ANN)– approximate k-NN– maximální (uspokojivá) chyba ε > 0

• (supplied error)• parametr většiny přibližných algoritmů

– výsledek k-ANN(q) dotazu ( U ):

• |U| = k• dist(q, u) ≤ (1 + ε)rk u ∈ U,

• rk – skutečná vzdálenost ke k-tému nejbližšímu sousedu

6

Kvalita přibližného vyhledávání 3

• Způsoby měření přesnosti (1) – přesah výsledku (ε)

– ui – i-tý nejbližší soused ve výsledku– ri – vzdálenost skutečně i-tého nejbližšího souseda– A1 i A2 nabývají hodnot „1+ ε“

7

Kvalita přibližného vyhledávání 4

• Způsoby měření přesnosti (2) – úspěšnost dotazu– recall

– U’ je zároveň podmnožina ideálního (přesného) dotazu

– Vyjadřuje procentuelní přesnost / úspěšnost dotazu

8

Kvalita přibližného vyhledávání 5

• Sekvenční hledání k-NN(q) (Seq)– Objekt se q se porovná s celou databází.

• Sekvenční hledání v podmnožině dat (SSeq)– Sekvenční k-NN dotaz se provede na náhodně

vybrané podmnožině dat velikosti m.– úspěšnost = m / n– rychlost (n / m)-krát větší než při sekvenčním

hledání

9

Přibližné indexační metody 1FTAE

• Ferhatosmanoglu, Tuncel, Agrawal, El Abbadi (2001)

1. Rozdělí data do clusterů pomocí heuristiky K-means.

2. Při k-ANN(q) najde clustery nejbližší dotazu.

3. Data uvnitř vybraných clusterů setřídí podle vzdálenosti od q a nejbližší vrátí.

– Při třídění vezme v úvahu jen některé souřadnice

4. Výsledek se ještě iterativně zpřesňuje– Prozkoumáním více clusterů

– Setříděním podle dalších souřadnic

10

Přibližné indexační metody 2 FTAE - výsledky

• Zrychlení zhruba o jeden řád (degree of magnitude)• 100 000 obrázků, 64 dimenzí, 10-ANN

– Přesnost 70%, A1 = 1,05• 43x méně načtených obrázků

– Přesnost 90%, A1 = 1,02• 16x méně načtených obrázků

• Nevýhody FTAE– Problematické ladění parametrů algoritmu– Funkčnost závisí na výsledku K-means heuristiky,

která má mnoho neduhů.

11

Přibližné indexační metody 3 Clindex

• Li, Chang, Garcia-Molina, Wiederhold (2002)

• Opět metoda založená na clusterování

• Speciální technika vytváření clusterů– Funguje pouze na datech snadno rozdělitelných

do clusterů

• Používá Euklidovu vzdálenost

12

Přibližné indexační metody 4 Clindex - výsledky

• 30 000 obrázků, 48 dimenzí, 20-ANN– Přesnost 70%

• 21x rychlejší než sekvenční čtení

– Přesnost 90%• 12x rychlejší než sekvenční čtení

13

Přibližné indexační metody 5 Indyk & Motwani

• P. Indyk, R. Motwani (1998)• Metoda založená na hašování (LSH)

• 200 000 textur, 65 dimenzí, 10-ANN– A2 = 1,14

– 20x méně načtených záznamů než při sekvenčním hledání

14

Přibližné indexační metody 6 iMinMax

• B. C. Ooi, K. L. Tan, C. Yu, S. Bressan (2000)1. Převede vektorové hodnoty na reálná čísla

• Výpočet založený na hodnotě největší souřadnice a na pozici této souřadnice uvnitř vektoru

2. Reálná čísla setřídí3. k-NN hledání probíhá postupným

rozšiřováním relevantního intervalu reálných čísel.

• Dokud interval neobsahuje k nejbližších sousedů.

15

Přibližné indexační metody 7 iDistance

• C. Yu, B. C. Ooi, K. L. Tan, H. Jagadish (2001)

• Modifikace iMinMax• Místo extrémních hodnot souřadnic

indexuje podle extrémních vzdáleností od referenčních bodů (pivotů).

• iDistance a iMinMax dobře fungují pro data s dim < 30

– Při redukci dimenze pro dim < 200

16

Přibližné indexační metody 8 MTree (1)

• P. Zezula, P. Savino, G. Amato, F. Rabitti (1998)

• Několik metod pro k-ANN nad prostorovými indexy (především M-tree)

• Jedná se o přibližné – „randomizované“ varianty klasického (přesného) algoritmu, založeného na trojúhelníkové nerovnosti.

17

Přibližné indexační metody 8 MTree (2)

• Metoda MTree předčasně ukončí vyhledávání

– Využívá hodnotu distribuce vzdáleností k hledanému objektu.

– Distribuce se odhaduje.– Odhadnuta z předpočítané distribuce

vzdáleností mezi prvky databáze• Nevyhovuje složitě strukturovaným datům

18

Dimenze - problém všech metod

• Všechny uvedené metody selhávají, pokud je dimenze dat příliš vysoká.

• Časová složitost často lineárně závisí na počtu dimenzí dat.

• Pro vysoké dimenze jsou uvedené metody pomalejší než sekvenční hledání.

19

SASH

The Spatial Approximation Sample Hierarchy

(Michael E. Houle, Jun Sakuma)

• Přibližná prostorová hierarchie

• Prakticky použitelný index pro přibližné vyhledávání v datech s extrémně vysokou dimenzí.

20

SASH – datová struktura 1

• Orientovaný graf podobný stromu– ohodnocené hrany

• S vlastnostmi (1):– Každý uzel odpovídá jednomu záznamu.– Uzly jsou rozděleny do level-ů.

• Poslední level obsahuje n / 2 uzlů.

• Každý další level je dvakrát menší než předchozí.

• První level obsahuje jediný uzel – kořen.

21

SASH – datová struktura 2

• S vlastnostmi (2):– Hrany vedou pouze mezi sousedními level-y

• ve směru dolů (od kořene)

– Každý uzel má• alespoň jednoho rodiče (mimo kořen)• maximálně p rodičů• maximálně c dětí (doporučeno c = 4p)

– Ohodnocení hrany (u,v) = dist(u,v)• Vypočteno při konstrukci struktury

22

SASH – datová struktura 3

• S vlastnostmi (3):– Každý uzel je dosažitelný z kořene.– Pro každý uzel v označíme jednoho rodiče jako

guarantor, g(v).– Pak říkáme, že uzel je závislý (dependent) na

uzlu g(v).

23

Konstrukce SASH struktury

1. Uzlům se náhodně přiřadí level-y.

2. SASH struktura se konstruuje iterativně od kořene.

• Level-y se propojují hranami tak, aby byly spojeny právě nejbližší sousedé.

• Algoritmus ConnectSASHLevel(l) popisuje, jak ve struktuře, která je zbudovaná (propojená) až po level l-1 připojit level l.

24

ConnectSASHLevel(l)

1. If (l == 2)• Připoj všechny prvky v l ke kořeni.

g(v) = kořen

2. Else pro každý uzel v levelu l:a) Najdi p nejbližších sousedů Pl-1(v,p) z levelu

l-1. (viz dále)

b) Označ Pl-1(v,p) jako prozatímní rodiče.

c) Vyřeš skutečné rodičovství (vytvoř hrany).

25

Najdi Pi(v,p)(p nejbližších sousedů uzlu v v levelu i)

1. case (i == 1) P1(v, p) = kořen2. case (i > 1)

• rekurzivní konstrukce:

a) Označ Pi’(v) jako množinu všech dětí všech uzlů z Pi-1(v,p)

b) Vrať Pi (v,p) která má následující vlastnosti:• Pi (v,p) Pi’(v) • |Pi (v,p)| = p (resp. p pro malé Pi’(v))• Prvky Pi (v,p) jsou co nejblíže k v (podle míry dist)

26

Postupné určování nejbližších sousedů

27

Vyber rodiče z prozatímních rodičů

• Máme– Pro každý uzel v v levelu l množinu prozatímních

rodičů z levelu l-1.

• Pro každý uzel u v levelu l-1:1. Označíme C(u) jako množinu uzlů (v levelu l),

které ho chtějí za rodiče.2. C(u) zmenšíme na velikost c

• vypuštěním nejvzdálenějších prvků od u.

3. Prvky C(u) spojíme s u hranami. • (uděláme z nich skutečné děti u)

28

Problém se sirotky

• Předchozí postup každému uzlu nezaručí rodiče – vzniknou sirotci.

• Pro ne-sirotky nastavíme g(v) na nejbližšího rodiče.

• Sirotkům najdem jednoho rodiče, který se stane i guarantor.

• Hledáme vždy v dvojnásobném množství nejbližších sousedů.

29

Problém se sirotky - algoritmus

a) nastav i = 1

b) spočítej Pl-1(v , 2ip)c) if

• v Pl-1(v , 2ip) mají všechny prvky maximální počet dětí

then zvyš i o 1 a opakuj od kroku b)

d) zvol g(v) = nejbližší volný prvek v Pl-1(v , 2ip)

• Konečnost algoritmu je zaručena pro c > 2p.

30n=22, p=2, c=5, H nemůže být otcem V

31

k-ANN dotaz (uniformní verze)

• Provádí se podobně jako jako algoritmus pro hledání nejbližších sousedů Pi (v,p).

• Spočítá P1(q, k) P∪ 2(q, k) . . . P∪ ∪ h(q, k)

– h je počet level-ů.

• Ze sjednocení vybere k nejbližších prvků a vrátí je jako výsledek dotazu.

32

Kandidáti na výsledek dotazu

33

k-ANN dotaz (geometrická verze)

• Od předchozí případu se liší ve vyhledávaném počtu sousedů.– Pro různé levely se používá různé k.

• P1(q, k1) P∪ 2(q, k2) . . . P∪ ∪ h(q, kh)

•

• Dává lepší výsledky v kratším čase. – (než uniformní verze)

34

Prostorová složitost

• Počet uzlů v levelu i:• Max počet hran od radičů (z levelu i do i+1):

– • Max počet hran k dětem (z levelu i-1 do i):

– maximálně tolik co bylo rodičovských

• Průměrný počet hran na uzel je tedy maximálně2p + 1/2i

• Hran celkem: 2pm + O(log2n) < O(pn)

35

Časová složitost

• v počtech použití míry dist

• Při zanedbání ošetřování sirotků:– konstrukce struktury: pcn log2n

– uniformní k-ANN: ck log2n

– geometrický k-ANN:

36

Časová složitost - zobecnění

• Za předpokladu, že by k bylo v Ω(nε):– pro libovolné ε > 0

– konstrukce struktury: O(n log n)– geometrický k-ANN: O(k + logn)

• Složitost vůbec nezávisí na na počtu dimenzí!

37

Testování

• Pro srovnání autoři implementovali ještě zmíněnou metodu MTree

• Implementace– Microsoft Visual C++ v7.0

• Testování– Windows XP– 3.0GHz Pentium IV single processor

• Měření výkonu– Vždy průměr ze 100 náhodných dotazů.– Recall se zvyšoval pomocí parametru k’ < k.

38

Experimentální paměťové nároky

39

MEDLINE

• Výskyty klíčových slov v MEDLINE žurnálu– z U.S. National Library of Medicine’s PubMed

database

• 1 055 073 záznamů• 1 101 003 atributů

– z toho průměrně 75 nenulových

• míra dist: – úhel mezi vektorem dokumentu a dotazu

40

41

42

BactORF

• Biologická databáze proteinových sekvencí– DNA Data Bank of Japan

• 385 039 záznamů• 40 000 atributů

– z toho po filtraci průměrně 125 nenulových

43

44

45

VidFrame• Databáze videosnímků z ranního varieté

japonské televize. • 9 000 000 záznamů• 32 atributů• míra dist:

– Euklidovská vzdálenost

• Testovalo se zrychlení algoritmu při zmenšení počtu objektů v databázi.– zrychlení 100, 200, 350 -krát – pro data velikosti 9×104, 9×105, 9×106

46

Časová složitost je skutečně sub-lineární

47

SASH – závěr 1

• První přibližná metoda použitelná na data s dimenzí větší než 1000.

• Flexibilní metoda

• dist nemusí splňovat metrické axiomy.

• Navrženo pro použití v operační paměti.– Kvůli hustému propojení hranami.– Neumí využít procesor cache (oproti MTree).

48

SASH – závěr 2

• Bohužel pouze statická metoda– Nevadí pro účely clustering-u a klasifikace– Lze doplnit o omezené přidávání nových prvků

• Ztrácí se kvalita náhodnosti.

• Nejde delete a update.

– Dynamická verze struktury je předmětem dalšího výzkumu.