Spatial databases - their purpose, differences to relational db; rd-trees, space representations, data structures for storing point objects, data structures usable also for more complex objects, spatial join. Textual databases - inverted file, lemmatization; Term count reduction, Zipf's law; signature methods. Data compression - purpose, basic notions, integer coding, symbol coding methods, basic dictionary methods, index compression and compaction. Semistructured document indexing. Web indexing. Object persistency.
Last update: G_I (16.03.2011)
Prostorové databáze. Hledání v textových kolekcích. Možnosti redukce lemmat, Zipfův zákon, signaturové metody.
Komprese dat. Indexace semistrukturovaných dokumentů. Persistence objektů.
Předpokládají se znalosti v rozsahu bakalářského kursu NDBI007 Organizace a zpracování dat I.
Literature - Czech
Last update: T_KSI (15.04.2003)
Pokorný, J.: Základy implementace souborů a databází. Skripta UK, Vydavatelství Karolinum, 1997.
Pokorný, J., Žemlička, M.: Základy implementace souborů a databází. Skripta UK, Vydavatelství Karolinum, 2003. 2. uprav. vydání.
Syllabus -
Last update: T_KSI (15.04.2003)
1. Spatial databases - services, differences to relational db; rd-trees, space representations (naive, spiral, z-ordering; path and width ordering).
2. Spatial databases - data structures for storing point objects (B-cubes, k-d-trees, buddy-trees).
3. Spatial databases - data structures usable also for more complex objects (R-trees, R*-trees).
4. Spatial databases - spatial join.
5. Textual databases - introduction: inverted file, lemmatization - what is it and trivial implementation; Term count reduction, Zipf's law.
6. Text databases - signature methods (document signature and query signature, superimposed coding, S-trees, multilevel signatures).
7. Data compression - purpose, basic notions, integer coding.
8. Data compression - symbol coding methods (Shannon-Fano, Huffman, arithmetic coding).
9. Data compression - basic dictionary methods 1 (LZ77,LZ78).
10. Data compression - basic dictionary methods 2 (LZW,BSTW), compression and compaction of indexes.
11. Semistructured document indexing.
12. Web indexing.
13. Object persistency.
Last update: T_KSI (15.04.2003)
1. Prostorové databáze - k čemu slouží, čím se liší od relačních db; rd-stromy, reprezentace prostoru (naivní, spirálovité, z-uspořádání; uspořádání cestou a do šířky).
2. Prostorové databáze - datové struktury určené pro primárně pro body (B-kostky, k-d-stromy, buddy-stromy).
3. Prostorové databáze - datové struktury využitelné i pro komplexní objekty (R-stromy, R*-stromy).
4. Prostorové databáze - prostorová spojení.
5. Hledání v textových kolekcích - úvod: invertovaný soubor, co je to lemmatizace a jak fungují triviální implementace; Možnosti redukce lemmat, Zipfův zákon.
6. Hledání v textových kolekcích - signaturové metody (signatura dotazu a dokumentu, vrstvené signatury, S-stromy, víceúrovňové signatury).
7. Komprese dat - k čemu slouží, základní pojmy, kódování přirozených čísel.
8. Komprese dat - metody kódující symboly (Shannon-Fano, Huffman, aritmetické kódování).
9. Komprese dat - základní slovníkové metody 1 (LZ77,LZ78).
10. Komprese dat - základní slovníkové metody 2 (LZW,BSTW), komprese a kompakce indexů.
