ETD system

Electronic theses and dissertations repository

 

Tesi etd-10182008-074928


Thesis type
Tesi di dottorato di ricerca
Author
BIALYNICKA BIRULA, IWONA
URN
etd-10182008-074928
Title
Ranked Queries in Index Data Structures
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Commissione
Relatore Prof. Grossi, Roberto
Parole chiave
  • Nessuna parola chiave trovata
Data inizio appello
15/12/2008;
Consultabilità
completa
Riassunto analitico
A ranked query is a query which returns the top-ranking elements of a set, sorted by rank, where the rank corresponds to some sort of preference function defined on the items of the set. This thesis investigates the problem of adding rank query capabilities to several index data structures on top of their existing functionality. First, we introduce the concept of rank-sensitive data structures, based on the existing concept of output-sensitive data structures. Rank-sensitive data structures are output-sensitive data structures which are additionally given a ranking of the items stored and as a result of a query return only the k best-ranking items satisfying the given query, sorted according to rank, where k is specified at query time. We explore several ways of adding rank-sensitivity to different data structures and the different trade-offs which this incurs. The second part of the work deals with the first efficient dynamic version of the Cartesian tree – a data structure intrinsically related to rank queries.
File