Что такое вероятностные структуры данных?
Я читал о структурах данных, таких как фильтры Блума и пропустить списки.
Каковы общие характеристики вероятностных структур данных и для чего они используются?
5 ответов
Вероятно, есть много разных (и хороших) ответов, но, по моему скромному мнению, общие характеристики вероятностных структур данных состоят в том, что они дают вам приблизительный, а не точный ответ.
Сколько предметов здесь? Около 1523425 с вероятностью 99%
Обновление: Быстрый поиск производится ссылка на достойную статью по этому вопросу:
https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
Если вас интересуют вероятностные структуры данных, вы можете прочитать мою недавно опубликованную книгу "Вероятностные структуры данных и алгоритмы для приложений с большими данными" (ISBN: 9783748190486, доступную в Amazon), где я объяснил многие из таких неэффективных по объему структур данных. и быстрые алгоритмы, которые чрезвычайно полезны в современных приложениях Big Data.
В этой книге вы можете найти современные алгоритмы и структуры данных, которые помогают решать такие распространенные проблемы в обработке больших данных, как
- Запрос на членство (фильтр Блума, фильтр подсчета Блума, фильтр частных отношений, фильтр кукушки).
- Кардинальность (линейный подсчет, вероятностный подсчет, LogLog, HyperLogLog, HyperLogLog++).
- Частота (алгоритм Majority, Frequent, Count Sketch, Count-Min Sketch).
- Ранг (Случайная выборка, q-digest, t-digest).
- Сходство (LSH, MinHash, SimHash).
Вы можете получить бесплатный предварительный просмотр и всю связанную информацию о книге на https://pdsa.gakhov.com/
Вероятностные структуры данных не могут дать вам точного ответа, вместо этого они дают вам разумное приближение к ответу и способ приблизить эту оценку. Они чрезвычайно полезны для больших данных и потоковых приложений, потому что они позволяют значительно уменьшить объем необходимой памяти (по сравнению со структурами данных, которые дают точные ответы).
В большинстве случаев эти структуры данных используют хеш-функции для рандомизации элементов. Поскольку они игнорируют коллизии, они сохраняют размер постоянным, но это также причина, почему они не могут дать вам точные значения. Преимущества, которые они приносят:
- они используют небольшое количество памяти (вы можете контролировать, сколько)
- они могут быть легко распараллеливаемыми (хэши независимы)
- они имеют постоянное время запроса (даже не амортизированная константа, как в словаре)
Часто используемые вероятностные структуры данных:
Для справки в Википедии есть список вероятностных структур данных: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures
Существуют разные определения того, что такое "вероятностная структура данных". ИМХО, вероятностная структура данных означает, что структура данных использует некоторый рандомизированный алгоритм или использует некоторые вероятностные характеристики внутри, но они не должны вести себя вероятностно или недетерминированно с точки зрения пользователя структуры данных.
Существует много "вероятностных структур данных" с вероятностным поведением, таких как фильтр Блума и HyperLogLog, упомянутые в других ответах.
В то же время существуют другие "вероятностные структуры данных" с определенным поведением (с точки зрения пользователя), такие как список пропусков. Для списка пропуска пользователи могут использовать его аналогично в качестве сбалансированного бинарного дерева поиска, но реализовано с некоторой внутренней вероятностью. И по словам автора списка пропуска Уильяма Пью:
Списки пропусков - это вероятностная структура данных, которая, вероятно, вытеснит сбалансированные деревья в качестве метода реализации, выбранного для многих приложений. Алгоритмы пропуска списка имеют те же асимптотические ожидаемые временные границы, что и сбалансированные деревья, и они проще, быстрее и занимают меньше места.
Вероятностные структуры данных обеспечивают постоянный объем памяти и чрезвычайно быструю обработку, сохраняя при этом низкий уровень ошибок с заданной степенью неопределенности.
Некоторые варианты использования
- Проверка наличия значения в наборе данных
- Частота событий
- Оценить приблизительный размер набора данных
- Рейтинг и группировка