1 Search Results for "Balke, Wolf-Tilo"

Document

Efficient Evaluation of Numerical Preferences: Top k Queries, Skylines and Multi-objective Retrieval

Authors: Wolf-Tilo Balke

Published in: Dagstuhl Seminar Proceedings, Volume 4271, Preferences: Specification, Inference, Applications (2006)

Abstract

Query processing in databases and information systems has developed beyond mere SQL-style exact matching of attribute values. Scoring database objects according to numerical user preferences and retrieving only the top k matches or Pareto-optimal result sets (skyline queries) are already common for a variety of applications. Recently a lot of database literature has focussed on how to efficiently evaluate queries based on numerical preferences. Specialized algorithms using either top k retrieval (assuming a single compensation function defined over all query predicates, i.e. a global utility function) or computing skylines (assuming all query predicates as pairwise incomparable) have been shown to be capable of avoiding naïve linear database scans by pruning large numbers of database objects and thus vastly improve scalability. However, both paradigms are only two extreme cases of exploring viable compromises for each user’s objectives, which may or may not be comparable. To find the correct result set for arbitrary cases of multi-objective query processing in databases a novel algorithm for computing sets of objects that are non-dominated with respect to a set of monotonic objective functions representing a user's notion of utility, has recently been presented. Naturally containing top k and skyline retrieval paradigms as special cases, this algorithm maintains scalability also for all cases in between. To be more precise, in both special cases the multi-objective retrieval algorithm will behave exactly like the most efficient known evaluation algorithms for top k and skyline queries respectively. This algorithm has also been proved to be correct and instance-optimal in terms of necessary object accesses. Moreover, it improves the psychological response behavior by progressively producing result objects as quickly as possible, while the algorithm is still running, so user can deal with result objects at the earliest point in time. Our tutorial will discuss all state of the art algorithms for top k retrieval, skyline queries and multi-objective retrieval and point to open problems, future extensions of the paradigm and research in numerical preferences.

Cite as

Wolf-Tilo Balke. Efficient Evaluation of Numerical Preferences: Top k Queries, Skylines and Multi-objective Retrieval. In Preferences: Specification, Inference, Applications. Dagstuhl Seminar Proceedings, Volume 4271, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{balke:DagSemProc.04271.3,
  author =	{Balke, Wolf-Tilo},
  title =	{{Efficient Evaluation of Numerical Preferences: Top k Queries, Skylines and Multi-objective Retrieval}},
  booktitle =	{Preferences: Specification, Inference, Applications},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4271},
  editor =	{Gianni Bosi and Ronen I. Brafman and Jan Chomicki and Werner Kie{\ss}ling},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04271.3},
  URN =		{urn:nbn:de:0030-drops-4007},
  doi =		{10.4230/DagSemProc.04271.3},
  annote =	{Keywords: Top k retrieval , skyline queries, multi-objective optimization, numerical preferences, utility functions}
}

Refine by Author
1 Balke, Wolf-Tilo

Refine by Classification

Refine by Keyword
1 Top k retrieval
1 multi-objective optimization
1 numerical preferences
1 skyline queries
1 utility functions

Refine by Type
1 document

Refine by Publication Year
1 2006

1 Search Results for "Balke, Wolf-Tilo"

Efficient Evaluation of Numerical Preferences: Top k Queries, Skylines and Multi-objective Retrieval

Abstract

Cite as

Thanks for your feedback!

Could not send message