Каковы вероятностные структуры данных?

Ответ 1

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

Сколько пунктов здесь? Около 1523425 с вероятностью 99%

Обновление: Быстрый поиск дал ссылку на достойную статью по этому вопросу:

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

Ответ 2

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

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

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

Часто используемые вероятностные структуры данных:

• цветные фильтры
• эскиз count-min
• hyperLogLog

Ответ 3

В вашей википедии есть список вероятностных структур данных: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures

Существуют разные определения того, что такое "вероятностная структура данных". ИМХО, структура вероятностных данных означает, что структура данных использует некоторый рандомизированный алгоритм или использует некоторые вероятностные характеристики внутри страны, но им не нужно вести себя вероятностно или недетерминированно с точки зрения пользователя структуры данных.

• Существует множество "вероятностных структур данных" с вероятностным таких как фильтр цветения и HyperLogLog упомянутый другими ответами.

• В то же время существуют и другие "вероятностные структуры данных", с определенным поведением (с точки зрения пользователя), например skip Список. Для списка пропусков пользователи могут использовать его аналогично сбалансированному двоичному дереву поиска, но реализуются с некоторой вероятностной идеей внутри. И по словам автора списка пропусков Уильяма Пью:

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