Elliptical hotspot detection: A summary of results

Xun Tang; Emre Eftelioglu; Shashi Shekhar

doi:10.1145/2835185.2835192

Elliptical hotspot detection: A summary of results

Xun Tang, Emre Eftelioglu, Shashi Shekhar

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

Given a set of points in Euclidean space, a minimum log likelihood ratio threshold, and a statistical significance threshold, Elliptical Hotspot Detection (EHD) finds elliptical hotspot areas where the concentration of activities inside is significantly higher than outside. The EHD problem is important to many fields, such as criminology, transportation engineering, and epidemiology. Related work (e.g., SatScan) enumerates only circular candidates using activities as centers, and may miss many significant ellipses. EHD problem is challenging for two reasons, namely the large enumeration space and the lack of monotonicity of the log likelihood ratio. To overcome the challenges and limitations of the related work, this paper proposes a novel algorithm for EHD. A case study on real crime data shows that our algorithm is able to find hotspots that cannot be detected by the related work. Experimental evaluation shows that the proposed algorithm saves substantial amount of computation compared to the naïve approach.

Original language	English (US)
Title of host publication	Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015
Editors	Varun Chandola, Ranga Raju Vatsavai
Publisher	Association for Computing Machinery, Inc
Pages	15-24
Number of pages	10
ISBN (Electronic)	9781450339742
DOIs	https://doi.org/10.1145/2835185.2835192
State	Published - Nov 3 2015
Event	4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015 - Seattle, United States Duration: Nov 3 2015 → …

Publication series

Name	Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015

Other

Other	4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015
Country/Territory	United States
City	Seattle
Period	11/3/15 → …

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. 1029711, IIS-1320580, 0940818 and IIS-1218168, USDOD under Grant No. HM1582-08-1-0017, HM0210-13-1-0005, and University of Minnesota via U-Spatial. We would like to thank Kim Koffolt and the members of the University of Minnesota Spatial Computing Research Group for their comments.

Keywords

Hotspot detection
Spatial data mining
Statistical significance

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Publisher link

10.1145/2835185.2835192

Find It

Find It at U of M Libraries

Cite this

Tang, X., Eftelioglu, E., & Shekhar, S. (2015). Elliptical hotspot detection: A summary of results. In V. Chandola, & R. R. Vatsavai (Eds.), Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015 (pp. 15-24). (Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015). Association for Computing Machinery, Inc. https://doi.org/10.1145/2835185.2835192

Elliptical hotspot detection: A summary of results. / Tang, Xun; Eftelioglu, Emre; Shekhar, Shashi.
Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015. ed. / Varun Chandola; Ranga Raju Vatsavai. Association for Computing Machinery, Inc, 2015. p. 15-24 (Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Tang, X, Eftelioglu, E & Shekhar, S 2015, Elliptical hotspot detection: A summary of results. in V Chandola & RR Vatsavai (eds), Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015. Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015, Association for Computing Machinery, Inc, pp. 15-24, 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015, Seattle, United States, 11/3/15. https://doi.org/10.1145/2835185.2835192

Tang X, Eftelioglu E, Shekhar S. Elliptical hotspot detection: A summary of results. In Chandola V, Vatsavai RR, editors, Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015. Association for Computing Machinery, Inc. 2015. p. 15-24. (Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015). doi: 10.1145/2835185.2835192

Tang, Xun ; Eftelioglu, Emre ; Shekhar, Shashi. / Elliptical hotspot detection : A summary of results. Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015. editor / Varun Chandola ; Ranga Raju Vatsavai. Association for Computing Machinery, Inc, 2015. pp. 15-24 (Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015).

@inproceedings{ec36495911dd48d19cbe5407608c3b7f,

title = "Elliptical hotspot detection: A summary of results",

abstract = "Given a set of points in Euclidean space, a minimum log likelihood ratio threshold, and a statistical significance threshold, Elliptical Hotspot Detection (EHD) finds elliptical hotspot areas where the concentration of activities inside is significantly higher than outside. The EHD problem is important to many fields, such as criminology, transportation engineering, and epidemiology. Related work (e.g., SatScan) enumerates only circular candidates using activities as centers, and may miss many significant ellipses. EHD problem is challenging for two reasons, namely the large enumeration space and the lack of monotonicity of the log likelihood ratio. To overcome the challenges and limitations of the related work, this paper proposes a novel algorithm for EHD. A case study on real crime data shows that our algorithm is able to find hotspots that cannot be detected by the related work. Experimental evaluation shows that the proposed algorithm saves substantial amount of computation compared to the na{\"i}ve approach.",

keywords = "Hotspot detection, Spatial data mining, Statistical significance",

author = "Xun Tang and Emre Eftelioglu and Shashi Shekhar",

note = "Funding Information: This material is based upon work supported by the National Science Foundation under Grant No. 1029711, IIS-1320580, 0940818 and IIS-1218168, USDOD under Grant No. HM1582-08-1-0017, HM0210-13-1-0005, and University of Minnesota via U-Spatial. We would like to thank Kim Koffolt and the members of the University of Minnesota Spatial Computing Research Group for their comments.; 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015 ; Conference date: 03-11-2015",

year = "2015",

month = nov,

day = "3",

doi = "10.1145/2835185.2835192",

language = "English (US)",

series = "Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015",

publisher = "Association for Computing Machinery, Inc",

pages = "15--24",

editor = "Varun Chandola and Vatsavai, {Ranga Raju}",

booktitle = "Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015",

}

TY - GEN

T1 - Elliptical hotspot detection

T2 - 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015

AU - Tang, Xun

AU - Eftelioglu, Emre

AU - Shekhar, Shashi

N1 - Funding Information: This material is based upon work supported by the National Science Foundation under Grant No. 1029711, IIS-1320580, 0940818 and IIS-1218168, USDOD under Grant No. HM1582-08-1-0017, HM0210-13-1-0005, and University of Minnesota via U-Spatial. We would like to thank Kim Koffolt and the members of the University of Minnesota Spatial Computing Research Group for their comments.

PY - 2015/11/3

Y1 - 2015/11/3

N2 - Given a set of points in Euclidean space, a minimum log likelihood ratio threshold, and a statistical significance threshold, Elliptical Hotspot Detection (EHD) finds elliptical hotspot areas where the concentration of activities inside is significantly higher than outside. The EHD problem is important to many fields, such as criminology, transportation engineering, and epidemiology. Related work (e.g., SatScan) enumerates only circular candidates using activities as centers, and may miss many significant ellipses. EHD problem is challenging for two reasons, namely the large enumeration space and the lack of monotonicity of the log likelihood ratio. To overcome the challenges and limitations of the related work, this paper proposes a novel algorithm for EHD. A case study on real crime data shows that our algorithm is able to find hotspots that cannot be detected by the related work. Experimental evaluation shows that the proposed algorithm saves substantial amount of computation compared to the naïve approach.

AB - Given a set of points in Euclidean space, a minimum log likelihood ratio threshold, and a statistical significance threshold, Elliptical Hotspot Detection (EHD) finds elliptical hotspot areas where the concentration of activities inside is significantly higher than outside. The EHD problem is important to many fields, such as criminology, transportation engineering, and epidemiology. Related work (e.g., SatScan) enumerates only circular candidates using activities as centers, and may miss many significant ellipses. EHD problem is challenging for two reasons, namely the large enumeration space and the lack of monotonicity of the log likelihood ratio. To overcome the challenges and limitations of the related work, this paper proposes a novel algorithm for EHD. A case study on real crime data shows that our algorithm is able to find hotspots that cannot be detected by the related work. Experimental evaluation shows that the proposed algorithm saves substantial amount of computation compared to the naïve approach.

KW - Hotspot detection

KW - Spatial data mining

KW - Statistical significance

UR - http://www.scopus.com/inward/record.url?scp=84982861753&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84982861753&partnerID=8YFLogxK

U2 - 10.1145/2835185.2835192

DO - 10.1145/2835185.2835192

M3 - Conference contribution

AN - SCOPUS:84982861753

T3 - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015

SP - 15

EP - 24

BT - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2015

A2 - Chandola, Varun

A2 - Vatsavai, Ranga Raju

PB - Association for Computing Machinery, Inc

Y2 - 3 November 2015

ER -

Elliptical hotspot detection: A summary of results

Abstract

Publication series

Other

Bibliographical note

Keywords

UN SDGs

Publisher link

Find It

Other files and links

Fingerprint

Cite this