Deep Learning for Skyline Queries Open Access

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	Emory College
Department	Computer Science
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Computer Science
Keyword	Skyline Queries Sequence-to-sequence Deep learning
Committee Chair / Thesis Advisor	Li Xiong, Emory University
Committee Members	Bree Ettinger, Emory University Vaidy Sunderam, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Deep Learning for Skyline Queries ()	2019-04-09 05:56:40 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions