A k-d tree is a data structure. Whether you use that for exact nearest neighbor query or approximate is up to the algorithm used. K-d trees work well for a handful of dimension beyond that it becomes quite expensive.