  Given a graph $G=(V,E)$ where each vertex is assigned a color from the set
$C=\{c_1, c_2, .., c_\sigma\}$. In the (approximate) nearest colored node
problem, we want to query, given $v \in V$ and $c \in C$, for the (approximate)
distance $\widehat{\mathbf{dist}}(v, c)$ from $v$ to the nearest node of color
$c$. For any integer $1 \leq k \leq \log n$, we present a Color Distance Oracle
(also often referred to as Vertex-label Distance Oracle) of stretch $4k-5$
using space $O(kn\sigma^{1/k})$ and query time $O(\log{k})$. This improves the
query time from $O(k)$ to $O(\log{k})$ over the best known Color Distance
Oracle by Chechik \cite{DBLP:journals/corr/abs-1109-3114}. We then prove a
lower bound in the cell probe model showing that our query time is optimal in
regard to space up to constant factors. We also investigate dynamic settings of
the problem and find new upper and lower bounds.
