검색 엔진이 부정확 한 계산 (약 XXX 결과)

Question

Google에서 검색 할 때 (Altavista가 같은 일을했다고 확신합니다) "약 1-10의 xxxx의 결과"라고 말합니다.

이것은 항상 나를 놀라게했다 ... "에 관한"무슨 뜻인가요?
그들은 어떻게 대략적으로 계산할 수 있습니까?
왜 그들이 합리적인 시간 안에 정확한 인물을 제시 할 수 없는지 이해하지만,이 "근사"하나에 어떻게 도달합니까?

내가 놓친 이론 뒤에 많은 이론이 있다고 확신합니다 ...

Answer 1

아마도 쿼리 계획에서 대부분의 SQL 시스템에서 사용하는 추정 행 카운트와 유사합니다. 테이블의 여러 행 (마지막으로 통계가 수집되었지만 일반적으로 최신 상태가 아닌)의 여러 행이 추정 된 선택성을 곱한 (일반적으로 일부 작은 서브 세트를 샘플링하여 계산 된 일종의 통계 분포 모델을 기반으로합니다. 행).

PostgreSQL 매뉴얼에는 섹션이 있습니다 플래너가 사용하는 통계 적어도 PG_STATS 및 기타 여러 섹션에 대한 링크를 따라 가면 상당히 유익합니다. 나는 그것이 Google이하는 일을 실제로 설명하지는 않지만, 첫 번째 N 행을 얻을 수있는 하나의 모델과 더 많은 수의 추정치를 보여줍니다.

Answer 2

귀하의 질문과 관련이 없지만 간단한 자아 검색을 할 때 내 친구가 만든 작은 농담을 상기시켜줍니다 (그리고 이름을 구글링 한 적이 없다고 말하지 마십시오). 그는 같은 것을 말했다

"와우, 약 5,000 개의 결과가 0.22 초 만에! 이제, 이것이 1 분, 1 시간, 하루에 얼마나 많은 결과가 얼마나 많은지 상상해보십시오!"

Answer 3

추정치가 통계를 기반으로한다고 생각합니다. 그들은 모든 관련 페이지 일치를 계산하지는 않을 것이므로, 그들이 할 일은 일부 휴리스틱을 기반으로 쿼리와 일치하는 페이지의 대략 어떤 비율을 해결 한 다음,이를 카운트의 기초로 사용하는 것입니다. .

한 가지 휴리스틱은 샘플 수를 수행하는 것일 수 있습니다. 통계적으로 중요한 답변을 얻으려면 샘플에서 너무 많이 걸리지 않을 것입니다.

Answer 4

아직 언급되지 않은 한 가지는 중복 제거입니다. 일부 검색 엔진 (특히 Google이 어떻게 수행하는지 정확히 잘 모르겠습니다)는 휴리스틱을 사용하여 두 개의 다른 URL에 동일한 (또는 매우 유사한) 컨텐츠가 포함되어 있는지 결정하고 결정하여 결과적으로 결과입니다.

156 개의 고유 한 URL이 있지만 그 중 9 개가 다른 결과의 복제물로 표시된 경우 "147 개의 고유 한 결과와 9 개의 복제물을 포함하는 156 개의 결과"와 같은 것보다 "약 150 개의 결과"라고 말하는 것이 간단합니다.

Answer 5

정확한 결과를 반환하는 것은 정확하게 계산할 오버 헤드의 가치가 없습니다. '약 1,000,000'이 아닌 1,004,345 개의 결과가 있다는 것을 알면 값이 많지 않기 때문에 최종 사용자 경험 관점에서 총계를 계산하는 데 추가 시간이 아닌 결과를 더 빨리 반환하는 것이 더 중요합니다.

Google 자체에서 :"Google의 총 검색 결과 수에 대한 계산은 추정치입니다. 우리는 야구장 수치가 가치가 있다는 것을 이해하고 정확한 계정보다는 추정치를 제공함으로써 품질 검색 결과를 더 빨리 반환 할 수 있습니다."