In Search of the Max Coverage Region in Road Networks

被引:1
作者
Fang, Lanting [1 ]
Kou, Ze [1 ]
Zhou, Yuzhang [1 ]
Zhang, Yudong [2 ]
Yuan, George Y. [3 ]
机构
[1] Southeast Univ, Sch Cyber Sci & Engn, Nanjing 211189, Peoples R China
[2] Univ Leicester, Sch Comp & Math Sci, Leicester LE1 7RH, England
[3] Thinvent Digital Technol Co Ltd, Nanchang 330096, Peoples R China
基金
英国生物技术与生命科学研究理事会; 中国国家自然科学基金; 英国医学研究理事会;
关键词
road network; region search; location selection; spatial data management; shortest distance; RECTANGLES; MAXIMUM;
D O I
10.3390/rs15051289
中图分类号
X [环境科学、安全科学];
学科分类号
08 ; 0830 ;
摘要
The widespread use of mobile devices has resulted in the generation of vast amounts of spatial data. The availability of such large-scale spatial data facilitates the development of data-driven approaches to address real-life problems. This paper introduces the max coverage region (MCR) problem in road networks and provides efficient solutions. Given a set of spatial objects and a coverage radius, the MCR problem aims to identify a location from the road network, so that we can reach as many spatial objects as possible within the given coverage radius from the location. This problem is fundamental to supporting many real-world applications. Given a road network and a set of sensors, this problem can be used to find the best location for a sensor maintenance station. This problem can also be applied in medical research, such as in a protein-protein interaction network, where the nodes represent proteins, the edges represent their interactions, and the weight of an edge represents confidence. We can use the MCR problem to find the set of interacting proteins with a confidence budget. We propose an efficient exact solution to solve the problem, where we reduce the MCR problem to an equivalent problem named the most overlapped interval and design an edge-level upper bound estimation method to reduce the search space. Furthermore, we propose two approximate solutions that sacrifice a little accuracy for much better efficiency. Our experimental study on real-road network datasets demonstrates the effectiveness and superiority of the proposed approaches.
引用
收藏
页数:20
相关论文
共 22 条
[11]   Towards Best Region Search for Data Exploration [J].
Feng, Kaiyu ;
Cong, Gao ;
Bhowmick, Sourav S. ;
Peng, Wen-Chih ;
Miao, Chunyan .
SIGMOD'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2016, :1055-1070
[12]  
Huang J., 2011, P ACM INT C INF KNOW, P2377, DOI DOI 10.1145/2063576
[13]   FINDING THE CONNECTED COMPONENTS AND A MAXIMUM CLIQUE OF AN INTERSECTION GRAPH OF RECTANGLES IN THE PLANE [J].
IMAI, H ;
ASANO, T .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1983, 4 (04) :310-323
[14]   Interactive Data Exploration Using Semantic Windows [J].
Kalinin, Alexander ;
Cetintemel, Ugur ;
Zdonik, Stan .
SIGMOD'14: PROCEEDINGS OF THE 2014 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2014, :505-516
[15]   Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data [J].
Kalinin, Alexander ;
Cetintemel, Ugur ;
Zdonik, Stan .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2015, 8 (10) :1094-1105
[16]   Class-based Conditional MaxRS Query in Spatial Data Streams [J].
Mostafiz, Mir Imtiaz ;
Mahmud, S. M. Farabi ;
Hussain, Muhammed Mas-ud ;
Ali, Mohammed Eunus ;
Trajcevski, Goce .
SSDBM 2017: 29TH INTERNATIONAL CONFERENCE ON SCIENTIFIC AND STATISTICAL DATABASE MANAGEMENT, 2017,
[17]   A UNIFIED ALGORITHM FOR FINDING MAXIMUM AND MINIMUM OBJECT ENCLOSING RECTANGLES AND CUBOIDS [J].
NANDY, SC ;
BHATTACHARYA, BB .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1995, 29 (08) :45-61
[18]   Approximate MaxRS in Spatial Databases [J].
Tao, Yufei ;
Hu, Xiaocheng ;
Choi, Dong-Wan ;
Chung, Chin-Wan .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2013, 6 (13) :1546-1557
[19]  
Wong RCW, 2009, PROC VLDB ENDOW, V2
[20]  
Xiao XK, 2011, PROC INT CONF DATA, P804, DOI 10.1109/ICDE.2011.5767845