maps.google.com은 검색 결과 마커를 어떻게 효율적으로 선택하고 렌더링합니까?

Question

지도에 많은 수의 마커를 표시하는 방법을 여러 번 조사해 본 결과, Google에이 문제에 대한 매우 효율적인 해결책이 있어야한다고 생각했습니다. 지도 검색 창에 '숙박 시설'을 입력하면 약 100 점 정도의지도가 표시되며 (확대/축소 수준에 관계없이) 특정 지역을 확대하면 더 많은 지점이 표시됩니다. 그러나 '숙박'검색 레이블에 해당하는 수백만 포인트가 있어야하므로 상당한 양의 마커가 발생합니다.

나는 사용자가 줌인 할 때/그 마커에서 아마도 임의의 선택에 대한 이동 그들이 마커를 필터링 할 도로 getBounds 접근 방식을 사용해야합니다 같은데요. 그러나지도 경계 내에있는 지점 만 선택하려면 전체 데이터베이스를 트롤링해야하므로 잠재적으로 비효율적이라고 생각합니다. Google지도를 너무 빨리 만들 수있는 엄청난 컴퓨팅 성능을 단순히 가지고 있습니까? (대부분의 경우 ...)? 또는 위에 설명 된 접근 방법 이외의 다른 유형의 데이터베이스 쿼리를 수행하는보다 효율적인 방법이 있습니까?

나는 Rails/Google지도 앱을 구축하고 있는데, 백만 점 이상으로 확장 할 수 있기를 바랍니다. 모든 점을 동시에 표시하고 싶지는 않지만 개발하고 싶습니다. 빠른 검색 알고리즘은 서버에 엄청나게 과중하지 않아서 (비교적 작은) 점 선택이 Google에서 수행하는 것과 유사한 방식으로 언제든지지도에 렌더링 될 수 있습니다. 어떤 제안이라도 대단히 감사 할 것입니다!

Answer 1

데이터에 공간 인덱스가 필요합니다. SQL Server 2008에는이 기능이 내장되어 있습니다. 데이터베이스가 아니라면 좌표와 인덱스에서 "타일 번호"를 생성해야합니다. 타일 ​​번호는 1km 정사각형 내의 모든 지점에 대해 고유해야합니다 (예 :). 보기에서 현재 표시된 타일의 타일 번호로 검색하면 효율적인 검색이 이루어져야합니다.

Answer 2

소니아, 같은 검색 내일, 다음 주 또는 다음 달에도 다른 점수가 산출됩니다. Google이 1 백만 가지의 결과로 얻는 결과는 무작위로 그 큰 숫자에서 1000 개를 추출한 것입니다. 그러면 쿼리에서 "임의 샘플링"을 할 수 있습니다.

Answer 3

질문은 두 부분으로 나눌 수 있습니다 :
1. 표시 할 점을 선택하는 방법.
2. 선택한 지점을 빠르게 표시하는 방법.

선택은 여러 가지 정책으로 수행 할 수 있습니다. 예를 들어 사용자 등급이있는 호텔의 경우 가장 높은 등급의 호텔을 먼저 선택할 수 있습니다. 또는 Google은 일부 다른 사람들에게 우선 순위를 부여하기 위해 수익을 얻습니다. 하지만 가장 가능성이 실시간으로 완료되지 않습니다! (단지 이것에 대해서 짐작할 것)

빠른 표시는 사전 제작 된 사용자 정의 타일을 사용하여 이루어집니다. 작은 빨간 점은 자바 스크립트 마커 객체가 아니라 사용자 정의 타일, 같은 :

http://mt3.google.com/mapslt?lyrs=lmq:1000:hotel|cc:US|h:18b|s:115968771510351694523,m%40130&x=2&y=5&z=4&w=256&h=256&hl=en&style=18,28

그 타일을 주기적으로 작성됩니다 (예를 들어 하루에 한 번 또는 일주일에 한 번), 구원, 그래서 그들은 서버입니다 - 캐싱되어 사용할 준비가되었습니다. 마우스 오버 및 클릭 기능은 타일에 선택되고 플롯 된 점에 해당하는 레코드 만 포함하는 작은 테이블 만 검색하는 ajax 호출을 통해 수행 할 수 있습니다. 이 작은 테이블은 새로운 타일셋이 생성 될 때마다 업데이트됩니다.