MC2LS: Towards Efficient Collective Location Selection in Competition
Lists
Only you see this
Abstract
Collective Location Selection (CLS) has received significant research attention in the spatial database community due to its wide range of applications. The CLS problem selects a group of <i>k</i> preferred locations among candidate sites to establish facilities, aimed at collectively attracting the maximum number of users. Existing studies commonly assume every user is located in a fixed position, without considering the competition between peer facilities. Unfortunately, in real markets, users are mobile and choose to patronize from a host of competitors, making traditional techniques unavailable. To this end, this paper presents the first effort on a CLS problem in competition scenarios, called <small>mc<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mn>2</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="li-ieq3-3510100.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>ls</small>, taking into account the mobility factor. Solving <small>mc<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mn>2</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="li-ieq4-3510100.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>ls</small> is a non-trivial task due to its NP-hardness. To overcome the challenge of pruning multi-point users with highly overlapped minimum boundary rectangles (MBRs), we exploit a position count threshold and design two square-based pruning rules. We introduce IQuad-tree, a user-MBR-free index, to benefit the hierarchical and batch-wise properties of the pruning rules. We propose an <inline-formula><tex-math notation="LaTeX">$(1-\frac{1}{e})$</tex-math></inline-formula>-approximate greedy solution to <small>mc<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mn>2</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="li-ieq6-3510100.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>ls</small> and incorporate a candidate-pruning strategy to further accelerate the computation for handling skewed datasets. Extensive experiments are conducted on real datasets, demonstrating the superiority of our proposed pruning rules and solution compared to the state-of-the-art techniques.
BibTeX
@article{wang2024mc,
author = {Meng Wang and Mei Zhao and Hui Li and Jiangtao Cui and Bo Yang and Tao Xue},
title = {{MC2LS: Towards Efficient Collective Location Selection in Competition}},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2024},
doi = {10.1109/tkde.2024.3510100},
}Loading related content...