We present a new approach for approximate 
nearest neighbor queries for sets of high dimensional points under any
$L_t$-metric, $t=1,\ldots,\infty$.
The proposed algorithm is efficient and simple to implement. 
The algorithm uses multiple shifted copies of the data points 
and stores them in up to $(d+1)$ B-trees where $d$ is the dimensionality
of the data, sorted according to their position along a space filling curve.
%such as the Hilbert curve. 
This is done in
a way that allows us to guarantee that a neighbor 
within an $O(d^{1+1/t})$ factor of the exact nearest, can be
returned with at most $(d+1)\log_p n$ page accesses, where $p$ is
the branching factor of the B-trees.
In practice, for real data sets, our approximate technique finds
the {\em exact} nearest neighbor between 87\% and 99\% of the time
and a point no farther than the third nearest neighbor between
98\% and 100\% of the time.
Our solution is dynamic,
allowing insertion or deletion of points in $O(d\log_p n)$ page
accesses and
generalizes easily to find approximate $k$-nearest
neighbors.