Researchers Qian Zou, Lizhen Wang, Peizhong Yang, and Hongmei Chen have introduced a computational framework called DCG-Miner to discover dynamic region co-location patterns in spatial datasets. Traditional spatial data mining identifies static co-occurrences of features, such as schools and supermarkets consistently appearing near one another, yet real-world landscapes evolve dynamically over time. To capture how the appearance and disappearance of physical entities correlate within localized zones, the researchers formulated dynamic region co-location patterns, termed DRCPs. By incorporating temporal transitions directly into spatial pattern mining, the method detects synchronized shifts, such as emerging commercial districts or ecological shifts where one species suppresses another. Evaluated across synthetic data and urban point-of-interest records from Beijing and Shanghai spanning 2014 to 2021, the system overcomes conventional limitations in spatial partitioning and prevalence measurement.
Existing spatial pattern mining techniques encounter two persistent challenges when applied to dynamic geographic data: an inability to model changing features and severe inefficiencies in spatial partitioning. While classic tools track static co-location, spatial objects constantly emerge or vanish over time, creating dynamic relationships such as rising water hyacinth populations coinciding with declining algae. Similarly, in thriving urban nightlife districts, newly established restaurants, hotels, and bars frequently emerge in unison. Previous attempts to partition geographic areas into sub-regions relied either on rigid rule-based boundaries or clustering algorithms. Rule-based partitions, often drawn along road networks, frequently dissect natural spatial clusters and sever valid connections between neighboring entities. Conversely, conventional clustering approaches often produce skewed groupings where a single partition contains only one type of feature, rendering co-location analysis impossible.
To overcome these obstacles, the research team established explicit mathematical definitions for dynamic features and dynamic instances within spatio-temporal databases. Under this model, the emergence of a spatial object type is designated with a new label, while its departure or closure is designated with a dead label. For instance, urban records track newly opened bank branches as dynamic instances of a new bank feature and closed dining establishments as dynamic instances of a dead restaurant feature. A dynamic database organizes these classified instances along with their exact spatial coordinates, while spatial neighborhood relationships are evaluated using Euclidean distance without temporal constraints. Two dynamic entities satisfy a neighborhood relationship if the Euclidean distance between their coordinates falls within a predefined threshold. Dynamic row instances are formed when dynamic instances covering all pattern features are pairwise spatial neighbors.
A critical innovation within DCG-Miner is a revised interest measure designed to prevent the discovery of spurious or illogical co-location patterns. In standard co-location mining, prevalence is evaluated using participation ratios, but previous dynamic metrics divided participating instances solely by the count of instances belonging to that specific active state. Consequently, if a rare closure occurred near expanding establishments, such as four restaurants closing near newly opened banks, the pattern artificially registered a high participation ratio and was deemed prevalent. The authors resolved this distortion by formulating the dynamic participation ratio, which divides dynamic participating instances by the combined total of both new and dead instances for that feature. The overall dynamic participation index of a candidate pattern is defined as the minimum dynamic participation ratio among all its constituent dynamic features.
The authors demonstrated that the proposed dynamic participation ratio and dynamic participation index satisfy the vital anti-monotonicity property, also known as downward closure. In combinatorial pattern discovery, anti-monotonicity guarantees that if a pattern fails to meet the minimum prevalence threshold, any larger candidate pattern containing that subset cannot be prevalent. Lemma 1 proves that because any instance participating in a larger dynamic row instance necessarily participates in row instances of its sub-patterns, the dynamic participation index monotonically decreases or remains unchanged as features are added. This mathematical characteristic is essential for computational scalability, allowing DCG-Miner to prune unpromising feature combinations early in the search process without evaluating non-viable candidates. By establishing a user-specified threshold, the algorithm reliably rejects chance co-occurrences while retaining statistically robust dynamic regional associations.
Beyond prevalence metrics, the framework resolves regional partitioning bottlenecks through the concept of generalized maximal row instances, or GMRIs. Prior partitioning approaches that relied on maximal cliques, known as maximal row instances, required every dynamic instance in a group to be pairwise spatial neighbors with every other instance. The GMRI concept relaxes this pairwise requirement: it requires neighbor relationships only between dynamic instances belonging to different dynamic features, while allowing instances of the same feature to coexist without mutual connections. This relaxation compresses multiple overlapping maximal row instances into a unified generalized instance without sacrificing any underlying neighborhood relationships.
The authors provided rigorous theoretical proofs demonstrating that GMRIs preserve the complete spatial topology of the underlying dataset. Lemma 2 establishes that all pairwise neighborhood relationships between differing features remain intact within GMRIs, while Lemma 3 confirms that all dynamic participating instances necessary for evaluating candidate patterns are fully preserved. To generate these structures efficiently from large spatial databases, the researchers formulated the P_BK algorithm, an adapted variant of the classical Bron-Kerbosch maximal clique algorithm featuring pivoting and spatial partitioning. The procedure selects an unprocessed dynamic instance, constructs an expanded neighborhood partition around its spatial neighbors, and applies recursive pivoting checking neighbor constraints exclusively across differing dynamic features. The resulting GMRIs compress the spatial representation, drastically shrinking the candidate structures passed to subsequent clustering and mining stages.
To streamline downstream pattern extraction and eliminate redundant memory overhead, the framework organizes discovered GMRIs into a double-nested hash structure called GHash. Within this storage model, outer hash keys represent candidate dynamic feature combinations, while inner keys correspond to individual dynamic features mapped directly to their participating spatial instances. Once GMRIs are compiled, DCG-Miner identifies meaningful regional boundaries using Algorithm 2, known as RePart, which deploys the HDBSCAN density-based clustering algorithm. Each GMRI is abstracted into a representative spatial point, after which HDBSCAN discovers arbitrarily shaped clusters without requiring user-specified neighborhood distance parameters. A cluster filtering threshold of zero point five percent of total abstract points and a minimum cluster size of ten points eliminate trivial spatial noise, ensuring that only geographically dense sub-regions are retained.
The complete mining pipeline, formalized in Algorithm 3, integrates these components into an efficient end-to-end workflow. After P_BK extracts GMRIs and RePart delineates regional boundaries, the algorithm processes each identified region independently. For each region, a localized GHash structure is constructed to generate candidate feature combinations in sorted alphabetical order, calculate dynamic participation instances, and evaluate dynamic participation indices against the prevalence threshold. Prevalent patterns are recorded in the regional result set, while non-prevalent patterns generate candidate subsets for subsequent evaluation. The theoretical time complexity of DCG-Miner is governed by GMRI generation, regional clustering, GHash construction, and candidate evaluation, expressed as big-O of partition counts, squared GMRI counts, and candidate verification steps. Localized memory is promptly deallocated after processing each region, preventing cumulative memory escalation.
The research team implemented all algorithms in Java and conducted comprehensive empirical evaluations on a Windows 11 workstation equipped with an Intel Core i7-8700K processor running at 3.70 gigahertz and 128 gigabytes of main memory. Testing on real-world Beijing point-of-interest records spanning 2014 to 2021—encompassing 114 distinct features and 10,031 dynamic instances—demonstrated the practical superiority of the improved interest metric over traditional methods. When evaluated with a neighborhood distance threshold of 200 meters and a prevalence threshold of 0.3, the traditional dynamic metric erroneously identified a co-location between new banks and disappearing restaurants as prevalent.
Comparative evaluations against state-of-the-art regional and dynamic mining algorithms—specifically RCPM-MCC, FDPC-RCPM, and MDC—highlighted DCG-Miner’s unique analytical precision on urban datasets. While all evaluated algorithms identified the synchronized growth of new restaurants, new hotels, and new bars in active nightlife zones, baseline algorithms missed critical patterns elsewhere. In commercial areas, RCPM-MCC failed to discover the four-feature pattern linking new cafes, new convenience stores, new clothing shops, and new bars due to flawed regional boundary partitioning. Similarly, RCPM-MCC missed the co-location of newly established pharmacies and bakeries because sparse localized density led the algorithm to misclassify valid instances as noise. Most notably, DCG-Miner successfully captured inverse commercial transformations, such as disappearing restaurants paired with newly opening clothing boutiques, providing urban planners with actionable evidence of functional retail turnover within evolving city neighborhoods.
Extensive computational benchmarking on Shanghai POI data containing 8,409 instances and synthetic datasets of up to 100,000 instances demonstrated that DCG-Miner consistently outperforms existing approaches in speed and scalability. On synthetic datasets generated across a 1,000 by 1,000 grid with 100 features and controlled clumpiness degrees, baseline algorithms encountered severe operational bottlenecks; FDPC-RCPM failed to complete execution when instances reached 100,000 due to memory exhaustion, and both FDPC-RCPM and MDC failed to deliver results within 24 hours when prevalence thresholds dropped below 0.2. In contrast, DCG-Miner maintained low execution times, reusing saved row instances across varying prevalence thresholds and compressing maximal cliques into far fewer GMRIs as clumpiness increased. The authors noted that while DCG-Miner exhibits superior memory efficiency during standard workloads, processing data with exponential growth rates remains challenging, making distributed computing a promising future research direction.
Subject of Research: Dynamic spatial co-location pattern mining using generalized maximal row instances
Article Title: Dynamic Region Co-location Pattern Discovery: An Efficient Approach Based on Generalized Maximal Row Instances
Article References: Zou, Q., Wang, L., Yang, P., & Chen, H. (2026). Dynamic Region Co-location Pattern Discovery: An Efficient Approach Based on Generalized Maximal Row Instances. Data Science and Engineering, 11(3), 560-578. https://doi.org/10.1007/s41019-025-00323-9
Image Credits: AI Generated
DOI: 10.1007/s41019-025-00323-9
Keywords: spatial data mining, dynamic co-location patterns, DCG-Miner, urban computing, spatial algorithms, data science, spatio-temporal analysis, point-of-interest data, Dynamic, Region, Co-location, Pattern
News Source: Denise Maddox. (November 9, 2026). Scientists Develop DCG-Miner Algorithm to Track Dynamic Spatial Co-Location Patterns. Scienmag.
