Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    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 rend az adott szak honlapján és képzési programjában található.

    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