Nagyméretű adathalmazok kezelése

A tantárgy angol neve: Very Large Databases

Adatlap utolsó módosítása: 2009. október 26.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnök informatikus szak, MSc képzés
Számításelmélet szakirány


Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZM144 1 2/1/0/v 4  
3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
A tantárgy tanszéki weboldala http://www.cs.bme.hu/nagyadat/
4. A tantárgy előadója

Csima Judit Dr., egyetemi adjunktus

Katona Gyula Dr., egyetemi docens

Sali Attila Dr., egyetemi docens

 

5. A tantárgy az alábbi témakörök ismeretére épít Adatbázisok elmélete, gráfelmélet, alapvető algoritmikus technikák
6. Előtanulmányi rend
Kötelező:
NEM ( TárgyEredmény( "BMEVISZMA01" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA01", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

7. A tantárgy célkitűzése A tárgy célja a nagy adathalmazok esetében felmerülő különleges elméleti és gyakorlati problémák áttekintése. A hallgatók betekintést kapnak a témakör modern irányzataiba, az adatbányászat, relációs adatbázisok, nagy gráfok, adatfolyamok elméleti és gyakorlati kérdésibe.
8. A tantárgy részletes tematikája
  • Másodlagos tárolók használata, I/O modell, rendezés a másodlagos táron, trükkök a hozzáférés javítására
  • Többdimenziós indexek, térinformatikai rendszerek, hagyományos indexek használata ebben az esetben, hash-alapú módszerek és faszerű struktúrák többdimenziós adatokhoz
  • Lekérdezések végrehajtása nagy adathalmazok esetén, lekérdezésfeldolgozás alapjai, kifejezésfák, egymenetes algoritmusok, beágyazott ciklusú összekapcsolások, kétmenetes algoritmusok rendezéssel, index-alapú algoritmusok, többmenetes algoritmusok, párhuzamosság használata
  • Lekérdezésfordítás alapvető szabályai lekérdezéstervezéskor, műveletek költségbecslése, összekapcsolások sorrendjének kiválasztása
  • Gyakori minták kinyerése (gyakori elemhalmazok, sorozatok, epizódok, címkézett, gyökeres fák, feszített részgráfok, részgráfok keresése, APRIORI, Eclat, FP-growth algoritmusok különböző típusú mintákra való alkalmazása, kétfázisú algoritmusok, elemhalmazok lezártja, kényszerek kezelése), adatstruktúrák hatékony klaszterezéshez (kd-fa), döntési fák építése nagy adathalmazok esetén
  • Adatfolyamok, alapfogalmak, mintavételezés, véletlen vetületek, csoportos tesztelés, fa módszer
  • Véletlen gráfok modelljei (Rényi, Barabási-Albert), nagy véletlen gráfok tulajdonságai, fázisátmenet, lokális tulajdonságok, nagy komponens, Szemerédi lemmája és néhány alkalmazása, gráfpontok osztályozása, k-klikk perkoláció, webes keresés (Page rank, HITS módszer, SALSA módszer)
  • Függőségek elmélete: funkcionális, tartalmazási, összekapcsolási függőségek, axiomatizálásuk, az implikációs probléma, általános függőségek: egyenlőség generáló és sorgeneráló függőségek, kombinatorikus és komplexitási kérdések, magasabb rendű adatmodellek, az XML elmélete
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás + gyakorlat
10. Követelmények
  • szorgalmi időszakban: öt kiszárthelyi (10-15 perces) dolgozat a gyakorlatokon; az aláíráshoz ezekből legalább hármat megfelelt szinten kell teljesíteni
  • vizsgaidőszakban: szóbeli vizsga
11. Pótlási lehetőségek A kiszárthelyik pótlására nincs mód.
12. Konzultációs lehetőségek Előzetes egyeztetés szerint.
13. Jegyzet, tankönyv, felhasználható irodalom
  • Garcia-Molona, Ullman, Widom: Adatbázisrendszerek megvalósítása, Panem-John Wiley & Sons, (2001)
  • Dr. Bodon Ferenc: Adatbányászati algoritmusok, kézirat: http://www.cs.bme.hu/~bodon/magyar/adatbanyaszat/tanulmany/adatbanyaszat.pdf
  • Handbook of Large-Scale Random Networks, szerk.: Bollobás Béla, Kozma Róbert, Miklós Dezső. Springer-Verlag (2008)
  • S. Muthukrishnan: Data Streams: Algoritms and applications, http://www.cs.rutgers.edu/~muthu/stream-1-1.ps
  • B. Thalheim: Dependencies in Relational Databases. Teubner-Verlag, 1991.
  • S. Abiteboul, P. Buneman, D. Suciu: Data on the Web: From Relations
    to Semistructured Data and XML.
    Morgan Kaufmann Publishers, 2000.
  • S. Hartmann, S. Link, K.-D. Schewe: Functional dependencies over XML
    documents with DTDs
    . Acta Cybernetica 17, 1 (2005), 153–171.
14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra42
Félévközi készülés órákra30
Felkészülés zárthelyire 
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés48
Összesen120
15. A tantárgy tematikáját kidolgozta Katona Gyula Dr., egyetemi docens