New Algorithm Tracks Patterns That Grow Stronger in Evolving Spatial Data

Researchers have introduced a new way to find patterns in spatial data that keep getting stronger over time, even when the underlying database is constantly changing. The method, described in a study published in Data Science and Engineering, tackles a long-standing blind spot in spatial co-location pattern mining: what happens when new instances of features keep appearing in a database that never stands still.

Sustained emerging spatio-temporal co-occurrence patterns, or SECOPs, are subsets of spatial features whose instances consistently appear in close proximity across both space and time. Discovering them is valuable in fields ranging from public health, where they can help predict emerging infectious diseases, to the military, where they can support forecasting of defense and attack intent, to ecology, where they can help identify novel predator-prey interactions. The concept was originally developed for moving objects, with a pattern labeled sustained emerging when its participation index, a standard prevalence measure in co-location mining, shows a monotonic increase over continuous time intervals.

The participation index is defined as the minimum participation ratio of all features in a co-location pattern. For a pattern containing several features, each feature’s participation ratio is the fraction of its instances that appear in row-instances of the pattern, where a row-instance is a collection of mutually neighboring instances that collectively cover all features in the pattern. The measure gained wide application after Shekhar and Huang introduced it because of its statistical significance and its satisfaction of the antimonotone property, which allows efficient pruning of candidate patterns during mining.

The problem, as the authors Liuwei Li, Peizhong Yang, Lizhen Wang and Hongmei Chen demonstrate, is that the participation index can mislead when the database is dynamic. New instances continuously emerge, causing complex changes in the neighbor relationships between instances. The team illustrates the issue with an influenza and migrating birds example: as new cases of influenza appear near both existing and newly arriving migrating birds, the pattern involving the two features actually occurs more frequently over time. Yet when the participation index is calculated at the two time slots, the value stays flat at 0.8, so the pattern fails to be flagged as sustained emerging even though its co-occurrence has clearly intensified.

A second distortion arises from heterogeneity in how quickly different features multiply. In urban development, for example, a surge of new coffee brands means coffee shops spring up on and near university campuses, so universities and coffee shops co-occur more frequently. But because many new coffee shops also open elsewhere in the city, the participation ratio of coffee shops in the pattern drops, dragging the participation index down with it. Existing methods would therefore miss this genuinely emerging pattern simply because one feature grew much faster than the other.

To fix both problems, the researchers propose a weighted emerging participation index, or WEPI. The measure builds on an emerging participation ratio that targets only old non-participation-instances from the previous time slot and new instances in the subsequent slot, capturing the probability that instances newly join a pattern. Because features with many new instances can still show low participation ratios, the ratio is weighted by an emerging intensity derived from a Gaussian kernel function. This intensity depends both on how much faster a feature’s instances grow relative to the slowest-growing feature in the pattern and on the average increase degree across the whole dataset, which is used as the kernel’s width parameter in a data-driven way.

One catch is that WEPI lacks the antimonotone property that classical measures enjoy. In the paper’s own example, the three-feature pattern {A, B, C} has a higher WEPI than its subpattern {B, C}, which means Apriori-style pruning cannot be applied directly. The authors resolve this by proving an upper bound on the weighted emerging participation ratio of features. When this upper bound falls below the user-specified sustained emerging threshold, all superpatterns containing the limiting feature can be safely pruned, narrowing the search space without sacrificing correctness.

Building on that pruning strategy, the team developed IM-DFS, an incremental mining algorithm based on depth-first search. Instead of regenerating complete table-instances for every time slot, IM-DFS searches for new participation-instances, reusing processed information from the previous time slot to shrink the candidate set. Backtracking search with a heuristic that prioritizes unverified instances speeds up the identification of incremental row-instances. The authors also discuss the completeness, correctness and time complexity of the algorithm, showing that the actual cost is far below the worst-case bound thanks to the pruning and optimization techniques.

Experiments on two real-world dynamic spatial datasets, point-of-interest data from Beijing and Shanghai covering 2014 to 2021, support both the effectiveness of the new measure and the efficiency of the algorithm. The Beijing dataset contains 95 features with instances growing from 4,496 to 13,686, while the Shanghai dataset has 71 features growing from 3,831 to 11,929. Examples such as {Artwork, Hostel, Nightclub} and {Post_office, Toilet} show patterns whose participation index decreases despite genuinely intensifying co-occurrence, and which WEPI correctly identifies. Conversely, patterns like {Bicycle_shop, Post_office} and {Pub, ATM, Hospital} can be wrongly flagged by traditional measures but are handled more reasonably by the weighted approach.

In efficiency comparisons against an adapted Non-overlapping incremental algorithm and an adapted Filter-Verification algorithm, IM-DFS ran faster across varying distance thresholds, sustained emerging thresholds and timeslot increments on both datasets. Ablation tests also showed that the pruning strategy substantially reduces the number of candidate patterns tested, so much so that running the algorithm without pruning exceeded 24 hours without producing results when processing all features. The authors note that users must still preset the distance and sustained emerging thresholds, which may require domain knowledge, and they plan future work on data-driven threshold selection and on extending the measure to diverse spatial data types.

Subject of Research: A new weighted measure and incremental mining algorithm for discovering sustained emerging spatio-temporal co-occurrence patterns in dynamic spatial databases

Article Title: Mining Sustained Emerging Spatio-Temporal Co-occurrence Patterns from Dynamic Spatial Databases

Article References: Li, L., Yang, P., Wang, L., & Chen, H. (2026). Mining Sustained Emerging Spatio-Temporal Co-occurrence Patterns from Dynamic Spatial Databases. Data Science and Engineering. https://doi.org/10.1007/s41019-026-00347-9

Image Credits: AI Generated

DOI: 10.1007/s41019-026-00347-9

Keywords: spatial data mining, co-location patterns, spatio-temporal patterns, participation index, incremental mining, depth-first search, dynamic spatial databases, Gaussian kernel, pruning strategy, point-of-interest data, pattern mining algorithms, spatial heterogeneity