Equivalence Heuristics for Malleability-Aware Skylines

TitleEquivalence Heuristics for Malleability-Aware Skylines
Publication TypeJournal Article
Year of Publication2012
AuthorsLofi, C., U. Güntzer, and W. - T. Balke
JournalJournal of Computing Science and Engineering (JCSE)
Start Page207-218
Date Published09/2012

In recent years, the skyline query paradigm has been established as a reliable method for database query personalization.
While early efficiency problems have been solved by sophisticated algorithms and advanced indexing, new challenges in
skyline retrieval effectiveness continuously arise. In particular, the rise of the Semantic Web and linked open data leads
to personalization issues where skyline queries cannot be applied easily. We addressed the special challenges presented
by linked open data in previous work; and now further extend this work, with a heuristic workflow to boost efficiency.
This is necessary; because the new view on linked open data dominance has serious implications for the efficiency of the
actual skyline computation, since transitivity of the dominance relationships is no longer granted. Therefore, our contri-butions in this paper can be summarized as: we present an intuitive skyline query paradigm to deal with linked open data;
we provide an effective dominance definition, and establish its theoretical properties; we develop innovative skyline
algorithms to deal with the resulting challenges; and we design efficient heuristics for the case of predicate equivalences
that may often happen in linked open data. We extensively evaluate our new algorithms with respect to performance, and
the enriched skyline semantics.

JCSE-2012-0037.pdf1.97 MB