Machine learning models often struggle with raw geographic coordinates. Latitude and longitude are continuous, high-precision values that do not naturally fit into the discrete architectures used for natural language processing or formal state-based verification. To bridge this gap, researchers have converged on a strategy of spatial tokenization: partitioning continuous space into a discrete set of hierarchical cells.
By treating a location not as a pair of floats but as a "token" in a vocabulary, researchers can apply powerful sequence-modeling tools—from Markov chains to Transformers—to problems ranging from autonomous vehicle safety to geospatial reasoning in large language models (LLMs).
Bridging the Gap Between Space and Language
The primary intuition behind spatial tokenization is that geographic trajectories share a structural similarity with natural language. Just as a sentence is a sequence of discrete words, a movement path can be viewed as a sequence of visited regions.
Tsiligkaridis et al. demonstrate this by mapping GPS coordinates to a discrete vocabulary using hierarchical indexing. This allows their STARE model to treat agent trajectories as sequences suitable for self-supervised masked modeling, effectively "learning the language" of human mobility without requiring external map data. Similarly, Palowitch et al. use hierarchical grid cells as discrete tokens in sequence-to-sequence models to translate natural language descriptions (e.g., "a block north of the park") into precise geographic coordinates.
For LLMs, this discretization is essential for cross-modal reasoning. Huang et al. argue that representing coordinates as hierarchical tokens, such as S2 cells, allows models to treat locations as structured vocabulary. This enables the model to bridge the gap between continuous spatial data and the discrete token space of language, facilitating more robust reasoning between text and maps.
Multi-Scale Reasoning via Hierarchical Grids
A simple uniform grid often fails because spatial data exists at multiple scales; a taxi ride across a city requires different precision than an aircraft's flight path. Hierarchical systems like S2, H3, or quad-trees solve this by representing the Earth's surface as a nested set of cells.
Wang et al. utilize this in the ERNIE-GeoL model, transforming coordinates into a sequence of hierarchical identifiers. This converts spatial prediction into a multi-scale classification task, allowing the model to learn features at varying levels of granularity—from broad regions down to specific points of interest. Vorona et al. apply a similar logic using space-filling curves and quad-trees to create "neural synopses" of massive datasets, enabling fast, approximate queries on low-end devices by learning spatial dependencies across different resolutions.
The choice of grid geometry also impacts performance. Soares et al. found that the H3 hexagonal grid system provides a more structured and sparse representation for aircraft trajectories compared to traditional coordinates, leading to improved long-term prediction accuracy.
Simplifying Dynamics with Markovian Abstractions
Beyond deep learning, discretization serves as a foundational tool for formal safety and probabilistic modeling. By partitioning a continuous environment into discrete cells, complex system dynamics can be modeled as transitions between states in a Markov chain.
Matthias Althoff pioneered this for autonomous vehicle safety, discretizing state spaces to model stochastic transitions. This abstraction allows for the formal assessment of collision probabilities by predicting state distributions over time. Althoff et al. further refined this by pre-calculating transition probabilities between cells, enabling rapid updates of a vehicle's future occupancy.
This Markovian approach is equally effective in sports analytics. Oliver Schulte partitions hockey rinks into discrete zones to value player actions based on transition probabilities toward a goal. In tennis, Fearing et al. use a finite grid to decouple a player's intention (where they aim) from their execution (where the ball lands), allowing for the simulation of millions of shots to find optimal strategies.
Overcoming Data Sparsity and Noise
Raw trajectory data is often noisy and sparse, making it difficult to find frequent patterns. Discretization acts as a filter that aggregates nearby points into shared identifiers.
Gidófalvi et al. show that converting continuous movement into spatio-temporal grid cells allows for the mining of "Long, Sharable Patterns" across different users. To handle the "data sparsity problem"—where specific transitions have never been observed—Zhang and Liu and Zhang et al. use grid-based discretization combined with entropy estimation and matrix factorization. This allows them to "fill in the blanks" of unobserved transitions, making destination predictions more robust.
Finally, discretization facilitates privacy-preserving data synthesis. Wang and Kankanhalli map GPS coordinates to a grid of anchor points, transforming raw data into discrete sequences that can be synthesized using differential privacy while maintaining the utility of the original movement patterns.
Key Foundational Work
Mining Long, Sharable Patterns in Trajectories of Moving Objects (2006) — contributed 1 concept elements to this direction.
Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars (2010) — contributed 1 concept elements to this direction.