TY - GEN
T1 - Local co-location pattern detection
T2 - 10th International Conference on Geographic Information Science, GIScience 2018
AU - Li, Yan
AU - Shekhar, Shashi
N1 - Publisher Copyright:
© Yan Li and Shashi Shekhar.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - Given a set of spatial objects of different features (e.g., mall, hospital) and a spatial relation (e.g., geographic proximity), the problem of local co-location pattern detection (LCPD) pairs co-location patterns and localities such that the co-location patterns tend to exist inside the paired localities. A co-location pattern is a set of spatial features, the objects of which are often related to each other. Local co-location patterns are common in many fields, such as public security, and public health. For example, assault crimes and drunk driving events co-locate near bars. The problem is computationally challenging because of the exponential number of potential co-location patterns and candidate localities. The related work applies data-unaware or clustering heuristics to partition the study area, which results in incomplete enumeration of possible localities. In this study, we formally defined the LCPD problem where the candidate locality was defined using minimum orthogonal bounding rectangles (MOBRs). Then, we proposed a Quadruplet & Grid Filter-Refine (QGFR) algorithm that leveraged an MOBR enumeration lemma, and a novel upper bound on the participation index to efficiently prune the search space. The experimental evaluation showed that the QGFR algorithm reduced the computation cost substantially. One case study using the North American Atlas-Hydrography and U.S. Major City Datasets was conducted to discover local co-location patterns which would be missed if the entire dataset was analyzed or methods proposed by the related work were applied.
AB - Given a set of spatial objects of different features (e.g., mall, hospital) and a spatial relation (e.g., geographic proximity), the problem of local co-location pattern detection (LCPD) pairs co-location patterns and localities such that the co-location patterns tend to exist inside the paired localities. A co-location pattern is a set of spatial features, the objects of which are often related to each other. Local co-location patterns are common in many fields, such as public security, and public health. For example, assault crimes and drunk driving events co-locate near bars. The problem is computationally challenging because of the exponential number of potential co-location patterns and candidate localities. The related work applies data-unaware or clustering heuristics to partition the study area, which results in incomplete enumeration of possible localities. In this study, we formally defined the LCPD problem where the candidate locality was defined using minimum orthogonal bounding rectangles (MOBRs). Then, we proposed a Quadruplet & Grid Filter-Refine (QGFR) algorithm that leveraged an MOBR enumeration lemma, and a novel upper bound on the participation index to efficiently prune the search space. The experimental evaluation showed that the QGFR algorithm reduced the computation cost substantially. One case study using the North American Atlas-Hydrography and U.S. Major City Datasets was conducted to discover local co-location patterns which would be missed if the entire dataset was analyzed or methods proposed by the related work were applied.
KW - Co-location pattern
KW - Participation index
KW - Spatial heterogeneity
UR - http://www.scopus.com/inward/record.url?scp=85051320995&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85051320995&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.GIScience.2018.10
DO - 10.4230/LIPIcs.GIScience.2018.10
M3 - Conference contribution
AN - SCOPUS:85051320995
SN - 9783959770835
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 10th International Conference on Geographic Information Science, GIScience 2018
A2 - Griffin, Amy L.
A2 - Winter, Stephan
A2 - Sester, Monika
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 28 August 2018 through 31 August 2018
ER -