You list hyperdimensional hashing as one of the early methods that you tried without success. While only good for point-to-point distance comparison in its simplest application, it seems that geohashes meet the scalar/vector problem that you describe. Do you have any experience with geohashes, and if so, what's your opinion of them?