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

17 Citations (Scopus)

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.
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)
Pages845-856
Number of pages12
ISBN (Electronic)978-1-4503-2037-5
Publication statusPublished - 2013
Externally publishedYes

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

Cite this