查询稀疏的多维数据集

Question

我们有一个包含带标签的实体的数据集.每个标记都是一个字符串,每个实体最多可以有3个与之关联的标记.

我们希望实现一个索引,以便能够快速查询哪些标签最常与一组给定的标签共同出现.例如,我可能有以下实体:

Entity 1 - tags A, B, Z
Entity 2 - tags B, C, E
Entity 3 - tags A, B, Y
Entity 4 - tags A, E, F

与A共同出现的标签是B(2次).与A和B最常出现的标签是Y和Z(每次一次).

我们的数据集相当小(约2000个项目),它所代表的2000维空间非常稀疏,所以毫无疑问,只需按标签对数据进行分区,然后枚举实体以找到最常见的标签,就可以实现可接受的性能. .但是,如果有一个特定的索引类型可以有效地处理大型数据集的这类问题,我很感兴趣.

Answer 1

假设：

1) 标签在实体中按字母顺序排列。

2）一个实体可以包含至少1个标签，最多3个标签（你实际上已经说过了）

3）实体是非唯一的

4）标签是唯一的

5) 同现可以是 2 个标签或 3 个标签（如上所述）

6) 实体第二个和第三个位置的标签对是您希望索引的共现

7）您能够使用RDBMS，例如MySQL

两个表 - 实体和标签。请参阅下面的 MySQL 语法表创建语句。

标签上有一个唯一的索引。

实体由 2 个多列（或串联）索引编制索引，以便您可以从左到右搜索：例如，在 (tag1)、或 (tag1 AND tag2)、或 (tag1 AND tag2 AND tag3)、或 (tag2 和 tag3) 上）。请参阅解释：https://dev.mysql.com/doc/refman/5.7/en/multiple-column-indexes.html

多列索引允许您使用以下查询快速解决所有同时出现的情况：

SELECT * FROM entity
  WHERE tag1='A'
  AND tag2='B' 
  AND tag3='C';

SELECT count(*) AS count, tag2, tag3 FROM entity
  GROUP BY tag2, tag3
  ORDER BY count DESC;

CREATE TABLE entity (
    entity_name  CHAR(30) NOT NULL,
    tag1         CHAR(30) NOT NULL,
    tag2         CHAR(30) NULL,
    tag3         CHAR(30) NULL,
    PRIMARY KEY (entity_name),
    INDEX tags  (tag1, tag2, tag3),
    INDEX tags2 (tag2, tag3)
);

CREATE TABLE tag (
    tag          CHAR(30) NOT NULL
    PRIMARY KEY (tag)
);