{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T10:13:16Z","timestamp":1760955196210,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003803","name":"University of Hong Kong","doi-asserted-by":"publisher","award":["7155\/09E"],"award-info":[{"award-number":["7155\/09E"]}],"id":[{"id":"10.13039\/501100003803","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p>\n            Consider a set of\n            <jats:italic>customers<\/jats:italic>\n            (e.g., WiFi receivers) and a set of\n            <jats:italic>service providers<\/jats:italic>\n            (e.g., wireless access points), where each provider has a\n            <jats:italic>capacity<\/jats:italic>\n            and the quality of service offered to its customers is anti-proportional to their distance. The\n            <jats:italic>Capacity Constrained Assignment<\/jats:italic>\n            (CCA) is a matching between the two sets such that (i) each customer is assigned to at most one provider, (ii) every provider serves no more customers than its capacity, (iii) the maximum possible number of customers are served, and (iv) the sum of Euclidean distances within the assigned provider-customer pairs is minimized. Although max-flow algorithms are applicable to this problem, they require the complete distance-based bipartite graph between the customer and provider sets. For large spatial datasets, this graph is expensive to compute and it may be too large to fit in main memory. Motivated by this fact, we propose efficient algorithms for\n            <jats:italic>optimal assignment<\/jats:italic>\n            that employ novel edge-pruning strategies, based on the spatial properties of the problem. Additionally, we develop incremental techniques that maintain an optimal assignment (in the presence of updates) with a processing cost several times lower than CCA recomputation from scratch. Finally, we present\n            <jats:italic>approximate<\/jats:italic>\n            (i.e., suboptimal) CCA solutions that provide a tunable trade-off between result accuracy and computation cost, abiding by theoretical quality guarantees. A thorough experimental evaluation demonstrates the efficiency and practicality of the proposed techniques.\n          <\/jats:p>","DOI":"10.1145\/1735886.1735888","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T14:14:06Z","timestamp":1272982446000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Optimal matching between spatial datasets under capacity constraints"],"prefix":"10.1145","volume":"35","author":[{"given":"Leong Hou","family":"U","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyriakos","family":"Mouratidis","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hung Hom, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,5,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"Ahuja , R. K. , Magnanti , T. L. , and Orlin , J. B . 1993 . Network Flows: Theory, Algorithms, and Applications , 1 st ed. Prentice Hall . Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications, 1st ed. Prentice Hall.","edition":"1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.3.527"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584237"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186476"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1969.1054385"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015231126594"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110407"},{"volume-title":"Proceedings of the International Symposium on Advances in Spatial Databases (SSD). 67--82","author":"Ester M.","key":"e_1_2_1_10_1","unstructured":"Ester , M. , Kriegel , H.-P. , and Xu , X . 1995. Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification . In Proceedings of the International Symposium on Advances in Spatial Databases (SSD). 67--82 . Ester, M., Kriegel, H.-P., and Xu, X. 1995. Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification. In Proceedings of the International Symposium on Advances in Spatial Databases (SSD). 67--82."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585996"},{"key":"e_1_2_1_14_1","unstructured":"Gusfield D. and Irving R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press.   Gusfield D. and Irving R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_17_1","first-page":"595","article-title":"A polynomial simplex method for the assignment problem. Opera","volume":"31","author":"Hung M.","year":"1983","unstructured":"Hung , M. 1983 . A polynomial simplex method for the assignment problem. Opera . Res. 31 , 595 -- 600 . Hung, M. 1983. A polynomial simplex method for the assignment problem. Opera. Res. 31, 595--600.","journal-title":"Res."},{"volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 439--450","author":"Irving R. W.","key":"e_1_2_1_18_1","unstructured":"Irving , R. W. , Manlove , D. , and Scott , S . 2003. Strong stability in the hospitals\/residents problem . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 439--450 . Irving, R. W., Manlove, D., and Scott, S. 2003. Strong stability in the hospitals\/residents problem. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 439--450."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_20_1","unstructured":"Mills-Tettey G. A. Stentz A. T. and Dias M. B. 2007. The dynamic Hungarian algorithm for the assignment problem with changing costs. Tech. rep. CMU-RI-TR-07-27 Robotics Institute.  Mills-Tettey G. A. Stentz A. T. and Dias M. B. 2007. The dynamic Hungarian algorithm for the assignment problem with changing costs. Tech. rep. CMU-RI-TR-07-27 Robotics Institute."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0045-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"volume-title":"Network Programming","author":"Murty K. G.","key":"e_1_2_1_23_1","unstructured":"Murty , K. G. 1992. Network Programming . Prentice-Hall . Murty, K. G. 1992. Network Programming. Prentice-Hall."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_1_25_1","unstructured":"Orlin J. B. and Lee Y. 1993. QuickMatch--A very fast algorithm for the assignment problem. Working papers 3547-93. Sloan School of Management MIT.  Orlin J. B. and Lee Y. 1993. QuickMatch--A very fast algorithm for the assignment problem. Working papers 3547-93. Sloan School of Management MIT."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 507--518","author":"Sellis T. K.","key":"e_1_2_1_28_1","unstructured":"Sellis , T. K. , Roussopoulos , N. , and Faloutsos , C . 1987. The R+-tree: A dynamic index for multi-dimensional objects . In Proceedings of the International Conference on Very Large Databases (VLDB). 507--518 . Sellis, T. K., Roussopoulos, N., and Faloutsos, C. 1987. The R+-tree: A dynamic index for multi-dimensional objects. In Proceedings of the International Conference on Very Large Databases (VLDB). 507--518."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1030.0073"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842247"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.05.004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.85"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376621"},{"volume-title":"Approximation Algorithms forFacility Location Problems (Lecture Notes)","author":"Vygen J.","key":"e_1_2_1_34_1","unstructured":"Vygen , J. 2004. Approximation Algorithms forFacility Location Problems (Lecture Notes) . University of Bonn. Vygen, J. 2004. Approximation Algorithms forFacility Location Problems (Lecture Notes). University of Bonn."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 579--590","author":"Wong R. C.-W.","key":"e_1_2_1_35_1","unstructured":"Wong , R. C.-W. , Tao , Y. , Fu , A. W.-C. , and Xiao , X . 2007. On efficient spatial matching . In Proceedings of the International Conference on Very Large Databases (VLDB). 579--590 . Wong, R. C.-W., Tao, Y., Fu, A. W.-C., and Xiao, X. 2007. On efficient spatial matching. In Proceedings of the International Conference on Very Large Databases (VLDB). 579--590."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007619"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 643--654","author":"Zhang D.","key":"e_1_2_1_37_1","unstructured":"Zhang , D. , Du , Y. , Xia , T. , and Tao , Y . 2006. Progressive computation of the min-dist optimal-location query . In Proceedings of the International Conference on Very Large Databases (VLDB). 643--654 . Zhang, D., Du, Y., Xia, T., and Tao, Y. 2006. Progressive computation of the min-dist optimal-location query. In Proceedings of the International Conference on Very Large Databases (VLDB). 643--654."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1735886.1735888","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1735886.1735888","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:33Z","timestamp":1750250733000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1735886.1735888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1145\/1735886.1735888"],"URL":"https:\/\/doi.org\/10.1145\/1735886.1735888","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}