Pith. sign in

REVIEW 3 major objections 8 minor 72 references

SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting

T0 review · 3 major / 8 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read SqLinear shows that a balanced, padding-free square partition of traffic sensors plus a low-rank linear interaction module can replace attention and beat state-of-the-art baselines on large-scale traffic forecasting benchmarks.

desk verdict SqLinear is a solid, well-run empirical architecture paper whose central bet—that inter-patch dependencies are low-rank—holds up on these four freeway benchmarks but is not yet shown to transfer to dense urban networks. read the letter →

arxiv 2606.21072 v2 pith:53T3WR6M submitted 2026-06-19 cs.LG cs.AI

Yongfeng Su , Hongwen Li , Zijian Zhang , Ziquan Fang , Lu Chen , Christian S. Jensen , Hong Gao , Yinjun Han This is my paper · ORCID
classification cs.LGcs.AI
keywords large-scaletrafficforecastingspatialpartitioningsquarepartitionhierarchicallinearinteractionlow-rankprojectioncomplexitypredictionspatio-temporalmodeling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that expensive attention mechanisms are unnecessary for large-scale traffic forecasting if the sensor network is first reorganized into compact, balanced, padding-free spatial patches. On top of that partition, a hierarchical linear interaction—low-rank global mixing across patches plus local linear mixing within each patch—captures both long-range and short-range dependencies at linear computational cost. The authors prove the partition yields full utilization, bounded imbalance, and no elongation amplification, and they show the low-rank projection's error reduces to the tail energy of a rapidly decaying spectral distribution. Empirically, the architecture reduces mean absolute error by 2.30% on average under standard 12-step forecasting and by 5.81% under long horizons (up to 672 steps), while cutting training runtime by 13%–31%. A sympathetic reader would care because this makes city-scale traffic prediction practical without sacrificing accuracy.

What carries the argument

The load-bearing components are (1) Square Partition and (2) the Hierarchical Linear Interaction (HLI) block. Square Partition recursively splits nodes along the axis with the larger geographic span, sorts along that axis, and chooses split points as multiples of a capacity C (Sp = C·ceil(ceil(N/C)/2)). This guarantees padding-free tensorization when N = P·C, split imbalance below 2C, and no amplification of elongation. The resulting patches are non-overlapping, approximately square, and map directly to tensors of shape C×P×d. HLI replaces attention with two linear stages: an inter-patch stage that aligns corresponding nodes across patches, applies a linear MLP, and communicates globally thr

What would settle it

Compute the singular-value spectrum of the empirical patch-wise dependency matrix on a new large-scale traffic dataset with many independent, non-synchronized arterial corridors (rather than the studied metropolitan networks). If the tail energy beyond a practical rank r (say r ≈ 10–50) is large—for instance, if top-r components capture well under 90% of variance—then the low-rank inter-patch operator loses information a full attention matrix would retain, and the accuracy advantage over attention-based models should shrink or invert. Alternatively, run SqLinear with r set to full rank P: if a

Watch

Extended reading notes

Core claim

The central claim is that a well-chosen spatial partition, not a more expressive interaction layer, is what unlocks scalable traffic forecasting. The Square Partition algorithm recursively splits the sensor set along the currently longest geographic span, choosing split positions as multiples of a leaf capacity C, so each resulting patch has exactly C nodes (no padding), the split imbalance stays below 2C, and the effective aspect ratio is not systematically amplified. On this layout, the Hierarchical Linear Interaction block propagates global dependencies through a low-rank projection Θ_r1 Θ_r2 with rank r < C < P, then refines local features with a per-patch linear MLP, achieving O(Nd²) ti

Load-bearing premise

The result holds only if the dependency matrix among spatial patches is approximately low-rank—i.e., the top few latent components capture most of the inter-patch correlation variance—so that replacing the full P×P coupling with a rank-r projection loses negligible information.

Editorial extensions

If this is right

  • City-scale traffic forecasting with thousands of sensors can run at linear complexity without sacrificing accuracy—O(Nd²) time and O(Nd) memory—making deployment on large networks feasible.
  • Replacing attention with hierarchical linear interaction is safe when the spatial partition is well constructed; the ablation study shows the attention variant does not outperform the linear HLI while consuming more compute.
  • The rank r of the inter-patch projection serves as an accuracy–efficiency dial: moderate r is sufficient because patch-level dependency spectra decay quickly on the studied datasets.
  • The partition's guarantees—full utilization, perfect balance, no padding—transfer to any sensor layout approximated by coordinates, suggesting applicability beyond traffic (e.g., environmental or energy monitoring).
  • The accuracy gain over baselines remains stable as the forecast horizon extends to 672 steps, indicating the learned spatial representation does not degrade with longer prediction ranges.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • I infer the method's effectiveness hinges on the assumption that inter-patch traffic correlations are approximately low-rank; on networks with many spatially interleaved but functionally independent corridors, a full-rank or attention-based interaction would likely retain an accuracy advantage, which is a testable boundary condition.
  • The Square Partition index depends only on sensor coordinates and capacity, so I would expect it to serve as a drop-in preprocessing step for other spatio-temporal models, improving their scalability without retraining the partitioner.
  • Because HLI's weights are linear matrices, the learned spatial dependencies are directly interpretable; I infer this opens a route to explainable traffic forecasting and to anomaly detection by monitoring weight drift over time.
  • The paper's topology-aware extensions suggest that for road networks where geometric proximity is a poor proxy for traffic coupling, the geometry-first or topology-first partitioning variants would be the appropriate fallbacks—though the current experiments show pure geometric partitioning already wins on the tested datasets.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. The paper proposes SqLinear, a traffic-forecasting architecture that combines a geometry-adaptive square partitioning algorithm with a hierarchical linear interaction (HLI) module. The partition algorithm recursively splits sensor nodes along their longest spatial span using capacity-aware split points, producing balanced, non-overlapping, near-square patches without padding when the total node count is an exact multiple of the leaf capacity. The HLI module replaces quadratic-complexity attention with a linear inter-patch low-rank projection plus an intra-patch linear refinement, achieving O(N d^2) time and O(N d) memory. The paper reports state-of-the-art accuracy on four LargeST benchmarks, including an average 2.30% MAE reduction over PatchSTG under the standard 12-step setting and an average 5.81% MAE reduction over strong baselines in long-horizon (96=>672) settings, with reduced training runtime. Theoretical results cover partition utilization, split balance, non-amplification of elongation, low-rank approximation capacity, expressiveness relative to linear baselines, and complexity.

Significance. If the empirical results hold, SqLinear is a practically valuable contribution: it demonstrates that, on large freeway sensor networks, a carefully designed linear-complexity model can outperform attention- and graph-based state-of-the-art baselines, addressing a real scalability bottleneck for city-scale traffic forecasting. The paper's strengths include a principled partitioning scheme with explicit theoretical guarantees (Theorems C.2, C.4, C.6), a clear complexity analysis, extensive experiments across four datasets and ten baselines, and a complete long-horizon study covering 16 dataset-horizon combinations. The central empirical claim is well supported by the reported tables. However, the title-level claim that linear interaction is 'sufficient' for large-scale traffic forecasting is broader than what the evidence supports: the low-rank inter-patch assumption is only weakly validated, the padding-free property is conditional on N=PC, and the paper itself acknowledges a limitation on incident-driven dynamics. These issues are fixable within the scope of a revision.

major comments (3)
  1. [§4.3.1, Eq. (11), Theorem C.7, Figure 3] The central accuracy claim depends on the low-rank inter-patch projection. Theorem C.7 is a correct Eckart-Young identity, but it only states that the best rank-r approximation error equals the tail singular-value energy of an 'ideal' dependency matrix M; it does not establish that the tail is small for the forecasting task. Figure 3 shows spectral decay of observed patch-wise dependency matrices, but such decay is dominated by strong daily periodicity and regional congestion and does not bound the rank of the conditional dependencies needed for prediction (e.g., residual dynamics after removing periodic components or incident-activated correlations). Moreover, the rank r is not reported anywhere in the experiments, and no error bars are given. It is therefore impossible to assess whether the reported 2.30% average improvement is robust to the choice of r. Please report the value of r us
  2. [§4.2, Theorem C.2, Abstract] The padding-free guarantee is explicitly conditional on C being selected such that N=PC. For an arbitrary sensor network, such a C may not exist (e.g., if N is prime, the only exact divisors are C=1 and C=N, neither of which yields a useful partition). The abstract and Section 1 claim that SqLinear works 'without performing padding operations' as a general property, and the efficiency comparison against PatchSTG's 43% padding overhead relies on this. Please either state the N=PC condition prominently in the contribution claims or describe a fallback for non-divisible N (e.g., allowing at most one partially filled patch with bounded overhead). As written, the padding-free contribution is narrower than it appears.
  3. [Appendix D.6, Title, Abstract] The paper admits in D.6 that the linear interaction module 'may have limited capacity to model abrupt and highly nonlinear dynamics, such as those caused by traffic accidents.' This directly qualifies the title claim that balanced square partitioning 'makes linear interaction sufficient' for large-scale traffic forecasting. All four benchmarks are California freeway sensor networks with similar free-flow/congestion regimes; the low-rank and linear-sufficiency evidence may not transfer to dense urban arterials with many weakly coupled independent roads or to incident-rich settings. Please scope the central claim to recurrent congestion dynamics on freeway-scale sensor networks, and discuss whether the architecture can be extended to incident scenarios (e.g., a hybrid linear-nonlinear module). Without such qualification, the 'sufficient' wording overstates the demonstrated scope.
minor comments (8)
  1. [Abstract and §5.3] The abstract is inconsistent: it says '10 baselines' in the full text but '11 baselines' in the header version, and 'reduces MAE by 5.81%' versus 'up to 6.78%' in different places. Please unify these numbers.
  2. [Algorithm 1, line 15] Typo: 'SqarePartition' should be 'SquarePartition'.
  3. [Algorithm 2, line 4] The spatial embedding uses 'X_P' in the algorithm but Eq. (4) uses X_H. Please align the notation.
  4. [Figure 3] Please specify how the patch-wise dependency matrix is computed (e.g., covariance or correlation of which input features, which layer/aggregation), and define the 'cumulative variance' precisely. This is needed to interpret the low-rank motivation.
  5. [Notation] The rank is denoted r in Eq. (11) and Theorem C.7 but k in Figure 8 and Appendix D.3. Unify the notation.
  6. [Theorem C.8] The statement that 'the additional intra-patch operator makes HLI strictly more expressive' is not established by the proof sketch, which shows only containment of linear mixing operator classes. Please state the precise sense of expressiveness and prove strictness, or soften the claim.
  7. [§4.5.2 and Figure 9] The Topology-First Road Grouping (TFRG) variant can generate highly imbalanced groups (e.g., a long highway vs. a short ramp), yet no theoretical or empirical analysis of its balance is provided. Please add a discussion of its limitations, especially since the paper's main contribution is balanced partitioning.
  8. [Table 7] Aspect ratios are computed from raw longitude/latitude degrees. Please clarify whether an equal-area projection was used; unprojected degrees can distort aspect ratios, especially at the latitude of California.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the low-rank error bound is a standard identity, the partition guarantees follow from the algorithm's own construction, and self-citations are not load-bearing.

full rationale

The derivation chain is not circular. The theorem that could look tautological is Theorem C.7 (Eq. 23), but it is exactly the Eckart-Young-Mirsky identity, and the paper explicitly treats the smallness of the tail as an empirical observation ('when the empirical singular spectrum decays rapidly, the discarded tail energy is small'), supported by Fig. 3, rather than as an input assumption. The expressiveness claim (Theorem C.8) is a rank-containment statement about the spatial-mixing operators of RPMixer and BigST, not a claim that those baselines' accuracies are reproduced. The partition results (Theorems C.2, C.4, C.6) are internal correctness statements about Square Partition's own split rule; they are definitional in the benign sense that a designed algorithm satisfies its design properties, and the paper does not use them as a fitted 'prediction' of MAE. Aspect ratio is explicitly labeled 'an empirical compactness diagnostic rather than a universal guarantee' (Definition C.5), so no universal claim is smuggled in. Self-citations ([14], [39], [46], [63]) appear only as background or framework references and are not load-bearing. The stated limitation in D.6—'may have limited capacity to model abrupt and highly nonlinear dynamics, such as those caused by traffic accidents'—is a scope restriction on the central claim, not evidence that the derivation reduces to its inputs. The headline accuracy numbers are external benchmark results against 10 baselines; no fitted parameter is renamed as a prediction.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The paper introduces no physical or ontological entities; its inventions are algorithmic/architectural constructs (Square Partition, HLI). The free parameters are all standard ML hyperparameters, but their exact values are only partially reported, which matters because the padding-free and low-rank claims depend on them.

free parameters (4)
  • leaf capacity C = C=48 (GBA), C=86 (CA); unspecified for SD/GLA
    Chosen per dataset such that N=PC (padding-free tensorization) and tuned for accuracy; controls patch count P=N/C, split balance bound δ<2C, and rank constraint r<C<P. Exact values for SD/GLA are not given.
  • low-rank dimension r (also called k) = not reported in main text
    Rank of global inter-patch projection Θ_r1∈R^{P×r}, Θ_r2∈R^{r×P}; hyperparameter study (Fig. 8) shows a moderate k is optimal, but exact values per dataset are absent; controls expressiveness vs O(dPr) cost.
  • number of HLI layers L = not reported
    Stacked depth; larger networks need deeper layers (Fig. 8b/e), but exact L per dataset is absent.
  • hidden dimensions d_h, d_d, d_w, d_s = not reported
    Embedding sizes in Eqs. 2-5; the paper defines d as the sum but does not list the values or training configuration.
assumptions (6)
  • standard math Eckart-Young-Mirsky theorem: the best rank-r approximation of a matrix is its truncated SVD
    Used in Theorem C.7 to bound low-rank projection error; standard result invoked without proof.
  • standard math Singular vectors are orthonormal, so the Frobenius residual norm equals the square root of the sum of tail squared singular values
    Used in the proof sketch of Theorem C.7.
  • domain assumption First Law of Geography: nearby traffic sensors are more strongly correlated than distant ones
    Invoked in §1 Challenge I to justify compact spatial patches; if false, coordinate-based partitioning could hurt accuracy.
  • domain assumption Patch-wise dependency matrices are approximately low-rank with fast spectral decay
    Empirically argued via Fig. 3; underpins the low-rank inter-patch projection. The paper has no non-empirical guarantee that the tail energy is small for unseen cities.
  • domain assumption Geographic coordinates are a valid proxy for traffic network topology
    Main experiments use free-space partitioning, which assumes lat/lng neighborhoods reflect traffic-relevant proximity; topology-aware variants are presented as extensions and are not used in the main results.
  • ad hoc to paper A capacity C can always be chosen such that N=PC while preserving balanced, compact patches
    Padding-free tensorization (Theorem C.2) requires N=PC and split points at multiples of C; the choice of C is tuned to the data, and no constructive guarantee is given that such C preserves compactness for arbitrary N.

how reviews work

0 comments
Cite this review

Pith. "Pith review of SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting." pith.science (2026). https://pith.science/paper/53T3WR6M

@misc{pith2026260621072,
  author       = {Pith},
  title        = {Pith review of: SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/53T3WR6M}},
  note         = {Machine review of arXiv:2606.21072}
}
read the original abstract

Traffic prediction is a core task in intelligent transportation systems and urban-scale decision making. Despite the effectiveness of mainstream neural network-based methods, their deployment in real-world settings with thousands of traffic sensors is severely jeopardized by their poor computational scalability. To address this, the community has attempted to incorporate spatial database partitioning techniques to improve model scalability. However, these approaches rely on handcrafted geometric heuristics and often produce irregular or imbalanced data partitions, leading to boundary fragmentation, excessive padding overheads, and degraded model accuracy. In this paper, we propose SqLinear, an efficient and effective architecture for large-scale traffic prediction. First, we design Square Partition, a geometry-adaptive algorithm that partitions massive traffic sensors into balanced, non-overlapping, and compact spatial regions. Unlike existing heuristic-based designs, Square Partition is theoretically grounded and provides provable guarantees on partition utilization and split balance, establishing a high-quality foundation for downstream spatio-temporal modeling. Next, we propose a Hierarchical Linear Interaction (HLI) module that abandons the costly attention mechanisms commonly used in Transformer-based spatio-temporal models. HLI efficiently propagates global inter-region dependencies and refines them at the node level through a lightweight linear interaction scheme, enabling effective spatio-temporal modeling with linear computational complexity. Extensive experiments on four large-scale traffic datasets and 11 baselines show that SqLinear reduces MAE by 2.30% on average under the standard setting and by up to 6.78% under extreme scalability settings, while reducing training runtime by 13.27%--30.84% in spatial- and horizon-scaling scenarios.

Figures

Figures reproduced from arXiv: 2606.21072 by the authors.

Figure 1
Figure 1. Top: spatial partitioning quality; Bottom: training [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The architecture and workflow of SqLinear. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Low-rank measurement. iii) More importantly, unlike general-purpose spatial indexing structures designed for range and 𝑘NN queries, Square Partition is specifically tailored for tensorized trajectory forecasting. By enforc￾ing a capacity constraint on every leaf node, each partition can be directly mapped to a padding-free tensor in R 𝐶×𝑃×𝑑 , thereby align￾ing the partitioning objective with the computational requir… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Performance comparison under long-horizon forecasting settings. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Accuracy-efficiency bubble plots under the stan [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: Per-sample training time comparison. the per-sample training time under long-horizon forecasting set￾tings. On the largest CA dataset, SqLinear achieves the shortest per-sample training time across all prediction horizons and reduces per-sample training time by 46.78% …
Figure 7
Figure 7. Figure 7: Ablation study. alternating axes instead of Eq. 6; (5) w/ MedianSplit uses the median split point instead of Eq. 7; (6) w/o Inter and (7) w/o Intra remove inter- and intra-patch interactions, respectively; (8) w/ Attn replaces the linearMLP with standard attention. As …
Figure 8
Figure 8. Figure 8: Hyperparameter sensitivity analysis [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: Partition strategy analysis. shallower models are sufficient for smaller graphs. Excessive depth can add unnecessary computation and may lead to overfitting on smaller datasets. The low-rank dimension 𝑘. A moderate low-rank dimension is enough to encode latent spatial …
Figure 11
Figure 11. Figure 11: Visualization of learned spatial dependencies. [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 10
Figure 10. Figure 10: Visualization of partitioning results. (down to 0.16). These measurements confirm that Square Partition realizes the utilization and balance guarantees of the analysis while remaining the most compact among capacity-balanced partitions in practice. D.5 Case Study (RQ7…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

72 extracted references · 6 linked inside Pith

  1. [1]

    Evangelos C Alexopoulos. 2010. Introduction to multivariate regression analysis. Hippokratia14, Suppl 1 (2010), 23

    2010

  2. [2]

    Bang An, Xun Zhou, Amin Vahedian, Nick Street, Jinping Guan, and Jun Luo

  3. [3]

    Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. 2020. Adaptive graph convolutional recurrent network for traffic forecasting. InNeural Information Processing Systems. 17804–17815

    2020

  4. [4]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching.Commun. ACM18, 9 (1975), 509–517

    1975

  5. [5]

    Friedman

    Jon Louis Bentley and Jerome H. Friedman. 1979. Data Structures for Range Searching.Comput. Surveys11, 4 (1979), 397–409

    1979

  6. [6]

    George EP Box and David A Pierce. 1970. Distribution of residual autocorrelations in autoregressive-integrated moving average time series models.Journal of the American statistical Association65, 332 (1970), 1509–1526

    1970

  7. [7]

    Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. 2020. Spectral Tem- poral Graph Neural Network for Multivariate Time-series Forecasting.Neural Information Processing Systems(2020), 17766–17778

    2020

  8. [8]

    Peng Chen, Yingying ZHANG, Yunyao Cheng, Yang Shu, Yihang Wang, Qingsong Wen, Bin Yang, and Chenjuan Guo. 2024. Pathformer: Multi-scale Transformers with Adaptive Pathways for Time Series Forecasting. InInternational Conference on Learning Representations

    2024

Show all 72 references
  1. [9]

    Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh

  2. [10]

    Zheng Dong, Renhe Jiang, Haotian Gao, Hangchen Liu, Jinliang Deng, Qingsong Wen, and Xuan Song. 2024. Heterogeneity-Informed Meta-Parameter Learning for Spatiotemporal Time Series Forecasting. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 631–641

    2024

  3. [11]

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xi- aohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al . 2020. An Image is Worth 16x16 Words: Trans- formers for Image Recognition at Scale. InInterna...

    2020

  4. [12]

    James Durbin. 1959. Efficient estimation of parameters in moving-average models. Biometrika46, 3/4 (1959), 306–316

    1959

  5. [13]

    Yuchen Fang, Yuxuan Liang, Bo Hui, Zezhi Shao, Liwei Deng, Xu Liu, Xinke Jiang, and Kai Zheng. 2025. Efficient Large-Scale Traffic Forecasting with Trans- formers: A Spatial Data Management Perspective. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 307–317

    2025

  6. [14]

    Jensen, Xiaofang Zhou, and Kai Zheng

    Yuchen Fang, Hao Miao, Yuxuan Liang, Liwei Deng, Yue Cui, Ximu Zeng, Yuyang Xia, Yan Zhao, Torben Bach Pedersen, Christian S. Jensen, Xiaofang Zhou, and Kai Zheng. 2025. Unraveling Spatio-Temporal Foundation Models via the Pipeline Lens: A Comprehensive Review.arXiv preprint a...

    2025 arXiv

  7. [15]

    Yuchen Fang, Yanjun Qin, Haiyong Luo, Fang Zhao, Bingbing Xu, Liang Zeng, and Chenxing Wang. 2023. When spatio-temporal meet wavelets: Disentangled traffic forecasting via efficient spectral graph attention networks. InIEEE International Conference on Data Engineering. 517–529

    2023

  8. [16]

    Friedman, Jon Louis Bentley, and Raphael Ari Finkel

    Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. An Al- gorithm for Finding Best Matches in Logarithmic Expected Time.ACM Trans. Math. Software3, 3 (1977), 209–226

    1977

  9. [17]

    Han Gao, Xu Han, Jiaoyang Huang, Jian-Xun Wang, and Liping Liu. 2022. Patchgt: Transformer over non-trainable clusters for learning graph representations. In Learning on Graphs Conference. 1–27

    2022

  10. [18]

    Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. 2019. Attention based spatial-temporal graph convolutional networks for traffic flow forecasting. InAAAI Conference on Artificial Intelligence. 922–929

    2019

  11. [19]

    Jindong Han, Weijia Zhang, Hao Liu, Tao Tao, Naiqiang Tan, and Hui Xiong

  12. [20]

    Xiaoxue Han, Zhuo Feng, and Yue Ning. 2024. A topology-aware graph coars- ening framework for continual graph learning.Neural Information Processing Systems37 (2024), 132491–132523

    2024

  13. [21]

    Jiahao Ji, Jingyuan Wang, Chao Huang, Junjie Wu, Boren Xu, Zhenhe Wu, Junbo Zhang, and Yu Zheng. 2023. Spatio-temporal self-supervised learning for traffic flow prediction. InAAAI Conference on Artificial Intelligence. 4356 – 4364

    2023

  14. [22]

    InProceedings of the VLDB Endowment

    BigST: Linear Complexity Spatio-Temporal Graph Neural Network for Traffic Forecasting on Large-Scale Road Networks. InProceedings of the VLDB Endowment. 1081–1090

  15. [23]

    Guangyin Jin, Yuxuan Liang, Yuchen Fang, Zezhi Shao, Jincai Huang, Junbo Zhang, and Yu Zheng. 2023. Spatio-temporal graph neural networks for predictive learning in urban computing: A survey.IEEE Transactions on Knowledge and Data Engineering(2023), 5388–5408

    2023

  16. [24]

    Weiyang Kong, Kaiqi Wu, Sen Zhang, and Yubao Liu. 2025. GraphSparseNet: A Novel Method for Large Scale Traffic Flow Prediction.Proceedings of the VLDB Endowment18, 7 (2025), 2295–2307

    2025

  17. [25]

    Jiahao Ji, Wentao Zhang, Jingyuan Wang, and Chao Huang. 2025. Seeing the Un- seen: Learning Basis Confounder Representations for Robust Traffic Prediction. InACM International Conference on Information and Knowledge Management. 577–588

    2025

  18. [26]

    Dilfira Kudrat, Zongxia Xie, Yanru Sun, Tianyu Jia, and Qinghua Hu. 2025. Patch- wise Structural Loss for Time Series Forecasting.arXiv preprint arXiv:2503.00877 (2025)

    2025 arXiv

  19. [27]

    Shiyong Lan, Yitong Ma, Weikang Huang, Wenwu Wang, Hongyu Yang, and Pyang Li. 2022. DSTAGNN: Dynamic spatial-temporal aware graph neural network for traffic flow forecasting. InInternational Conference on Machine Learning. 11906–11917

    2022

  20. [28]

    Xiangjie Kong, Wenfeng Zhou, Guojiang Shen, Wenyi Zhang, Nali Liu, and Yao Yang. 2023. Dynamic graph convolutional recurrent imputation network for spatiotemporal traffic missing data.Knowledge-Based Systems261 (2023), 110188

    2023

  21. [29]

    Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting. InInternational Conference on Learning Representations

    2018

  22. [30]

    Zhonghang Li, Lianghao Xia, Jiabin Tang, Yong Xu, Lei Shi, Long Xia, Dawei Yin, and Chao Huang. 2024. UrbanGPT: Spatio-Temporal Large Language Models. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 5351–5362

    2024

  23. [31]

    Fuxian Li, Jie Feng, Huan Yan, Guangyin Jin, Fan Yang, Funing Sun, Depeng Jin, and Yong Li. 2023. Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution.ACM Transactions on Knowledge Discovery from Data(2023), 1–21

    2023

  24. [32]

    Chenxi Liu, Kethmi Hirushini Hettige, Qianxiong Xu, Cheng Long, Shili Xiang, Gao Cong, Ziyue Li, and Rui Zhao. 2025. ST-LLM+: Graph Enhanced Spatio- Temporal Large Language Models for Traffic Prediction.IEEE Transactions on Knowledge and Data Engineering37, 8 (2025), 4846–4859

    2025

  25. [33]

    Chenxi Liu, Sun Yang, Qianxiong Xu, Zhishuai Li, Cheng Long, Ziyue Li, and Rui Zhao. 2024. Spatial-temporal large language model for traffic prediction. In IEEE International Conference on Mobile Data Management. 31–40

    2024

  26. [34]

    Yuxuan Liang, Haomin Wen, Yuqi Nie, Yushan Jiang, Ming Jin, Dongjin Song, Shirui Pan, and Qingsong Wen. 2024. Foundation models for time series analysis: A tutorial and survey. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 6555–6565

    2024

  27. [35]

    Xu Liu, Yutong Xia, Yuxuan Liang, Junfeng Hu, Yiwei Wang, Lei Bai, Chao Huang, Zhenguang Liu, Bryan Hooi, and Roger Zimmermann. 2024. LargeST: A benchmark dataset for large-scale traffic forecasting. InNeural Information Processing Systems. 75354–75371

    2024

  28. [36]

    Zhi Liu, Yang Chen, Feng Xia, Jixin Bian, Bing Zhu, Guojiang Shen, and Xiangjie Kong. 2023. TAP: Traffic Accident Profiling via Multi-Task Spatio-Temporal Graph Representation Learning.ACM Transactions on Knowledge Discovery from Data17, 4 (2023), 1–25

    2023

  29. [37]

    Hangchen Liu, Zheng Dong, Renhe Jiang, Jiewen Deng, Jinliang Deng, Quanjun Chen, and Xuan Song. 2023. Spatio-temporal adaptive embedding makes vanilla transformer sota for traffic forecasting. InACM International Conference on Information and Knowledge Management. 4125–4129

    2023

  30. [38]

    Ilya Loshchilov and Frank Hutter. 2017. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101(2017)

    2017 arXiv

  31. [39]

    Tinghui Luo, Ziquan Fang, Kaixuan Duan, Lu Chen, Panpan Feng, and Mingfan Lu. 2025. Towards Online Spatio-Temporal Prediction: A Knowledge Distillation Driven Continual Learning Approach. InIEEE International Conference on Data Engineering. 2642–2655

    2025

  32. [40]

    Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. 2021. Swin transformer: Hierarchical vision transformer using shifted windows. InIEEE/CVF International Conference on Computer Vision. 10012–10022

    2021

  33. [41]

    Moin Hussain Moti, Panagiotis Simatis, and Dimitris Papadias. 2022. Waffle: A workload-aware and query-sensitive framework for disk-based spatial indexing. Proceedings of the VLDB Endowment16, 4 (2022), 670–683

    2022

  34. [42]

    Yuqi Nie, Nam H Nguyen, Phanwadee Sinthong, and Jayant Kalagnanam. 2023. A Time Series is Worth 64 Words: Long-term Forecasting with Transformers. In International Conference on Learning Representations

    2023

  35. [43]

    Tengfei Lyu, Weijia Zhang, Jinliang Deng, and Hao Liu. 2025. AutoSTF: Decou- pled Neural Architecture Search for Cost-Effective Automated Spatio-Temporal Forecasting. InACM SIGKDD Conference on Knowledge Discovery and Data Min- ing. 985–996

    2025

  36. [44]

    Hanan Samet. 1984. The quadtree and related hierarchical data structures.ACM Computing Surveys (CSUR)16, 2 (1984), 187–260

    1984

  37. [45]

    2006.Foundations of multidimensional and metric data structures

    Hanan Samet. 2006.Foundations of multidimensional and metric data structures. Morgan Kaufmann

    2006

  38. [46]

    Namuk Park and Songkuk Kim. 2022. How do vision transformers work?arXiv preprint arXiv:2202.06709(2022)

    2022 arXiv

  39. [47]

    Zezhi Shao, Zhao Zhang, Fei Wang, Wei Wei, and Yongjun Xu. 2022. Spatial- temporal identity: A simple yet effective baseline for multivariate time series forecasting. InACM International Conference on Information and Knowledge Management. 4454–4458

    2022

  40. [48]

    Zezhi Shao, Zhao Zhang, Fei Wang, and Yongjun Xu. 2022. Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1567–1577

    2022

  41. [49]

    Jensen, and Xueqi Cheng

    Zezhi Shao, Fei Wang, Yongjun Xu, Wei Wei, Chengqing Yu, Zhao Zhang, Di Yao, Tao Sun, Guangyin Jin, Xin Cao, Gao Cong, Christian S. Jensen, and Xueqi Cheng

  42. [50]

    Waldo R Tobler. 1970. A computer movie simulating urban growth in the Detroit region.Economic geography46 (1970), 234–240

    1970

  43. [51]

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need.Neural Information Processing Systems30 (2017)

    2017

  44. [52]

    Senzhang Wang, Jiannong Cao, and S Yu Philip. 2020. Deep learning for spatio- temporal data mining: A survey.IEEE transactions on knowledge and data engi- neering34, 8 (2020), 3681–3700

    2020

  45. [53]

    Zezhi Shao, Zhao Zhang, Wei Wei, Fei Wang, Yongjun Xu, Xin Cao, and Chris- tian S Jensen. 2022. Decoupled dynamic spatial-temporal graph neural network for traffic forecasting. InProceedings of the VLDB Endowment. 2733–2746

    2022

  46. [54]

    Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. 2020. Connecting the dots: Multivariate time series forecasting with graph neural networks. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 753–763

    2020

  47. [55]

    Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. 2019. Graph wavenet for deep spatial-temporal graph modeling. InInternational Joint Conference on Artificial Intelligence. 1907–1913

    2019

  48. [56]

    Zhenda Xie, Yutong Lin, Zhuliang Yao, Zheng Zhang, Qi Dai, Yue Cao, and Han Hu. 2021. Self-supervised learning with swin transformers.arXiv preprint arXiv:2105.04553(2021)

    2021 arXiv

  49. [57]

    Yuxuan Wang, Haixu Wu, Jiaxiang Dong, Yong Liu, Mingsheng Long, and Jianmin Wang. 2024. Deep time series models: A comprehensive survey and benchmark. arXiv preprint arXiv:2407.13278(2024)

    2024 arXiv

  50. [58]

    Yueyang Yao, Xingyuan Dai, and Yisheng Lv. 2025. Leveraging Heterogeneous Experts with Advantageous Pattern Memory Learning for Traffic Prediction. In IEEE International Conference on Data Engineering. 3342–3355

    2025

  51. [59]

    Chin-Chia Michael Yeh, Yujie Fan, Xin Dai, Uday Singh Saini, Vivian Lai, Prince Osei Aboagye, Junpeng Wang, Huiyuan Chen, Yan Zheng, Zhongfang Zhuang, et al. 2024. RPMixer: Shaking Up Time Series Forecasting with Random Projections for Large Spatial-Temporal Data. InACM SIGKDD...

    2024

  52. [60]

    Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Con- volutional Networks: A Deep Learning Framework for Traffic Forecasting. In International Joint Conference on Artificial Intelligence. 3634–3640

    2018

  53. [61]

    Haiqiang Yang, Zihan Li, and Yashuai Qi. 2024. Predicting traffic propagation flow in urban road network with multi-graph convolutional network.Complex & Intelligent Systems10, 1 (2024), 23–35

    2024

  54. [62]

    Zhuoning Yuan, Xun Zhou, and Tianbao Yang. 2018. Hetero-ConvLSTM: A deep learning approach to traffic accident prediction on heterogeneous spatio- temporal data. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 984–992

    2018

  55. [63]

    Zhihao Zeng, Ziquan Fang, Yuting Huang, Qilong Wang, Lu Chen, and Yunjun Gao. 2025. Heterogeneous-Aware Traffic Prediction: A Privacy-Preserving Feder- ated Learning Framework . InIEEE International Conference on Data Engineering. 419–432

    2025

  56. [64]

    Cheng Zhang, Haocheng Wan, Xinyi Shen, and Zizhao Wu. 2022. Patchformer: An efficient point transformer with patch attention. InProceedings of the IEEE/CVF conference on computer vision and pattern recognition. 11799–11808

    2022

  57. [65]

    Yuan Yuan, Jingtao Ding, Jie Feng, Depeng Jin, and Yong Li. 2024. UniST: A Prompt-Empowered Universal Model for Urban Spatio-Temporal Prediction. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 4095–4106

    2024

  58. [66]

    Yiji Zhao, Zihao Zhong, Ao Wang, Haomin Wen, Ming Jin, Yuxuan Liang, Huaiyu Wan, and Hao Wu. 2026. FaST: Efficient and Effective Long-Horizon Forecasting for Large-Scale Spatial-Temporal Graphs via Mixture-of-Experts. InProceedings of the 32nd ACM SIGKDD Conference on Knowledg...

    2026

  59. [67]

    Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi. 2020. Gman: A graph multi-attention network for traffic prediction. InAAAI Conference on Artificial Intelligence. 1234–1241

    2020

  60. [68]

    Qi Zheng, Zihao Yao, and Yaying Zhang. 2025. ST-ReP: Learning Predictive Representations Efficiently for Spatial-Temporal Forecasting. InAAAI Conference on Artificial Intelligence, Vol. 39. 13419–13427. SqLinear Appendix Directory Appendix A Related Work11 Appendix B Algorithm...

    2025

  61. [69]

    Weijia Zhang, Le Zhang, Jindong Han, Hao Liu, Yanjie Fu, Jingbo Zhou, Yu Mei, and Hui Xiong. 2024. Irregular Traffic Time Series Forecasting Based on Asynchronous Spatio-Temporal Graph Convolutional Networks. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 4302–4313

    2024

  62. [2019]

    InACM SIGKDD Conference on Knowledge Discovery and Data Mining

    Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. InACM SIGKDD Conference on Knowledge Discovery and Data Mining. 257–266

  63. [2024]

    InIEEE International Conference on Data Mining

    LISA: Learning-Integrated Space Partitioning Framework for Traffic Acci- dent Forecasting on Heterogeneous Spatiotemporal Data. InIEEE International Conference on Data Mining. 11–20

  64. [2025]

    Su et al

    Exploring Progress in Multivariate Time Series Forecasting: Comprehensive Benchmarking and Heterogeneity Analysis.IEEE Transactions on Knowledge and Data Engineering37, 1 (2025), 291–305. Su et al

    2025

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.