A Scalable Algorithm for Maximizing Range Sum in Spatial Databases

被引:46
作者
Dong-Wan Choi [1 ]
Chin -Wan Chung [1 ,2 ]
Tao, Yufei [2 ,3 ]
机构
[1] Korea Adv Inst Sci & Technol, Dept Comp Sci, Daejeon, South Korea
[2] Korea Adv Inst Sci & Technol, Div Web Sci & Technol, Daejeon, South Korea
[3] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China
来源
PROCEEDINGS OF THE VLDB ENDOWMENT | 2012年 / 5卷 / 11期
基金
新加坡国家研究基金会;
关键词
D O I
10.14778/2350229.2350230
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper investigates the MaxRS problem in spatial databases. Given a set O of weighted points and a rectangular region r of a given size, the goal of the MaxRS problem is to find a location of r such that the sum of the weights of all the points covered by r is maximized. This problem is useful in many location-based applications such as finding the best place for a new franchise store with a limited delivery range and finding the most attractive place for a tourist with a limited reachable range. However, the problem has been studied mainly in theory, particularly, in computational geometry. The existing algorithms from the computational geometry community are in-memory algorithms which do not guarantee the scalability. In this paper, we propose a scalable external-memory algorithm (ExactMaxRS) for the MaxRS problem, which is optimal in terms of the I/O complexity. Furthermore, we propose an approximation algorithm (ApproxMaxCRS) for the MaxCRS problem that is a circle version of the MaxRS problem. We prove the correctness and optimality of the ExactMaxRS algorithm along with the approximation bound of the ApproxMaxCRS algorithm. From extensive experimental results, we show that the ExactMaxRS algorithm is two orders of magnitude faster than methods adapted from existing algorithms, and the approximation bound in practice is much better than the theoretical bound of the ApproxMaxCRS algorithm.
引用
收藏
页码:1088 / 1099
页数:12
相关论文
共 22 条
[1]  
[Anonymous], 2009, PVLDB, V2, P1126
[2]  
Arge L., 1993, Algorithms and Data Structures. Third Workshop, WADS'93, P83
[3]  
Aronov B, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P886
[4]   ON A CIRCLE PLACEMENT PROBLEM [J].
CHAZELLE, BM ;
LEE, DT .
COMPUTING, 1986, 36 (1-2) :1-16
[5]   Indexing range sum queries in spatio-temporal databases [J].
Cho, Hyung-Ju ;
Chung, Chin-Wan .
INFORMATION AND SOFTWARE TECHNOLOGY, 2007, 49 (04) :324-331
[6]   Cache-Oblivious Dynamic Programming [J].
Chowdhury, Rezaul Alam ;
Ramachandran, Vijaya .
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :591-600
[7]   Covering Many or Few Points with Unit Disks [J].
de Berg, Mark ;
Cabello, Sergio ;
Har-Peled, Sariel .
THEORY OF COMPUTING SYSTEMS, 2009, 45 (03) :446-469
[8]   ON A MODIFIED ONE-CENTER MODEL [J].
DREZNER, Z .
MANAGEMENT SCIENCE, 1981, 27 (07) :848-851
[9]  
Du Y, 2005, LECT NOTES COMPUT SC, V3633, P163
[10]  
Goodrich T., 1993, FOCS, P714