Deep Learning for Skyline Queries Público

Guo, Yuzhang (Spring 2019)

Permanent URL: https://etd.library.emory.edu/concern/etds/zg64tn10d?locale=es
Published

Abstract

Skyline computation is important in many applications. It identifies a set of skyline points that are not dominated by any other point and is used in multi-criteria data analysis and decision making. In this paper, we propose the first neural architecture for skyline, called neural skyline networks (SkyNet), to learn the spatial knowledge of skyline patterns. Given SkyNet, we can predict the skyline points rather than compute the skyline points using traditional algorithms. SkyNet can predict the skyline points in linear $O(n)$ time with high accuracy, where $n$ is the number of points. To achieve higher accuracy, we further propose two spatial aware loss functions which distinguish the contribution/weights of non-skyline points. Extensive experiments show that our neural skyline networks are capable of high accuracy and are at least one order of magnitude faster than the state-of-the-art algorithms for skyline computation. The main contribution of this paper is to outline and evaluate the potential of a novel approach to compute computational geometry structures (e.g., skyline and convex hull), which complements existing works and arguably opens up an entirely new research direction for a decades-old field. 

Table of Contents

Introduction ......................................................................................................... 1 Related Work ...................................................................................................... 6

2.1 Skyline ............................................................................................................ 6

2.2 NeuralNetworks .............................................................................................. 7

3. Definitions and Preliminaries ............................................................................. 9

3.1 Definitions ...................................................................................................... 9

3.2 Sequence-to-sequenceFramework ................................................................ 10

3.3 AttentionModel ............................................................................................. 12

3.4 PointerNetworks ..........................................................................,................. 13

4. Proposed Models ................................................................................................ 16

4.1 Pointer Networks with an additional skyline layer ........................................ 16

4.2 NeuralSkylineNetworks ................................................................................. 19

4.2.1 Neural Skyline Networks with layer based loss function ......................... 21

4.2.2 Neural Skyline Networks with Euclidean distance based loss function ... 22

4.3 Discussion ...................................................................................................... 24

5. Experiments ........................................................................................................ 26

5.1 ExperimentSetup ........................................................................................... 26

5.2 AverageNumberofSkylinePoints .................................................................... 27

5.3 PredictionTimeCost ....................................................................................... 28

5.4 PredictionAccuracy ....................................................................................... 29

5.5 ModelTransformability ................................................................................. 33

5.6 RealDataset ................................................................................................... 36

5.7 Summary ....................................................................................................... 38

6. Conclusion and Future Work .............................................................................. 39 

About this Honors Thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
Palabra Clave
Committee Chair / Thesis Advisor
Committee Members
Última modificación

Primary PDF

Supplemental Files