COL-Trees: Efficient Hierarchical Object Search in Spatial Networks
Authors: Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt
Organizations: Center for Computational Science, RIKEN, Japan · Faculty of Information Technology, Monash University, Australia · Department of Computer and Information Science, University of Konstanz, Germany
Many spatial network applications, such as map-based services, rely heavily on efficient methods to search for relevant nearby points-of-interest (POIs). A k Nearest Neighbor (kNN) query is one such example that finds the k closest POIs from an agent's location. While most existing techniques for spatial networks focus on retrieving nearby POIs for a single agent, these search heuristics do not translate to many other applications. For example, Aggregate k Nearest Neighbor (AkNN) queries require POIs that are close to multiple agents. k Farthest Neighbors (kFN) queries require POIs that are the antithesis of nearest. Such problems naturally benefit from a hierarchical approach, but existing methods rely on Euclidean-based heuristics, which have diminished effectiveness in spatial networks such as road network graphs. We propose a novel data structure, COL-Tree (Compacted Object-Landmark Tree), to address this gap by enabling efficient hierarchical graph traversal using a more accurate landmark-based heuristic. We then present query algorithms that utilize COL-Trees to efficiently answer AkNN, kFN, and other queries. Our experiments evaluate performance on real-world and synthetic datasets including multiple types of spatial networks, such as road networks of varying sizes and edge weights, terrain networks, and 2D physics meshes. The results demonstrate that our techniques significantly outperform existing approaches, achieving up to three orders of magnitude improvement. Moreover, this comes at a small pre-processing overhead in both theory and practice.
Figures & tables
Symbol
Description
G
A spatial network graph
V
The vertex set of G , e.g., representing intersections
E
The edge set of G , e.g., representing road segments
P
The POI (object) vertex set ( P⊆V )
k
The number of result objects a query must return ( k≤∣P∣ )
d(s,t)
Shortest path (network) distance between s and t in G
Table 1: Summary of frequently used notations and symbols
Figure 1: Running example graph with sample query and object vertices, and their network distances
Figure 2: Subgraph-Landmark Tree (SUL-Tree)
Figure 3: Compacted Object-Landmark Tree (COL-Tree)
Complexity
ALT [ 30 ]
SUL-Tree (Ours)
OL [ 4 ]
COL-Tree (Ours)
Space
O(m∣V∣)
O(m∣V∣log∣V∣)
O(m∣P∣)
O(m∣P∣)
Time
O(m∣V∣log∣V∣)
O(m∣V∣log2∣V∣)
O(m∣P∣log∣P∣)
O(m∣P∣log∣P∣)
Table 2: Comparison of space and time complexity for the proposed methods versus previous landmark-based indexes
Figure 4: Hierarchical Subgraph Vertex Ordering
Figure 5: Lower-Bound Distance to Subgraph Borders
Name
Type
∣V∣
∣E∣
Edge Weights
b
α
λ
US
Road Network
23,947,347
57,708,624
Time
8
1024
256
W-US
Road Network
6,262,104
15,119,284
Time, Distance
8
512
128
NACA0015
2D Mesh
1,039,183
6,229,636
Distance
4
256
64
SRTMGL3
Terrain
1,442,401
11,524,800
Distance
4
256
64
Table 3: Datasets tested and their features/statistics
Table 9
Technique
A k NN
k FN
Range
k NN
COLT-PHL (Ours)
✓
✓
✓
✓
IER-PHL [ 69 ]
✓
✗
✓
✓
NVD-PHL [ 4 ]
✓
✗
✓
✓
AUB-PHL
✗
✓
✗
✗
Table 6: Compared methods for each query
Figure 6: A k NN max query performance on different real-world POI sets
Figure 7: Performance for max function
Figure 8: Performance for sum function
Figure 14
Figure 11: k FN query performance on different real-world POI sets
Figure 12: Performance for k FN queries
Figure 13: Range query performance on different real-world POI sets
Figure 14: Performance for range queries
Table 7: Pre-processing costs of graph and object indexes
Optimization
Before
After
% Improv.
No Hash-table Dijk.
218 s
144 s
34.0%
Border Set Dijk. (s)
144 s
103 s
28.5%
Border Set Dijk. ( γ )
6.5
3.7
43.1%
Subgraph Ordering
3,410 MB
2,291 MB
32.8%
Subgraph Ordering ( m=1 )
1,696 MB
577 MB
66.0%
Table 8: Impact of SUL-Tree pre-processing optimizations described in Section 8 on the US road network ( m=4 random landmarks unless stated otherwise). Times are for SDL computation only, so they exclude other costs included by timing for Table 7(a) , such as partitioning.
Variable
Tested Values
A k NN
k FN
Range
b
2 , 4 , 8 , 16
8
8
8
λ
128 , 256 , 512 , 1024
256
256
256
m
1 , 2 , 4 , 8
1
8
1
Landmark Type
Random , Minmax , Farthest , Slice
Minmax
Random
Minmax
Table 9: Tested values and finalized COL-Tree parameters on the US dataset for each query
Figure 15: Query performance with varying branching factor b (relative to each query’s default in Table 9 )
Figure 16: Query performance with varying object distance list size λ (relative to each query’s default in Table 9 )
Figure 17: Query performance with varying number of landmarks m (relative to each query’s default in Table 9 )
Figure 18: Query performance with varying landmark type (relative to each query’s default in Table 9 )
Figure 19: Heuristic performance of distance vs. travel time edge-weights on Western US dataset (A k NN by sum )
Figure 20: NACA0015 ( k FN)
Figure 21: SRTMGL3 (A k NN by sum )
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 22: k NN query performance on different real-world POI sets