DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Tao, Yufei | - |
dc.contributor.advisor | 유페이 | - |
dc.contributor.advisor | Myaeng, Sung-Hyon | - |
dc.contributor.advisor | 맹성현 | - |
dc.contributor.author | Yoon, Jeong-Hun | - |
dc.contributor.author | 윤정훈 | - |
dc.date.accessioned | 2015-04-23T07:06:22Z | - |
dc.date.available | 2015-04-23T07:06:22Z | - |
dc.date.issued | 2013 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=566504&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/197098 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공, 2013.8, [ iv, 32 p. ] | - |
dc.description.abstract | 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). | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | range skyline | - |
dc.subject | external memory | - |
dc.subject | efficient | - |
dc.subject | 극대점 | - |
dc.subject | 외장형메모리 | - |
dc.subject | 스카이라인 | - |
dc.subject | 효율성 | - |
dc.subject | skyline | - |
dc.subject | maxima | - |
dc.title | I/O-efficient planar range skyline | - |
dc.title.alternative | 외장형 메모리상에서 범위내 극대점을 효율적으로 구해주는 선형 자료 구조 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 566504/325007 | - |
dc.description.department | 한국과학기술원 : 웹사이언스공학전공, | - |
dc.identifier.uid | 020114429 | - |
dc.contributor.localauthor | Tao, Yufei | - |
dc.contributor.localauthor | 유페이 | - |
dc.contributor.localauthor | Myaeng, Sung-Hyon | - |
dc.contributor.localauthor | 맹성현 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.