서지주요정보
I/O-Efficient minimizing range sum = 영역 합 최소화를 위한 외부 메모리 알고리즘
서명 / 저자 I/O-Efficient minimizing range sum = 영역 합 최소화를 위한 외부 메모리 알고리즘 / Eun-Seok Kim.
저자명 Kim, Eun-Seok ; 김은석
발행사항 [대전 : 한국과학기술원, 2014].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8026533

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 14011

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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 xed. 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.

2차원 공간의 지역 Q 내부에 오브젝트들의 집합 P와 사각형 r이 주어졌을 때, 영역합 최소화 문제는 사각형 r 내부에 위치한 점들의 가중치의 합이 최소화가 될 수 있는 r 의 위치를 찾는 문제이다. 각각의 오브젝트는 음이 아닌 가중치를 가지는 점에 대응되며 사각형 r의 크기는 고정되어 있다. 이 문제는 서비스 영역을 가지는 프렌차이즈 상점 그리고 중국집과 같은 상점을 짓기 위한 위치를 찾을 때 유용하게 쓰일 수 있다. 또한, 이 문제는 이미 주메모리 알고리즘이 존재하지만 오브젝트의 수가 엄청나게 많을 때에는 적용하기가 어렵다. 이 논문에서 우리는 영역합 최소화 문제가 I/O 시간 관점으로 하한선안에 문제를 해결할 수 있음을 보인다. 어떤 경우에는 사용자들에게 최적의 장소로 선택될 수 있는 모든 위치를 제공하는 곳이 더 좋을 것이다. 이로써 사용자들은 임대료, 유동인구, 그리고 정부 정책 등의 이유를 고려하여 하나의 위치를 선택할 수 있다. 우리는 하나가 아닌 모든 최적의 위치를 찾는 전영역합 최소화 문제를 제시한다. 게다가 우리는 지역 Q 내부에 위치할 수 있는 최적의 위치 개수의 상한선를 증명하고 이것으로 전영여합 최소화 문제의 I/O 시간 복잡도를 알아낼 수 있음을 보인다.

서지기타정보

서지기타정보
청구기호 {MCS 14011
형태사항 iii, 26 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 김은석
지도교수의 영문표기 : Sung-Hee Choi
지도교수의 한글표기 : 최성희
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 References : p. 22-23
주제 Algorithm
External memory
I/O Complexity
Computational Geometry
알고리즘
외부 메모리
I/O 복잡도
계산 기하학
QR CODE qr code