velikost textu

Preference Top-k Search Based on Multidimensional B-tree

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Preference Top-k Search Based on Multidimensional B-tree
Název v češtině:
Preferenčné vyhľadávanie založené na viacrozmernom B-strome
Typ:
Disertační práce
Autor:
RNDr. Matúš Ondreička, Ph.D.
Školitel:
prof. RNDr. Jaroslav Pokorný, CSc.
Oponenti:
Prof. Dr. Martin Theobald
RNDr. Peter Gurský, Ph.D.
Id práce:
60121
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra softwarového inženýrství (32-KSI)
Program studia:
Informatika (P1801)
Obor studia:
Softwarové systémy (4I2)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
10. 6. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
top-k vyhladávanie, viacrozmerný B-strom, používatelské preferencie, nemonotónne ohodnocovanie, MD algoritmus, MXT algoritmus.
Klíčová slova v angličtině:
top-k search, multidimensional B-tree, user preferences, non-monotone ranking, MD algorithm, MXT algorithm.
Abstrakt:
Názov: Prefernčné top-k vyhľadávanie založené na viacrozmernom B-strome Autor: RNDr. Matúš Ondreička Katedra: Katedra softwarového inženýrství Matematicko-fyzikální fakulta Univerzita Karlova v Praze Školiteľ: Prof. RNDr. Jaroslav Pokorný, CSc. Email autora: ondreicka@ksi.mff.cuni.cz Email školiteľa: pokorny@ksi.mff.cuni.cz Abstrakt: V tejto práci sa zameriavame na top-k vyhľadávanie podľa použí- vateľských preferencií s použitím B+-stromov a viacrozmerného B-stromu (MDB-strom). Používame model používateľských preferencií založený na fuzzy funkciách, ktorý nám umožňuje vyhľadávať podľa nemonotónnej ohod- nocovacej funkcie. Navrhujeme model zotriedeného zoznamu založený na B+-strome, ktorý umožní faginovym algoritmom vyhľadávať k najlepších ob- jektov podľa nemonotónnej ohodnocovanej funkcie. Tento model používame v prostredí internetu s dátami na rôznych vzdialených serveroch. Okrem toho sme navrhli nové dynamické stromové štruktúry, konkrétne MDB-strom zložený z B+-stromov, MDB-strom so zoznamami, MDB-strom so skupinami B+-stromov a viacnásobne zoradený MDB-strom. Súčasne sme vyvinuli nové top-k algoritmy, konkrétne MD algoritmus, MXT algoritmus a ich varianty, ktoré dokážu vyhľadávať k najlepších objektov podľa nemonotónnej ohodno- covacej funkcie. Tieto top-k algoritmy sú efektívne, pretože dokážu nájsť k najlepších objektov bez potreby získania väčšiny objektov, ktoré sú uložené v navrhovaných stromových dátových štruktúrach. Kľúcové slová: top-k vyhľadávanie, viacrozmerný B-strom, používateľské preferencie, nemonotónne ohodnocovanie, MD algoritmus, MXT algoritmus. 1
Abstract v angličtině:
Title: Preference Top-k Search Based on Multidimensional B-Tree Author: RNDr. Matúš Ondreička Department: Department of Software Engineering Faculty of Mathematics and Physics Charles University in Prague Supervisor: Prof. RNDr. Jaroslav Pokorný, CSc. Author’s e-mail address: ondreicka@ksi.mff.cuni.cz Supervisor’s e-mail address: pokorny@ksi.mff.cuni.cz Abstract: In this thesis, we focus on the top-k search according to user pref- erences by using B+-trees and the multidimensional B-tree (MDB-tree). We use model of user preferences based on fuzzy functions, which enable us to search according to a non-monotone ranking function. We propose model of sorted list based on the B+-tree, which enables Fagin’s algorithms to search for the top-k objects according to a non-monotone ranking function. We apply this model in the Internet environment with data on different remote servers. Furthermore, we designed novel dynamic tree-based data structures, namely, MDB-tree composed of B+-trees, MDB-tree with lists, MDB-tree with groups of B+-trees and multiple-ordered MDB-tree. Concurrently, we have developed novel top-k algorithms, namely, the MD algorithm, the MXT algorithm and their variants which are able search for the top-k objects ac- cording to a non-monotone ranking function. These top-k algorithms are efficient because they are able to find the top-k objects without the need to obtain the majority of the objects stored in the designed tree-based data structures. Keywords: top-k search, multidimensional B-tree, user preferences, non- monotone ranking, MD algorithm, MXT algorithm. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Matúš Ondreička, Ph.D. 3.22 MB
Stáhnout Abstrakt v českém jazyce RNDr. Matúš Ondreička, Ph.D. 57 kB
Stáhnout Abstrakt anglicky RNDr. Matúš Ondreička, Ph.D. 56 kB
Stáhnout Posudek vedoucího prof. RNDr. Jaroslav Pokorný, CSc. 107 kB
Stáhnout Posudek oponenta Prof. Dr. Martin Theobald 320 kB
Stáhnout Posudek oponenta RNDr. Peter Gurský, Ph.D. 301 kB
Stáhnout Záznam o průběhu obhajoby 134 kB