Spatial regionalization partitions a set of spatial polygons into contiguous, non-overlapping regions that optimize a specific objective function. This spatial operation serves diverse applications in environmental science, urban planning, public health, and economics. Due to the NP-hardness of this problem, most studies rely on heuristics and approximation techniques to balance solution quality with runtime efficiency. This tutorial reviews the main methods in the literature of spatial regionalization, organizing them into four categories: (i) linear and integer-programming formulations, (ii) top-down divisive strategies, (iii) bottom-up agglomerative strategies, and (iv) learning-based methods. For each category, we outline the core ideas and representative algorithms. We also discuss the open problems and future research directions.

Spatial regionalization seeks to partition a set of spatial polygons into contiguous, non-overlapping regions that optimize a specified objective function.This problem is fundamental in diverse applications across environmental science, urban planning, and public health, serving purposes such as resource allocation, policy formulation, and disease monitoring.Due to its computational complexity as an NP-hard problem, researchers typically rely on heuristics and approximation algorithms to achieve a practical balance between accuracy and runtime efficiency.This tutorial comprehensively reviews the main methodologies in the field, systematically categorizing them into three primary groups: (i) exact algorithms, (ii) top-down divisive strategies, and (iii) bottom-up agglomerative techniques.We detail each category by highlighting the core principles and representative algorithms.Furthermore, we identify and discuss open challenges in spatial regionalization.

The rapid expansion of location-based services has generated an unprecedented volume of spatial data. Spatial grouping queries, which categorize sets of spatial objects based on their geographical properties and data characteristics, are fundamental in uncovering significant patterns from large-scale spatial data. This query type is applicable to both spatial points and spatial polygons. In the realm of spatial polygons, regionalization serves as a crucial grouping query by organizing spatial polygons into regions. For spatial points, hotspot detection over spatial networks identifies clusters that demonstrate areas of high concentration. However, existing algorithms often lack scalability, struggle with large datasets, and fail to offer the expressiveness needed to handle flexible, user-defined constraints. To address these limitations, this paper introduces novel algorithms tailored for enhanced spatial grouping queries, including both regionalization and hotspot detection.

This paper demonstrates Pyneapple-L, an open-source library designed to enhance scalable spatial analysis through learning-based techniques. Through collaboration with social scientists and domain experts, we identify scalability challenges inherent in conventional spatial analysis methods, particularly as the data size increases. Pyneapple-L addresses these challenges by leveraging learning-based models to offer scalable solutions. We demonstrate two modules: scalable learning of spatial hotspots along spatial networks and augmented geographically weighted regression. To showcase Pyneapple-L, we have developed a user-friendly frontend web application to interact with different datasets, algorithms, model configurations, and visualize outcomes on interactive maps that support both broad and analytical views.

This paper demonstrates Pyneapple-R, an open-source library for scalable and expressive regionalization. Re-gionalization algorithms, also known as the ‘spatially-constrained clustering algorithms', have been widely adopted in spatial analysis tasks and now evolving towards a more large-scale and fine-scale direction. Through collaborations with social scientists and domain experts, we have identified emerging challenges in existing regionalization techniques, particularly regarding scalability and expressiveness. As data volumes continue to grow and regionalization algorithms become increasingly crucial to decision-making across various fields, enhancing these aspects can significantly impact the quality and effectiveness of re-search and applications. To address these challenges, Pyneapple-R provides novel algorithms for regionalization queries including the expressive p-regions algorithm, the scalable max-p regions algorithm, and the expressive max-p regions problem. To show-case Pyneapple-R, we have developed frontend web applications that enable users to interact with the algorithms by selecting constraints or simply engaging in conversation with the system to issue queries with the help of popular AI models. Interactive notebooks, designed to demonstrate the superiority and simplicity of Pyneapple-R, provide varying levels of detail to help social scientists and developers explore its full potential.

The widespread of geotagged data combined with modern map services allows for the accurate attachment of data to spatial networks. Applying statistical analysis, such as hotspot detection, over spatial networks is very important for precise quantification and patterns analysis, which empowers effective decision-making in various important applications. Existing hotspot detection algorithms on spatial networks either lack statistical evidence on detected hotspots, such as clustering, or they provide statistical evidence at a prohibitive computational overhead. In this paper, we propose efficient algorithms for detecting hotspots based on the network local K-function for predefined and unknown hotspot radii. The network local K-function is a widely adopted statistical approach for network pattern analysis that enables the understanding of the density and distribution of activities and events in the spatial network. However, its practical application has been limited due to the inefficiency of existing algorithms, particularly for large-sized networks. Extensive experimental evaluation using real and synthetic datasets shows that our algorithms are up to 28 times faster than the state-of-the-art algorithms in computing hotspots with a predefined radius and up to more than four orders of magnitude faster in identifying hotspots without a predefined radius.

MP-regions is an NP-hard problem that groups spatial areas to produce a maximum number of regions by enforcing a user-defined constraint at the regional level. Existing approximate algorithms for MP-regions do not scale for large datasets due to their high computational cost. This paper introduces SMP; a scalable technique to support MP-regions on large datasets. SMP works on two stages. The first stage finds an initial solution through randomized search, and the second stage improves this solution through efficient heuristic search. SMP optimizes the region building efficiency and quality by tuning the randomized area selection to trade-off runtime with region homogeneity. The experimental evaluation shows the superiority of our technique to support an order of magnitude larger datasets efficiently compared to the state-of-the-art techniques while producing high-quality solutions.

Spatial keyword queries have been popular in the research community for over a decade due to the explosive growth in user-generated data and its prime applications in different domains. kNN queries make a major category of spatial keyword queries that is heavily studied. However, the expressiveness of existing kNN queries is limited in supporting negative keyword predicates, e.g., find tweets with keywords "Chipotle" but NOT "Chipotle sauce", which have prime applications. In addition, existing architectures suffer from a lack of generality for different types of kNN queries. This paper proposes U-ASK; a Unified Architecture for Spatial-Keyword query supporting negative keyword predicates. U-ASK includes an indexing framework named TEQ (Textual-Enhanced Quadtree) and a query processor POWER (Parallel bOttom-up search With incrEmental pRuning) that handle various forms of kNN spatial keyword queries with negative keyword predicates. The experimental evaluation on real tweet datasets demonstrates up to 30× faster runtime compared to the state-of-the-art algorithms.

The excessive amount of data that online users produce through social media platforms provides valuable insights about users and communities at scale. Existing techniques have not fully exploited such data to help practitioners perform a deep analysis of large online communities. Lack of scalability hinders analyzing communities of large sizes and requires tremendous system resources and unacceptable runtime. This paper introduces a new analytical query that reveals the top-k posts of interest of a given user community over a period of time and in a certain location. We propose a novel indexing framework that captures the interactions of community users to provide a low query latency. Moreover, we propose efficient query algorithms that utilize the index content to prune the search space. The extensive experimental evaluation on real data has shown the superiority of our techniques and their scalability to support large online communities.

This paper introduces a generalized spatial regionalization problem, namely, PRUC ( P -Regions with User-defined Constraint) that partitions spatial areas into homogeneous regions. PRUC accounts for user-defined constraints imposed over aggregate region properties. We show that PRUC is an NP-Hard problem. To solve PRUC, we introduce GSLO (Global Search with Local Optimization), a parallel stochastic regionalization algorithm. GSLO is composed of two phases: (1) Global Search that initially partitions areas into regions that satisfy a user-defined constraint, and (2) Local Optimization that further improves the quality of the partitioning with respect to intra-region similarity. We conduct an extensive experimental study using real datasets to evaluate the performance of GSLO. Experimental results show that GSLO is up to 100× faster than the state-of-the-art algorithms. GSLO provides partitioning that is up to 6× better with respect to intra-region similarity. Furthermore, GSLO is able to handle 4× larger datasets than the state-of-the-art algorithms.