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

Authors: Nieves, R. Brisaboa; Guillermo, de Bernardo; Roberto, Konow; Gonzalo, Navarro;
Year: 2014
Venue: 21th Int. Symp. on String Processing and Information Retrieval (SPIRE 2014) - LNCS 8799
Link: http://link.springer.com/chapter/10.1007%2F978-3-319-11918-2_21#page-1
Product of the Action: No

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.