Computation of spatial skyline points

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 62
  • Download : 0
The database skyline query (or non-domination query) has a spatial form: Given a setPwithnpoint sites, and a point set S of m locations of interest, a site p is an element of P is a skyline point if and only if for each q is an element of P\{p}, there exists at least one location s is an element of S that is closer topthan toq. We reduce the problem of determining skyline points to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites ofP, while the convex distance function is derived from the set of locationsS. In the two-dimensional plane, this reduction gives an O((n + m) log(n + m))-time algorithm to find the skyline points.
Publisher
ELSEVIER
Issue Date
2021-02
Language
English
Article Type
Article
Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.93, pp.101698

ISSN
0925-7721
DOI
10.1016/j.comgeo.2020.101698
URI
http://hdl.handle.net/10203/277080
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0