Skyline query processing [Elektronische Ressource] / vorgelegt von Steffen Thomas Rost

English
167 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

INAUGURAL-DISSERTATIONzurErlangungderDoktorwurde¨derNaturwissenschaftlich MathematischenGesamtfakult at¨derRuprecht Karls Universit at¨ HeidelbergvorgelegtvonDiplom Informatiker(Univ.) SteffenThomasRostausHeilbronnTagdermundlichen¨ Prufung:¨ 09. Oktober2006SkylineQueryProcessingGutachter: Prof. Dr. DonaldKossmannProf. Dr. GerhardReineltAcknowledgmentsAs with all big projects there were a lot of people who helped me in manifold ways to writethisthesis. Drawingupalistandthankingthemallwouldprobablygobeyondthescopeofthischapter and in the end I would have forgotten someone, anyway. So to all who helped me andare not mentioned on this page, I say, thank you, thank you, thank you. Your help was muchappreciated.HowevertherearesomepeopleIwouldliketothankfortheiroutstandinghelpandsupport.I would like to thank my supervisor Donald Kossmann who helped me to navigate throughroughwaters,nevergivinguphopeonme,andalwayschallengingmetogivemybest. Withouthimthisthesiswouldnothavebeenpossible.¨I would like to thank my colleagues, Andreas Grunhagen, Peter Fischer, Angelika Reiser, andCristianDudafortheirhelp. Showingupintheirofficesanytime,justaskingasimplequestionand finding yourself in a fruitful discussion is the help I am most grateful for. I hope I havedonethesameforthem.I also would like to thank all the other authors who contributed to the Skyline. By publishingtheirthoughtsontheSkylineitwaspossibleformetoextendmyknowledgeontheSkyline.

Subjects

Informations

Published by
Published 01 January 2006
Reads 24
Language English
Document size 1 MB
Report a problem

INAUGURAL-DISSERTATION
zur
ErlangungderDoktorwurde¨
der
Naturwissenschaftlich MathematischenGesamtfakult at¨
der
Ruprecht Karls Universit at¨ Heidelberg
vorgelegtvon
Diplom Informatiker(Univ.) SteffenThomasRost
ausHeilbronn
Tagdermundlichen¨ Prufung:¨ 09. Oktober2006SkylineQueryProcessing
Gutachter: Prof. Dr. DonaldKossmann
Prof. Dr. GerhardReineltAcknowledgments
As with all big projects there were a lot of people who helped me in manifold ways to write
thisthesis. Drawingupalistandthankingthemallwouldprobablygobeyondthescopeofthis
chapter and in the end I would have forgotten someone, anyway. So to all who helped me and
are not mentioned on this page, I say, thank you, thank you, thank you. Your help was much
appreciated.
HowevertherearesomepeopleIwouldliketothankfortheiroutstandinghelpandsupport.
I would like to thank my supervisor Donald Kossmann who helped me to navigate through
roughwaters,nevergivinguphopeonme,andalwayschallengingmetogivemybest. Without
himthisthesiswouldnothavebeenpossible.
¨I would like to thank my colleagues, Andreas Grunhagen, Peter Fischer, Angelika Reiser, and
CristianDudafortheirhelp. Showingupintheirofficesanytime,justaskingasimplequestion
and finding yourself in a fruitful discussion is the help I am most grateful for. I hope I have
donethesameforthem.
I also would like to thank all the other authors who contributed to the Skyline. By publishing
theirthoughtsontheSkylineitwaspossibleformetoextendmyknowledgeontheSkyline.
And, last but not least, I would like to thank my parents whose love and support I can always
count on. Without them neither my studies nor this thesis would have been possible. I love
themfromthebottomofmyheart.
A five year project is now almost finished. Many things happened during these years. Looking
back I see foremost the positive things: working together with colleagues, teaching students,
andagreatdealofpersonaldevelopment.
S.T.R.
June2006Abstract
This thesis deals with a special subset of multi dimensional set of points, called the Skyline.
These points are the maxima or minima of the complete set and are of special interest for the
field of decision support. Coming from basic algorithms for computing the Skyline we will
develop ideas and algorithms for “on the fly” or online computation of the Skyline. We will
also extend the concept of Skyline with new application domains leading us to user profiling
withthehelpofSkyline.
Zusammenfassung
Diese Arbeit behandelt eine spezielle Untermenge einer multi dimensionalen Punktemenge,
Skyline genannt. Diese Punkte sind die Maxima oder Minima der ganzen Menge und sind
im Gebiet des Decision Support von besonderem Interesse. Wir werden grundlegende Skyline
Algorithmen vorstellen und Ideen und Algorithmen, um die Skyline “on the fly” oder online
zu berechnen. Wir werden außerdem das Skyline Konzept mit neuen Anwendungsgebieten
erweiternwobeiwirBenutzerpraferenzen¨ mitHilfederSkylineberechnenwollen.Contents
I Introduction 7
1 Motivation 9
2 ApplicationDomains 11
2.1 HotelBooking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 ElectronicMarketPlaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 StockTicks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 QualityAssurance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 MathematicalFoundations 15
3.1 MaximumVectorProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2Vectorfor“1 dimensional”Vectors . . . . . . . . . . . . . 16
3.3 SkylineProperties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 NumberofSkylinePoints . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.2 TreatmentofDuplicatePoints . . . . . . . . . . . . . . . . . . . . . . 17
3.3.3 NoEmphasisofCertainDimensions . . . . . . . . . . . . . . . . . . . 17
3.3.4 Transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Taxonomy 19
4.1 PointComparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 SkylineQueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4 SkylineAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4.1 BatchAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4.2 ProgressiveAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.4.3 OnlineAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.5 InformationPre filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12 CONTENTS
5 RelatedWork 24
5.1 Skyline,ConvexHullandTop KProcessing . . . . . . . . . . . . . . . . . . . 24
5.2 UserPreferencesandUserProfiling . . . . . . . . . . . . . . . . . . . . . . . 26
5.3 StreamingandContinuousQueryProcessing . . . . . . . . . . . . . . . . . . 26
5.4 MultipleQueryOptimizationandViewMaintenance . . . . . . . . . . . . . . 27
5.5 ContinuousSkylineProcessing . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.6 Miscellany . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6 SettingsforPerformanceMeasurements 28
6.1 Multi DimensionalDataSets . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.2 ConductingMeasurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2.1 Distinguishing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2.2 MachineData . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 HotelExampleandPseudoCode 32
7.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.2 PseudoCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
II BatchandProgressiveSkylineComputation 35
8 Classification 37
8.1 BatchAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8.2 ProgressiveAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8.3 CandidateSkylineComputation-SkylinePre filters . . . . . . . . . . . . . . . 38
9 TheStandardAlgorithm 39
9.1 AlgorithmDescription . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
9.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
10 TheBlock Nested LoopsAlgorithm 42
10.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
10.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
11 TheDivide and ConquerAlgorithm 45
11.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
11.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
12 BitmapBasedAlgorithm 50
12.1 AlgorithmDescription . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
12.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
13 Partition IndexAlgorithm 54
13.1 AlgorithmDescription . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
13.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58