Original title:
Preferenčné vyhľadávanie založené na viacrozmernom B-strome
Translated title:
Preference Top-k Search Based on Multidimensional B-tree
Authors:
Ondreička, Matúš ; Pokorný, Jaroslav (advisor) ; Theobald, Martin (referee) ; Gurský, Peter (referee) Document type: Doctoral theses
Year:
2013
Language:
eng Abstract:
[eng][cze] 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...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...
Keywords:
MD algorithm; multidimensional B-tree; MXT algorithm; non-monotone ranking; top-k search; user preferences; MD algoritmus; MXT algoritmus; nemonotónne ohodnocovanie; používatelské preferencie; top-k vyhladávanie; viacrozmerný B-strom
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/60005