DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis

Tsz Nam Chan; Bojian Zhu; Dingming Wu; Renchi Yang; Ruisheng Wang

doi:10.1109/ICDE65706.2026.00118

DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis

Tsz Nam Chan
, Bojian Zhu
, Dingming Wu^*
, Renchi Yang
, Ruisheng Wang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

Abstract

Generating a spatiotemporal K-function plot is frequently adopted to analyze point patterns by domain experts in a wide range of application domains, including criminology, transportation science, urban planning, and epidemiology. However, with the high worst-case time complexity of computing a spatiotemporal K-function plot, the state-of-the-art methods are unable to efficiently (or feasibly) support this tool. To overcome this issue, we develop Distribution-aNd-Aggregation (DNA), which is the first solution that can reduce the worst-case time complexity for supporting this tool. Experiment results on four large-scale location datasets show that DNA achieves speedups of 4.58x to 57.42x over the state-of-the-art methods, without incurring significant space overhead. The implementation of all methods can be found in https://github.com/edisonchan2013928/DNA.

Original language	English
Title of host publication	Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026
Editors	Khuzaima Daudjee, Qiong Luo, Alkis Simitsis
Publisher	IEEE
Pages	1533-1546
Number of pages	14
ISBN (Electronic)	9798331583651
ISBN (Print)	9798331583668
DOIs	https://doi.org/10.1109/ICDE65706.2026.00118
Publication status	Published - 4 May 2026
Event	42nd International Conference on Data Engineering, ICDE 2026 - Montreal, Canada Duration: 4 May 2026 → …

Publication series

Name	Proceedings - International Conference on Data Engineering
Publisher	IEEE
ISSN (Print)	1063-6382
ISSN (Electronic)	2375-026X

Conference

Conference	42nd International Conference on Data Engineering, ICDE 2026
Country/Territory	Canada
City	Montreal
Period	4/05/26 → …

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure
SDG 11 Sustainable Cities and Communities

Access to Document

10.1109/ICDE65706.2026.00118

Cite this

Chan, T. N., Zhu, B., Wu, D., Yang, R., & Wang, R. (2026). DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis. In K. Daudjee, Q. Luo, & A. Simitsis (Eds.), Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026 (pp. 1533-1546). (Proceedings - International Conference on Data Engineering). IEEE. https://doi.org/10.1109/ICDE65706.2026.00118

Chan, Tsz Nam ; Zhu, Bojian ; Wu, Dingming et al. / DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis. Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026. editor / Khuzaima Daudjee ; Qiong Luo ; Alkis Simitsis. IEEE, 2026. pp. 1533-1546 (Proceedings - International Conference on Data Engineering).

@inproceedings{55e155287a0e498a837f6f2014bfb84c,

title = "DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis",

abstract = "Generating a spatiotemporal K-function plot is frequently adopted to analyze point patterns by domain experts in a wide range of application domains, including criminology, transportation science, urban planning, and epidemiology. However, with the high worst-case time complexity of computing a spatiotemporal K-function plot, the state-of-the-art methods are unable to efficiently (or feasibly) support this tool. To overcome this issue, we develop Distribution-aNd-Aggregation (DNA), which is the first solution that can reduce the worst-case time complexity for supporting this tool. Experiment results on four large-scale location datasets show that DNA achieves speedups of 4.58x to 57.42x over the state-of-the-art methods, without incurring significant space overhead. The implementation of all methods can be found in https://github.com/edisonchan2013928/DNA.",

author = "Chan, \{Tsz Nam\} and Bojian Zhu and Dingming Wu and Renchi Yang and Ruisheng Wang",

note = "This work was supported by the Natural Science Foundation of China under grants 23IAA00610, 62572326, 62372308, and 62302414, Scientific Foundation for Youth Scholars of Shenzhen University, the Guangdong and Hong Kong Universities “1+1+1” Joint Research Collaboration Scheme, project No.: 2025A0505000002, and the Key Technological Innovation Program of Ningbo City under Grant No. 2024Z297. Dingming Wu is the corresponding author of this paper. Publisher Copyright: {\textcopyright} 2026 IEEE; 42nd International Conference on Data Engineering, ICDE 2026 ; Conference date: 04-05-2026",

year = "2026",

month = may,

day = "4",

doi = "10.1109/ICDE65706.2026.00118",

language = "English",

isbn = "9798331583668",

series = "Proceedings - International Conference on Data Engineering",

publisher = "IEEE",

pages = "1533--1546",

editor = "Khuzaima Daudjee and Qiong Luo and Alkis Simitsis",

booktitle = "Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026",

address = "United States",

}

Chan, TN, Zhu, B, Wu, D, Yang, R & Wang, R 2026, DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis. in K Daudjee, Q Luo & A Simitsis (eds), Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026. Proceedings - International Conference on Data Engineering, IEEE, pp. 1533-1546, 42nd International Conference on Data Engineering, ICDE 2026, Montreal, Canada, 4/05/26. https://doi.org/10.1109/ICDE65706.2026.00118

DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis. / Chan, Tsz Nam; Zhu, Bojian; Wu, Dingming et al.
Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026. ed. / Khuzaima Daudjee; Qiong Luo; Alkis Simitsis. IEEE, 2026. p. 1533-1546 (Proceedings - International Conference on Data Engineering).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis

AU - Chan, Tsz Nam

AU - Zhu, Bojian

AU - Wu, Dingming

AU - Yang, Renchi

AU - Wang, Ruisheng

N1 - This work was supported by the Natural Science Foundation of China under grants 23IAA00610, 62572326, 62372308, and 62302414, Scientific Foundation for Youth Scholars of Shenzhen University, the Guangdong and Hong Kong Universities “1+1+1” Joint Research Collaboration Scheme, project No.: 2025A0505000002, and the Key Technological Innovation Program of Ningbo City under Grant No. 2024Z297. Dingming Wu is the corresponding author of this paper. Publisher Copyright: © 2026 IEEE

PY - 2026/5/4

Y1 - 2026/5/4

N2 - Generating a spatiotemporal K-function plot is frequently adopted to analyze point patterns by domain experts in a wide range of application domains, including criminology, transportation science, urban planning, and epidemiology. However, with the high worst-case time complexity of computing a spatiotemporal K-function plot, the state-of-the-art methods are unable to efficiently (or feasibly) support this tool. To overcome this issue, we develop Distribution-aNd-Aggregation (DNA), which is the first solution that can reduce the worst-case time complexity for supporting this tool. Experiment results on four large-scale location datasets show that DNA achieves speedups of 4.58x to 57.42x over the state-of-the-art methods, without incurring significant space overhead. The implementation of all methods can be found in https://github.com/edisonchan2013928/DNA.

AB - Generating a spatiotemporal K-function plot is frequently adopted to analyze point patterns by domain experts in a wide range of application domains, including criminology, transportation science, urban planning, and epidemiology. However, with the high worst-case time complexity of computing a spatiotemporal K-function plot, the state-of-the-art methods are unable to efficiently (or feasibly) support this tool. To overcome this issue, we develop Distribution-aNd-Aggregation (DNA), which is the first solution that can reduce the worst-case time complexity for supporting this tool. Experiment results on four large-scale location datasets show that DNA achieves speedups of 4.58x to 57.42x over the state-of-the-art methods, without incurring significant space overhead. The implementation of all methods can be found in https://github.com/edisonchan2013928/DNA.

UR - https://www.scopus.com/pages/publications/105048922396

U2 - 10.1109/ICDE65706.2026.00118

DO - 10.1109/ICDE65706.2026.00118

M3 - Conference proceeding

SN - 9798331583668

T3 - Proceedings - International Conference on Data Engineering

SP - 1533

EP - 1546

BT - Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026

A2 - Daudjee, Khuzaima

A2 - Luo, Qiong

A2 - Simitsis, Alkis

PB - IEEE

T2 - 42nd International Conference on Data Engineering, ICDE 2026

Y2 - 4 May 2026

ER -

Chan TN, Zhu B, Wu D, Yang R, Wang R. DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis. In Daudjee K, Luo Q, Simitsis A, editors, Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026. IEEE. 2026. p. 1533-1546. (Proceedings - International Conference on Data Engineering). doi: 10.1109/ICDE65706.2026.00118

DNA: A Distribution-and-Aggregation Solution for Spatiotemporal K-Function-Based Analysis

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this