java - 提高矩阵/表聚合和搜索的性能

Question

有一个产品特征矩阵。它有数千行(产品)和数百个功能。它具有二进制值，显示产品是否具有此功能。所以它可能是一个包含 40 000 行和 900 列的表。


<strong>Product-feature matrix</strong><br/>
pr f1 f2 f3 fn ...<br/>
01 0 1 1 1<br/>
02 0 0 0 0<br/>
03 1 0 1 0<br/>
04 1 0 1 0<br/>
.....


首先，我必须找到具有一组给定功能 Q 的产品。 Q=(f1=1, f5=1, f27=1)。简单地说，找到蓝色汽车、两厢车、三门车。


<strong>Result 1</strong><br/>
Given Q=(f1=1, f5=1, f27=1)<br/>
Relevant products: 03, 04, 08...


其次，也是最重要的，我必须找出有多少产品具有一组特征 Q，同时具有特征 f_i(其中 i - 1..n)。换句话说，我们正在选择满足 Q 的行，并计算每列中有多少个 1(进行 SUM 聚合)。例如。多少蓝车，两厢，三门还有:柴油机，汽油机，氙气灯。


<strong>Result 2</strong><br/>
Given Q=(f1=1, f5=1, f27=1)<br/>
sum f2 = 943<br/>
sum f3 = 543<br/>
sum f4 = 7<br/>
sum f6 = 432<br/>
....


当然可以使用 RDBMS 来解决此任务，但它不是那么有效 - 在一般情况下，它需要全扫描来查找每个列中的产品和聚合。至少我不知道如何为这个任务建立有效的 b 树索引。 Oracle 位图索引可以提供帮助，但我不能使用 Oracle。

目前，我们正在使用 MySQL 来完成这项任务，但结果并不理想。实际上我们正在使用整数表示(我们将特征分组并将整数存储在列中，而不是 boolean 值)来减少列的数量。

可以将此矩阵视为稀疏二进制矩阵。而且完全存储在内存中问题不大。我想知道是否可以应用一些算法来处理稀疏矩阵、 vector 空间(SVD、矩阵 vector 乘法等)。但它可能有助于找到满足 vector Q 的产品，而不是聚合。问题更多在于聚集的时间，而不是空间。

也许可以将矩阵存储为多链表，这将有助于查找产品并为每一列进行聚合。

最后，问题是如何对待这个任务。查找具有给定特征的产品然后计算具有附加特征的产品(按每列汇总)的最有效算法是什么。

Answer 1

您可以按列排列数据。即有一个 BitSet 用于列出具有该特征的汽车/行的列。

这使您可以利用 BitSet 提供的快速和/或操作。

使用这些功能，您应该能够将每个功能的搜索和计数时间缩短到 2 微秒以内。

对于 40,000 * 900 的数据集，打印以下内容

average search time 1396 ns.
average count time 1234 ns.

这应该比使用 RDBMS 数据库快几个数量级。即使是一百万行，每行也只需要不到 50 微秒。

public static void main(String... args) throws IOException {
    final int rows = 40 * 1000;
    final int cols = 900;

    List<BitSet> features = new ArrayList<BitSet>();
    features.add(new BitSet(rows));
    features.add(new BitSet(rows));
    for (int i = 2; i < cols; i++) {
        final BitSet bs = new BitSet(rows);
        for (int j = 0; j < rows; j++)
            bs.set(j, j % i == 0);
        features.add(bs);
    }

    // perform the search
    int[] factors = new int[]{2, 5, 7};
    BitSet matches = new BitSet();
    long runs =  1000*1000;
    {
        long start = System.nanoTime();
        for (int i = 0; i < runs; i++) {
            // perform lookup.
            lookup(matches, features, factors);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average search time " + avgTime  + " ns.");
    }
    {
        long start = System.nanoTime();
        int count9 = 0;
        BitSet col9matched = new BitSet(cols);
        for (int i = 0; i < runs; i++) {
            final int index = 9;
            final BitSet feature = features.get(index);
            count9 = countMatches(col9matched, matches, feature);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average count time " + avgTime + " ns.");
    }
}

private static int countMatches(BitSet scratch, BitSet matches, BitSet feature) {
    // recycle.
    scratch.clear();
    scratch.or(matches);
    scratch.and(feature);
    return scratch.cardinality();
}

private static void lookup(BitSet matches, List<BitSet> data, int[] factors) {
    matches.clear();
    matches.or(data.get(factors[0]));
    for (int i = 1, factorsLength = factors.length; i < factorsLength; i++) {
        matches.and(data.get(factors[i]));
    }
}