I/O-efficient planar range skyline = 외장형 메모리상에서 범위내 극대점을 효율적으로 구해주는 선형 자료 구조

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 291
  • Download : 0
In the planar range skyline reporting problem, the goal is to store a set P of n 2D points in a structure such that, given a query rectangle Q = [α_1, α_2] × [β_1, β_2] the maxima (a.k.a. skyline) of P∩Q can be reported efficiently. The query is 3-sided if an edge of Q is grounded, giving rise to two variants: top-open queries (β_2 = ∞) and left-open queries (α_1 = -∞). This paper presents results in external memory under the O(n/B) space budget (B is the block size), specifically: - We give structures that answer top-open queries in O(log_B n + k/B), O(loglog_B U + k/B), and O(1 +k/B) I/Os when the universe is R^2, a U×U grid, and rank space [O(n)]^2, respectively (where k is the number of reported points). The query complexity is optimal in all cases. - We show that the left-open case is harder, such that any linear-size structure must incur Ω((n/B)^ε + k/B) I/Os to answer a query. In fact, this case turns out to be just as difficult as the general 4-sided queries, for which we provide a static structure with the optimal query cost O((n/B)^ε + k/B).
Advisors
Tao, Yufei유페이Myaeng, Sung-Hyon맹성현
Description
한국과학기술원 : 웹사이언스공학전공,
Publisher
한국과학기술원
Issue Date
2013
Identifier
566504/325007  / 020114429
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공, 2013.8, [ iv, 32 p. ]

Keywords

range skyline; external memory; efficient; 극대점; 외장형메모리; 스카이라인; 효율성; skyline; maxima

URI
http://hdl.handle.net/10203/197098
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=566504&flag=dissertation
Appears in Collection
WST-Theses_Master(석사논문)
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