Grid-based optimization for DBSCAN clustering with periodic boundary conditions

Periodic boundary conditions (PBC) occur in scientific and geospatial data, where conventional density-based spatial clustering of applications with noise (DBSCAN) can fragment clusters at the domain seam. This study proposes GPDBSCAN, a replica-free grid-indexed DBSCAN algorithm for rectangular domains with periodic dimensions. GPDBSCAN canonicalizes periodic coordinates, indexes the original samples in \(ε \) -governed cells, wraps adjacent-cell coordinates across periodic faces, and verifies candidates with the minimum-image Euclidean distance. A cell-width construction with \(h≥ ε \) guarantees candidate completeness, and an adaptive strategy selects between offset enumeration and occupied-cell comparison. Formal analysis shows that the resulting neighborhoods and density-connected core components are equivalent to exact periodic DBSCAN. Experiments on representative and controlled synthetic datasets show identical PBC-DBSCAN and GPDBSCAN clusterings while GPDBSCAN consistently reduces peak Python-managed memory. Runtime is data-dependent: GPDBSCAN is faster when PBC replica overhead is large, but slower when grid-candidate costs dominate. On 17 IBTrACS dateline-crossing storm tracks, both periodic methods achieve ARI, NMI, and FMI of 1.000; GPDBSCAN reduces peak memory by 26.4% on the full subset but requires more runtime. GPDBSCAN is therefore most useful when exact periodic clustering and reduced memory overhead are priorities.