Table of Contents vi
Table of Figures viii
Table of Tables ix
1 Introduction 1
2 Related Work 6
2.1 Traditional skyline queries . . . 6
2.2 Skyline queries in road networks . . . 7
3 Data Structures 10
3.1 Static Attribute Dominating Matrix . . . 10
3.2 Dynamic Attribute Sorting List . . . 12
3.3 Skyline Point Expansion Tree . . . 13
4 Processing Cdε-SQ with Updates 16
4.1 Object update for Cdε-SQ . . . 16
4.2 Edge update for Cdε-SQ . . . 23
4.3 Query path update for Cdε-SQ. . . 26
5 Processing Cknn-SQ with Updates 28
5.1 Object update for Cknn-SQ . . . 28
5.2 Edge update for Cknn-SQ. . . 31
5.3 Query path update for Cknn-SQ . . . 32
6 Performance Evaluation 33
6.1 Experimental Settings . . . 33
6.2 Cdε-update algorithm vs. Cdε-SQ algorithm . . . 34
6.3 Cknn-update algorithm vs. Cknn-SQ algorithm . . . 37
7 Conclusions 42
Bibliography 43
|