Efficient caching for constrained skyline queries

Publication: Research - peer-reviewArticle in proceedings

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.
Original languageEnglish
Title of host publicationInternational Conference on Extending Database Technology (EDBT 2015)
Number of pages12
Publisheropenproceedings.org
Publication yearMar 2015
Pages337-348
ISBN (print) 978-3-89318-067-7
DOIs
StatePublished - Mar 2015
EventInternational Conference on Extending Database Technology - Brussels, Belgium

Conference

ConferenceInternational Conference on Extending Database Technology
Nummer18
LandBelgium
ByBrussels
Periode23/03/201527/03/2015

    Keywords

  • skyline, caching

See relations at Aarhus University Citationformats

ID: 83938806