|
Title |
K^2-Treaps: Range Top-k Queries in Compact Space |
|
Authors |
Nieves Brisaboa, Guillermo de Bernardo, Roberto Konow, Gonzalo Navarro |
|
Publication date |
2014 |
|
Abstract |
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. |
|
Downloaded |
4 times |
|
Pages |
215-226 |
|
Conference name |
International Symposium on String Processing and Information
Retrieval |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
PDF |
|
|
Reference URL |
|
