Original title:
Eliptické indexování vícerozměrných dat
Translated title:
Eliptic indexing of multidimensional databases
Authors:
Danko, Ondrej ; Hoksza, David (referee) ; Skopal, Tomáš (advisor) Document type: Master’s theses
Year:
2008
Language:
eng Abstract:
[eng][cze] In this work variation of R-tree, which hierarchically partition indexed space using minimum volume covering ellipsoids (MVCE) instead of usually used minimum bounding rectangles, is presented. Main aspects, which determine R-tree index structure performance, are studied from the available resources at the beginning. Base on this studies "e-Rtree" (ellipsoid R-tree) is designed. Afterward algorithms of MVCE construction are carefully analyzed, as the choice of the algorithm is crucial for the efficiency of indexing and retrieval. At the end of the work, eR-tree implementation over ATOM framework is presented along with experiments done on synthetic and real data sets.V tejto práci je diskutovaná variácia R-stromu, ktorá k hierarchickému deleniu indexovaného priestoru využíva namiesto bežne používaných minimálne ohraničujúcich obdlžnikov minimálne ohraničujúce ellipsoidy (MVCE). V úvode práce sú zosumarizované hlavné faktory ovplyvňujúce výkon Rstromových štruktúr z dostupných štúdií, čo vedie k niekolkým variantá"eR-stromu" (ellipsoid R-tree). Následne sú rozobrané známe algoritmy konštrukcie ellipsoidov. Výber vhodnej metódy konštrukcie MVCE je jedným z klúčových faktorov ovplyvňujúcich efektivitu indexácie a následného vyhladávania. V závere práce je prezentovaná experimentálna implementácia eRstromu nad frameworkom ATOM. Výhodnost použitia MVCE v R-strome je prezentovaná experimentami jak nad syntetickými datami, tak nad reálnymi.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/14850