NDLI: Restricting skyline sizes using weak Pareto dominance

Please wait, while we are loading the content...

Restricting skyline sizes using weak Pareto dominance

Content Provider	Springer Nature Link
Author	Balke, Wolf Tilo Güntzer, Ulrich Siberski, Wolf
Copyright Year	2007
Abstract	Skyline queries have recently received a lot of attention due to their intuitive query formulation: users can state preferences with respect to several attributes. Unlike numerical or score-based preferences, preferences over discrete value domains do not show an inherent total order, but have to rely on partial orders as stated by the user. In such orders typically many object values are incomparable, increasing the size of skyline sets significantly, and making their computation expensive. In this paper we explore how to enable interactive tasks like query refinement or relevance feedback by providing interesting subsets of the full Pareto skyline, which give users a good overview over the skyline. To be practical these subsets have to be small, efficient to compute, suitable for higher numbers of query predicates, and representative. The key to improved performance and reduced result set sizes is the relaxation of Pareto semantics to the concept of weak Pareto dominance. We argue that this relaxation yields intuitive results and show how it opens up the use of efficient and scalable query processing algorithms. We first derive the complete skyline subset given by weak Pareto dominance called ‘restricted skyline’ and then considering the individual performance of objects limit this further to a subset called ‘focused skyline’. Assessing the practical impact our experiments show that our approach indeed leads to lean result set sizes and outperforms Pareto skyline computations by up to two orders of magnitude. Skyline-Queries stehen in den letzten Jahren im Fokus der Aufmerksamkeit, da sie eine besonders intuitive Form der Anfragestellung unterstützen. Der Benutzer spezifiziert Präferenzen nur in qualitativer Weise im Bezug auf alle gewünschten Attribute. Im Gegensatz zu numerischen oder Score-basierten Präferenzen, definieren attribut-basierte Präferenzen dabei nicht immer eine totale Ordnung auf den Datenbankobjekten. Sie basieren typischerweise lediglich auf partiellen Ordnungen, die der Benutzer angibt. In solchen Ordnung sind daher viele Objekte unvergleichbar, was die durchschnittliche Größe der Skyline signifikant anwachsen lässt und die Effizienz ihrer Berechnung deutlich verbessert. In dieser Arbeit untersuchen wir die Ableitung interessanter Teilmengen der Pareto-Skyline, die Benutzern einen guten Überblick über die zu erwartenden Objekte für interaktive Aufgaben wie Anfrageverfeinerung oder Relevanz-Feedback bieten. Um nützlich zu sein, müssen diese Teilmengen klein, effizient zu berechnen, für hoch-dimensionale Anfragen geeignet und möglichst repräsentativ sein. Der Schlüssel zu guten Berechnungszeiten und deutlich verkleinerten Skylines ist dabei die Abschwächung der Pareto-Optimalität auf das Konzept der schwachen Pareto-Dominanz. Wir zeigen, dass diese Abschwächung zu intuitiven Ergebnissen führt und die Verwendung effizienter und skalierbarer Anfrageauswertungsalgorithmen erlaubt. Wir werten zuerst die komplette Menge der nicht schwach dominierten Objekte (Restricted Skyline) aus und leiten dann daraus eine besondere Teilmenge jener Objekte ab, die viel versprechend bezüglich des Benutzerinteresses sind (Focused Skyline). Unsere Experimente zur Überprüfung der praktischen Anwendbarkeit unseres Ansatzes zeigen, dass nicht nur die Größe der Resultatmengen deutlich schrumpft, sondern auch die notwendige Auswertungszeit um etwa zwei Größenordnungen reduziert werden kann.
Starting Page	165
Ending Page	178
Page Count	14
File Format	PDF
ISSN	01783564
Journal	Informatik - Forschung und Entwicklung
Volume Number	21
Issue Number	3-4
e-ISSN	09492925
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-05-11
Publisher Place	Berlin, Heidelberg
Access Restriction	Subscribed
Subject Keyword	Skyline queries Pareto optimality Result size Weak Pareto dominance Theory of Computation Data Structures, Cryptology and Information Theory Software Engineering/Programming and Operating Systems Computer Systems Organization and Communication Networks Computer Hardware Computer Science
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in