File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Capacity constrained assignment in spatial databases

TitleCapacity constrained assignment in spatial databases
Authors
KeywordsOptimal Assignment
Spatial Databases
Issue Date2008
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/sigmod
Citation
Proceedings Of The Acm Sigmod International Conference On Management Of Data, 2008, p. 15-27 How to Cite?
AbstractGiven a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q ∈ Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M ⊆ Q × P such that (i) each point q ∈ Q (p ∈ P) appears at most k times (at most once) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|, Σq∈Qq.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs) is minimized. Thus, the CCA problem is to identify the assignment with the optimal overall quality; intuitively, the quality of q's service to p in a given (q, p) pair is anti-proportional to their distance. Although max-flow algorithms are applicable to this problem, they require the complete distance-based bipartite graph between Q and P. 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 approximate (i.e., suboptimal) CCA solutions that provide a 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. Copyright 2008 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/151934
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorHou U, Len_US
dc.contributor.authorYiu, MLen_US
dc.contributor.authorMouratidis, Ken_US
dc.contributor.authorMamoulis, Nen_US
dc.date.accessioned2012-06-26T06:31:10Z-
dc.date.available2012-06-26T06:31:10Z-
dc.date.issued2008en_US
dc.identifier.citationProceedings Of The Acm Sigmod International Conference On Management Of Data, 2008, p. 15-27en_US
dc.identifier.issn0730-8078en_US
dc.identifier.urihttp://hdl.handle.net/10722/151934-
dc.description.abstractGiven a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q ∈ Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M ⊆ Q × P such that (i) each point q ∈ Q (p ∈ P) appears at most k times (at most once) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|, Σq∈Qq.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs) is minimized. Thus, the CCA problem is to identify the assignment with the optimal overall quality; intuitively, the quality of q's service to p in a given (q, p) pair is anti-proportional to their distance. Although max-flow algorithms are applicable to this problem, they require the complete distance-based bipartite graph between Q and P. 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 approximate (i.e., suboptimal) CCA solutions that provide a 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. Copyright 2008 ACM.en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/sigmoden_US
dc.relation.ispartofProceedings of the ACM SIGMOD International Conference on Management of Dataen_US
dc.subjectOptimal Assignmenten_US
dc.subjectSpatial Databasesen_US
dc.titleCapacity constrained assignment in spatial databasesen_US
dc.typeConference_Paperen_US
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_US
dc.identifier.authorityMamoulis, N=rp00155en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/1376616.1376621en_US
dc.identifier.scopuseid_2-s2.0-57149136904en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-57149136904&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage15en_US
dc.identifier.epage27en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridHou U, L=13605267100en_US
dc.identifier.scopusauthoridYiu, ML=8589889600en_US
dc.identifier.scopusauthoridMouratidis, K=9637493700en_US
dc.identifier.scopusauthoridMamoulis, N=6701782749en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats