skip to main content
10.1145/2463676.2465321acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
research-article

On optimal worst-case matching

Published: 22 June 2013 Publication History

Abstract

Bichromatic reverse nearest neighbor (BRNN) queries have been studied extensively in the literature of spatial databases. Given a set P of service-providers and a set O of customers, a BRNN query is to find which customers in O are "interested" in a given service-provider in P. Recently, it has been found that this kind of queries lacks the consideration of the capacities of service-providers and the demands of customers. In order to address this issue, some spatial matching problems have been proposed, which, however, cannot be used for some real-life applications like emergency facility allocation where the maximum matching cost (or distance) should be minimized. In this paper, we propose a new problem called Spatial Matching for Minimizing Maximum matching distance (SPM-MM). Then, we design two algorithms for SPM-MM, Threshold-Adapt and Swap-Chain. Threshold-Adapt is simple and easy to understand but not scalable to large datasets due to its relatively high time/space complexity. Swap-Chain, which follows a fundamentally different idea from Threshold-Adapt, runs faster than Threshold-Adapt by orders of magnitude and uses significantly less memory. We conducted extensive empirical studies which verified the efficiency and scalability of Swap-Chain.

References

[1]
Fire services department, hong kong: Performance pledge 2012. http://www.hkfsd.gov.hk/eng/performance.html.
[2]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[3]
E. Bortnikov, S. Khuller, J. Li, Y. Mansour, and J. S. Naor. The load-distance balancing problem. Networks, 2010.
[4]
R. E. Burkard, M. Dell'Amico, and S. Martello. Assignment problems. Society for Industrial Mathematics, 2009.
[5]
M. S. Chang, C. Y. Tang, and R. C. T. Lee. Solving the euclidean bottleneck matching problem by k-relative neighborhood graphs. Algorithmica, 8(1):177--194, 1992.
[6]
B. Chazelle. New upper bounds for neighbor searching. In Information and Control, 1986.
[7]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. 2009.
[8]
T. Dokka, A. Kouvela, and F. C. R. Spieksma. Approximating the multi-level bottleneck assignment problem. In Operations Research Letter, 2012.
[9]
A. Efrat, A. Itai, and M. J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1):1--28, 2001.
[10]
A. Efrat and M. J. Katz. Computing euclidean bottleneck matchings in higher dimensions. Information processing letters, 2000.
[11]
H. N. Gabow and R. E. Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411--417, 1988.
[12]
D. Gale and L. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly, 69:9--15, 1962.
[13]
A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. F. Werneck. Maximum flows by incremental breadth-first search. In ESA, 2011.
[14]
O. Gross. The bottleneck assignment problem. The Rand Corporation, 1959.
[15]
D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 1985.
[16]
J. E. Hopcroft and R. M. Karp. A n5/2 algorithm for maximum matchings in bipartite graphs. In Switching and Automata Theory, 1971.
[17]
J. M. Kang, M. F. Mokbel, S. Shekhar, T. Xia, and D. Zhang. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In ICDE, 2007.
[18]
F. Korn and S. Muthukrishnan. Influence sets based on reverse nearest neighbor queries. In SIGMOD, 2000.
[19]
C. Long, R. C.-W. Wong, P. S. Yu, and M. Jiang. On optimal worst-case matching (technical report). In http://www.cse.ust.hk/~raywong/paper/spm-mm-technical.pdf, 2013.
[20]
Statistics Canada. Postal code conversion file (pccf). In http://www5.statcan.gc.ca/bsolc/olc-cel/olc-cel?lang=eng&catno=92F0153X, 2012.
[21]
L. H. U, K. Mouratidis, and N. Mamoulis. Continuous spatial assignment of moving users. VLDB Journal, 2010.
[22]
L. H. U, M. L. Yiu, K. Mouratidis, and N. Mamoulis. Capacity constrained assignment in spatial databases. In ACM SIGMOD, 2008.
[23]
T. Verma and D. Batra. Maxflow revisited: An empirical comparison of maxflow algorithms for dense vision problems. 2012.
[24]
R. C.-W.Wong, M. T. Özsu, P. S. Yu, A. W.-C. Fu, and L. Liu. Efficient method for maximizing bichromatic reverse nearest neighbor. Proc. VLDB Endow., 2(1), Aug. 2009.
[25]
R. C.-W.Wong, Y. Tao, A. W.-C. Fu, and X. Xiao. On efficient spatial matching. VLDB, 2007.
[26]
H. Q. Ye and D. D. Yao. Utility-maximizing resource control: Diffusion limit and asymptotic optimality for a two-bottleneck model. In Operations Research, 2010.

Cited By

View all
  • (2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
  • (2022)Task Scheduling in Three-Dimensional Spatial Crowdsourcing: A Social Welfare PerspectiveIEEE Transactions on Mobile Computing10.1109/TMC.2022.3175305(1-1)Online publication date: 2022
  • (2022)Design of personalized recommendation method for entertainment news based on collaborative filtering algorithm2022 International Symposium on Advances in Informatics, Electronics and Education (ISAIEE)10.1109/ISAIEE57420.2022.00108(494-500)Online publication date: Dec-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data
June 2013
1322 pages
ISBN:9781450320375
DOI:10.1145/2463676
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. bottleneck matching
  2. optimal worst-case spatial matching

Qualifiers

  • Research-article

Conference

SIGMOD/PODS'13
Sponsor:

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;
Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
  • (2022)Task Scheduling in Three-Dimensional Spatial Crowdsourcing: A Social Welfare PerspectiveIEEE Transactions on Mobile Computing10.1109/TMC.2022.3175305(1-1)Online publication date: 2022
  • (2022)Design of personalized recommendation method for entertainment news based on collaborative filtering algorithm2022 International Symposium on Advances in Informatics, Electronics and Education (ISAIEE)10.1109/ISAIEE57420.2022.00108(494-500)Online publication date: Dec-2022
  • (2022)Privacy-Preserving Online Task Assignment in Spatial Crowdsourcing: A Graph-based ApproachIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796827(570-579)Online publication date: 2-May-2022
  • (2022)Big Data-Driven Stable Task Allocation in Ride-Hailing ServicesDatabase Systems for Advanced Applications. DASFAA 2022 International Workshops10.1007/978-3-031-11217-1_21(291-300)Online publication date: 16-Jul-2022
  • (2021)Deep Reinforcement Learning for Task Assignment in Spatial Crowdsourcing and SensingIEEE Sensors Journal10.1109/JSEN.2021.305737621:22(25323-25330)Online publication date: 15-Nov-2021
  • (2021)Dynamic data compression algorithm for wireless sensor networks based on grid deduplication2021 International Conference on Communications, Information System and Computer Engineering (CISCE)10.1109/CISCE52179.2021.9445966(178-182)Online publication date: 14-May-2021
  • (2020)A Dynamic Task Assignment Framework based on Prediction and Adaptive Batching2020 IEEE 39th International Performance Computing and Communications Conference (IPCCC)10.1109/IPCCC50635.2020.9391525(1-8)Online publication date: 6-Nov-2020
  • (2020)Spatial Two-Sided Online Bottleneck Matching With DeadlinesIEEE Access10.1109/ACCESS.2020.29824238(57772-57785)Online publication date: 2020
  • (2019)Minimizing Maximum Delay of Task Assignment in Spatial Crowdsourcing2019 IEEE 35th International Conference on Data Engineering (ICDE)10.1109/ICDE.2019.00131(1454-1465)Online publication date: Apr-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media