AWS SimpleDB에 대한 공간 쿼리

Question

사람들이 Amazon Web Services SimpleDB에서 공간 쿼리를 효율적으로 수행하는 방법을 제안했는지 알고 싶습니다.

공간 쿼리는 주어진 위도와 경도 반경의 객체를 찾는 것을 의미합니다.

Answer 1

SimpleDB는 현재 내장 된 공간 검색 작업을 제공하지 않지만 수행 할 수 없다는 것을 의미하지는 않습니다. Geospatial을 인식하지 못하는 SimpleDB와 같은 데이터베이스에서 지형 공간 검색을 구현하는 몇 가지 방법이 있으며, 모두 데이터베이스를 사용하여 지리 정보 경계 상자를 기반으로 한 거친 첫 번째 선택을 검색 한 다음 애플리케이션에서 반환 된 데이터를 필터링하여 Haversine formula과 같은보다 정확한 알고리즘.

당신 수 저장 (제로 패딩과 정규화) 숫자 속성 다음 이중 범위 쿼리 (lat >= minLat and lat <= maxLat and lon >= minLat and lon <= maxLat)를 수행하지만 theese 조건 중 어느 것도 선택하기 때문에 (각 술어가 항목을 많이 일치)와 같은 위도와 경도 이상적이지 않습니다 (Tuning Queries 참조).

더 좋은 방법은 GeoHashes입니다.

Geohashes는 임의 정밀도와 같은 속성, 근처의 위치에 대한 유사한 접두사 , 점차 그 크기를 줄일 (점차 정밀도를 잃게)하는 코드의 끝에서 문자를 제거하는 가능성을 제공합니다. 가 -49.265506 좌표 -25.382708하고

실용적인 예로서, geohash와 6gkzwgjzn820가 디코딩 geohash와 6gkzwgjz 동안 것 디코드 -25.383 및 -49.266에, 우리는 동일한 영역에서 동일한 위치를 가지고 있다면, -25.427 및 -49.315와 같이이 6gkzmg1w로 인코딩 된 것을 볼 수 있습니다 (유사한 접두사에 유의하십시오).

GeoHashes 같은 항목의 위치와 http://geohash.org/site/tips.html

에서 당신은 경계 상자 (where GeoHash like '6gkzmg1w%')를 검색 할 like 연산자를 사용할 수 있지만, like 운영자가 고가이기 때문에 (Comparison Operators) 더 좋은 방법은 비정규 화하는 것 (GeoHash6 GeoHash8 등) 별도의 속성으로 각 GeoHash 접두어 수준 (필요한 검색 정밀도에 따라 달라지는 수)을 저장 한 다음 간단한 등가 술어 (where Geohash8 = '6gkzmg1w')를 사용하여 데이터를 저장합니다.

이제 GeoHash의 단점을 살펴 보겠습니다. GeoHash가 검색 창 중앙에 위치한다는 가정을 할 수 없으므로 이웃하는 모든 접두어도 검색해야합니다. 프로세스가 양호 geohash와도 자릿수 (오른쪽) 감소로 특성을 갖는다 geohash-js

설명되어 정밀도가 저하시킨다. 이 속성은 바운딩 상자 검색을 수행하는 데 사용될 수 있습니다. 서로 인접한 점은 Geohash 접두어와 비슷합니다. 주어진 포인트가 소정 geohash와 바운딩 박스의 에지에 표시 될 수 있으므로

그러나,이 점을 중심으로 실제 근접 검색을 수행하기 위해 geohash와 값의리스트를 생성 할 필요가있다. Geohash 알고리즘은 base-32 번호 매기기 시스템을 사용하기 때문에 은 단순한 찾아보기 테이블을 사용하여 Geohash 값인 다른 Geohash 값을 둘러싼 Geohash 값을 유도 할 수 있습니다. 38.897, -77.036

가 geohash와 알고리즘을 사용하여이 위도와 경도가 를 변환됩니다 : dqcjqcp84c6e

간단한 경계 상자에

그래서, 예를 들어, 1600 펜실베이니아 애비뉴, 워싱턴 DC는 해결 이 점은이 geohash와 자른 에 의해 설명 될 수있는 주위 :

그러나

dqcjqc 'dqcjqcp84c6e'dqcjqc '내부 중심 아니고,'dqcjqc '내의 찾고 어떤 것은 원하는 타지 놓칠 수도 ts.

그래서 Geohash의 수학적 속성을 사용하여 에 'dqcjqc'의 이웃을 빠르게 계산할 수 있습니다. 우리는 그들이 것을 발견 : 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8'이 주위에 우리에게 경계 상자를 제공

를 ' dqcjqcp84c6e '대략 2km x 1.5km 이며 단지 9 개의 키로 데이터베이스를 검색 할 수 있습니다. SELECT * FROM table 어디 LEFT (geohash, 6) IN ('dqcjqc ', 'dqcjq1 ','dqcjq1 ',' 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8'); 만 검색 반경 내에서의 아이템을 얻을 where GeoHash6 in('dqcjqc', 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8')을 것 한 다음에 순서대로 결과에 대한 당신의 하버 사인 필터링을 할거야 SimpleDB의 쿼리로 번역

.

Answer 2

도움이 될 수 있으므로 여기를 남겨 두겠습니다.

14 년 전 우리는 반경 내에서 위치의 지리 검색 테이블을 만들려고했습니다. 분명히 지형 지수 나 그와 비슷한 것이 없었습니다. 문자 그대로 표준 SQL과 오라클 만있었습니다 ... 어쨌든, 고정 된 평면 필드에서 모든 lat/lng를 킬로미터로 변환했습니다. 본질적으로 요즘에는 어떤 지형 공간 색인이 사용됩니까?

정확히 무엇을하는지 설명하기 위해 세계를 평평한 표면으로 바꾸고 반경별로 선택할 수있는 SQL 속임수를 사용하여 선택하는 두 점으로부터 거리를 얻을 수도 있습니다. 또한 원시 풀 정수이기 때문에 쿼리가 빠르게 빠르게 수행됩니다. Geohashes에 대한 논의에 대한

https://gist.github.com/tobsn/899413