{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:14Z","timestamp":1759638494997},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,29]]},"abstract":"<jats:p>In the maximizing range sum (MaxRS) problem, given (i) a set<jats:italic>P<\/jats:italic>of 2D points each of which is associated with a positive weight, and (ii) a rectangle<jats:italic>r<\/jats:italic>of specific extents, we need to decide where to place<jats:italic>r<\/jats:italic>in order to maximize the covered weight of<jats:italic>r<\/jats:italic>- that is, the total weight of the data points covered by<jats:italic>r<\/jats:italic>. Algorithms solving the problem exactly entail expensive CPU or I\/O cost. In practice, exact answers are often not compulsory in a MaxRS application, where slight imprecision can often be comfortably tolerated, provided that approximate answers can be computed considerably faster. Motivated by this, the present paper studies the (1 - \u03b5)-approximate MaxRS problem, which admits the same inputs as MaxRS, but aims instead to return a rectangle whose covered weight is at least (1-\u03b5)<jats:italic>m<\/jats:italic>*, where<jats:italic>m<\/jats:italic>* is the optimal covered weight, and \u03b5 can be an arbitrarily small constant between 0 and 1. We present fast algorithms that settle this problem with strong theoretical guarantees.<\/jats:p>","DOI":"10.14778\/2536258.2536266","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1546-1557","source":"Crossref","is-referenced-by-count":40,"title":["Approximate MaxRS in spatial databases"],"prefix":"10.14778","volume":"6","author":[{"given":"Yufei","family":"Tao","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong and Korea Advanced Institute of Science and Technology, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaocheng","family":"Hu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong-Wan","family":"Choi","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Wan","family":"Chung","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","article-title":"Computing the largest empty rectangle","volume":"15","author":"Chazelle B.","year":"1986","unstructured":"B. Chazelle , R. L. S. D. III, and D. T. Lee . Computing the largest empty rectangle . SIAM J. of Comp. , 15 ( 1 ): 300 - 315 , 1986 . B. Chazelle, R. L. S. D. III, and D. T. Lee. Computing the largest empty rectangle. SIAM J. of Comp., 15(1):300-315, 1986.","journal-title":"SIAM J. of Comp."},{"issue":"11","key":"e_1_2_1_2_1","first-page":"1088","article-title":"A scalable algorithm for maximizing range sum in spatial databases","volume":"5","author":"Choi D.-W.","year":"2012","unstructured":"D.-W. Choi , C.-W. Chung , and Y. Tao . A scalable algorithm for maximizing range sum in spatial databases . PVLDB , 5 ( 11 ): 1088 - 1099 , 2012 . D.-W. Choi, C.-W. Chung, and Y. Tao. A scalable algorithm for maximizing range sum in spatial databases. PVLDB, 5(11):1088-1099, 2012.","journal-title":"PVLDB"},{"issue":"3","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1007\/s00224-008-9135-9","article-title":"Covering many or few points with unit disks","volume":"45","author":"de Berg M.","year":"2009","unstructured":"M. de Berg , S. Cabello , and S. Har-Peled . Covering many or few points with unit disks . Theory Comput. Syst. , 45 ( 3 ): 446 - 469 , 2009 . M. de Berg, S. Cabello, and S. Har-Peled. Covering many or few points with unit disks. Theory Comput. Syst., 45(3):446-469, 2009.","journal-title":"Theory Comput. Syst."},{"key":"e_1_2_1_4_1","first-page":"163","volume-title":"SSTD","author":"Du Y.","year":"2005","unstructured":"Y. Du , D. Zhang , and T. Xia . The optimal-location query . In SSTD , pages 163 - 180 , 2005 . Y. Du, D. Zhang, and T. Xia. The optimal-location query. In SSTD, pages 163-180, 2005."},{"key":"e_1_2_1_5_1","first-page":"143","volume-title":"ICDT","author":"Govindarajan S.","year":"2003","unstructured":"S. Govindarajan , P. K. Agarwal , and L. Arge . CRB-tree: An efficient indexing scheme for range-aggregate queries . In ICDT , pages 143 - 157 , 2003 . S. Govindarajan, P. K. Agarwal, and L. Arge. CRB-tree: An efficient indexing scheme for range-aggregate queries. In ICDT, pages 143-157, 2003."},{"issue":"4","key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","article-title":"Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane","volume":"4","author":"Imai H.","year":"1983","unstructured":"H. Imai and T. Asano . Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane . J. of Algorithms , 4 ( 4 ): 310 - 323 , 1983 . H. Imai and T. Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. of Algorithms, 4(4):310-323, 1983.","journal-title":"J. of Algorithms"},{"key":"e_1_2_1_7_1","first-page":"299","volume-title":"SIGMOD","author":"Jermaine C.","year":"2004","unstructured":"C. Jermaine , A. Pol , and S. Arumugam . Online maintenance of very large random samples . In SIGMOD , pages 299 - 310 , 2004 . C. Jermaine, A. Pol, and S. Arumugam. Online maintenance of very large random samples. In SIGMOD, pages 299-310, 2004."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/375663.375718","volume-title":"SIGMOD","author":"Lazaridis I.","year":"2001","unstructured":"I. Lazaridis and S. Mehrotra . Progressive approximate aggregate queries with a multi-resolution tree structure . In SIGMOD , pages 401 - 412 , 2001 . I. Lazaridis and S. Mehrotra. Progressive approximate aggregate queries with a multi-resolution tree structure. In SIGMOD, pages 401-412, 2001."},{"issue":"4","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","article-title":"Linear-time algorithms for linear programming in R3 and related problems","volume":"12","author":"Megiddo N.","year":"1983","unstructured":"N. Megiddo . Linear-time algorithms for linear programming in R3 and related problems . SIAM J. of Comp. , 12 ( 4 ): 759 - 776 , 1983 . N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. of Comp., 12(4):759-776, 1983.","journal-title":"SIAM J. of Comp."},{"issue":"8","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0898-1221(95)00029-X","article-title":"A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids","volume":"29","author":"Nandy S.","year":"1995","unstructured":"S. Nandy and B. Bhattacharya . A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids . Computers & Mathematics with Applications , 29 ( 8 ): 45 - 61 , 1995 . S. Nandy and B. Bhattacharya. A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids. Computers & Mathematics with Applications, 29(8):45-61, 1995.","journal-title":"Computers & Mathematics with Applications"},{"key":"e_1_2_1_11_1","first-page":"443","volume-title":"SSTD","author":"Papadias D.","year":"2001","unstructured":"D. Papadias , P. Kalnis , J. Zhang , and Y. Tao . Efficient OLAP operations in spatial data warehouses . In SSTD , pages 443 - 459 , 2001 . D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient OLAP operations in spatial data warehouses. In SSTD, pages 443-459, 2001."},{"key":"e_1_2_1_12_1","first-page":"129","volume-title":"PODS","author":"Sheng C.","year":"2011","unstructured":"C. Sheng and Y. Tao . New results on two-dimensional orthogonal range aggregation in external memory . In PODS , pages 129 - 139 , 2011 . C. Sheng and Y. Tao. New results on two-dimensional orthogonal range aggregation in external memory. In PODS, pages 129-139, 2011."},{"issue":"2","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik V.","year":"1971","unstructured":"V. Vapnik and A. Chervonenkis . On the uniform convergence of relative frequencies of events to their probabilities . Theory of Probability and its Applications , 16 ( 2 ): 264 - 280 , 1971 . V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.","journal-title":"Theory of Probability and its Applications"},{"key":"e_1_2_1_14_1","first-page":"253","volume-title":"SPAA","author":"Wei Z.","year":"2009","unstructured":"Z. Wei , K. Yi , and Q. Zhang . Dynamic external hashing: the limit of buffering . In SPAA , pages 253 - 259 , 2009 . Z. Wei, K. Yi, and Q. Zhang. Dynamic external hashing: the limit of buffering. In SPAA, pages 253-259, 2009."},{"issue":"1","key":"e_1_2_1_15_1","first-page":"1126","article-title":"Efficient method for maximizing bichromatic reverse nearest neighbor","volume":"2","author":"Wong R. C.-W.","year":"2009","unstructured":"R. C.-W. Wong , M. T. Ozsu , P. S. Yu , A. W.-C. Fu , and L. Liu . Efficient method for maximizing bichromatic reverse nearest neighbor . PVLDB , 2 ( 1 ): 1126 - 1137 , 2009 . R. C.-W. Wong, M. T. Ozsu, P. S. Yu, A. W.-C. Fu, and L. Liu. Efficient method for maximizing bichromatic reverse nearest neighbor. PVLDB, 2(1):1126-1137, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_16_1","first-page":"804","volume-title":"ICDE","author":"Xiao X.","year":"2011","unstructured":"X. Xiao , B. Yao , and F. Li . Optimal location queries in road network databases . In ICDE , pages 804 - 815 , 2011 . X. Xiao, B. Yao, and F. Li. Optimal location queries in road network databases. In ICDE, pages 804-815, 2011."},{"key":"e_1_2_1_17_1","first-page":"643","volume-title":"VLDB","author":"Zhang D.","year":"2006","unstructured":"D. Zhang , Y. Du , T. Xia , and Y. Tao . Progressive computation of the min-dist optimal-location query . In VLDB , pages 643 - 654 , 2006 . D. Zhang, Y. Du, T. Xia, and Y. Tao. Progressive computation of the min-dist optimal-location query. In VLDB, pages 643-654, 2006."},{"key":"e_1_2_1_18_1","first-page":"828","volume-title":"ICDE","author":"Zhou Z.","year":"2011","unstructured":"Z. Zhou , W. Wu , X. Li , M.-L. Lee , and W. Hsu . Maxfirst for maxbrknn . In ICDE , pages 828 - 839 , 2011 . Z. Zhou, W. Wu, X. Li, M.-L. Lee, and W. Hsu. Maxfirst for maxbrknn. In ICDE, pages 828-839, 2011."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536258.2536266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:44:28Z","timestamp":1689345868000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536258.2536266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":18,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,8,29]]}},"alternative-id":["10.14778\/2536258.2536266"],"URL":"https:\/\/doi.org\/10.14778\/2536258.2536266","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}