🔍 BI-VWM – Vyhledávání na webu a v multimediálních databázích

📚 Základy Information Retrieval (IR)

IR je základ každého fulltext vyhledávače. Klíčový problém: jak efektivně najít relevantní dokumenty v obrovských kolekcích?

Základní pojmy

• Dokument – entita obsahující fulltext (nebo fulltext anotaci jiné entity)
• Kolekce – množina dokumentů
• Term – slovo nebo fráze vyskytující se v dokumentu
• Slovník (Vocabulary) – množina všech unikátních termů v kolekci

Předzpracování textu (Text Preprocessing)

Bez předzpracování by slovník byl příliš velký (stovky tisíc termů). Cílem je ho zmenšit na ~20 % původní velikosti, čímž se zlepší jak kompaktnost, tak efektivita vyhledávání.

• Stop slova – velmi časté, neinformativní termy se odstraní (a, the, for, are, be, have, …). Mohou být i čísla, jména atp.
• Stemming / lemmatizace – redukce slov na jejich kořen/základní tvar: go, goes, went, going → go. Hledání pak propojí různé tvary téhož slova.

Měření kvality vyhledávání – Precision & Recall

• False alarm (false hit) – dokument je ve výsledku, ale neměl by být → snižuje precision
• False dismissal (false drop) – dokument měl být ve výsledku, ale není → snižuje recall
• Precision a recall jsou v přirozeném napětí: rozšíření výsledku zvyšuje recall, ale snižuje precision
• Precision-recall křivka – komplexní charakteristika systému; vyhodnocuje se na 11 standardních úrovních recallu

🔲 Booleovský model a invertovaný index

Datový model

• Dokument = množina termů → reprezentován jako binární vektor dimenze m (přítomnost/nepřítomnost termu)
• Term = množina dokumentů, ve kterých se vyskytuje → binární vektor dimenze n
• Výsledkem je řídká binární term-by-document matice (typicky 99 % nul)

Dotazování

• Dotaz = Booleovský výraz nad termy: AND, OR, NOT
• Příklad: q = Brutus AND Caesar AND NOT Calpurnia
• Evaluace = bitové operace nad vektory termů

Invertovaný index – implementace

Kompaktní reprezentace řídké matice. Každý term má tzv. inverted list – seřazený seznam ID dokumentů, ve kterých se vyskytuje.

• Zpracování dotazu probíhá ve stylu merge-sort: kurzory v jednotlivých listech se zarovnávají na stejná ID
• AND = průnik množin ID, OR = sjednocení, NOT = doplněk
• Optimalizace: termy se zpracovávají v pořadí od nejmenší frekvence (nejmenší listy) → nejmenší mezivýsledky
• Frekvence termů uložena → optimalizace pořadí zpracování AND výrazů

Pros

• Jednoduchý, intuitivní model
• Efektivní implementace (bitové operace)
• Oblíbený v profesionálním vyhledávání (právníci, lékaři)

📐 Rozšířený Booleovský model a Vektorový model (Vector Space Model)

Rozšířený Booleovský model

• Výsledek = celá kolekce seřazená dle klesající relevance
• Relevance q = k1 AND k2: vzdálenost vektoru dokumentu od bodu (1,1) v 2D prostoru
• Relevance q = k1 OR k2: vzdálenost od bodu (0,0)
• P-normy: generalizace s parametrem p ≥ 1 umožňuje ladit efektivitu systému
• Pros: stejný jazyk dotazů jako Booleovský, ale s rankingem
• Cons: výpočetně náročnější (p-mocniny a p-odmocniny)

Vektorový model (Bag of Words, BoW)

• Dokument = "bag of terms" (multi-množina termů)
• Slovník m termů → každý dokument dj je vektor dimenze m
• Dimenze prostoru jsou obvykle m > 10 000 (pro angličtinu)
• Dotaz = vektor stejné dimenze jako dokument (pár klíčových slov nebo celý dokument)

Vážení termů: TF-IDF

Ručním vážením by vznikly nekonzistence. Proto se používá automatické vážení na základě statistik frekvencí.

• TF (term frequency): tfᵢⱼ = fᵢⱼ / maxᵢ{fᵢⱼ} – normalizovaná frekvence termu tᵢ v dokumentu dⱼ (0..1)
• IDF (inverse document frequency): idfᵢ = log₂(n / dfᵢ) – termy vyskytující se v mnoha dokumentech mají nízké IDF
• TF-IDF: wᵢⱼ = tfᵢⱼ · log₂(n / dfᵢ) → experimentálně nejlepší w.r.t. precision/recall

Kosinusová podobnost – proč ne Euklid?

• Euklid není robustní w.r.t. násobení vah: dokument d2 zkonkatenovaný se sebou (d3) by byl vzdálenější od d1 než d2, ačkoli text je totožný
• Kosinusová podobnost porovnává směry vektorů (úhly), ne pozice:
  CosSim(dⱼ, q) = (dⱼ · q) / (|dⱼ| · |q|) = cos(θ)
• Vysoká hodnota = vysoká podobnost; ArCos dá úhlovou vzdálenost
• Proč ne Euklid v invertovaném indexu? Při Euklidu by nás zajímaly i dimenze s nulovými váhami v dotazu → nemůžeme přeskočit listy → ztráta efektivity

Implementace vektorového modelu invertovaným indexem

• Stejná struktura jako u Booleovského modelu, ale navíc každé ID dokumentu nese váhu: DocID(weight)
• Zpracování: merge-sort stylem, ale počítáme součet součinů (inner product/CosSim) místo Booleovských operací
• Výhoda: nulové váhy (99 % matice) přeskočeny → jen listy termů z dotazu

Relevance Feedback

• Uživatel označí relevantní / nerelevantní dokumenty
• Dotazový vektor q se posune: přidají se vektory relevantních dokumentů, odečtou nerelevantní
• Iterativní zpřesňování výsledku

Pros/Cons vektorového modelu

• ✅ Jednoduchý, geometrický model; query-by-example; ranking; efektivní
• ❌ Absence expresivní síly Booleovského dotazu; předpoklad nezávislosti termů (neřeší synonymii a homonymii)

🧠 Latentní sémantická indexace (LSI) a Word2Vec

Motivace pro LSI

• Vektorový model předpokládá nezávislé nízkoúrovňové termy – ale termy nezávislé nejsou!
• Problémy: synonymie (street, road, path → stejný koncept), homonymie (bank = banka / břeh)
• Dokumenty "more people look for jobs" a "unemployment is on rise" by měly být podobné, ale vektorový model je tak neohodnotí

SVD a dimenzionální redukce

• A = U · Σ · Vᵀ (matice U = bazové koncepty, Σ = singulární hodnoty = významnost konceptů, Vᵀ = concept-by-document matice)
• Koncepty jsou lineární kombinace termů; statisticky signifikantní (latentní sémantika)
• Zachováme pouze k nejvýznamnějších konceptů → dimenzionální redukce z 10⁴–10⁵ termů na 10¹–10³ konceptů
• Dotaz se projektuje do prostoru konceptů a porovnává kosinusovou podobností

Pros/Cons LSI

• ✅ Odhaluje "latentní sémantiku"; částečně řeší synonymii a homonymii; dimenzionální redukce
• ❌ Koncepty nejsou lingvisticky definované (jen statisticky); hustá matice → invertovaný index nevhodný (potřeba metrické metody); SVD má složitost O(n² + m³)

Word2Vec (Mikolov 2013)

• Dva algoritmy: CBOW (kontinuální bag of words – z kontextu predikuje střední slovo) a Skip-gram (z středního slova predikuje kontext)
• N-gram kontextové okno pro každé (centrální) slovo
• Výsledek: vektorová aritmetika pro NLP: vec("king") – vec("man") + vec("woman") ≈ vec("queen")
• Výhody oproti SVD: mnohem rychlejší, lépe škáluje, paralelně zpracovatelné; okno kontextu > celý dokument

🕸️ Webový graf, analýza odkazů, PageRank a HITS

Webový graf a motivace

• Web = orientovaný graf: uzly = webové stránky, hrany = URL odkazy
• Inlink: odkaz z pohledu odkazované stránky (těžko zjistitelný)
• Outlink: odkaz z pohledu odkazující stránky (v HTML kódu)
• Od 1998: samotné fulltext IR modely nestačí – spammeři zneužívají skrytý text. Strukturální informace v odkazech je sémanticky bohatší (jeden odkaz vs. spoustu textu)

Klíčové pojmy webového grafu

• Hub – stránka s mnoha outlinky (rozcestník)
• Authority – stránka s mnoha inlinky (autoritativní zdroj)
• Bipartitní graf – webová komunita; co-citation; in-tree; out-tree; 2-connected component; cycle (web ring)

PageRank (Brin & Page, 1998)

Iterativní vzorec:

• Inicializace: r₀(Pᵢ) = 1/n pro všechny stránky
• Aktualizace: rₖ₊₁(Pᵢ) = Σ rₖ(Pⱼ) / |Pⱼ| pro Pⱼ ∈ BPᵢ (stránky odkazující na Pᵢ)
• Stránka Pᵢ dostává rovnoměrný díl ranku každé stránky, která na ni odkazuje

Problémy původního vzorce a Google matice

• Rank sinks: stránky bez outlinků (dangling nodes) absorbují rank bez jeho redistribuce → rank se ztrácí
• Cykly: iterativní proces nemusí konvergovat (rank flipping)

Řešení – transformace matice H → Google matice G:

1. Dangling nodes: řádky s nulami nahradíme 1/n → stochastická matice S
2. Google matice: G = αS + (1–α)E, kde E = (1/n)·eeᵀ (matice jedniček dělená n)
3. Parametr α ≈ 0.85 (empiricky nejlepší): pravděpodobnost "následování odkazu" vs. "teleportace"

Vlastnosti Google matice a výpočet

• G je primitivní, ireducibilní, aperiodická → garantovaná konvergence do jediného PageRank vektoru
• Power method: π^(k+1)T = αP^(k)TH + (αP^(k)Ta + 1–α)eᵀ/n
• H je velmi řídká (~10 nenulových prvků na řádek) → každá iterace O(n)
• Stačí ~50 iterací pro 2–3 cifry přesnosti
• Google matice G je hustá → nemůže být materiálizována; používají se matrix-free metody

HITS (Hyperlink-Induced Topic Search, Kleinberg)

• Dva ranky: hub rank a authority rank
• Iterativní výpočet: auth(Pᵢ) = Σ hub(Pⱼ) pro Pⱼ odkazující na Pᵢ; hub(Pᵢ) = Σ auth(Pⱼ) pro Pⱼ odkazované z Pᵢ
• Používán ve vyhledávači Teoma

Aplikace rankingu v search engines – tři kroky

1. Ranking dle obsahu (vektorový model, kosinusová podobnost)
2. Získání PageRank skóre pro vrácené stránky
3. Re-ranking agregací content score a PageRank

🏆 Agregace rankingů – Fagin algoritmus a Threshold algoritmus

Fagin algoritmus (FA)

1. Čteme záznamy ze seřazených listů paralelně, dokud k objektů nemá přečteny všechny m ranků (z každého listu alespoň jeden)
2. Pro zbylé objekty doplníme chybějící ranky náhodným přístupem (cross links)
3. Spočteme agregace na všech přečtených objektech
4. Vrátíme k objektů s nejvyšším agregátním rankem

Threshold algoritmus (TA)

1. Paralelně čteme ze seřazených listů; po každém kroku zjistíme všechny ranky náhodným přístupem
2. Udržujeme buffer top-k kandidátů a threshold T = f(aktuální hodnoty na čelech listů) = horní mez agregátního ranku nepřečtených objektů
3. Pokud T ≤ rank k-tého kandidáta → zastavíme → výsledek je správný

One-step vs. Multi-step ranking

• One-step: globální agregační funkce přes všechny parciální ranky najednou → drahé, ale přesné
• Multi-step (re-ranking): postupné zužování kandidátů:
  1. Seřaď dle r1
  2. Vezmi prefix, seřaď dle r2
  3. Opakuj pro r3, …
  Příklad: 1) content similarity → prefix → 2) page rank → prefix → 3) layout similarity

🕷️ Webový crawling, indexování a architektury vyhledávačů

Složky webového vyhledávacího procesu

• Crawling – stahování obsahu (webových stránek) pomocí robotů/spiderů/botů
• Indexing – zpracování obsahu do formy vhodné pro vyhledávání
• Searching – vyhledávání relevantního obsahu pomocí dotazu

Crawler

• Krátký program řídící spidery – jak a které stránky stahovat
• Omezení: velikost webu, bandwidth → opakované návštěvy, prioritizace, optimální strategie
• Robot exclusion protocol – soubor robots.txt říká crawlerům, které stránky indexovat nesmí
• Etické crawlování = dodržování robots.txt

Typy indexů

• Content index – fulltext vyhledávání (invertovaný index)
• Structure/citation index – pro rankování stránek (PageRank)
• Special purpose index – pro content-based multimediální vyhledávání

Druhy dotazů

• Keyword query – malá sada termů (slov, frází)
• Full-text query – textový soubor parsovaný do keyword dotazu
• Content-based query – upload souboru, URL, nebo skica (pro multimediální vyhledávání)

Browsing a Filtering

• Browsing: iterativní navigace v databázi (neumíme formulovat dotaz) – explicitní nebo virtuální graf
• Filtering (doporučování): fixní nebo implicitní zájem uživatele; RSS, subscription, collaborative filtering

⚙️ Optimalizace pro vyhledávače (SEO)

On-page SEO elementy

• Název souboru (URL) – relevantní k obsahu; pomlčky = mezery; co nejkratší
• <title> tag – nejdůležitější ranking faktor; max 64 znaků; stručné shrnutí obsahu
• Header tagy (<h1>–<h6>) – hierarchická důležitost; <h1> = největší vizuální i sémantická váha
• <meta description> – text zobrazovaný ve výsledcích vyhledávání (ne vždy u Google, ale stále důležitý pro uživatele)
• <meta keywords> – dnes nevýznamné (zneužití spammery)
• <meta robots> – kontrola crawlerů (nahrazeno robots.txt)
• Text modifiers (<strong>, <em>, <b>, <i>) – vizuální i sémantická důležitost pro vyhledávače
• Alt text obrázků – vyhledávače nečtou obsah obrázků; alt text = popis relevantní k obrázku (ne spam)
• Interní odkazová struktura – descriptivní anchor text; menu v horní části; nepoužívat obrázky jako linky

Klíčová slova (Keyword generation)

• Nejdůležitější část SEO procesu
• Head terms (generic keywords): 1–2 slova, velký traffic, vysoká konkurence (např. "racing")
• Tail terms (specific keywords): 2–3 slova, menší traffic, cílenější vyhledávání (např. "old cars racing")
• Strategie: head terms na hlavní stránce, tail terms na podstránkách
• Keyword density: opakuj cílová KW, neopakuj necílová (propojení s vektorovým modelem – TF-IDF)
• Latentní sémantika: použij sémanticky příbuzná KW → prevence penalizace za over-optimization

Obsah stránek

• Pišme primárně pro lidi, ne pro vyhledávač
• Vyhněme se duplicitnímu obsahu (penalizace vyhledávači)
• Pravidelně aktualizujme obsah (fresh content = reward)
• User-generated content (testimonials, fóra, recenze)
• Optimalizujme i non-HTML dokumenty (PDF, Office) – čitelný text, ne bitmapy

Technická struktura webu

• Sitemap – HTML/XML soubor pomáhající robotům navigovat webem
• robots.txt – říká spiderům, které stránky (ne)indexovat; v root adresáři serveru
• .htaccess – konfigurace Apache serveru; password protection, banning botů
• Stránka "O firmě" a Privacy Policy zvyšují kredibilitu (spammeři je nemají)

Off-page SEO – budování odkazů

• Jeden kvalitní odkaz > stovky nekvalitních (propojení s PageRankem!)
• Hodnotit partnerské domény: věk domény, .edu/.gov domény, PageRank, původní obsah
• Jednosměrné (one-way) odkazy cennější než reciproční
• Komunitní participace: blogy, fóra (PageRank > 4, tematicky relevantní)
• Social Media Optimization (SMO): Facebook fan pages, Twitter, LinkedIn, YouTube
• Placené linky: text-link-ads.com ($10–$1000/měsíc), ale Google je kritizuje

Neetické SEO (Black Hat SEO)

• Skrytý text/header pro spam klíčových slov
• Zneužití meta tagů pro keyword spam
• Mass-submitting odkazů automatizovanými nástroji
• Link farms – umělé sítě odkazů
• TrustRank (Yahoo) – semi-automatické oddělení užitečných stránek od spamu
• Krátkodobý efekt; vyhledávače odhalí a penalizují/zabanují stránku

🌐 Sémantický web, RDF, OWL, Linked Data

Problém syntaktického webu

• Vyhledávače pracují s nízkoúrovňovými koncepty (klíčová slova), bez porozumění
• HTML = jazyk pro prezentaci, ne pro strojové porozumění
• Těžké dotazy: "Najdi hotel blízko pláže a levný" – vyžaduje zázemní znalosti

XML jako základ

• XML = eXtensible Markup Language; popis labeled stromové struktury
• Libovolné názvy elementů → nutnost globální dohody (namespace)
• XML namespace: identifikuje XML slovník pomocí URI
• Samotný XML sémantiku neurčuje – potřeba ontologií

RDF (Resource Description Framework)

• Příklad: <"Webová stránka", "has title", "Tony Benn">
• Množina RDF tripletů = labeled orientovaný multigraf = knowledge base
• RDFS (RDF Schema): definice aplikačně-specifických tříd a vztahů
• SPARQL: dotazovací jazyk pro RDF; SELECT, CONSTRUCT, ASK, DESCRIBE

OWL (Web Ontology Language)

• Rodina jazyků pro tvorbu ontologií (OWL Lite, OWL DL, OWL Full)
• OWL DL: based on description logic → možnost inference (odvozování)
• FOAF (Friend of a Friend): první aplikace Social Semantic Webu – popisuje osoby, vztahy

Linked Data

• Best practices pro publikaci strukturovaných dat na webu pomocí SW technologií
• 4 principy (Berners-Lee): 1) URI jako jména věcí; 2) HTTP URI; 3) poskytuj RDF info; 4) zahrň linky na jiné URI
• Globální distribuovaný datový prostor (DBpedia, EuroStat, data.gov.uk…)

✅ Shrnutí okruhu 1 a kontrolní otázky

Shrnutí (5 klíčových bodů)

• IR využívá tři základní modely: Booleovský (přesná shoda, bez rankingu), Vektorový (TF-IDF váhy, kosinusová podobnost, ranking) a LSI (konceptový prostor via SVD)
• Invertovaný index = klíčová datová struktura pro efektivní implementaci obou modelů
• PageRank: iterativní výpočet důležitosti stránek z linkové struktury; Google matice G = αS + (1–α)E zaručuje konvergenci; α≈0.85
• Top-k agregace (Fagin/TA): efektivní výběr k nejlepších dokumentů z více seřazených listů; TA je efektivnější díky threshold podmínce
• SEO = metodika tvorby stránek s ohledem na vyhledávače; propojeno s IR modely (TF-IDF, latentní sémantika, PageRank)

Kontrolní otázky a odpovědi

🖼️ Základy multimediálního vyhledávání

Motivace a kontext

• >99 % webového prostoru tvoří multimediální obsah (fotky, videa, audio)
• Instagram: 100M fotek/videí/den; Facebook: 350M fotek/den; YouTube: 500 h videa/min
• Tradiční IR (fulltext) nestačí – jak hledat "podobný obrázek"?

Kontext vs. Obsah

• Kontextové vyhledávání: snadná implementace (fulltext index), ale vyžaduje lidskou anotaci – subjektivní, neúplná
• Content-based search (CBIR): automatická extrakce vlastností z obsahu, bez potřeby anotace
• Semantic gap: nízkoúrovňové features vs. vysokoúrovňová sémantika (deep learning tuto mezeru zmenšuje)

Relační vs. Fulltext vs. Multimediální databáze

📊 Formalizovaný model podobnostního vyhledávání

Deskriptory – typy struktur

• Vektor – pro histogramy vlastností: x = <0.1, 0.4, 0.3, …>
• Množina (signature) – vážené centroidy: x = {<c₁,w₁>, <c₂,w₂>, …}
• Uspořádaná množina – pro časové řady, sekvence: x = <t₁, t₂, …, tₖ>

Typy podobnostních dotazů

• Range query (q, r): vrátí všechny objekty x ∈ S, kde d(q, x) ≤ r → "koule" v prostoru vzdáleností
• k Nearest Neighbor (kNN) query (q, k): vrátí k nejbližších objektů k q → "koule" s dynamickým poloměrem
• Range: vhodný, když uživatel zná sémantiku r (např. edit distance – počet editací). kNN: vhodný pro většinu případů, kdy r není znám.
• k Reverse Nearest Neighbors (kRNN): vrátí objekty xᵢ, pro které q ∈ kNN(xᵢ, k) → identifikace nejbližšího sousedství; využití v GIS (antény)
• Similarity join: spojení deskriptorů databáze A a B na základě range nebo kNN predikátu; self-join = detekce duplicit
• k closest pairs: k dvojic <x,y> ∈ A × B s nejmenší vzdáleností d(x,y)

📏 Vzdálenostní funkce pro různé typy dat

Vektorové vzdálenosti (pro histogramy, obecné vektory)

• Minkowski Lₚ vzdálenosti: Lₚ(q, d) = (Σ|wᵢⱼ – wᵢq|ᵖ)^(1/p)
• L₁ (Manhattan), L₂ (Euklid), L∞ (Chebyshev) = max rozdíl dimenzí
• Kosinusová vzdálenost – vhodná pro text (úhel důležitý, ne délka)
• Quadratic form distance – pro histogramy; zohledňuje podobnost binů (perceptuálně podobné barvy)

Adaptivní vzdálenosti (pro signature, obecné množiny)

• Signature Quadratic Form Distance (SQFD)
• Earth Mover's Distance (EMD) – "přepravní problém"; jak přetvořit jeden histogram na druhý; drahá O(2ⁿ) v obecném případě
• Hausdorff distance – max(max_min) vzdálenost; vhodná pro množiny bodů

Sekvenční vzdálenosti (řetězce, časové řady)

• Edit distance (Levenshtein) – min počet editací (insert, delete, replace) pro transformaci jedné sekvence na druhou
• Dynamic Time Warping (DTW) – elastické zarovnání časových řad; nedbá na lineární časové posuny
• Longest Common Subsequence (LCSS)

Výpočetní složitost vzdáleností

Příklady deskriptorů pro různá média

• Obrázky – globální features: Scalable Color (MPEG7) – HSV histogram 256 binů → Haar transform → 16–128D; Color Structure (MPEG7) – pohyblivý strukturovací element; L1 vzdálenost
• Obrázky – lokální features: SIFT/SURF – interest points/bloby; 128D SIFT vektor = gradient orientation histogramy; signature z vážených centroidů; SQFD nebo Hausdorff distance
• Obrázky – deep learning: globální vysokodimenzionální vektory; lokální detekce (bounding boxes + třídy)
• Tvary: centroid-to-contour time series; DTW nebo LCSS
• Audio: Diskrétní Fourierova transformace → power spectrum; Audio Spectrum Envelope (MPEG7) – lokální feature → spectrogram; vzdálenost pro multidimenzionální časové řady
• Melodie: noty → 2D body (pitch + timing); Earth Mover's Distance nebo Proportional Transportation Distance

🔺 Metrický prostor a metrické přístupové metody (MAM)

Metrické postuláty

• Reflexivita: d(x, x) = 0 – objekt je maximálně podobný sám sobě
• Nezápornost: d(x, y) ≥ 0; d(x, y) = 0 ⇔ x = y
• Symetrie: d(x, y) = d(y, x)
• Trojúhelníková nerovnost: d(x, z) ≤ d(x, y) + d(y, z) – klíčový postulát pro efektivní vyhledávání!

Dolní meze a filtrování (Lower Bounding)

• Pivot p: statický objekt z databáze; předpočítáme d(x, p) pro všechny x ∈ S
• Trojúhelníkovou nerovností: |d(q, p) – d(p, x)| ≤ d(q, x) → dolní mez z pivotu
• Čím těsnější dolní mez, tím více objektů filtrujeme → efektivnější vyhledávání
• Dolní mez nulová = zbytečná (nic nefiltruje)

Filtrování oblastí

• Kulové oblasti: dvě koule (Oᵢ, r_Oᵢ) a (q, r_q) se nepřekrývají, pokud d(Oᵢ, q) > r_Oᵢ + r_q
• Hyperplanové oblasti: objekt na jedné straně hyperplány – pokud d(Oᵢ, q) – r_q > d(Oⱼ, q) + r_q, první oblast se nepřekrývá s dotazem

Co je MAM?

• Předpoklad: d je metrika (trojúhelníková nerovnost nutná)
• Výsledek: pouze část databáze musí být prohledána → efektivní

📋 Pivot tabulky – AESA a LAESA

Základní myšlenka

• Mapování databázových objektů do "pivot space" – každý objekt x → vektor vzdáleností k pivotům
• L∞ vzdálenost v pivot space je dolní mez originální vzdálenosti d
• Výsledek: distance matrix (tabulka vzdáleností objekt × pivot)

AESA (Approximating and Eliminating Search Algorithm)

• Každý databázový objekt = pivot → čtvercová matice O(|S|²)
• Empiricky O(1) distance computations pro kNN – extrémně efektivní
• Problém: kvadratická konstrukce (příliš drahá pro velké databáze)

LAESA (Linear AESA)

• Pouze k vybraných objektů jako pivoté → matice O(|S|) = lineární
• Two-phase algoritmus:
  1. Zpracování distance matrix, filtrování objektů pomocí dolních mezí
  2. Nefiltrovaní kandidáti ověřeni výpočtem d(q, oᵢ) v originálním prostoru (refinement)
• Výběr dobrých pivotů klíčový pro efektivitu

🌳 Hierarchické metrické indexy – GNAT a M-tree

Obecný princip hierarchických MAM

• Partitioning metrického prostoru → hierarchie metrických oblastí
• Blízké objekty ve stejné oblasti (přímé dělení)
• Rekurzivní dělení stejným způsobem jako celá databáze
• Lokální pivoté (kontext-dependentní, z objektů podstromu)
• Problémy: velký objem oblastí, překryvy mezi sourozeneckými oblastmi, tvar oblastí

GNAT (Geometric Near-neighbor Access Tree)

• Hyperplanové dělení prostoru
• Generalizace gh-tree do n-ary stromu (více pivotů v každém uzlu)
• Zpracování range query: test překryvu všech oblastí; rekurzivně prohledáváme překrývající se podstromy
• Filtrování podstromu: pokud nejbližší možný objekt uvnitř oblasti (w.r.t. jednomu pivotu) je vzdálenější než nejbližší w.r.t. ostatním pivotům → filtruj

M-tree (Metric Tree)

• Hierarchie nested balls (vnořené koule); vyvážená stránkovaná struktura – vhodná pro sekundární uložiště
• Kompaktní hierarchie nutná – překryvy koulí vedou k neefektivnímu zpracování dotazů
• Zpracování query: traversal hierarchie, přístup jen k překrývajícím uzlům/podstromům
• Mnoho potomků: M*-tree, PM-tree, Slim-tree, …

Exact kNN algoritmus pro M-tree

• Branch-and-bound přístup s priority queue PR (uzly seřazené dle dolní-meze vzdálenosti k q)
• NN array: k kandidátů + jejich vzdálenosti (k-tý = dynamický query radius rq)
• Inicializace: rq = ∞, PR = {root}, NN prázdné
• Traversal: fetchujeme uzel z PR, vkládáme překrývající poduzel do PR, kandidáty do NN
• NN[k] se zmenšuje → uzly v PR mohou být prunovány dříve než jsou fetchnuty

🗂️ Hashové a hybridní metrické indexy: D-index, PM-tree, M-index

D-index (Hash-based index)

• Kombinace více bps funkcí → binární kód oblasti (pokud není 2 v kódu)
• Exclusion set: objekty s 2 v kódu; rekurzivně hashováno dalšími bps → víceúrovňový D-index
• Výhody: pro malý query radius ≤ jeden bucket na úroveň; pokud celý dotaz leží v oblasti → jen ten bucket
• Nevýhody: volba parametrů r, dₘ obtížná; nevyvážený index; vhodný jen pro malé query poloměry

PM-tree (Pivot M-tree)

• M-tree + sada p globálních pivotů
• Každá kulová oblast dále redukována p prstenci kolem pivotů
• Menší objem oblastí → lepší filtrování → rychlejší vyhledávání
• Synergie: M-tree ball partitioning + pivot table filtering

M-index (Metric Index)

• Kombinuje všechny principy: pivot tables, hyperplane partitioning, ball partitioning, hashing (order-preserving)
• Inspirace iDistance – mapování do 1D reálné osy
• n pivotů → n intervalů na reálné ose; každý objekt mapován k nejbližšímu pivotu + vzdálenost jako desetinná část klíče
• Range query = sada intervalů na reálné ose
• Víceúrovňový M-index: rekurzivní dělení jako GNAT
• Implementovatelný jakoukoliv strukturou udržující lineární pořadí (B⁺-strom)

⏱️ Výkonnost MAM – míry nákladů a srovnání

Míry logického nákladu

• DC (Distance Computations) – počet výpočtů d(*, *); dominantní, když je d drahá (O(n²) a více) nebo databáze fits in RAM
• I/O cost (disk access) – počet přístupů na disk; dominantní pro velké databáze na HDD/SSD
• Internal cost – overhead interních datových struktur a algoritmů

Fyzický náklad

• Realtime (wall clock time) – jediná objektivní míra v reálné aplikaci; ale platform-dependent

I/O analýza: HDD vs. SSD

Internal overhead MAM

• Složitější MAM → větší interní overhead: pomocné struktury, overhead data v indexu
• Příklad: inkrementální kNN (Hjaltason&Samet) – optimální v DC, ale velký overhead heap management
• LAESA s 128 pivoté: zpracování distance matrix = stejně nebo hůře než sekvenční vyhledávání

⚡ Aproximativní vyhledávání – motivace a metody

Proč aproximovat?

• Přesné vyhledávání může být příliš pomalé i s indexováním
• Multimediální vzdálenostní funkce stejně nedokonale modeluje lidskou sémantickou podobnost → i sekvenční scan je subjektivně přibližný
• Cíl: výrazné zrychlení za cenu malé ztráty kvality (řád rychlosti, jednotky % ztráty)

Indexovatelnost – Intrinsic Dimensionality

• Nízká δ (pod ~10): dataset je dobře strukturovaný, existují tight clustery → MAM efektivní
• Vysoká δ: dataset špatně strukturovaný, objekty téměř stejně vzdálené → jakýkoliv MAM stejně efektivní jako sekvenční scan!
• Intrinsicky vysokodimenzionální dataset = "curse of dimensionality"

Typy záruk aproximace

• Bounded guarantee: každý vrácený výsledek je relevantní do určité míry (nejsilnější)
• Probabilistic estimate: výsledky relevantní s určitou pravděpodobností (průměrně)
• No guarantee: jen empirické pozorování ze vzorků (nejslabší)

Aproximativní kNN heuristiky v M-tree

Přesný kNN algoritmus lze upravit pro rychlejší přibližné vyhledávání:

1. Slowdown of improvements: sledujeme, jak rychle se mění NN[k](čas); pokud první derivativa klesne pod κ → zastavíme
2. Approximately correct search (ε-kNN): relaxace na (1+ε)kNN; uzly z PR filtrovány agresivněji: rq' = rq/(1+ε)
3. Good fraction approximation: pro query (q, NN[k]) odhadneme podíl databáze F(r) = Pr{d(x,y) ≤ r} pomocí kumulativního histogramu vzdáleností; pokud F(rq) * |S| ≥ κ → zastavíme
4. PAC queries (Probably Approximately Correct): kombinace pravděpodobnostního a ε-správného přístupu; garantuje s pravděpodobností κ, že výsledky jsou (1+ε)-NN

Aproximativní vyhledávání v pivot tabulkách

• Přesné: kontrola všech objektů uvnitř prstenců z pivotů a range query
• Aproximativní: "zúžení" prstenců parametrem β; garantuje správnost s pravděpodobností δ
• β = f(počet pivotů p, rozptyl σ² distribuce vzdáleností)

Mapovací techniky (FastMap)

1. Vyber k (dimenzí target prostoru)
2. Pro každou dimenzi: najdi vzdálený pár pivotů (p1, p2) = nová osa
3. Pro každý objekt x: cₓ = (d(p1,x)² + d(p1,p2)² - d(p2,x)²) / (2·d(p1,p2)) [cosine law]
4. Aktualizuj d(*,*) na "kolmou" složku (Pythagorova věta) a goto 2

• Výsledek: přibližná Euklidovská reprezentace → rychlé L₂ dotazy v target prostoru

Permutační indexy

• Místo ukládání vzdáleností pivotů uložíme jen pořadí pivotů (permutaci) pro každý objekt
• Kompaktnější: k·n·log₂(k) bitů vs. 32·k·n bitů v pivot table
• Podobnost permutací: Spearman Rho nebo Spearman Footrule (pozice pivotů v permutaci)
• Aproximativní dotazy: seřadíme objekty dle permutační podobnosti + volitelný refinement krok

🔀 Multimodální vyhledávání, fúze výsledků a dotazovací jazyky

Popis objektů více modalitami

• Uživatel specifikuje dotaz více modalitami: klíčová slova + obrázek, více obrázků, obrázek + audio + relační data, atd.
• Early fusion: všechny modality agregovány v jednom podobnostním modelu → jeden deskriptor na objekt
• Late fusion: každá modalita reprezentována a dotazována samostatně → N modelů, nutný fúzní krok

Early Fusion – Multi-metric přístup

• Deskriptor složen z více sub-deskriptorů, každý se svým metrickým prostorem
• Multi-metric vzdálenost: D(q, x) = Σ wᵢ · dᵢ(q, x) kde wᵢ jsou váhy zadané uživatelem při dotazu
• Příklad: 3D model → depth buffer descriptor + silhouette descriptor; váhy W zadány při query time

Late Fusion – Skyline operátor

• Problém: velikost skyline neomezena; korelovaná data → malý skyline (a); anti-korelovaná → velký (b)
• V multimodálním vyhledávání: atributy = similarity orderings dle různých query příkladů → dynamic schema
• Multi-example similarity skyline query: vrátí objekty, které jsou kompromisem vůči více query příkladům

Late Fusion – Top-k operátor (viz okruh 1)

• Agregace parciálních rankingů z různých modalit pomocí monotónní funkce f (Min, Max, Avg)
• Implementace: Fagin nebo Threshold algoritmus
• Re-ranking: multi-phase querying – postupné zužování kandidátů různými modely

Dotazovací jazyky pro podobnostní vyhledávání

• Množinové operace nad výsledky podobnostních dotazů (sjednocení, průnik, …)
• Rozšíření SQL: similarity predicates pro BLOB atributy:
  • range(example.MMattribute, table.MMattribute, r)
  • kNN(example.MMattribute, table.MMattribute, k)
• Příklad: SELECT Id FROM BioData WHERE range(JohnSmith.Fingerprint, BioData.FingerPrint, 0.01)
• Similarity join: SELECT Criminal.Id, Citizen.Id FROM Criminal SIMILARITY JOIN Citizen ON range(Criminal.FingerPrint, Citizen.FingerPrint, 0.01)

Doporučovací systémy (Recommender Systems)

• Collaborative filtering (CF): doporučení na základě podobnosti uživatelů; user-based nebo item-based k-NN; problém sparsity dat, studený start
• Content-based: matching features položek s preferencemi uživatele; BoW, metrické vzdálenosti (Dice/Jaccard koeficient pro množiny)
• Knowledge-based: constraint-based nebo case-based; pro specializované domény (drahé zboží, profesionální nástroje)
• Social PageRank: tweeter je důvěryhodný/populární, pokud ho retweetují jiní populární tweeters
• Dimenzionální redukce v CF: SVD a PCA pro latentní vkusy/kategorie

✅ Shrnutí okruhu 2 a kontrolní otázky

Shrnutí (5 klíčových bodů)

• Multimediální vyhledávání = feature extraction (e: X→U) + distance function (d: U×U→ℝ) + query-by-example (range nebo kNN dotaz)
• Metrický model a trojúhelníková nerovnost umožňuje efektivní filtrování přes pivot-based lower bounds – základ všech MAM
• MAM typy: flat pivot tables (LAESA), hierarchické (GNAT, M-tree), hashové (D-index), hybridní (PM-tree, M-index) – každý má jiné trade-offs
• Aproximativní vyhledávání je nutné pro vysokodimenzionální data (curse of dimensionality); heuristiky v M-tree, permutační indexy, FastMap
• Multimodální vyhledávání: early fusion (multi-metric) vs. late fusion (skyline, top-k, re-ranking); rozšíření SQL o similarity predicates

Kontrolní otázky a odpovědi