Comments 8
Мой вопрос на тостере с сылками на кучу разных вероятностных алгоритмов: https://qna.habr.com/q/91971
Как правило, такие структуры позволяют существенно сэкономить вычислительные ресурсы в задачах, где допустимо получить примерный ответ.
Хочется добавить, что вероятностная логика и структуры активно используются также и в системах автонавигации. Т.к. там все данные имеют свои вероятности как по показателям, так и по времени. И пока ты общитываешь ситуацию на их основе реальность за это время меняется и это тоже нужно учитывать перед принятием решения.
Вообще это очень интересная тема!
Даже наш мозг постоянно так работает.
Первым в голову пришли списки с пропусками (skip list) в базах данных, позволяющих делать резервирование/репликацию.
Можно еще добавить, что фильтр Блума дает возможность свести объединение и пересечение множеств к побитовому "или" и побитовому "и" соответственно. Но при условии, что наборы хеш-функций и длины векторов одинаковы.
Я так понимаю APPROX_COUNT_DISTINCT в Oracle построен на этом.
Ссылка на HyperLogLog в Redis не работает.
Вероятностные структуры данных и где они обитают