Ranked Queries in Index Data Structures

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.