  Transformers are widely used deep learning architectures. Existing
transformers are mostly designed for sequences (texts or time series), images
or videos, and graphs. This paper proposes a novel transformer model for
massive (up to a million) point samples in continuous space. Such data are
ubiquitous in environment sciences (e.g., sensor observations), numerical
simulations (e.g., particle-laden flow, astrophysics), and location-based
services (e.g., POIs and trajectories). However, designing a transformer for
massive spatial points is non-trivial due to several challenges, including
implicit long-range and multi-scale dependency on irregular points in
continuous space, a non-uniform point distribution, the potential high
computational costs of calculating all-pair attention across massive points,
and the risks of over-confident predictions due to varying point density. To
address these challenges, we propose a new hierarchical spatial transformer
model, which includes multi-resolution representation learning within a
quad-tree hierarchy and efficient spatial attention via coarse approximation.
We also design an uncertainty quantification branch to estimate prediction
confidence related to input feature noise and point sparsity. We provide a
theoretical analysis of computational time complexity and memory costs.
Extensive experiments on both real-world and synthetic datasets show that our
method outperforms multiple baselines in prediction accuracy and our model can
scale up to one million points on one NVIDIA A100 GPU. The code is available at
\url{https://github.com/spatialdatasciencegroup/HST}.
