2012.04.17.
1
2
Hátralevı órák 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
A negyedik paradigma Amdahl-törvénye és az Amdahl-szám x64 alapú nagyteljesítményű hardverek Adattároló rendszerek Hálózatok Relációs adatbázis-kezelők Adatok tárolása adatbázis szerverekben Indexek Tranzakciók Biztonsági mentés, replikáció Alapvető fizikai operátorok Lekérdezés optimalizálás Adatbetöltés Metaadatok Többdimenziós adatok kezelése A gömbfelszín indexelése Adatbázisok particionálása, adatbázisklaszterek Különböző adatmodellek relációs leképezése Nem strukturált adatok kezelése Oszlop alapú adatbázisok Tömb alapú adatbázisok
• április 17. • április 24. • május 1. • május 08. • május 15.
Többdimenziós adatbázisok • Háromdimenziós tér euklideszi metrikával • Magasabb dimenziós terek ▫ fázistér (hely, impulzus) ▫ paraméterterek (pl. galaxisok színe 5 szűrőben)
Néhány fontos probléma • Pontok megtalálása egy adott tartományban ▫ A tartományt valamilyen módon analitikusan adjuk meg
• Legközelebbi szomszédos pontok megtalálása (k nearest-neighbor search) ▫ Klasztereződés kereséséhez ▫ Adatok osztályozására (tanulás) ▫ Nem-paraméteres becslésekhez (regresszió)
• Gömb felszíne – Föld / ég koordinátázása ▫ Polár koordinátákkal ▫ 3D egységvektorokkal ▫ (GIS = geographic information system)
• Ajánlott könyv: Hanan Samet: Foundations of Multidimensional and Metric Data Structures, Morgan-Kaufmann • Ábrák forrása: wikipedia.org
Relációs adatbázis-kezelık alkalmazása kD adatbázisokhoz • Hátrányok: ▫ Háttértár egy dimenziós (fizikailag, címzésileg) ▫ Indexek egy dimenziós adatokra optimalizáltak
• Előnyök: ▫ Optimalizált lemez és memória kezelés ▫ Párhuzamos végrehajtás
• Feladat: ▫ A többdimenziós adatstruktúrát valamilyen módon egydimenziós sokaságra kell vetíteni ▫ A síkot/teret/hiperteret cellákra osztjuk, a cellákhoz számokat rendelünk, a számokra indexet építünk
• • • • • • •
Pontsűrűség becslése (density estimators) Klaszterek megtalálása Trajektóriák megtalálása Kilógó pontok megtalálása (outlier detection) Hisztogramok gyors generálása Párkorrelációs függvény meghatározása Interaktív vizualizáció támogatása
k dimenziós térbeli indexek • Spatial Index • Adatpontok k koordinátával • Gyakran tartozik hozzájuk hiba (szétkent pontok) • Euklideszi metrika ▫ Dimenziónként lehet más a metrika skála ▫ Érdemes a metrikát a hibával skálázni
• Eljárás: ▫ A k dimenziós teret téglatest alakú cellákra osztjuk ▫ A cellákhoz számértéket rendelünk ▫ Az adatpontokat a cellákhoz rendeljük, és a cella számával felcímkézzük ▫ A cellacímkére indexet építünk, amit kereséskor fel tudunk használni: intervallum keresések lesznek (range queries)
1
2012.04.17.
Rács • A k dimenziós teret berácsozzuk • A rács szabályos k-dimenziós téglatestekből áll • Dimenziónként lehet más a téglalapok élhossza • Előnyök: ▫ A szerkezet előre definiált, a cellák koordinátái könnyen számolhatók ▫ A szomszédos cellák nagyon könnyen meghatározhatóak, de a címkéjük függ a bejárási módszertől
• Hátrányok: ▫ Magasabb dimenzióban nagyon nagy lesz a cellák száma ▫ Nem egyenletes eloszlású pontoknál sok üres vagy túl tömött cella lesz
• Rácscellák bejárása adja a számértékeket
Rács bejárása Cantor-módszerrel • Pl. Cantor-féle mellékátlós módszer • Egymáshoz közeli cellákhoz távoli számot rendel (nem lokális) • Túl bonyolult formula a számérték meghatározása • A bináris alaknak nincsen köze a struktúrához, a bitek nem jelentenek semmit • Nem túl jó
▫ Többféle bejárási algoritmus létezik ▫ Ezek többnyire rekurzív algoritmusok
Z-rendezés
Z-rendezés bit értékei
• Jó lokalitás (közeli cellákhoz közeli számértéket rendel) • A bináris reprezentáció jól értelmezhető, a biteknek van jelentésük • Tulajdonképpen ez lesz a Quad-tree (négyes-fa) • Az egyik legelterjedtebb módszer
Peano—Hilbert-görbe • A z-rendezésnél jobb lokalitási tulajdonság • Bonyolultabb a kiszámítása, mint a z-rendezésé • Bináris reprezentációban a bitek jelentése nem annyira egyértelmű
• Ez egy egydimenziós sokaság, a hossza exponenciálisan nő az iterációkkal, határértékben a dimenziója 2 (térkitöltő görbe)
Quad-tree • 2-dimenziós adatokhoz • Minden cella négy felé oszlik, ebből épül fel egy fa • A koordináták és a címkék könnyen meghatározhatók • A bináris reprezentációnak egyértelmű jelentése van, azonos a z-rendezéssel • A felépített fa nem kiegyenlített • Klasztereződve elrendeződő pontokhoz nem ideális
2
2012.04.17.
Octree • Az ötlet ugyanaz, mint a Quad-fánál, de itt 3 dimenziós teret indexelünk
Voronoi-cellázás • Meghatározzuk a ponthalmaz egy részhalmazának Voronoidiagramját • A többi pontot is ehhez a diagramhoz rendeljük • Lehetséges hierarchikus változatban is • Lokális sűrűség becslésre, vizualizációra jó • Bonyolultsága miatt egyébként problémás • Magasabb dimenzióban problémás • Pont cellájának megtalálása: pl. bolyongással a Delaunayháromszögelés szerint • Kód a generáláshoz: QHull
Voronoi és Delaunay
kd-fa • Eljárás: ▫ Az első dimenzió szerint megkeressük a mediánt ▫ Egy félsíkkal elvágjuk a teret ▫ Megismételjük a további dimenziókra
• A mediánt lehet közelíteni (pl. átlaggal) • Magasabb dimenziókban is jó • Tárolni kell a cellák koordinátáit • A cellák bináris azonosítójának bitjei követik a fa struktúráját
Térbeli keresések • Akkor hatékony, ha sokkal több pont van, mint cella • Először megnézzük, hogy a cella maga megfelel-e a keresési feltételnek, három lehetőség: ▫ A keresési feltételen kívül van: eldobjuk a cellát ▫ A keresési feltételen belül van: az összes pont jó eredmény ▫ A keresési feltétellel átmetsz: a cella pontjait muszáj egyenként megvizsgálni
k legközelebbi szomszéd • A legközelebbi szomszédok megkereséséhez az itt ismertetett térbeli indexeket használjuk • A legközelebbi pont mindig lehet az aktuális cellában, vagy valamelyik szomszédos cellában • Magas dimenzióban nagyon sok szomszédos cella lehet, ilyenkor csak sok pont esetén éri meg az egész cellázás (N > 2D) • A keresett pont távolságát nem kell minden egyes ponttól kiszámítani, csak az aktuális és a környező cellákban levő pontoktól
3
2012.04.17.
Klaszterek keresése • Nagy sűrűségű területeket keresünk, amik össze tartoznak • Friend-of-friend algoritmus ▫ Két pont „barát”, ha egymás legközelebbi szomszédjai, és távolságuk legfeljebb x ▫ Minden pont része a klaszternek, amelyik a klaszter bármelyik elemének „barátja” ▫ x megválasztásával lehet az algoritmust finomhangolni ▫ Többszörös szomszédság is megkövetelhető
• Felhasználás: ▫ Adatok automatikus klasszifikálása ▫ Statisztikus fizikai szimulációk ▫ Galaxisklaszterek keresése
Nem-parametrikus becslés • Folyamatos eloszlású paraméterek esetén • Megkeressük a vizsgált pont tanító halmazbeli legközelebbi szomszédjait • A szomszédok paraméter értékei között valamilyen módon interpolálunk, a távolságot is figyelembe véve • Azért nem paraméteres becslés a módszer neve, mert nincsen előzetes feltevésünk arról, hogy a keresett érték valamilyen paraméterektől függene. Pusztán a tanító halmazbeli eloszlástól függenek a becsült értékek.
Korrelációs függvény • Statisztikus fizikában, kozmológiában alapvető fontosságú • N-pont korrelációs függvény: ▫ Mi két pont távolságának az eloszlás-függvénye? g(r) ▫ Mi egy háromszög létezésének eloszlása ▫ stb.
• Alapesetben minden pontot minden másikkal össze kell hasonlítani és kiszámolni a távolságot • Jelentősen lehet gyorsítani kd-fa segítségével • Két előre kiszámolt adat kell: ▫ Pontok száma a cellában ▫ Cella legkisebb befoglaló gömbje (középpont, sugár)
Adatok osztályozása • Előre osztályozott adatok egy halmaza: tanító halmaz (training set) • A vizsgálandó pontokat a tanító halmazhoz hasonlítjuk, megnézzük • Megnézzük, hogy a tanító halmaz melyik osztályához (klaszteréhez) esik legközelebb • Diszkrét értékű osztályok esetében abba az osztályba tesszük, amelyikbe a legtöbb k legközelebbi szomszéd tartozik
Hisztogram számolás • A hisztogram számolása általában az összes pont becellázását igényli, de ▫ Sokszor közelítő érték is elegendő ▫ Igazából csak a pontsűrűséget kell nézni egy adott tér cellában
• A cellákhoz előre kiszámítjuk az alapvető statisztikai mutatókat (pontok száma, cella térfogat, szórás a cellában stb.) • Elegendő az index cellák és a hisztogram cellák metszetét meghatározni • Sokszor ez gyorsabb, mint elölről számolni a statisztikát
Többszintő vizualizáció • Nagyszámú pont esetén egyszerre nem lehet az összes pontot kitenni a képernyőre • Azt szeretnénk, ha interaktívan lehetne a ponthalmaz egyes részleteire ráközelíteni • Nagy távolságra csak a sűrűséget kell érzékeltetni ▫ A cellákhoz kiszámolt sűrűséget jelenítjük meg, pl. az átlátszóságba kódolva
• Közelítve meg akarjuk jeleníteni az egyes pontokat is ▫ Kitesszük az egyes pontokat is a képernyőre, ha elég közel vagyunk a cellához
4
2012.04.17.
Adatok kondicionálása indexeléshez • Érdemes a cellákat minél inkább gömbszerűnek tartani ▫ Átlag levonása ▫ Tengelyenkénti normálás a szórással
• A k dimenziós adatok sokszor alacsonyabb dimenziójú sokaságok mentén helyezkednek el ▫ Főkomponens transzformáció ▫ Bonyolultabb, nem lineáris transzformációk
Fıkomponens transzformáció • A koordinátarendszer tengelyeit a legnagyobb szórású irányokba akarjuk beforgatni • Az adatpontokat mátrixba rendezve kiszámítjuk a kovariancia mátrixot: C=<XXT>-µµT • Megoldjuk a C mátrix sajátérték problémáját ▫ ▫ ▫ ▫
Ez a gyakorlatban az SVD algoritmussal történik Singular Value Decomposition A szinguláris érték a sajátérték általánosítása Az SVD numerikusan instabil mátrixok esetére is jó
• A kapott sajátvektorokkal az adatokat a főkomponens térbe transzformáljuk, a szórás a koordináta tengelyek irányába lesz a legnagyobb • Létezik iteratív közelítő algoritmus is: Budavári et al., 2008
5
