高效计算 SQL 中的重要术语

Question

不久前有人介绍我使用 ElasticSearch significant terms aggregation，我对这个指标的好坏和相关性感到非常惊讶。对于那些不熟悉它的人来说，这是一个非常简单的概念 - 对于给定的查询（前景集），给定的属性根据背景集的统计显着性进行评分。

例如，如果我们查询英国交通警察中最严重的犯罪类型：

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

Ordinarily, bicycle thefts represent only 1% of crimes (66,799/5,064,554) but for the British Transport Police, who handle crime on railways and stations, 7% of crimes (3,640/47,347) is a bike theft. This is a significant seven-fold increase in frequency.

"bicycle theft" 的意义是 [(I/S) - (T/C)] * [(I/S) / (T/C)] = 0.371...

其中：

C是集合中所有文档的个数
S是匹配查询的文档数
T 是具有特定术语的文档数
I 是与 S 和 T[=55 相交的文档数=]

出于实际原因（我拥有的大量数据和巨大的 ElasticSearch 内存需求），我希望在 SQL 中或直接在代码中实现重要术语聚合。

我一直在寻找一些可能优化此类查询的方法，特别是降低内存需求并提高查询速度，但代价是一些错误率 - 但到目前为止我还没有破解它.在我看来：

变量 C 和 S 很容易缓存或查询。
变量 T 可以派生自 Count-Min Sketch 而不是查询数据库。
然而，变量 I 似乎无法通过 T.

我也在看MinHash，但是从描述来看似乎不能在这里应用。

有谁知道一些有助于解决这个问题的聪明算法或数据结构？

Answer 1

我怀疑 SQL impl 会更快。 C 和 T 的值由 Lucene 提前维护。 S 是从查询结果派生的简单计数，使用 O(1) 数据结构查找 I。主要成本是对所选字段中观察到的每个术语进行多次 T 查找。使用 min_doc_count 通常有助于大大减少这些查找的次数。

For practical reasons (the sheer amount of data I have and huge ElasticSearch memory requirements

您是否考虑过使用文档值来更好地管理 elasticsearch 内存？参见 https://www.elastic.co/blog/support-in-the-wild-my-biggest-elasticsearch-problem-at-scale

Answer 2

对于前景集足够小的情况，可能会有一个有效的解决方案。然后你可以负担得起处理前台集中的所有文档。

收集在所选字段的前景集中出现的所有术语的集合 {X_k}，以及它们在前景集中的频率 {f_k}。
对于每个 X_k
- 计算 X_k 的重要性为 (f_k - F_k) * (f_k / F_k), 其中 F_k=T_k/C是X[=49=的频率]_k在后台设置

Select 具有最高显着性值的项。

但是，由于这种方法的简单性，我想知道 ElasticSearch 是否已经包含该优化。如果没有 - 那么它很快就会！

高效计算 SQL 中的重要术语

Efficiently Computing Significant Terms in SQL

sql

query-optimization

aggregation

elasticsearch

significant-terms