DB에 장소들을 어떤식으로 저장해야 가까운 장소를 뽑기 편할까요?

[ㅍㅍ(1.237)]

예를들어 10000개의 장소가 db에 저장된다고 가정했을때

사용자의 위치로부터 가장 가까운 n곳을 뽑아내고자 합니다.(n은 사용자가 원하는만큼)

이럴경우 현재위치에서부터 10000개의 장소 각각의 거리를 전부 계산하기에는 너무 비효율적일거 같은데 어떤식으로 하는게 좋을까요?

[ㅁㄴㅇㄹ(211.55)]

Locality Sensitive Hashing요.. O(1)에 근처있는거 대충 찾아냄.. 정확하진 않을수도 있으나.. ㅎㅎㅎ

[ㅁㄴㅇㄹ(211.55)]

좌표를 f(X)를 가지고 더 낮은 차원으로 projection 시킨다음에 그 값을 저장합니다. 그리고 input값을 f(X)로 projection 시켜서 bit 비교 ㄱㄱ

[ㅁㄴㅇㄹ(211.55)]

파라미터에 따라 정확도가 달라질 수 있으나.. 대충 95%는 맞추지 않을까

[ㅁㄴㅇㄹ(211.55)]

K-nearest Searching도 있겠네 클러스터 여러게 생성해서 가까운 클러스터 찾아내서 후보군 추리는거.. 다만 앞에서 말했듯이, 속도가 빨라지면 정확도는 떨어지는데.. 약간 희생해서 O(1) 수준으로 줄일 수 있으면 할만하지 않나