主题：Expediting Location-based Max-Coverage Query Processing on Massive Trajectory Data

时间： 11月6日，周五，10：15-11：00

地点：郁A102会议室

主讲：微软研究员-Jie Bao

Abstract: A location-based max-coverage query aims to find k locations within a given spatial region, which covers the maximum number of unique trajectories. This type of query is vital in many urban applications, including: 1) advertisement, 2) resource allocation, and 3) business location selection.  Unfortunately, finding the optimal result of the query is equivalent to an NP-hard problem (i.e., submodular maximization problem), and the greedy algorithm has been proven to be the most efficient polynomial time solution with the guarantee of (1-1/e) approximation. In many application scenarios, users generate location-based max-coverage queries with arbitrary user-specified parameters, (i.e., spatial area and location budget k), which makes it challenging to scale up and support such queries in a large-scale data management system, due to the high computational cost.

In this talk, we will discuss both efficient optimal and approximate solutions to location-based max-coverage queries. For queries with a small spatial region and location budget k, we develop an efficient optimal solution, using vertices grouping and best-first pruning techniques. On the other hand, for queries with large spatial area and location budget k, we propose an efficient greedy-based approximate algorithm, which employs: 1) efficient updating strategy, 2) index partition and 3) workload-based optimization techniques. Based on the large scale experiments performed over 4 million taxi trajectories collected from City of Tianjin, we show that our proposed solutions improve the query response time up to ten times comparing to the baseline approaches. All results are reproducible through our online query processing system.

Short Bio:  Dr. Jie Bao, currently, is an associate researcher at urban computing group in MSR Asia. His research interests lie broadly over spatio-temporal data management and location-based services. Before joining MSRA, he got his BS, MS, and Ph.D. degree in Computer Science from Zhejiang University, Auburn University and University of Minnesota at Twin Cities, respectively.