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 시간 복잡도를 알아낼 수 있음을 보인다.
