logo SBA

ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-10182008-074928


Thesis type
Tesi di dottorato di ricerca
Author
BIALYNICKA BIRULA, IWONA
URN
etd-10182008-074928
Thesis title
Ranked Queries in Index Data Structures
Academic discipline
INF/01
Course of study
INFORMATICA
Supervisors
Relatore Prof. Grossi, Roberto
Keywords
  • Nessuna parola chiave trovata
Graduation session start date
15/12/2008
Availability
Full
Summary
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