Archiv/Databázové modely a jazyky/MMDB

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 $δ: U \times U \rightarrow R$ - libovolná fce vracející pro 2 dekriptory z univerza podobnostní skóre

základní dotazy ::

**range **- vezme se objekt $Q$ a poloměr dotazu $r$
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 $M$ * vzor $v$ , který chceme klasifikovat * a celé kladné číslo $k$ Algoritmus :: * v množine $M$ najdeme množinu $N$ obsahujíci $k$ vzoru, ktere jsou k vzoru $v$ nejbližší ze všech vzorů z $M$ * vzoru $v$ dáme klasifikaci, která je nejčastejší v množine $N$

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 :: MM DB 6250395489241108110.png does not exist. Create it?{: alt="300px"} * L1 manhattanska * L2 eukleidovská :: rychlé $O(n)$ , 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 :: MM DB 954379289549314657.png does not exist. Create it?{: alt="300px"}
  - složitost výpočtu $O(n^2)$ , 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 $x$ na masu $y$
  - složitost $O(2^n)$ , metrická

sekvence

časové řady
- DTW Dynamic Time Warping - nemetrická
  - používá se pro měření podobnosti na časových řadách :: MM DB 6351594138144169526.png does not exist. Create it?{: alt="300px"}
  - 💡 je výhodná bo představuje robustní zarovnání díky lokálnímu natahování/zkracování (time warp)
  - složitost $O((m+n)w)$ , 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á $O(mn)$ , metrická
- Hammingova - Editační pouze s replace
  - levná $O(n)$ , 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á $O(mn)$ , 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 :: MM DB 2027159719468114462.png does not exist. Create it?{: alt="300px"}
- 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 :: MM DB 573347960994207990.png does not exist. Create it?{: alt="300px"}
  - složitost $O(mn)*O(ground~ dist.)$ (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

Image:Ba08b30c7cd184254b353527.jpg

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 nejbližší možný objekt v query (vzhledem k O1) je dále než nejvzdálenější možný objekt v query (vzhledem k O6), pak neprojdeme levý podstrom (pokud spodní odhad z O1 je větší než horní odhad z O6) :: MM DB 5136080282252636911.png does not exist. Create it?{: alt="MM DB 5136080282252636911.png"} * $δ(Q, O1) - r > δ(Q, O6) + r$ * 💡 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 nejbližší možný objekt v query (vzhledem k O5) je dále než nejvzdálenější možný objekt v query (vzhledem k alespoň jedné partišně O1, O3, O4), pak neprojdeme podstrom :: MM DB 4281588065894422188.png does not exist. Create it?{: alt="MM DB 4281588065894422188.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%20DB%20752255278805970585.png :*využívá hierarchické hnízdění metrických regionů a je vyvážený

:: MM DB 2115865289095682470.png does not exist. Create it?{: alt=" 400px"}

::*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

Image:MM%20DB%206151133926930239281.png

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 $bps$ 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|

http://siret.ms.mff.cuni.cz/skopal/DBI034.htm
http://siret.ms.mff.cuni.cz/members/skopal/courses/NDBI034
https://is.cuni.cz/studium//soub_mana/index.php?tid=1&do=zobrazit https://is.cuni.cz/studium//soub_mana/index.php?tid=1&do=zobrazit

}}