Улучшение производительности агрегирования и поиска матриц/таблиц

Question

Существует матрица характеристик продукта. Он имеет тысячи рядов (продуктов) и сотни функций. Он имеет двоичные значения, которые показывают, есть ли у продукта эта функция или нет. Таким образом, это может быть таблица из 40 000 строк и 900 столбцов.

Product-feature matrix
pr f1 f2 f3 fn ...
01 0 1 1 1
02 0 0 0 0
03 1 0 1 0
04 1 0 1 0
.....

Во-первых, я должен найти продукты, которые имеют определенный набор функций Q. Э.Г. Q = (f1 = 1, f5 = 1, f27 = 1). Простые сказали, найдите синие автомобили, хэтчбек, 3-дверные.

Result 1
Given Q=(f1=1, f5=1, f27=1)
Relevant products: 03, 04, 08...

Во-вторых, и самое главное, я должен найти, сколько продуктов, которые имеют множество функций Q, также есть функция F_i (где я - 1..n). Другими словами, мы выбираем строки, которые удовлетворяют Q, и подсчитывают, сколько 1 в каждом столбце (сделать агрегацию SUM). Например. сколько синих автомобилей, хэтчбек, 3-дверный также имеет: дизельный двигатель, бензиновый двигатель, ксеноновые фары.

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

Конечно, можно решить эту задачу с помощью РСУБД, но это не так эффективно - в общем случае это потребует FullScan как для поиска продуктов и агрегации в каждом столбцах. По крайней мере, я не знаю, как создать эффективный индекс дерева b для этой задачи. Oracle bitmap index может помочь, но я не могу использовать Oracle.

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

Можно рассматривать эту матрицу как разреженную двоичную матрицу. И это не большая проблема, чтобы сохранить его полностью в памяти. И мне интересно, можно ли применить некоторые алгоритмы для работы с разреженными матрицами, векторным пространством (SVD, умножением матричных векторов и т. Д.). Но это, вероятно, помогает найти продукты, удовлетворяющие вектору Q, а не в агрегации. Проблема заключается скорее во времени агрегации, а не в пространстве.

Возможно, можно хранить матрицу как многосвязный список, который поможет найти продукты и сделать агрегацию для каждого столбца.

Наконец, вопрос заключается в том, как лечить эту задачу. Каков наиболее эффективный алгоритм для поиска продуктов с заданными функциями, а затем подсчет продуктов с дополнительными функциями (совокупность по каждому столбцу).

Answer 1

Вы можете организовать ваши данные по столбцам. то есть иметь один битный набор для столбца, в котором перечислены автомобили/строки, которые имеют эту функцию.

Это позволяет вам использовать преимущества быстрой и/или операции, предоставляемые BitSet.

Используя эти функции, вы сможете достичь менее 2 микросекунд для поиска и подсчета каждой функции.

Для 40 000 * 900 набора данных, следующие печатные издания

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

Это должно несколько порядков быстрее, чем вы можете получить с базой данных СУБД. Даже один миллион строк занимает менее 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])); 
    } 
} 

Answer 2

Если я понимаю ваше текущее решение, у вас есть одна таблица со строкой для каждого продукта со столбцом для каждой функции. Это довольно неэффективный способ решения проблемы.

Как насчет трех таблиц

"продукты" (product_ref, product_name) индекс product_ref (список товаров)

"особенности" (feature_ref, описание) индекс feature_ref (список возможных функций)

и

"productfeatures" (product_ref, feature_ref) индекс product_ref, feature_ref и feature_ref, product_ref (каждая строка представляет собой характеристику продукта)

Вы можете выполнить соединение между таблицами

выберите * из продуктов t1 присоединиться productfeatures t2 присоединиться productfeatures t3, где t1.product_ref = t2.product_ref и t1.product_ref = t3.product_ref и t2.feature_ref = 45 и t3.feature_ref = 67 и т. д.

Answer 3

, пожалуйста, взгляните на этот пример, который я сделал некоторое время назад, это следует за тем, что jaydee правильно изложил, но более подробно и против 125 миллионов poster_categories (car_features) со временем выполнения 0,02 сек. - ваш, худший случай имел бы 40K ++ * 900 cols = 36 миллионов строк, то есть, это ребенок!

Rewriting mysql select to reduce time and writing tmp to disk

select count(*) from category 
count(*) 
======== 
500,000 


select count(*) from poster 
count(*) 
======== 
1,000,000 

select count(*) from poster_category 
count(*) 
======== 
125,675,688 

select count(*) from poster_category where cat_id = 623 
count(*) 
======== 
342,820 

explain 
select 
p.*, 
c.* 
from 
poster_category pc 
inner join category c on pc.cat_id = c.cat_id 
inner join poster p on pc.poster_id = p.poster_id 
where 
pc.cat_id = 623 
order by 
p.name 
limit 32; 

id select_type table type possible_keys key  key_len ref       rows 
== =========== ===== ==== ============= ===  ======= ===       ==== 
1 SIMPLE  c  const PRIMARY   PRIMARY 3  const      1 
1 SIMPLE  p  index PRIMARY   name 257  null      32 
1 SIMPLE  pc  eq_ref PRIMARY   PRIMARY 7  const,foo_db.p.poster_id 1 

select 
p.*, 
c.* 
from 
poster_category pc 
inner join category c on pc.cat_id = c.cat_id 
inner join poster p on pc.poster_id = p.poster_id 
where 
pc.cat_id = 623 
order by 
p.name 
limit 32; 

0.021: Query OK