Как Bloom Filters может помочь определить, просканирован ли уже URL?

Я все время слышу о том, как фильтры Блума могут быть полезны при сканировании веб-сайтов, особенно при определении того, просканирован ли уже URL-адрес (поскольку фильтр Блума эффективно использует память при тестировании членства в наборе).

Однако в случае использования веб-сканирования не должно ли количество битов / сегментов быть огромным, учитывая, что встречается почти бесконечное количество URL-адресов? Особенно, если вы используете Google или поисковую систему, ежедневно пытающуюся сканировать данные.

Итак, мой вопрос: как фильтр Блума помогает определить, был ли уже просканирован URL-адрес, когда количество URL-адресов продолжает расти, а количество сегментов остается постоянным?


web-crawler bloom-filter
person Henley    schedule 15.06.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Фильтры Блума основаны на хэш-функциях, которые производят конечный диапазон значений. Независимо от того, сколько URL встречается, каждая функция вернет одно из значений в своем диапазоне. Использование нескольких хеш-функций для выбора битов снижает вероятность ложных срабатываний, но это всегда возможно. Однако это имеет небольшую вероятность и представляет собой расчетный компромисс между точностью и эффективностью.

Существуют практические ограничения на длину URL-адреса, см. этот вопрос. Конечно, это ошеломляющее число. Когда создается больше URL-адресов, может потребоваться обновить хэш-функции и размеры сегментов, но те, которые доступны сегодня, вполне способны справиться с URL-адресами, доступными сегодня, с приемлемо небольшой частотой ошибок.

person Joe    schedule 15.06.2013

arrow_upward
1
arrow_downward

В этом случае, если не будет огромного количества сегментов, вы застрянете с большим процентом ложных срабатываний (в любом случае почти невозможно полностью исключить ложные срабатывания, даже для небольшого приложения).

Один интересный обходной путь будет заключаться в использовании нескольких уровней фильтров цветения вместо плоской структуры, например, первый уровень основан только на имени домена (например, cnn.com), следующий уровень может содержать расширенные URL-адреса (например, как cnn.com/sports/athletics). Но когда речь идет о строковых операциях и нескольких хэш-функциях, не уверен, насколько хорошо это будет работать.

person Rajeev Sampath    schedule 15.06.2013