File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal matching between spatial datasets under capacity constraints

TitleOptimal matching between spatial datasets under capacity constraints
Authors
KeywordsOptimal assignment
Spatial databases
Issue Date2010
Citation
ACM Transactions On Database Systems, 2010, v. 35 n. 2, article no. 9 How to Cite?
AbstractConsider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The Capacity Constrained Assignment (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 optimal assignment 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 approximate (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. © 2010 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/129985
ISSN
2023 Impact Factor: 2.2
2023 SCImago Journal Rankings: 1.730
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong RGCHKU 7155/09E
Research Center, School of Information Systems, Singapore Management University
Funding Information:

Supported by grant HKU 7155/09E from Hong Kong RGC, and by the Research Center, School of Information Systems, Singapore Management University.

References

 

DC FieldValueLanguage
dc.contributor.authorLeong, HUen_HK
dc.contributor.authorMouratidis, Ken_HK
dc.contributor.authorYiu, MLen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.date.accessioned2010-12-23T08:45:08Z-
dc.date.available2010-12-23T08:45:08Z-
dc.date.issued2010en_HK
dc.identifier.citationACM Transactions On Database Systems, 2010, v. 35 n. 2, article no. 9en_HK
dc.identifier.issn0362-5915en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129985-
dc.description.abstractConsider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The Capacity Constrained Assignment (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 optimal assignment 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 approximate (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. © 2010 ACM.en_HK
dc.languageengen_US
dc.relation.ispartofACM Transactions on Database Systemsen_HK
dc.subjectOptimal assignmenten_HK
dc.subjectSpatial databasesen_HK
dc.titleOptimal matching between spatial datasets under capacity constraintsen_HK
dc.typeArticleen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1145/1735886.1735888en_HK
dc.identifier.scopuseid_2-s2.0-77952028212en_HK
dc.identifier.hkuros176418en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77952028212&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume35en_HK
dc.identifier.issue2en_HK
dc.identifier.spage44en_US
dc.identifier.spagearticle no. 9-
dc.identifier.epagearticle no. 9-
dc.identifier.isiWOS:000277925600002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridLeong, HU=36020318000en_HK
dc.identifier.scopusauthoridMouratidis, K=9637493700en_HK
dc.identifier.scopusauthoridYiu, ML=8589889600en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.issnl0362-5915-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats