On optimal worst-case matching

Cheng Long, Raymond Chi-Wing Wong, Philip S. Yu, Minhao Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings of the 2013 ACM SIGMOD International Conference on Management of Data
Place of PublicationNew York, USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages12
ISBN (Electronic)978-1-4503-2037-5
Publication statusPublished - 2013
Externally publishedYes


Dive into the research topics of 'On optimal worst-case matching'. Together they form a unique fingerprint.

Cite this