Went back to standard manhattan distance. It is not taking forever now, and it provides better results for farther away objects. But I suspect it will be slow if we cannot find the requested object...