Эффективное вычисление значимых терминов в SQL

Недавно я познакомился с ElasticSearch агрегацией значительных терминов и был удивлен, насколько хороша и уместна эта метрика. Для тех, кто не знаком с этим, это довольно простая концепция - для данного запроса (набор переднего плана) данное свойство оценивается по статистической значимости фонового набора.

Например, если мы запрашивали наиболее важные виды преступлений в Британской транспортной полиции:

C = 5,064,554 -- total number of crimes
T =    66,799 -- total number of bicycle thefts
S =    47,347 -- total number of crimes in British Transport Police
I =     3,640 -- total number of bicycle thefts in British Transport Police

Обычно кражи велосипеда представляют только 1% преступлений (66 799/5 064 554), но для британской транспортной полиции, которые занимаются преступностью на железных дорогах и станциях, 7% преступлений (3,640/47,347) - это кража велосипеда. Это значительное семикратное увеличение частоты.

Значение для "кражи велосипеда" было бы [(I/S) - (T/C)] * [(I/S) / (T/C)] = 0.371...

Где:

C - количество всех документов в коллекции
S - количество документов, соответствующих запросу
T - количество документов с определенным термином
I - это число документов, которые пересекают как S, так и T

По практическим соображениям (явное количество данных, которые у меня есть и огромные требования к памяти ElasticSearch), я ищу, чтобы реализовать значительное агрегирование терминов в SQL или непосредственно в коде.

Я искал некоторые способы потенциально оптимизировать этот тип запросов, в частности, уменьшая требования к памяти и увеличивая скорость запросов за счет некоторого запаса погрешности - но пока я его не разорвал. Мне кажется, что:

Переменные C и S легко кэшируются или могут быть запрошены.
Переменная T может быть получена из Count-Min Sketch вместо запроса к базе данных.
Переменная I, однако, невозможно получить с помощью эскиза Count-Min от T.

Я также смотрел MinHash, но из описания кажется, что его здесь нельзя было использовать.

Кто-нибудь знает о некотором умном алгоритме или структуре данных, которые помогают решить эту проблему?

Ответ 1

Я сомневаюсь, что SQL impl будет быстрее. Значения для C и T поддерживаются Lucene. S - это простой счет, полученный из результатов запроса, и я просматривается с использованием структур данных O (1). Основная стоимость - это многозначные поисковые запросы для каждого из терминов, наблюдаемых в выбранном поле. Использование min_doc_count обычно помогает значительно сократить количество этих поисков.

По практическим соображениям (явное количество данных, которые у меня есть, и огромные требования к памяти ElasticSearch

Вы изучали использование значений doc для более эффективного управления памятью elasticsearch? См. https://www.elastic.co/blog/support-in-the-wild-my-biggest-elasticsearch-problem-at-scale

Ответ 2

Эффективное решение возможно для случая, когда набор переднего плана достаточно мал. Затем вы можете позволить обрабатывать все документы в наборе переднего плана.

Соберите набор { X _k} всех членов, входящих в набор переднего плана для выбранного поля, а также их частоты { f _k} в наборе переднего плана.
Для каждого X _k
- Вычислить значение X _k как (f _k - F _k) * ( f _k/ F _k), где F _k= T _k/ C - частота X _k в фоновом режиме.
Выберите термины с наивысшими значениями значимости.

Однако, из-за простоты этого подхода, интересно, ElasticSearch уже содержит эту оптимизацию. Если это не так, то это очень скоро!