I have a large data set (more than 3 Million distinct data points that have 6 integer numbers). I want to compute the shortest route in terms of hamming distance. (amount of numbers that change between two data points, meaning that the distance between two points can either be 1, 2, 3, 4, 5 or 6).

Using even nearest neighbour is too slow because it is O(n²). And all the other algorithms I have seen so far ar also at least O(n²).

Are there faster heuristics for optimising the traveling salesman problem? (maybe O(n*log(n)) for example)