  Traditional route planning and k nearest neighbors queries only consider
distance or travel time and ignore road safety altogether. However, many
travellers prefer to avoid risky or unpleasant road conditions such as roads
with high crime rates (e.g., robberies, kidnapping, riots etc.) and bumpy
roads. To facilitate safe travel, we introduce a novel query for road networks
called the k safest nearby neighbors (kSNN) query. Given a query location
$v_l$, a distance constraint $d_c$ and a point of interest $p_i$, we define the
safest path from $v_l$ to $p_i$ as the path with the highest path safety score
among all the paths from $v_l$ to $p_i$ with length less than $d_c$. The path
safety score is computed considering the road safety of each road segment on
the path. Given a query location $v_l$, a distance constraint $d_c$ and a set
of POIs P, a kSNN query returns k POIs with the k highest path safety scores in
P along with their respective safest paths from the query location. We develop
two novel indexing structures called Ct-tree and a safety score based Voronoi
diagram (SNVD). We propose two efficient query processing algorithms each
exploiting one of the proposed indexes to effectively refine the search space
using the properties of the index. Our extensive experimental study on real
datasets demonstrates that our solution is on average an order of magnitude
faster than the baselines.
