A fast algorithm for combinatorial hotspot mining based on spatial scan statistic

Shin ichi Minato, Jun Kawahara, Fumio Ishioka, Masahiro Mizuta, Koji Kurihara

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)

    Abstract

    It is a popular and classical problem to detect a hotspot cluster from a statistical data which is partitioned by geographical regions such as prefectures or cities. Spatial scan statistic is a standard measure of likelihood ratio which has been widely used for testing hotspot clusters. In this work, we propose a very fast algorithm to enumerate all combinatorial regions which are more significant than a given threshold value. Our algorithm features the fast exploration by pruning the search space based on the partial monotonicity of the spatial scan statistic. Experimental results for a nation-wide 47 prefectures dataset show that our method generates the highest-ranked hotspot cluster in a time a million or more times faster than the previous naive search method. Our method works practically for a dataset with several hundreds of regions, and it will drastically accelerate hotspot analysis in various fields.

    Original languageEnglish
    Title of host publicationSIAM International Conference on Data Mining, SDM 2019
    PublisherSociety for Industrial and Applied Mathematics Publications
    Pages91-99
    Number of pages9
    ISBN (Electronic)9781611975673
    DOIs
    Publication statusPublished - 2019
    Event19th SIAM International Conference on Data Mining, SDM 2019 - Calgary, Canada
    Duration: May 2 2019May 4 2019

    Publication series

    NameSIAM International Conference on Data Mining, SDM 2019

    Conference

    Conference19th SIAM International Conference on Data Mining, SDM 2019
    Country/TerritoryCanada
    CityCalgary
    Period5/2/195/4/19

    Keywords

    • Combinatorial problem
    • Data mining
    • Enumeration algorithm
    • Hotspot detection
    • Scan statistic

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'A fast algorithm for combinatorial hotspot mining based on spatial scan statistic'. Together they form a unique fingerprint.

    Cite this