Efficient caching for constrained skyline queries

TY - GEN

T1 - Efficient caching for constrained skyline queries

AU - Mortensen, Michael Lind

AU - Chester, Sean

AU - Assent, Ira

AU - Magnani, Matteo

N1 - Conference code: 18

PY - 2015/3

Y1 - 2015/3

N2 - Constrained skyline queries retrieve all points that optimize some user’s preferences subject to orthogonal range constraints, but at significant computational cost. This paper is the first to propose caching to improve constrained skyline query response time. Because arbitrary range constraints are unlikely to match a cached query exactly, our proposed method identifies and exploits similar cached queries to reduce the computational overhead of subsequent ones.We consider interactive users posing a string of similar queries and show how these can be classified into four cases based on how they overlap cached queries. For each we present a specialized solution. For the general case of independent users, we introduce the Missing Points Region (MPR), that minimizes disk reads, and an approximation of the MPR. An extensive experimental evaluation reveals that the querying for an (approximate) MPR drastically reduces both fetch times and skyline computation.

AB - Constrained skyline queries retrieve all points that optimize some user’s preferences subject to orthogonal range constraints, but at significant computational cost. This paper is the first to propose caching to improve constrained skyline query response time. Because arbitrary range constraints are unlikely to match a cached query exactly, our proposed method identifies and exploits similar cached queries to reduce the computational overhead of subsequent ones.We consider interactive users posing a string of similar queries and show how these can be classified into four cases based on how they overlap cached queries. For each we present a specialized solution. For the general case of independent users, we introduce the Missing Points Region (MPR), that minimizes disk reads, and an approximation of the MPR. An extensive experimental evaluation reveals that the querying for an (approximate) MPR drastically reduces both fetch times and skyline computation.

KW - skyline

KW - caching

U2 - 10.5441/002/edbt.2015.30

DO - 10.5441/002/edbt.2015.30

M3 - Article in proceedings

SN - 978-3-89318-067-7

SP - 337

EP - 348

BT - International Conference on Extending Database Technology (EDBT 2015)

PB - openproceedings.org

T2 - International Conference on Extending Database Technology

Y2 - 23 March 2015 through 27 March 2015

ER -