Вероятностные структуры данных и где они обитают

Мой вопрос на тостере с сылками на кучу разных вероятностных алгоритмов: https://qna.habr.com/q/91971

Как правило, такие структуры позволяют существенно сэкономить вычислительные ресурсы в задачах, где допустимо получить примерный ответ.

Хочется добавить, что вероятностная логика и структуры активно используются также и в системах автонавигации. Т.к. там все данные имеют свои вероятности как по показателям, так и по времени. И пока ты общитываешь ситуацию на их основе реальность за это время меняется и это тоже нужно учитывать перед принятием решения.

Вообще это очень интересная тема!

Даже наш мозг постоянно так работает.

Первым в голову пришли списки с пропусками (skip list) в базах данных, позволяющих делать резервирование/репликацию.

Можно еще добавить, что фильтр Блума дает возможность свести объединение и пересечение множеств к побитовому "или" и побитовому "и" соответственно. Но при условии, что наборы хеш-функций и длины векторов одинаковы.

Я так понимаю APPROX_COUNT_DISTINCT в Oracle построен на этом.

Ссылка на HyperLogLog в Redis не работает.