[esafak]

The solution to that is balanced LSH, which ensures each hyperplane divides the data evenly by moving its offset, if I recall.