Faster output-sensitive skyline computation algorithm

被引：13

作者：

Liu, Jinfei ^{[1
]}

Xiong, Li ^{[1
]}

Xu, Xiaofeng ^{[1
]}

机构：

[1] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

来源：

INFORMATION PROCESSING LETTERS | 2014年 / 114卷 / 12期

关键词：

Skyline; Output-sensitive; Time complexity; Worst case; Computational complexity; VECTORS; MAXIMA; SET;

D O I：

10.1016/j.ipl.2014.06.014

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present the second output-sensitive skyline computation algorithm which is faster than the only existing output-sensitive skyline computation algorithm [1] in worst case because our algorithm does not rely on the existence of a linear time procedure for finding medians. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：710 / 713

页数：4

共 10 条

[1] AVERAGE NUMBER OF MAXIMA IN A SET OF VECTORS AND APPLICATIONS [J].

BENTLEY, JL ;

KUNG, HT ;

SCHKOLNICK, M ;

THOMPSON, CD .

JOURNAL OF THE ACM, 1978, 25 (04) :536-543

[2] MULTIDIMENSIONAL DIVIDE-AND-CONQUER [J].

BENTLEY, JL .

COMMUNICATIONS OF THE ACM, 1980, 23 (04) :214-229

[3]

BENTLEY JL, 1990, SODA, P179

[4]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[5]

Chan T.M., 2014, S COMP GEOM, P40

[6] Optimal output-sensitive convex hull algorithms in two and three dimensions [J].

Chan, TM .

DISCRETE & COMPUTATIONAL GEOMETRY, 1996, 16 (04) :361-368

[7]

Hu XC, 2013, PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), P887

[8]

Kirkpatrick D.G., 1985, S COMP GEOM, P89

[9] FINDING MAXIMA OF A SET OF VECTORS [J].

KUNG, HT ;

LUCCIO, F ;

PREPARATA, FP .

JOURNAL OF THE ACM, 1975, 22 (04) :469-476

[10]

Luccio F., 1973, FINDING MAXIMA SET V

← 1 →