K^2-Treaps: Range Top-k Queries in Compact Space

Nieves Brisaboa, Guillermo de Bernardo, Roberto Konow, and Gonzalo Navarro

Efficient processing of top-k queries on multidimensional grids is a common requirement in information retrieval and data mining, for example in OLAP cubes. We introduce a data structure, the K^2-treap, that represents grids in compact form and supports efficient prioritized range queries. We compare the K^2-treap with state-of-the-art solutions on synthetic and real-world datasets, showing that it uses 30% of the space of competing solutions while solving queries up to 10 times faster.