More Web Proxy on the site http://driver.im/

research-article

A neighborhood graph based approach to regional co-location pattern discovery: a summary of results

Authors:

Shashi Shekhar,

James A. Shine,

James P. Rogers,

Nicole WayantAuthors Info & Claims

GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 122 - 132

https://doi.org/10.1145/2093973.2093991

Published: 01 November 2011 Publication History

Abstract

Regional co-location patterns (RCPs) represent collections of feature types frequently located together in certain localities. For example, RCP < (Bar, Alcohol -- Crimes), Downtown >suggests that a co-location pattern involving alcohol-related crimes and bars is often localized to downtown regions. Given a set of Boolean feature types, their geo-located instances, a spatial neighbor relation, and a prevalence threshold, the RCP discovery problem finds all prevalent RCPs (pairs of co-locations and their prevalence localities). RCP discovery is important in many societal applications, including public safety, public health, climate science and ecology. The RCP discovery problem involves three major challenges: (a) an exponential number of subsets of feature types, (b) an exponential number of candidate localities and (c) a tradeoff between accurately modeling pattern locality and achieving computational efficiency. Related work does not provide computationally efficient methods to discover all interesting RCPs with their natural prevalence localities. To address these limitations, this paper proposes a neighborhood graph based approach that discovers all interesting RCPs and is aware of a pattern's prevalence localities. We identify partitions based on the pattern instances and neighbor graph. We introduce two new interest measures, a regional participation ratio and a regional participation index to quantify the strength of RCPs. We present two new algorithms, Pattern Space (PS) enumeration and Maximal Locality (ML) enumeration and show that they are correct and complete. Experiments using real crime datasets show that ML pruning outperforms PS enumeration.

References

[1]

L. C. P. department. lincoln city crime records, 2008.

[2]

W. Ding, C. F. Eick, X. Yuan, J. Wang, and J. Nicot. A framework for regional association rule mining and scoping in spatial datasets. GeoInformatica, 15(1):1--28, 2011.

Digital Library

[3]

C. C. Aggarwal, C. M. Procopiuc, and P. S. Yu. Finding localized associations in market basket data. IEEE Trans. Knowl. Data Eng., 14(1):51--62, 2002.

Digital Library

[4]

R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between sets of items in large databases. In P. Buneman and S. Jajodia, editors, Proceedings of the ACM SIGMOD, Washington, D. C., May 26--28, pages 207--216. ACM Press, 1993.

Digital Library

[5]

L. Anselin, J. Cohen, D. Cook, W. Gorr, and G. Tita. Spatial analyses of crime. Criminal justice, 4:213--262, 2000.

[6]

C. Brunsdon, A. Fotheringham, and M. Charlton. Geographically weighted regression: a method for exploring spatial nonstationarity. Geographical analysis, 28(4):281--298, 1996.

[7]

M. Celik, J. M. Kang, and S. Shekhar. Zonal co-location pattern discovery with dynamic parameters. In ICDM, pages 433--438, 2007.

Digital Library

[8]

J. E. Eck, S. Chainey, J. G. Cameron, M. Leitner, and R. E. Wilson. Mapping crime: Understanding hot spots. 2005.

[9]

J. E. Eck and D. Weisburd. Crime places in crime theory. Crime and place, crime prevention studies, 4:1--33, 1995.

[10]

C. F. Eick, R. Parmar, W. D. 0003, T. F. Stepinski, and J. Nicot. Finding regional co-location patterns for sets of continuous variables in spatial datasets. In GIS, page 30, 2008.

Digital Library

[11]

Y. Huang, S. Shekhar, and H. Xiong. Discovering colocation patterns from spatial data sets: A general approach. IEEE Trans. Knowl. Data Eng., 16(12):1472--1485, 2004.

Digital Library

[12]

E. H. Jacox and H. Samet. Spatial join techniques. ACM Trans. Database Syst., 32(1):7, 2007.

Digital Library

[13]

N. Levine. Crimestat: A spatial statistics program for the analysis of crime incident locations (v 3.1). Ned Levine & Associates, Houston, TX, and the National Institute of Justice, Washington, DC, 2007.

[14]

P. Mohan, S. Shekhar, J. A. Shine, and J. P. Rogers. Cascading spatio-temporal pattern discovery: A summary of results. In SDM, pages 327--338, 2010.

[15]

A. Okabe, B. Boots, and T. Satoh. A class of local and global k functions and their exact statistical methods. Perspectives on Spatial Data Analysis, page 101--112, 2010.

[16]

J. M. Patel and D. J. DeWitt. Partition based spatial-merge join. In ACM SIGMOD Record, volume 25, page 259--270, 1996.

Digital Library

Cited By

Li JWang LYang PZhou L(2024)A Novel Algorithm for Efficiently Mining Spatial Multi-Level Co-Location PatternsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338117836:9(4361-4374)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3381178
Liu YWang LYang PZhou L(2024)Mining Interpretable Regional Co-location Patterns Based on Urban Functional Region DivisionData Science and Engineering10.1007/s41019-024-00256-9Online publication date: 29-Aug-2024
https://doi.org/10.1007/s41019-024-00256-9
蒋希王丽TRAN V(2023)A parallel algorithm for regional co-location mining based on fuzzy density peak clusteringSCIENTIA SINICA Informationis10.1360/SSI-2022-0004Online publication date: 30-Jun-2023
https://doi.org/10.1360/SSI-2022-0004
Show More Cited By

Index Terms

A neighborhood graph based approach to regional co-location pattern discovery: a summary of results
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Data management systems
  2. Information systems applications
    1. Spatial-temporal systems

Recommendations

Density based co-location pattern discovery
GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Co-location pattern discovery is to find classes of spatial objects that are frequently located together. For example, if two categories of businesses often locate together, they might be identified as a co-location pattern; if several biologic species ...
A Constraint Neighborhood Based Approach for Co-location Pattern Mining
KSE '12: Proceedings of the 2012 Fourth International Conference on Knowledge and Systems Engineering

Driven by the ever increasing amount of spatial data collected by observations and GPS-enabled devices, mining such data for interesting or previously unknown patterns has become a major challenge. Among the many possible patterns, co-location patterns ...
Hyperclique pattern discovery

Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2011

559 pages

ISBN:9781450310314

DOI:10.1145/2093973

Editors:
Divyakant Agrawal
University of California at Santa Barbara
,
Isabel Cruz
University of Illinois at Chicago
,
Christian S. Jensen
Aarhus University, Denmark
,
Eyal Ofek
Microsoft, USA
,
Egemen Tanin
University of Melbourne, Australia

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

U.S. Army

Conference

GIS '11

Sponsor:

SIGSPATIAL

GIS '11: 19th SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 1 - 4, 2011

Illinois, Chicago

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
544
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JWang LYang PZhou L(2024)A Novel Algorithm for Efficiently Mining Spatial Multi-Level Co-Location PatternsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338117836:9(4361-4374)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3381178
Liu YWang LYang PZhou L(2024)Mining Interpretable Regional Co-location Patterns Based on Urban Functional Region DivisionData Science and Engineering10.1007/s41019-024-00256-9Online publication date: 29-Aug-2024
https://doi.org/10.1007/s41019-024-00256-9
蒋希王丽TRAN V(2023)A parallel algorithm for regional co-location mining based on fuzzy density peak clusteringSCIENTIA SINICA Informationis10.1360/SSI-2022-0004Online publication date: 30-Jun-2023
https://doi.org/10.1360/SSI-2022-0004
Wang LTran VDo T(2023)A Clique-Querying Mining Framework for Discovering High Utility Co-Location Patterns without Generating CandidatesACM Transactions on Knowledge Discovery from Data10.1145/361737818:1(1-42)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3617378
Hakyemez TBabaoglu CBasar A(2023)Putting spatial crime patterns in their social contexts through a contextualized colocation analysisGeoJournal10.1007/s10708-023-10931-588:6(5721-5741)Online publication date: 13-Sep-2023
https://doi.org/10.1007/s10708-023-10931-5
Uday Kiran RVeena PRavikumar PVenus Vikranth Raj BDao MZettsu KBommisetti S(2023)HDSHUI-miner: a novel algorithm for discovering spatial high-utility itemsets in high-dimensional spatiotemporal databasesApplied Intelligence10.1007/s10489-022-04436-w53:8(8536-8561)Online publication date: 11-Mar-2023
https://doi.org/10.1007/s10489-022-04436-w
Tran VPham CDo TPham H(2023)Discovering Prevalent Co-location Patterns Without Collecting Co-location InstancesIntelligent Information and Database Systems10.1007/978-981-99-5834-4_33(408-420)Online publication date: 5-Sep-2023
https://doi.org/10.1007/978-981-99-5834-4_33
Wang DWang LYang P(2023)ODSS-RCPM: An Online Decision Support System Based on Regional Co-location Pattern MiningDatabase Systems for Advanced Applications10.1007/978-3-031-30678-5_52(663-668)Online publication date: 14-Apr-2023
https://doi.org/10.1007/978-3-031-30678-5_52
Li YXie YShekhar S(2023)Spatial Data ScienceMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_18(401-422)Online publication date: 18-Aug-2023
https://doi.org/10.1007/978-3-031-24628-9_18
Chambers EDuchin MEdmonds REdwards PMatthews JPizzimenti ARichardson CRule PStern ARenz MSarwat M(2022)Aggregating community mapsProceedings of the 30th International Conference on Advances in Geographic Information Systems10.1145/3557915.3560961(1-12)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1145/3557915.3560961
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents