Capacity constrained assignment in spatial databases

ABSTRACT

Given 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∈Q^q.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.

REFERENCES

• 1: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, first edition, 1993.
• 2: N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD, 1990.
• 3: T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6(2):153--180, 2002.
• 4: A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. Closest Pair Queries in Spatial Databases. In SIGMOD, 2000.
• 5: A. V. Goldberg and R. Kennedy. An Efficient Cost Scaling Algorithm for the Assignment Problem. Mathematical Programming, 71:153--177, 1995.
• 6: A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD, 1984.
• 7: G. R. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. ACM Trans. Database Syst., 24(2):265--318, 1999.
• 8: J. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32--38, 1957.
• 9: T. K. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB, 1987.
• 10: A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts. McGraw-Hill, fifth edition, 2005.
• 11: I. H. Toroslu and G. Üçoluk. Incremental Assignment Problem. Inf. Sci., 177:1523--1529, 2007.
• 12: L. H. U, N. Mamoulis, and M. L. Yiu. Continuous Monitoring of Exclusive Closest Pairs. In SSTD, 2007.
• 13: J. Vygen. Approximation Algorithms for Facility Location Problems (Lecture Notes). University of Bonn, 2004.
• 14: R. C.-W. Wong, Y. Tao, A. Fu, and X. Xiao. On Efficient Spatial Matching. In VLDB, 2007.
• 15: M. L. Yiu and N. Mamoulis. Clustering objects on a spatial network. In SIGMOD, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
optimal assignment, spatial databases