Podobnostní dotazy v multimediálních databázích, metrické indexacní metody. (nové od 2011) (🎓)

Podobnostní dotazy v multimediálních databázích

Funkce podobnosti <math>δ: U \times U \rightarrow R</math> - libovolná fce vracející pro 2 dekriptory z univerza podobnostní skóre

základní dotazy

  • range - vezme se objekt <math>Q</math> a poloměr dotazu <math>r</math>

  • k-Nearest Neigbour - vybere k nejpodobnějších objektů k dotazu (💡 lze použít i na regresi a klastrování)

    Vstup

    • trénovací množina klasifikovaných vzoru <math>M</math>

    • vzor <math>v</math>, který chceme klasifikovat

    • a celé kladné číslo <math>k</math>

    Algoritmus

    • v množine <math>M</math> najdeme množinu <math>N</math> obsahujíci <math>k</math> vzoru, ktere jsou k vzoru <math>v</math> nejbližší ze všech vzorů z <math>M</math>

    • vzoru <math>v</math> dáme klasifikaci, která je nejčastejší v množine <math>N</math>

  • Reverse kNN - objekt Q a číslo k -> vrátí všechny objekty pro které je Q v kNN

advanced queries

  • Distinct kNN (DkNN) - vrať k nejbližších a disjunktních sousedů

  • skyline - vrať prvky z množiny vyhovující nejlépe dvěma/více atributům

  • aggregation (top-k operator)

SQL

  • nativní SQL - výhody: nemusí se měnit ex.db, nemá restrikce na range dotazy ; nevýhody: pomalé (nejsou indexy, ani optimalizace dotazů), musí se doprogramovat funkcionalita

  • SQL extensions (např. SIREN - rozšiřuje SQL o podobnostní dotazy) - nové db objekty (dat.typy, vzdálenostní fce, indexy), nativní predikáty pro WHERE, operátory - similarity JOIN

{{collapse|Podobnosti (vzdálenosti) v mm.db|2= vektorové

  • independent dimensions

    • Lp (Minkowského) vzdálenosti - je třída vekt. vzdáleností uvažujících nezávislé dimenze

    +get/MM%20DB%206250395489241108110.png

    • L1 manhattanska

    • L2 eukleidovská

    rychlé <math>O(n)</math>, metrická

  • histogramy

    • vážená eukleidovská vzd. L2

    • kvadratická forma (Quadratic Form Distance)

      • dimenze prostoru se předpokládají korelované (💡 např histogram na homogenní doméně)

      • matice pro histogramy obsahuje korelace mezi reprezentanty barev vyskytujícími se v obrázcích

    +get/MM%20DB%20954379289549314657.png

    • složitost výpočtu <math>O(n^2)</math>, metrická

    • Earth Mover Distance

      • řeší se nejmenší přesun masy mezi histogramy (💡 nestačí pouhá korelace dimensí (sloupců))

      • EMD(x,y) = nejmenší množství práce pro přesun masy <math>x</math> na masu <math>y</math>

      • složitost <math>O(2^n)</math>, metrická

sekvence

  • časové řady

    • DTW Dynamic Time Warping - nemetrická

      • používá se pro měření podobnosti na časových řadách

      +get/MM%20DB%206351594138144169526.png

      • 💡 je výhodná bo představuje robustní zarovnání díky lokálnímu natahování/zkracování (time warp)

      • složitost <math>O((m+n)w)</math>, nemetrická

  • řetězce

    • Editační (edit distance)

      • počítá se nejmenší počet operací nutných ke konverzi jednoho řetezce na druhý

      • operace: insert, delete, replace

      • náročná <math>O(mn)</math>, metrická

    • Hammingova - Editační pouze s replace

      • levná <math>O(n)</math>, metrická

    • LCSS Longest Common SubSequence - hledá se nejdelší společný podřetězec (💡 NE jenom substring)

      • LCSS(ABCD, ACBD) = 3 (either ABD or ACD)

      • náročná <math>O(mn)</math>, nemetrická

      • 💡 je výhodná protože: umožňuje lokální zarovnání (tj. zarovnání pouze podposloupností)

množinové

  • obecné

    • Jaccardova - normovaná velikost průniku

    +get/MM%20DB%202027159719468114462.png

    • Hausdorff distance - podobnost elementů množin využívá ground distance

      • ground distance - vzdálenost dvou vlastností (např: vzdálenost obrysů)

      • HD je pak nejdelší vzdálenost od nejbližšího souseda

      +get/MM%20DB%20573347960994207990.png

      • složitost <math>O(mn)*O(ground~ dist.)</math> (metrická)

}}

Metrické indexování

metrický model podobnostního vyhledávání

místo metrické vzdálenosti se používá levnější spodní odhad (lower-bound)

pivoti (pro odhad vzdálenosti)

  • globální - statické indexy (platné po celý život indexu)

  • lokální - dynamické objekty zvolené během indexování (💡 centroidy klusterů)

vnitřní dimense ρ(S,d) = μ^2/2σ^2 (intrinsic dimensionality)

statistický ukazatel odvozený z distribuce vzdáleností v databázi

slouží jako indikátor indexovatelnosti db pod danou metrikou

vysoká vnitřní dimense - data netvoří shluky a tedy jsou špatně strukturovaná, 💡 prokletí dimese

nízká - dobře strukturovaná a tvoří těsné shluky

metrické přístupové metody (Metric Access Methods)

{{multiple image |align = tright

|direction = horizontal

| image1 = MM DB 3243662082400190120.png | width1 = 250

| caption1 = MAM

| image2 = MM DB 2659906073994319164.png | width2 = 400

| caption2 = (L)AESA range query: sekvenční průchod vzdálenostní maticí + kontrola výsledku v původním prostoru }}

algoritmy a/nebo datové struktury umožňující rychlé podobnostní hledání v metrickém modelu

💡! nepatří k nim R-strom

'''Pivotové tabulky'''

třída indexů používající mapování dat na prostor pivotů

vzdálenostní matice - vzdálenosti od každého z pivotů

(L)AESA - (Linear) Approximating and Eliminating Search Algorithm

AESA - každý prvek je pivot, rychlé hledání sousedů, pomalá kontrukce tabulky

k prvků jsou pivoti, matice má rozměr O(|S|)

NN query - cyklus vylepšuje kandidáty

+spatial access methods

'''Stromové''' indexy

  • gh-stromy (Generalized Hyperplane Tree) nadrovinový binární strom (hyperplane = nadrovina)

    • konstrukce - vyber 2 pivoty (např nejvzdálenější prvky) a rozděl db na dvě partišny nadrovinou podle vzdáleností, rekurzivně pokračuj

    • range query - otestuj na překrytí s query obě partišny, rekurzivně pokračuj níž a testuj stejně

    příklad pro levou partišnu (podstrom)

    • pokud <span style="color:#0000ff">nejbližší možný objekt</span> v query (vzhledem k O1) je dále než <span style="color:#008000">nejvzdálenější možný objekt</span> v query (vzhledem k O6), pak neprojdeme levý podstrom (pokud spodní odhad z O1 je větší než horní odhad z O6)

    +get/MM%20DB%205136080282252636911.png

    • <math>δ(Q, O1) - r > δ(Q, O6) + r</math>

    • 💡 tedy můžeme projít i oba podstromy

    • GNAT (Geometric Near-neighbor Access Tree) rozšíření na n-pivotů + tabulka vzdáleností

      • range query - příklad pro podstrom O5:

        • pokud <span style="color:#0000ff">nejbližší možný objekt</span> v query (vzhledem k O5) je dále než <span style="color:#008000">nejvzdálenější možný objekt</span> v query (vzhledem k alespoň jedné partišně O1, O3, O4), pak neprojdeme podstrom

      +get/MM%20DB%204281588065894422188.png

  • (P)M-tree - inspirován R-stromem (vyvážený, regiony jsou ale kruhové, data jsou v kořenech (stránky na disku), vnitřní uzly jsou routing entries se středy kruhových regionů a poloměrem)

Image:MM DB 752255278805970585.png :*využívá hierarchické hnízdění metrických regionů a je vyvážený

+get/MM%20DB%202115865289095682470.png

::*range query - traverzování překrývajícími se regiony (podstromy)

  • PM-tree - obohacuje M-tree o p globálních pivotů

    • každý kruhový region je redukován p kružnicemi se středy v pivotech

    • čímž zmenšuje regiony a tedy zlepšuje filtrování

'''Hashed '''indexes

  • D-Index

  • hashovaný index, základem jsou prstence

    • parametr 2ró je tloušťka prstence

    • parametr dm je median vzdálenosti od pivotu k jeho objektům

    • hashovaci fce bps vrací

      • 2 pokud je součástí prstence

      • 1 vně prstence (💡 tzn. není v prstenci)

      • 0 uvnitř prstence (💡 tzn. není v prstenci)

    • ruzne <math>bps</math> fukce se kombinují do řetězců hash kódu

      • pokud hashovací kód obsahuje 2 patří do exkluzní množiny

      • rekurzivně se zahashují znovu dokud se exkluzní množiny dostatečně nezmenší

    • struktura

      • hashované regiony jsou organizované do přihrádek na disku - parametry bps funkce se těžce určují

      • přehashování exkluzní množiny definuje další level D-indexu

::

{{Zdroje|

}}