COL-Trees: Efficient Hierarchical Object Search in Spatial Networks
Organizations: Center for Computational Science, RIKEN, Japan · Faculty of Information Technology, Monash University, Australia · Department of Computer and Information Science, University of Konstanz, Germany
Abstract
Many spatial network applications, such as map-based services, rely heavily on efficient methods to search for relevant nearby points-of-interest (POIs). A Nearest Neighbor (NN) query is one such example that finds the 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 Nearest Neighbor (ANN) queries require POIs that are close to multiple agents. Farthest Neighbors (FN) 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 ANN, FN, 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 |
|---|---|
| A spatial network graph | |
| The vertex set of , e.g., representing intersections | |
| The edge set of , e.g., representing road segments | |
| The POI (object) vertex set ( ) | |
| The number of result objects a query must return ( ) | |
| Shortest path (network) distance between and in |
| Complexity | ALT [ 30 ] | SUL-Tree (Ours) | OL [ 4 ] | COL-Tree (Ours) |
|---|---|---|---|---|
| Space | ||||
| Time |
| Name | Type | Edge Weights | |||||
|---|---|---|---|---|---|---|---|
| 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 |
| Technique | A NN | FN | Range | NN |
|---|---|---|---|---|
| COLT-PHL (Ours) | ✓ | ✓ | ✓ | ✓ |
| IER-PHL [ 69 ] | ✓ | ✗ | ✓ | ✓ |
| NVD-PHL [ 4 ] | ✓ | ✗ | ✓ | ✓ |
| AUB-PHL | ✗ | ✓ | ✗ | ✗ |
| 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 ( ) | 1,696 MB | 577 MB | 66.0% |
| Variable | Tested Values | A NN | FN | Range |
|---|---|---|---|---|
| , , , | ||||
| , , , | ||||
| , , , | ||||
| Landmark Type | Random , Minmax , Farthest , Slice | Minmax | Random | Minmax |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Graph-Based Retrieval
Graph-based retrieval uses links among documents, entities, or vectors to find connected evidence beyond isolated similarity matches.
See all 156 papers