Publications -> Conference Papers

Towards Best Region Search for Data Exploration


Authors: K. Feng, G. Cong, S. S. Bhowmick, W.-C. Peng, and C. Miao
Title: Towards Best Region Search for Data Exploration
Abstract: The increasing popularity and growth of mobile devices and location-based services enable us to utilize large-scale geo-tagged data to support novel location-based applications. This paper introduces a novel problem called the best region search (BRS) problem and provides efficient solutions to it. Given a set O of spatial objects, a submodular monotone aggregate score function, and the size a × b of a query rectangle, the BRS problem aims to find a×b rectangular region such that the aggregate score of the spatial objects inside the region is maximized. This problem is fundamental to support several real-world applications such as most influential region search (e.g., the best location for a signage to attract most audience) and most diversified region search (e.g., region with most diverse facilities). We propose an efficient algorithm called SliceBRS to find the exact answer to the BRS problem. Furthermore, we propose an approximate solution called CoverBRS and prove that the answer found by it is bounded by a constant. Our experimental study with real-world datasets and applications demonstrates the effectiveness and superiority of our proposed algorithms.
Keywords: 
Conference Name: 2016 International Conference on Management of Data (SIGMOD’16)
Location: San Francisco, USA
Publisher: ACM
Year: 2016
Accepted PDF File: Towards_Best_Region_Search_for_Data_Exploration_accepted.pdf
Permanent Link: https://dx.doi.org/10.1145/2882903.2882960
Reference: K. Feng, G. Cong, S. S. Bhowmick, W.-C. Peng, and C. Miao, “Towards best region search for data exploration,” in Proceedings of the 2016 International Conference on Management of Data (SIGMOD’16). ACM, June–July 2016, pp. 1055–1070.
bibtex: 
@inproceedings{LILY-c83, 
    author	= {Feng, Kaiyu and Cong, Gao and  Bhowmick, Sourav S. and Peng, Wen-Chih and Miao, Chunyan},
    title	= {Towards Best Region Search for Data Exploration},  
    booktitle	= {Proceedings of the 2016 International Conference on Management of Data (SIGMOD'16)}, 
    year		= {2016}, 
    month	= {June--July}, 
    pages	= {1055-1070}, 
    location	= {San Francisco, USA},
    publisher	= {ACM},
 }