DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Choi, Sung-Hee | - |
dc.contributor.advisor | 최성희 | - |
dc.contributor.author | Kim, Eun-Seok | - |
dc.contributor.author | 김은석 | - |
dc.date.accessioned | 2015-04-23T06:16:23Z | - |
dc.date.available | 2015-04-23T06:16:23Z | - |
dc.date.issued | 2014 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=569323&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/196895 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전산학과, 2014.2, [ iii, 26 p. ] | - |
dc.description.abstract | Given a set P of N objects in a region Q in 2-dimensional space and a rectangle r, the Minimizing Range Sum(MinRS) problem is to find an optimal location of the rectangle r that minimizes the sum of weights of objects covered by r. Each object corresponds to a non-negative weighted point and the size of a rectangle r is fixed. There already exists an in-memory algorithm which is not enough to adapt to a scalable environment. In this paper, we show that the MinRS problem returns a solution in the lower bound in terms of I/O costs. We also propose the All Minimizing Range Sum(AllMinRS) problem, which is to find all optimal locations. We prove how many optimal locations can exist at most in a given region Q, which implies the I/O complexity of the AllMinRS problem. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Algorithm | - |
dc.subject | 계산 기하학 | - |
dc.subject | I/O 복잡도 | - |
dc.subject | 외부 메모리 | - |
dc.subject | 알고리즘 | - |
dc.subject | Computational Geometry | - |
dc.subject | External memory | - |
dc.subject | I/O Complexity | - |
dc.title | I/O-Efficient minimizing range sum | - |
dc.title.alternative | 영역 합 최소화를 위한 외부 메모리 알고리즘 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 569323/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 020123135 | - |
dc.contributor.localauthor | Choi, Sung-Hee | - |
dc.contributor.localauthor | 최성희 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.