PaperlayerView exact revision on arXiv

Source-linked AI summary

k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation

Tenindra Abeywickrama, Muhammad Aamir Cheema, David Taniar

arXiv:1601.01549v2cs.DS

TL;DR

The paper addresses unresolved questions about kNN queries on road networks, including Euclidean heuristics and fair main-memory comparisons. It experimentally evaluates efficient memory-resident implementations and finds that improved IER often outperforms competing techniques.

  • Problem

    The efficacy of Euclidean distance as a heuristic and the fairness of main-memory comparisons for road-network kNN methods have not been thoroughly investigated.

  • Method

    The paper conducts an extensive experimental evaluation using efficient, fair memory-resident implementations of existing road-network kNN algorithms.

  • Results

    IER-PHL significantly outperformed every competitor in all but a few cases, including on travel time graphs where Euclidean distance is less effective.

  • Takeaways & Limitations

    IER should be included in future comparisons, while implementation efficiency and cache-friendliness require careful attention in main-memory algorithm design.

  • Takeaways & Limitations

    Existing work has emphasized query-processing time, leaving memory usage and index-construction time as additional efficiency concerns.

Abstract

from arXiv · show

A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

1. INTRODUCTION

Road-network kNN queries are important for ubiquitous map services but must avoid computing network distances to every object and irrelevant vertex. This paper evaluates established methods in main memory and revisits IER with faster shortest-path techniques.

  • Motivation: Smartphone adoption and map-based services have made nearby-facility kNN queries among the most popular map queries.Google Maps was used by 54% of smartphone users in 2013.
  • Research challenge: Because objects greatly outnumber k, efficient kNN search must avoid shortest-path computations to all objects.It must also bypass road-network vertices that are not associated with objects.
  • Study scope: The study conducts a thorough experimental evaluation of INE, IER, Distance Browsing, ROAD, and G-tree.The implementations and experiments extend earlier conference work.
  • IER revisited: IER had often been discarded, but the paper investigates it with efficient shortest-path techniques rather than only Dijkstra’s algorithm.Earlier comparisons had not tested IER with newer shortest-path methods.
  • Additional evaluations: The study additionally evaluates object indexes, travel-time graphs, and real-world POIs, addressing previously overlooked settings.These evaluations are identified as missing from earlier work.

2. BACKGROUND

The paper defines road-network kNN by shortest-path distance and focuses on decoupled indexing, which supports multiple changing object sets more economically than blended indexing. The study is limited to in-memory processing because of contemporary workload and hardware considerations.

  • Definitions: A road network is modeled as a connected undirected weighted graph, and kNN returns the k objects with smallest network distances from query vertex q.Network distance is the minimum sum of edge weights, which may represent distance or travel time.
  • Indexing models: Blended indexing combines objects and the road network, whereas decoupled indexing stores separate indexes for them.The evaluated recent techniques use decoupled indexing.
  • Indexing models: Decoupled indexing avoids rebuilding the road-network index for each object set and reduces the impact of object-set changes.This supports queries such as finding restaurants or parking spaces using one network index.
  • Search strategies: Decoupled kNN methods use either expansion-based search, which encounters objects in network-distance order, or heuristic best-first search.Heuristic search evaluates promising candidates without necessarily visiting them in network-distance order.
  • Scope: The experiments restrict attention to in-memory query processing; disk-based settings are considered important but remain outside the paper’s scope.The stated motivation is fast processing under high map-service workloads.

3. METHODS

The evaluated methods combine different indexes and search strategies to retrieve network-distance kNNs: incremental expansion, Euclidean restriction, SILC-based distance browsing, ROAD pruning, and G-tree traversal.

  • Incremental Network Expansion: INE adapts Dijkstra’s algorithm, expanding the nearest queued vertex and terminating when the kth object is found.It can visit every vertex closer to q than the kth object.
  • Incremental Euclidean Restriction: IER retrieves Euclidean nearest objects, computes their network distances, and uses the furthest candidate distance as an upper bound for pruning.The search stops when the next Euclidean distance reaches or exceeds that bound.
  • Distance Browsing: Distance Browsing uses SILC color quadtrees to identify successive vertices on shortest paths, with O(|V|^1.5) total index space and O(|V|^2 log |V|) preprocessing.Shortest paths are computed in O(m log |V|), where m is the number of path edges.
  • Distance Browsing: Distance Browsing estimates network-distance intervals by multiplying Euclidean distance by minimum and maximum Euclidean-to-network distance ratios stored in quadtree blocks.Its implementation retrieves Euclidean nearest neighbors as candidates before computing intervals.
  • ROAD: ROAD partitions the network into hierarchical Rnets and stores border-to-border shortcuts that bypass regions known to contain no objects.Its Association Directory identifies object-containing regions, while the Route Overlay supplies relevant shortcuts.
  • G-tree: G-tree recursively partitions the graph, uses distance matrices for hierarchical distance computation, and prunes empty subgraphs through Occurrence Lists.A priority-queue traversal begins near the query leaf and terminates when k objects are dequeued.

4. DATASETS

The study evaluates kNN methods on ten real-world road networks and uses real-world, uniform, clustered, and minimum-distance object sets to test varied query conditions.

  • 4. DATASETS: Ten real-world road networks include travel-distance and travel-time edge weights, with detailed studies on the 24-million-vertex US network and 1-million-vertex NW network.DisBrw is evaluated for the first time on a network exceeding 500,000 vertices.
  • 4. DATASETS: Eight real-world POI sets from OpenStreetMap represent categories such as fast-food outlets and are mapped to vertices on the US and NW networks.OpenStreetMap data quality can vary, so the largest sets may not represent the true largest sets.
  • 4. DATASETS: Uniform object sets sample road-network vertices randomly, with density d=|O|/|V | varied from 0.0001 to 1 to model POI distributions and sizes.Higher densities simulate larger object sets such as ATM machines.
  • 4. DATASETS: Clustered object sets select random centers and expand outward to choose nearby vertices, modeling POI types that occur in clusters.This distribution was previously used to evaluate ROAD.
  • 4. DATASETS: Minimum-distance object sets place objects progressively farther from an approximate network center, testing query performance as the minimum object distance increases.The sets use thresholds based on Dmax and compare query times across increasing set indices.

5. IER REVISITED

IER is revisited because its traditional Dijkstra-based network-distance computation is slow and repeatedly revisits vertices. Combining IER with faster distance techniques makes it highly competitive, with PHL the strongest variant in the reported comparison.

  • 5. IER REVISITED: IER’s network-distance stage is slow because Dijkstra’s algorithm revisits vertices across successive computations.Suspending and resuming Dijkstra for successive Euclidean neighbors is no better than INE’s Dijkstra-like expansion.
  • 5. IER REVISITED: The study combines IER with Pruned Highway Labelling, G-tree, and other fast shortest-path techniques to assess its true potential.PHL and G-tree support repeated network-distance queries, with G-tree additionally benefiting from materialization.
  • 5. IER REVISITED: 4 orders of magnitude faster than Dijkstra, PHL is the consistent winner among IER variants and is an order of magnitude faster than the next-best method at peak performance.All methods converge as object density increases because the search space becomes smaller.

6. IMPLEMENTATIONINMAINMEMORY

The paper shows that in-memory implementation choices can materially change algorithm comparisons. Case studies of G-tree distance matrices and INE demonstrate that data layout, locality, and simple implementation decisions strongly affect query time.

  • 6. IMPLEMENTATIONINMAINMEMORY: Memory-resident processing is realistic for map-based services, but implementation efficiency can make algorithmic efficiency irrelevant.The study therefore examines implementation choices and develops guidelines for efficient in-memory processing.
  • 6.1 Case Study: G-tree Distance Matrices: G-tree distance matrices store precomputed distances between child borders, enabling longer distances to be assembled piece by piece along a tree path.The assembly follows the path from the source leaf to the least-common ancestor and then to the target leaf.
  • 6.1 Case Study: G-tree Distance Matrices: G-tree distance matrices contain redundant border-to-border distances, while grouping borders and using offsets supports ordered array access and O(1) retrieval.The optimized layout avoids arbitrary-order access during assembly.
  • 6.1 Case Study: G-tree Distance Matrices: 30 times slower than a 1D array, chained hashing substantially degrades distance-matrix performance; quadratic probing improves it but remains an order of magnitude slower.Using either hash-table implementation would incorrectly make G-tree appear to be the worst algorithm.
  • 6.1 Case Study: G-tree Distance Matrices: Arrays incur the fewest cache misses because access order makes successive values more likely to remain in cache, whereas chained hashing suffers from indirection.Quadratic probing improves locality but requires more instructions for collision resolution.
  • 6.2 Guidelines for Implementation Choices: Each progressively improved INE implementation choice roughly halves query time, producing a final implementation 6−7× faster than the first cut.The improvements include priority-queue choices and contiguous graph-array layouts that increase cache-hit likelihood.

7. EXPERIMENTS

The experiments compare query performance, indexing costs, scaling behavior, and real-world object sets across in-memory kNN methods. IER-based methods are frequently strongest, while index size and heuristic behavior determine practical applicability.

  • Pre-Processing Cost: Index construction and storage remain important evaluation criteria: G-tree uses 2.9GB on the US dataset versus 4.4GB for ROAD, while DisBrw requires 17GB on NW.IER’s R-tree object indexes are significantly faster to build and support updates, making them relevant for changing object sets.
  • Varying Network Size: IER-based methods consistently achieve the fastest query times across increasing network sizes, while DisBrw’s large index restricts it to five datasets.DisBrw’s index size exceeds memory capacity beyond the first five road networks despite query performance close to ROAD.
  • Varying Network Size: As network size grows, ROAD scales extremely well because bypassed object-less regions remain similarly sized, while G-tree’s border-to-border path cost increases.G-tree’s advantage over ROAD decreases with network size as its nodes have more borders at the same depth.
  • Varying k: IER-PHL is 5× faster than every other method on NW, while IER-Gt is twice as fast as G-tree on US when PHL cannot be constructed.IER-Gt benefits from a heuristic that estimates distances to objects within subgraphs, reducing costly non-materialized distance computations.
  • Varying k: G-tree outperforms ROAD, DisBrw, and INE on NW and at its peak is nearly an order of magnitude better than ROAD and DisBrw as k increases.G-tree benefits from materializing more subsequent traversals as more objects are encountered.
  • Varying k: IER-PHL remains significantly faster than G-tree for sparse hospitals, whereas clustered fast-food outlets reduce Euclidean distance’s ability to distinguish candidates.The clustered-object trend mirrors the reduced effectiveness of Euclidean distance in synthetic clustered sets.

8. CONCLUSIONS

The paper’s conclusions emphasize that careful in-memory experimentation changes the comparative picture of road-network kNN methods. Revived IER is often the strongest approach, while implementation efficiency, memory use, and construction cost remain central concerns.

  • Conclusions: G-tree generally outperforms INE, DisBrw, and ROAD, but its relative improvement is smaller and sometimes reversed under efficient implementations.The study evaluates object indexes, travel-time graphs, and real-world POIs alongside query performance.
  • Conclusions: IER-PHL significantly outperforms every competitor in all but a few cases, including travel-time graphs where Euclidean distance is less effective.The authors investigated IER with fast network-distance techniques for the first time and identify it as a flexible framework.
  • Conclusions: IER-Gt often outperforms the original G-tree kNN algorithm despite using the same index, suggesting that Euclidean nearest-neighbor ordering can improve search heuristics.The authors identify room for richer object indexes and improved kNN search heuristics.
  • Conclusions: The study argues that future comparisons must include IER and evaluate memory usage and construction time alongside query efficiency.The paper notes a need for algorithms and indexes with comparable efficiency but lower memory use and construction cost.
  • Conclusions: Small cache-friendliness improvements can significantly improve algorithm performance, so main-memory implementations require careful attention to data structures and layout.The authors state that these implementation insights apply beyond the techniques studied.

A.1.1 Distance Browsing via Euclidean NN

Distance Browsing searches an Object Hierarchy using SILC-derived distance bounds, while DB-ENN replaces costly hierarchy intersections with Euclidean nearest-neighbor candidates. The variant preserves correctness by interleaving Euclidean search with network-distance refinement.

  • Distance Browsing via Euclidean NN: DisBrw prioritizes Object Hierarchy branches using lower and upper network-distance bounds computed from SILC quadtree intersections.Repeated intersections can be expensive and may be recomputed while descending the hierarchy.
  • Distance Browsing via Euclidean NN: DisBrw maintains a priority queue of vertices and hierarchy nodes keyed by lower bounds, plus a candidate queue of up to k objects keyed by upper bounds.The kth candidate upper bound Dk controls further refinement and candidate updates.
  • Distance Browsing via Euclidean NN: SILC refinement tightens candidate bounds and updates the next shortest-path vertex using a binary search on the Morton List.Candidates are re-enqueued when their lower bounds remain below Dk.
  • Distance Browsing via Euclidean NN: DB-ENN eliminates Object Hierarchy intersections by initially retrieving Euclidean kNNs from an R-tree as candidate objects.It computes distance intervals for candidates and inserts them into the same search queues used by DisBrw.
  • Distance Browsing via Euclidean NN: DB-ENN suspends the Euclidean kNN search and resumes it whenever its next candidate may precede the current network-search queue.This comparison uses the fronts of the Euclidean and network queues before dequeuing from Q.

A.1.2 Exploiting Vertices with Outdegree ≤2

The paper exploits chains of degree-2 road-network vertices to skip repeated quadtree work during shortest-path refinement. This optimization substantially accelerates DisBrw, especially on networks dominated by degree-2 vertices.

  • Exploiting Vertices with Outdegree ≤2: 30.3% of vertices in the US dataset have degree-2, while another 19.9% have degree-1.Such vertices can represent speed-limit changes or road curvature and affect shortest-path computation.
  • Exploiting Vertices with Outdegree ≤2: On a degree-2-or-less chain, SILC can skip quadtree consultation and jump directly to the next relevant vertex.This avoids the O(log |V|) per-vertex cost during refinement.
  • Exploiting Vertices with Outdegree ≤2: 30% improvement in query time is reported for OptDisBrw on the default NW dataset.The improvement coincides with the quoted proportion of degree-2 vertices.
  • Exploiting Vertices with Outdegree ≤2: 95% of vertices in the North America highway network are degree-2, producing longer chains for optimization.That network contains 175,813 vertices.
  • Exploiting Vertices with Outdegree ≤2: OptDisBrw is up to an order of magnitude faster than DisBrw on the North America highway network.The paper therefore uses chain-optimized refinement for DisBrw in its experiments.

A.2.1 G-tree Leaf Search Improvement

The improved G-tree leaf search handles both shortest paths confined to the query leaf and paths that leave and re-enter it. It yields substantial speedups, particularly when leaves contain many objects relative to k.

  • G-tree Leaf Search Improvement: G-tree leaf search must account for paths that stay inside the query leaf and paths that leave and re-enter through leaf borders.The original search uses Dijkstra’s algorithm within the leaf and inserts unsettled borders using the distance matrix.
  • G-tree Leaf Search Improvement: The modified search continues until the first k leaf objects are settled, while tracking borders that may enable shorter external paths.Before a border is settled, settled objects are kNNs; afterward, subsequent objects may not be.
  • G-tree Leaf Search Improvement: The improved leaf search produces a significant speed-up for k = 10 and over an order of magnitude improvement for k = 1 at the highest density on both datasets.Benefits also appear at lower densities when leaves contain far more objects than k.
  • G-tree Leaf Search Improvement: The leaf-search procedure tracks visited vertices, settled targets, borders, and queued vertices while expanding the query leaf.Its stopping condition requires fewer than k results and fewer than k targets found.

B. REPEATED EXPERIMENTS

The paper extends evaluation to travel-time graphs, where kNNs are still ranked by network distance. DisBrw is excluded from these experiments because its SILC distance-ratio information depends heavily on Euclidean distance.

  • REPEATED EXPERIMENTS: A kNN query can rank objects by network distance defined using travel time rather than physical distance.The appendix reports additional experiments on travel-time graphs.
  • REPEATED EXPERIMENTS: ROAD’s travel-time implementation uses a route overlay and association directory with a priority queue of unvisited vertices.RelaxShortcuts processes shortcut paths and avoids revisiting vertices.
  • REPEATED EXPERIMENTS: DisBrw is not tested on travel times because SILC distance ratios rely heavily on Euclidean distance.The paper expects adaptation to be more complex and performance likely slower than for travel distances.

B.1 IER Variants on Travel Times

On travel-time graphs, IER benefits substantially from stronger shortest-path techniques, with IER-PHL generally outperforming alternatives while density increases false hits.

  • B.1 IER Variants on Travel Times: IER adapts to travel-time graphs, where Euclidean distance is a less effective lower bound than in travel-distance graphs.Travel-time networks can have stronger hierarchy structure, making shortest-path techniques behave differently across weight types.
  • B.1 IER Variants on Travel Times: Higher object densities worsen all methods because looser Euclidean bounds produce more false hits, although MGtree degrades least.At density 0.0001, fewer objects and fewer similar distances lead to fewer false hits than at density 0.001.
  • B.1 IER Variants on Travel Times: PHL performs significantly better than TNR across the tested travel-time settings.For low densities, TNR also outperforms MGtree on travel-time graphs.
  • B.1 IER Variants on Travel Times: As the network grows, TNR deteriorates more rapidly because fewer queries can use transit nodes and more kNN distances require slower local computation.With the same grid size, larger cells contain more vertices, increasing reliance on local processing.

B.2 Road Network Pre-Processing and Space

Travel-time graphs enable more effective preprocessing and pruning than travel-distance graphs, while experiments examine network size, object sets, and query settings alongside prior methods and indexing trade-offs.

  • B.2 Road Network Pre-Processing and Space: PHL is faster to construct and uses significantly less memory on travel-time graphs, scaling through the US dataset with 24 million vertices.The stronger hierarchy of travel-time graphs enables more effective pruning and smaller label sizes.
  • B.2 Road Network Pre-Processing and Space: IER-PHL is generally the best-performing method across varying travel-time query parameters, except at densities greater than 0.01.The experiments vary k, uniform object density, minimum object distances, and cluster count on the NW dataset.
  • B.2 Road Network Pre-Processing and Space: Real-world object-set experiments reproduce the previously observed trends, including degradation of G-tree on the US dataset and broader applicability of IER-PHL.IER-PHL can be compared on the US dataset because its index is constructible for all datasets.
  • B.2 Road Network Pre-Processing and Space: Earlier road-network kNN methods include RNE, VN3, Nearest Descendent, UNICONS, Islands, and full-index approaches with varying preprocessing and storage costs.Several methods precompute nearest neighbors or distance information, while full indexes store ordered objects for every vertex and incur substantial space overhead.
  • B.2 Road Network Pre-Processing and Space: Decoupling object sets from road-network indexes reduces repeated storage and preprocessing when many object sets are queried or changed.Blended indexing must repeatedly process the road network for each object set, whereas decoupled indexing uses one road-network index.
  • B.2 Road Network Pre-Processing and Space: The study focuses on static data; continuous kNN variants involving moving queries, paths, or moving objects remain beyond its scope.The related-work discussion identifies these continuous-query problems without evaluating them here.
Loading 1601.01549v2…