서버에서 "근처 사용자 검색"기능 구현

Question

도시에 다른 사용자의 위치 정보를 1000000 개 저장하는 데이터베이스가 있다고 가정합니다. 목록이나 배열을 사용하여 모든 지오 코딩을 유지하고 거리를 하나씩 비교하는 경우 서버에서 SearchNearbyUsers(myLocation, 50) 명령을 실행하는 것은 힘들 것입니다.

서버는 Web API 2를 사용하여 C#으로 코딩되었습니다. Geolocations와 같은 계산을 수행하도록 설계된 라이브러리가 있습니까?

사용할 수있는 라이브러리가없는 경우이 계산을 쉽게하기 위해 어떤 데이터 구조를 사용해야합니까? 나는 전에 R-tree을 보았지만 솔직히 말해 나는 논리를 분명히 이해하지 못하고 상당히 복잡해 보인다.

public class GeoLocation 
{ 
    public float latitude { get; set; } 
    public float longitude { get; set; } 
} 

는 위도와 경도 모두는 클라이언트가 전송됩니다 :

이 같은 위치 정보 클래스는 모습입니다. 값은 navigator.geolocation.getCurrentPosition()을 통해 얻습니다.

Answer 1

일반적으로 이러한 공간 작업은 공간 인덱스를 사용하여 수행됩니다. R-Tress는 이것의 단지 하나의 복잡한 예일 뿐이지 만 더 단순한 R-Tress를 얻을 수도 있습니다. 전체 영역을 작은 조각 (예 : 직사각형)으로 나누고 해당 좌표 내에서 색인을 공유하는 영역 내에서 검색하면됩니다. 그래서 저는 여러분의 서버에서 공간 인덱스를 사용하도록 제안한 다음 GDAL과 같은 공간 라이브러리를 사용하도록 제안합니다.

만약 여러분이 좌표 (4,5)를 가지고 있다면, 여러분은 먼저 여러분의 포인트 주위에 witdh x의 버퍼를 가로 지르는 모든 직사각형을 보게 될 것입니다. 이제 직사각형 내에있는 모든 지오메트리를 검색하면됩니다.

EDIT : SQL Server에서는 해당 주변 기능을 검색하기 위해 공간 확장을 사용할 수도 있습니다 (here 참조). 기본적으로 STBuffer을 사용하여 입력 지오 메트릭 주위에 버퍼를 만들고 그 버퍼에서 교차를 수행하십시오. 설명 된 공간 인덱스를 사용하면 이러한 작업이 매우 빠릅니다.

Answer 2

Mongo와 같은 데이터 저장소를 사용하는 경우 지형 공간 쿼리는 매우 쉽고 훌륭합니다. 여기에 있습니다 Docs

당신은 이런 식으로 뭔가를 시도해 볼 수 있습니다. 내가 최근에 프로젝트에서 위치 관련 데이터를 다운로드하는 데 클라이언트에서 사용하는 것입니다. 그것은 꿈입니다. 거리로 조회 할 때 북위 롱과 현실 세계에서의 위치를 ​​찾는

편집은, 가까운 쿼리를 사용하여 당신을 도울 것입니다 구형 인덱스

This Question를 사용해야 올바른 결과를 얻을 수 있습니다 몽고 C# 드라이버.

편집 2 MS SQL을 사용하여 당신에 대해 배우고 나면, 필립이 다른 대답으로 제공 한 유용한 링크가 있습니다.

Query Spatial Data For Nearest Neighbour
Spatial Data

Answer 3

글쎄, 당신은 SQL 서버에 데이터를 저장하는 경우 당신은 공간 인덱스 http://msdn.microsoft.com/en-us/library/bb934196.aspx을 사용하십시오.

Answer 4

초보자이고 나무를 피고 싶다면 ...

1. 지원되는 지역의 격자 맵을 생성

   • 단순한 2D 셀 그리드
   • 
   • 각 셀의 좌표를 가지고 i,j 또는 NI가 i 당 세포의 수는 인덱스 ix=i+j*ni 축
   • 그래서 각 점에 대해 간단하게 셀 소유권을 계산할 수 있습니다.
   • 각 셀마다 같은
   • 어떤 지점의 목록을 만들 :
   • Vector<int> map[nj][ni];
   • 셀 내부의 점 색인 목록을 채우기 ...

2. 비교를

   • 사용자 셀 위치
   • 을 계산하고 해당 셀의 포인트와 8 개의 인접한 포인트 의 ...
   • 더 조밀 한 셀 그리드 더 속도, 당신은
   • 휴대가 비교 범위는 다음
   • 는 전체 범위를 커버하는 것이 비교보다 이웃보다 작은 경우
   안전하게
   •