More or less but as always the devil is in the detail. Here is a paper[1] that summarizes issues with naive approaches. Incidentally. the proposed solution (Hierarchical NSW) in this paper performed fairly well in the industry benchmarks
I thought k-d trees were useless in high-dimentional case. So, it must be something else.
I'd say they're about as useful as euclidean distance is.
A k-d tree gives you exact answers to nearest neighbour queries.
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.