== XML data v relacích, indexace XML dat, podobnost XML dat, XML a webové služby. (nové od 2011) (🎓🎓🎓) ==
{{Zkazky|
* '''xPath (Pokorny)''' - 2009
* '''XQuery a XSLT (Mlýnková) 2010''' - Popsat co to je a k čemu to je. Stačí vědět jak to funguje, není nutný znát help zpaměti. Vědět jakou má který jazyk sílu a co umí. A pak vědět, že jsou vzásadě ekvivalentní. Akorát že XSLT umí přepínat mezi různými výstupními soubory.
* '''Technologie XML 2010''' - největší zádrhel mých státnic - přestože jsem znal co je a na co je a v principu jak se používá XML, SGML, DTD, XML Schema, XPath, XQuery, XSLT, DOM, SAX, docela chtěl zkoušející vědět, jak přesně (i když zase ne úplně syntakticky přesně) se něco konkrétního zapíše v XSLT nebo v XML Schema, což jsem přesně nevěděl; snažil jsem se říct princip (že v XML Schema např. určuju, co může daný element obsahovat skrze typy, co se může jak opakovat, atd., že v XSLT mám naskládány šablony a k nim příslušející XPath), leč to nestačilo, chtěl vidět konkrétní (polo-konkrétní) zápis a konkrétně jak se to vyhodnocuje krok za krokem, což jsem pořád nebyl schopen moc přesně napsat a popsat. Nakonec jsem to nějak ukoulel na 3 matným vzpomínáním na to, jak jsem někdy před šesti lety něco dělal v XSLT... Docela zrádná otázka, doporučuju na to dávat bacha. Viděl jsem nějaké zápisky, kde někdo tvrdí, že "stačí slajdy z 1. přednášky", no, myslím, že určitě nestačí.
** v tehle otazce je potreba znat XSLT, XPath a to vcetne prikladu
}}
{{TODO|umravnit a zkonfrontovat}}
=== Indexace XML ===
Metody indexace
:Indexace úplného textu
::nevýhoda: nelze dotazovat podle struktury
:Indexace relací klasicky (Lore) ???
:: http://infolab.stanford.edu/lore/
:Číselná schémata
::indexování založené na pozicích
:::použití absolutních resp. relativních adres pro reprezentaci pozic slov a značek v XML dokumentu
::Dietzovo číslování
::...
:...
;Absolutní souřadnice regionu (ARC)
:D( S, E )
::D : číslo dokumentu
::S : počátečni pozice, E : koncová pozice v dokumentu
:výhody: pro dotazování
:nevýhody: aktualizace v listu znamená, že všechny následníky je třeba změnit také
:[[File:XML_indexing-ARC.PNG]]
;Relativní souřadnice regionu (RRC)
:RRC uzlu n v XML stromu: [ c1, c2 ]
::c1 : počet byte z počáteční pozice rodičovského uzlu k počáteční pozici n
::c2 : počet byte z počáteční pozice rodičovského uzlu ke koncové pozici uzlu n
:výhoda: aktualizace je menší oproti ARC
:[[File:XML_indexing-RRC2.PNG]]
;Dietzovo číslování
:Preorder průchod - potomci každého uzlu následují při preorder průchodu stromem za svým rodičovským uzlem
:Postorder průchod - každý uzel posloupnosti je uveden až za svými potomky
:Konstrukce číselného schématu
::každému uzlu v∈N přiřadíme dvojici (x,y) značící preorder resp. postorder pořadí
::uzel v∈N s ohodnocením L(v) = (x,y) je potomkem uzlu L(u) = (x',y') právě když x' < x & y' > y
:[[File:XML_indexing-Dietz.PNG]]
=== Podobnost XML dat ===
;Typ dat
:Podobnost dokumentů
:Podobnost schémat
:Podobnost dokumentů a schémat
==== Podobnost XML dokumentů ====
;Idea
:Vstup: Dokumenty D1 a D2
:Výstup: sim(D1, D2) ∈ [0,1]
:Přístupy:
:*Zjistíme jak složité je transformovat dokument D1 na D2
:**''Editační vzdálenost stromů'' T1 na T2
:*Definujeme reprezentaci D1 a D2, která umožní '''efektivní''' vyhodnocení podobnosti
:**Př. reprezentace ''množinou cest'', reprezentace ''signálem'', …
'''Editační vzdálenost'''
(pro stromy) minimální počet operací pro transformaci stromu T1 na strom T2
;Editační operace na XML stromech
:Insert - vloží uzel n na pozici danou rodičovským uzlem p a pořadím určujícím pozici v rámci podelementů p
:Delete - smaže listový uzel n
:Relabel - přeznačí uzel n
:InsertTree - vloží celý podstrom T na pozici danou rodičovským uzlem p a pořadím určujícím pozici v rámci podelementů p
:DeleteTree - celý podstrom T s kořenem n je smazán
Minimální editační vzdálenost se jaksi vyhodnocuje pomoci dynamickeho programovani
'''Tree Alignment'''
Obdoba editační vzdálenosti
Myšlenka: Pro stromy T1 a T2 vybudujeme tzv. alignment
*Do obou stromů vložíme uzly tak, aby výsledné stromy T1’ a T2’ měly stejnou strukturu (bez ohledu na označení), tj. pokud bychom je přiložili na sebe, překrývaly by se
;Postup:
:Vybudujeme alignment
:Každé dvojici překrývajících se uzlů přiřadíme skóre
:Vzdálenost stromů = součet skóre
Obe dve transformace dokumentu jsou NP-tezke (tipl bych si, ze jsou primo slabe NP-tezke)
:Hledání minimální editační vzdálenosti XML stromů je obecně NP-těžký problém
:Tree Alignment: pokud je stupeň stromu omezený, lze minimální vzdálenost nalézt v polynomiálním čase, jinak je to NP-těžký problém.
'''Reprezentace množinami cest'''
Myšlenka: XML strom = množina cest
Které cesty budeme brát?
:Všechny různé cesty z kořene do listu
:Všechny různé cesty z kořene do listu a všechny jejich pod-cesty
:Všechny různé cesty z kořene do listu a všechny jejich pod-cesty + informace o četnosti
Problém podobnosti stromů se redukuje na určení velikosti průniku množin cest
Poznámka: Přístup ignoruje uspořádání
'''Signál XML dokumentu'''
Myšlenka: XML dokument reprezentujeme jako signál (impuls = počáteční/koncový tag)
Problém podobnosti XML dokumentů jsme převedli na problém podobnosti signálů
;Postup
:Signály jsou periodicky zopakovány (asi aby byly stejne dlouhe)
:Je na ně aplikována diskrétní Fourierova transformace
:Výsledek je lineárně interpolován
==== Podobnost XML dokumentů a schémat ====
Problém: Chceme porovnat podobnost XML dokumentu D (stromu) a XML schématu S (množina regulárních výrazů)
Možná myšlenka: z dokumentů odvodíme schéma a porovnáme schémata (prozatím se nevyužívá a potřebovali bychom hodně dokumentů)
Existující přístupy:
*Metoda měřící počet elementů, které se vyskytují v D, ale ne v S a naopak
*Metoda, měřící nejkratší vzdálenost mezi D a „všemi“ dokumenty validními vůči S
==== Podobnost XML schémat ====
Problém: podobnost regulární výrazů, resp. gramatik
Typické použití je integrace XML schémat - několik systémů poskytuje stejná (podobná) data v různých formátech → chceme sjednotit do společného
schématu (XML Schema, relační, objektové, …)
;Obecná myšlenka:
:Definujeme množinu pomocných podobnostních funkcí (matchers), kde každá vyhodnocuje podobnost určité charakteristiky (např. podobnost listů, podobnost jmen kořenových elementů, podobnost kontextu, …)
:Výsledky podobnostních funkcí jsou (váženě) agregovány do výsledné podobnosti
Poznámka: Velké množství metod využívá strojové učení (např. pro nastavení vah, pro vyhodnocování, …)
Algoritmy:
:Cupid - dvě fáze vyhodnocování (lingvistická a strukturální)
:COMA - kombinace velké množiny matcherů s uživatelskou interakcí
Matching velkých schémat
:Problém: U velkých schémat nechceme matchovat každý uzel s každým
:Myšlenka: Dekomponujeme problém do menších a jejich výsledky sloučíme
==== XML a webové služby ====
* http://cs.wikipedia.org/wiki/Webov%C3%A1_slu%C5%BEba
* http://cs.wikipedia.org/wiki/SOAP
* http://cs.wikipedia.org/wiki/Web_Services_Description_Language
== Datový model RDF, dotazovací jazyk SPARQL ==
===RDF===
RDF (Resource Description Framework) Dátový model tvorený orientovaným grafom ( bez násobných hrán)- prostředí na popis (webovských) zdrojů<br />
Rozlišujeme Zdroj, Prázdny uzol a literál ( Dátová hodnota ktorá nie je zdroj , môže mat dátový typ )<br />
RDF graf je možné reprezentovať : Množinou, Graficky, Slovami v abecede, Gramatikom , najčastejšie sa používa zoznam trojíc ('''s'''ubject,'''p'''redicate,'''o'''bject)<br />
Forma zápisu je N3 notácia, zložitý formalizmus alebo používanejšia Turtle:
* Turtle : URI ( jedinečná identifikácia ) v hranatých zátvorkách , forma prefixovej skratky
* Literály v úvodzovkách
* Trojice uzatvorené bodkou
* Mezery, eol, … se ignorují
* Opakujúce hodnoty môžeme vynechať, oddeľovať nie . ale ;
* Viac trojíc s rovnakým subjekt a predicate oddeľovať objekty ,
* Môžeme redukovať uzly na prázdne uzly , takýto uzol má lokálne meno ale nemá ur<br />
<br />
<br />
ex:index.html dc:creator ex:staffid/85740<br />
ex:staffid/85740 ex:maJmeno “John Smith” <br />
<br />
(Prázdne uzly)<br />
exstaff:85740 exterms:address ??? . <br />
??? exterms:street "1501 Grant Avenue" . <br />
??? exterms:city "Bedford" . <br />
<br />
RDF informuje o typoch , tz tvrdenia o tvrdeni <br />
exproducts:triple123 rdf:type rdf:Statement . <br />
exproducts:triple123 rdf:subject ex:index.html . <br />
===SPARQL===
Dotazovanie nad RDF datami. Hladaju sa zdroje s istymi vlastnostami . Sytax velmi podobna ako v SQL
<br />
SELECT ?(čo) <br />
WHERE { predikat, trojica splnajuca vlastno ?(čo) má vlastnosť. }
<br />
Construct: vratia RDF graf tvoreny substituciou za premene <br />
ASK: Vracia true/false ak bol vzor najdeny alebo nie <br />
DESCRIBE : Vracia RDF graf, ktory popisuje najdene zdroje <br />
OPTIONAL : Prida dodatocnu informaciu ale nefailne ked nenajde vhodne.
<br />
Data
<br />
_:a foaf:name "Alice" .
_:a foaf:knows _:b .
_:a foaf:knows _:c .
_:b foaf:name "Bob" .
_:c foaf:name "Clare" .
_:c foaf:nick "CT" .
<br />
Dotazy
<br />
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?nameX ?nameY ?nickY
WHERE { ?x foaf:knows ?y ;
foaf:name ?nameX .
?y foaf:name ?nameY .
OPTIONAL { ?y foaf:nick ?nickY } }
Vysledok
<br/>
?nameX
?nameY
?nickY
„Alice“
„Bob“
To není NULL
{| class="wikitable"
|-
! ?nameX !! ?nameY !! ?nickY
|-
| Text buňky || Text buňky || Text buňky
|-
| Alice|| Bob|| Prazdny vysledok, nieje to null
|-
| Alice || Clare || CT
|}
Pekne jednoduche dotazy [https://jena.apache.org/tutorials/sparql.html]
== Podobnostní dotazy v multimediálních databázích, metrické indexacní metody. (nové od 2011) (🎓🎓)==
{{TODO|ořezat je toho moc, nechat jen důležité}}
===Podobnostní dotazy v multimediálních databázích===
====Používané modely pro podobnost v mm.db====
'''Funkce podobnosti''' <math>δ: U \times U \rightarrow R</math> - libovolná fce vracející pro 2 dekriptory z univerza podobnostní skóre
'''Modely pro podobnost (tj. topologické vlastnosti):'''
* '''metrické''' - axiomy:
:* <math>δ(x, y) = 0 ⇔ x = y</math> (identita)
:* <math>δ(x, y) ≥ 0 ⇔ x ≠ y</math> (nezápornost)
:* <math>δ(x, y) = δ(y, x)</math> (symetrie)
:* <math>δ(x, y) + δ(y, z) ≥ δ(x, z)</math> (Δ nerovnost)
* '''nemetrické''' - dovolují modelovat robustnější podobnosti (na rozdíl od metrických) - 💡 např.ignorování šumu, blbě se indexují
====Dotazy v mm.db====
; základní
* 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
==== Podobnosti (vzdálenosti) v mm.db ====
'''úvod - kam dát logiku?'''
:* high-level deskriptory + jednodušší vzdálenost
::* feature extraction does most of the logic
::* assumed canonized representation of features is possible
::* cheaper similarity
:* low-level deskriptory + složitější vzdálenost
::* similarity aggregates relevant information at query time, i.e., information that cannot be extracted beforehand
::* more flexible but more expensive similarity
'''vektorové'''
* independent dimensions
::* '''Lp (Minkowského) vzdálenosti''' - je třída vekt. vzdáleností uvažujících nezávislé dimenze
::: [[File:MM DB 6250395489241108110.png|300px]]
:::* 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
:: [[File:MM DB 954379289549314657.png|300px]]
::* 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
::: [[File:MM DB 6351594138144169526.png|300px]]
::* 💡 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
:: [[File:MM DB 2027159719468114462.png|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
::: [[File:MM DB 573347960994207990.png|300px]]
::* složitost <math>O(mn)*O(ground~ dist.)</math> (metrická)
* signatures
:* '''SQFD''' (Signature Quadratic Form Distance) - signatura vlastnosti, množina vážených reprezentantů (např centroidy + poloměr)
:: generalizace QFD pro signatury
===Metrické indexování===
====metrický model podobnostního vyhledávání====
- založen na univerzu (množině) deskriptorů a metrické vzdálenosti sloužící jako podobnost na deskriptorech
- 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|right|thumb|261px|'''gh-strom''' - vyber 2 pivoty (např nejvzdálenější prvky) a rozděl db na dvě partišny nadrovinou podle vzdáleností, rekurzivně pokračuj]]
:* 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)
:::: [[File:MM DB 5136080282252636911.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 (<u>vzhledem k alespoň jedné partišně</u> O1, O3, O4), pak neprojdeme podstrom
:::: [[File:MM DB 4281588065894422188.png]]
:* '''(m)vp-tree''' ((multiple) vantage-point tree) - n-ární strom (💡 vantage point = pivot)
::*může být vyvážený
::*'''konstrukce''' - rozdělení prostoru soustřednými kruhy, poloměry = otcovské uzly
[[File:MM DB 337053922425371269.png]] [[File:MM DB 7168374847899962646.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|right|thumb|400px|'''PM-tree''' - obohacuje M-tree '''o p globálních pivotů''']]
::*využívá '''hierarchické hnízdění''' metrických regionů a je vyvážený
::: [[File:MM DB 2115865289095682470.png| 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 DB 6151133926930239281.png|right|thumb|400px|'''D-Index''' - hashované regiony jsou organizované do přihrádek na disku]]
:::* 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
:* bezindexové MAM
::* '''D-File'''
:::* just the original database using sequential scan, BUT it uses D-cache
:::* každá spočítaná vzdálenost se uloží do D-cache
:::* D-chache se používá pro výpočet dolního odhadu (jako dyn.pivoty)
:* výkon
::* realtime, distance computations, I/O, etc.
::* '''základní jednotka nákladů''' (v metr. indexování)
:::* počet výpočtů vzdáleností metriky
:::* místo metrické vzdálenosti se používá levnější spodní odhad (lower-bound)
::* '''Retrieval efficiency'''
:::* efektivita vyhledávače ve smyslu rychlosti vyhledávání
{{collapse|Unifikovaný model|2=
chceme využít výhod metrického i nemetrického modelu
{{TODO|jaky presne? (zacatek 13)}}
: nemetrický → metrický (převod)
:* δ(x, y) = 0 ⇔ x = y (identita)
::* δI(x,y) = δ(x,y) + e ⇔ x ≠ y
::* δI(x,y) = 0 ⇔ x = y
:* δ(x, y) ≥ 0 ⇔ x ≠ y (nezápornost)
::* δN(*,*) = δ(*,*) – d–
:* δ(x, y) = δ(y, x) (symetrie)
::* pomocí horního odhadu δS(x,y) = max(δ(x,y), δ(y,x))
::* výsledek projdi originální (asym.) vzdáleností
:* δ(x, y) + δ(y, z) ≥ δ(x, z) (Δ nerovnost)
::* potřebujeme '''SP-modifikátor'''
[[Image:MM DB 9003407825653614829.png|right|thumb|400px|'''TG-modifikátor''' příklad]]
:::* rostoucí funkce: f: R → R, že f(0)=0
:::* δ^f(O1,O2) = f(δ(O1,O2))
::* vlastnosti SP-m.
:::* zachovává pořadí
:::* zachovává výsledky range query
:::* zachovává výsledky kNN
:* '''T-chyba''' - proporce trojic v datové sadě porušujících trojúhelníkovou nerovnost (T-error)
:* '''SP-modifikátory''' (Similarity Preserving)
::* '''TG-modifikátor''' Triangle Generating
:::* striktně konkávní SP modifikátor, což zajišťuje nízkou hodnotu T-chyby (T-error)
:::* 💡 TG-m. ale také zvyšuje vnitřní dimenzi → snižuje indexovatelnost
:::* v praxi musíme najít nejméně konkávní TG-m. stále zajíšťující Δ nerovnost
::* '''TV-modifikátor'''
[[Image:MM DB 3258089576234140659.png|right|thumb|400px|'''TV-modifikátor''' příklad]]
:::* striktně konvexní SP modifikátor, což zajišťuje vyšší hodnotu T-chyby (T-error)
:::* 💡 TV-m. ale také snižuje vnitřní dimenzi → zvyšuje indexovatelnost
:::* někdy s nimi dosáhneme lepší indexovatelnosti s 0 T-chybou
::* '''T-base'''
:::* f(x,w) = generalizace TG- and TV- modifikátorů
:::* w > 0 – TG-modifier, w < 0 – TV-modifier
: '''TriGen algoritmus''' automatické gen. Δ nerovnosti
:* test identity (w=0)
::* T-chyba je pod tolerancí → hledáme TV-modifikátory (w<0)
::* jinak → TG-modifikátory (w>0)
:* ∀ T-base najdeme optimalní váhu w půlením/dvojnásobením intervalu (držíme T-error pod toterancí)
:* skončíme po fixním počtu iterací
:* z množiny kandidátů modifikátorů (T-base + váha) vybereme ten s nejmenší vnitřní dimenzí
: '''NM-tree''' Nonmetric M-tree
:* NMAM pro flexibilní podobnostní dotazování
:* pomocí TriGen, najdi T-modifikátory pro různé chybové prahy (včetně nulové chyby)
:* postavíme M-tree pomocí zero-error modified semimetric (i.e., using full metric)
:* tolerance T-chyby je parametr pro query
:* a single NM-tree performs as fast at multiple M-trees, each created for a single search approximation level (T-error threshold)
}}
{{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]]
}}
