Fast Network K-function-based Spatial Analysis

Summary: Proposes count augmentation (CA) and neighbor sharing (NS) to accelerate network K-function computation on spatial networks. Integrates shortest path sharing (ASPS) to reduce worst-case complexity, delivering up to 165.85x speedups over prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0b810e7e5103815b
Venue: VLDB
Year: 2022
Pagerank: 5.1064323e-05
Overall Rank: 9,850 | 33.98%
DOI: 10.14778/3551793.3551836
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Tsz Nam Chan (Hong Kong Baptist University)
2. Leong Hou U (University of Macau)
3. Yun Peng (Guangdong University of Technology)
4. Byron Choi (Hong Kong Baptist University)
5. Jianliang Xu (Hong Kong Baptist University)

BibTeX Citation

@article{chan_vldb22,
        title = {{Fast Network K-function-based Spatial Analysis}},
        author = {Chan, Tsz Nam and U, Leong Hou and Peng, Yun and Choi, Byron and Xu, Jianliang},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {11},
        pages = {2853--2866},
        doi = {10.14778/3551793.3551836},
        url = {https://doi.org/10.14778/3551793.3551836},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,482	Large Language Models for Spatial Analysis Queries	2025	VLDB	4.9605343e-05
11,606	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
192	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025740385
463	Query Processing in Spatial Network Databases	2003	VLDB	0.00017806376
1,233	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011397529
1,250	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011325987
1,270	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011232621
1,346	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010949128
2,689	Distance Indexing on Road Networks	2006	VLDB	8.1137602e-05
2,702	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	8.0958339e-05
3,935	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD	6.8990945e-05
7,762	Clustering Objects on a Spatial Network	2004	SIGMOD	5.4406715e-05
9,853	KDV-Explorer: A Near Real-Time Kernel Density Visualization System for Spatial Analysis	2021	VLDB	5.1064323e-05
11,892	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	4.9605343e-05
11,973	SAFE: A Share-and-Aggregate Bandwidth Exploration Framework for Kernel Density Visualization	2022	VLDB	4.9605343e-05
11,976	SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization	2022	VLDB	4.9605343e-05
12,052	Fast Augmentation Algorithms for Network Kernel Density Visualization	2021	VLDB	4.9605343e-05
12,108	QUAD: Quadratic-Bound-based Kernel Density Visualization	2020	SIGMOD	4.9605343e-05
13,782	LIBKDV: A Versatile Kernel Density Visualization Library for Geospatial Analytics	2022	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,375	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD
2	9,312	Efficient Algorithms for Finding Optimal Meeting Point on Road Networks	2011	VLDB
3	5,357	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
4	11,653	Efficient kNN Search in Public Transportation Networks	2024	VLDB
5	5,035	Fast Large-Scale Trajectory Clustering	2020	VLDB
6	7,762	Clustering Objects on a Spatial Network	2004	SIGMOD
7	449	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
8	10,719	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
9	681	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
10	12,052	Fast Augmentation Algorithms for Network Kernel Density Visualization	2021	VLDB