Journal
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume 33, Issue 1, Pages 271-286Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2019.2923914
Keywords
Skyline; voronoi; diagram; queries
Categories
Funding
- NSF [IIS-1838200, CNS-1618932]
Ask authors/readers for more resources
In this paper, a novel structure called the Skyline Diagram is proposed for partitioning the plane based on a set of points. Efficient algorithms are presented for building the diagram to accommodate various types of skyline queries. Experimental results demonstrate the efficiency and scalability of the algorithms proposed in this paper.
Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to kth-order Voronoi diagram commonly used to facilitate k nearest neighbor (kNN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. In addition, we propose an approximate skyline diagram which can significantly reduce the space cost. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available