Efficient caching for constrained skyline queries

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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
Publication yearMar 2015
ISBN (print) 978-3-89318-067-7
Publication statusPublished - Mar 2015
EventInternational Conference on Extending Database Technology - Brussels, Belgium
Duration: 23 Mar 201527 Mar 2015
Conference number: 18


ConferenceInternational Conference on Extending Database Technology

    Research areas

  • skyline, caching

See relations at Aarhus University Citationformats

ID: 83938806