Hashcube: A Data Structure for Space- and Query-Efficient Skycube Compression

TY - GEN

T1 - Hashcube

T2 - ACM International Conference on Conference on Information and Knowledge Management

AU - Bøgh, Kenneth Sejdenfaden

AU - Chester, Sean

AU - Sidlauskas, Darius

AU - Assent, Ira

N1 - Conference code: 23

PY - 2014/11

Y1 - 2014/11

N2 - The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. It is an expensive operator whose query performance can greatly benefit from materialization. However, a skyline can be executed over any subspace of dimensions, and the materialization of all subspace skylines, called the skycube, dramatically multiplies data size. Existing methods for skycube compression sacrifice too much query performance; so, we present a novel hashing- and bitstring-based compressed data structure that supports orders of magnitude faster query performance.

AB - The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. It is an expensive operator whose query performance can greatly benefit from materialization. However, a skyline can be executed over any subspace of dimensions, and the materialization of all subspace skylines, called the skycube, dramatically multiplies data size. Existing methods for skycube compression sacrifice too much query performance; so, we present a novel hashing- and bitstring-based compressed data structure that supports orders of magnitude faster query performance.

KW - skyline

KW - Compression

KW - Data Structures

U2 - 10.1145/2661829.2661891

DO - 10.1145/2661829.2661891

M3 - Article in proceedings

SN - 978-1-4503-2598-1

SP - 1767

EP - 1770

BT - Proceedings of The 23rd ACM International Conference on Information and Knowledge Management (CIKM 2014)

A2 - Li , Jianzhong

A2 - Wang, X. Sean

PB - Association for Computing Machinery

Y2 - 3 November 2014 through 7 November 2014

ER -