Можно ли использовать предварительно вычисленный индекс уменьшения карты (а-ля RavenDB/CouchDB) для такого рода алгоритмов?

Я пытаюсь выяснить, можно ли преобразовать конкретный алгоритм в тип индекса уменьшения карты, который использует RavenDB/CouchDB, т. е. «предварительно вычисленное» уменьшение карты (что означает, что индексы обновляются при вставке и обновлении, а не когда выполнение фактического запроса).

Допустим, у нас есть типичный интернет-магазин с 50 000 товаров, сгруппированных по категориям. Каждый продукт имеет набор «Значений атрибутов», т. е. что-то вроде «[Красный, Круглый, Металл]».

Поскольку на нашем веб-сайте так много товаров и, вероятно, много товаров в каждой из категорий, мы хотим дать пользователю еще один способ «фильтровать» продукты, которые он сейчас видит.

Например, если категория «Менее 20 долларов», в этой категории есть целая куча товаров. Но нашему пользователю нужно видеть только продукты, которые стоят менее 20 долларов и имеют красный цвет. К сожалению, в категории "Менее $20" нет подкатегории "Красный".

Наш алгоритм возьмет текущий список продуктов и сгенерирует список «интересных» атрибутов и значений атрибутов, то есть, учитывая список продуктов, он выведет что-то вроде:

Color
   Red (40)
   Blue (32)
   Yellow (17)
Material
   Metal (37)
   Plastic (36)
   Wood (23)
Shape
   Square (56)
   Round (17)
   Cylinder (12)

Может ли такой алгоритм быть каким-то образом предварительно вычисленным а-ля RavenDB/CouchDB map-reduce index? Если нет, то почему именно (чтобы я мог определить такой алгоритм в будущем) и если да, то как?

Доступно тестовое решение C# 4.0 Visual Studio, которое демонстрирует потенциальные структуры данных и образцы данных, а также как попытка реализации map-reduce (которая не кажется предварительно вычисляемой).


c# couchdb mapreduce algorithm ravendb
person Simon Labrecque    schedule 25.11.2010    source источник
comment
Для 50 000 элементов вы можете хранить все данные в памяти практически в любой структуре и циклически перебирать их. Также могут быть реализованы простые оптимизации. Тем не менее, сколько запросов в секунду вы просматриваете?   -  person Mikael Svenson    schedule 25.11.2010
comment
Хранение продуктов в памяти — это именно то, чем я сейчас занимаюсь, и это работает довольно хорошо. Однако я нахожусь в другом контексте (реляционная БД с O/R mapper). Время запуска важно для приложения, над которым я работаю, и в настоящее время оно становится проблемой, так как большую часть данных приходится извлекать и помещать в память во время запуска. Чтобы сделать это хорошей задачей, мы смотрим на любое количество запросов в секунду, которое может показаться вам сложным ;) То есть решение должно масштабироваться.   -  person Simon Labrecque    schedule 25.11.2010
comment
Не совсем понятно, что вам нужно, так как ‹20$ нет в образце вывода. Если пользователь хочет ‹20$ AND Red, а Red‹20$ нет, что вы ему показываете? "интересные" красные штучки (даже за $20) что ли?   -  person smirkingman    schedule 26.11.2010
comment
‹20$ — это категория. Красный — это атрибут. Категории выбираются администраторами заранее. Атрибуты для дальнейшей фильтрации динамически представляются пользователю на основе текущего списка продуктов.   -  person Simon Labrecque    schedule 27.11.2010

Ответы (2)


arrow_upward
2
arrow_downward

Общий случай. Всегда возможно использовать представление map-reduce в стиле CouchDB, но это не всегда практично.

В конце концов, это в основном аргумент, основанный на подсчете: если вам нужно задать вопрос для любого подмножества ваших 500 000 товаров, ваша база данных должна быть в состоянии предоставить отдельный ответ для каждого из 2500 000. различные возможные вопросы, которые используют непомерно большой объем памяти, если вам нужно выдать лист B-дерева для каждого из них (и вам нужно выдать данные, если ответом на большинство этих запросов не будет ноль, ложь, пустой набор или аналогичное нулевое значение).

CouchDB обеспечивает первую небольшую оптимизацию за счет существования запросов диапазона (это означает, что в идеальном случае он может использовать всего N листьев B-дерева для ответа на N2 вопросов). Однако в вашем примере это сократит количество листьев до 2250 000 (и это теоретическая нижняя граница).

CouchDB обеспечивает вторую небольшую оптимизацию с помощью запросов префикса ключа, что означает, что вы можете сжимать запросы [A], [A,B] и [A,B,C] в один ключ [A,B,C]. Таким образом, вместо 2250 000 возможностей у вас осталось всего 2249 999...

Таким образом, хотя вы можете придумать излучающую стратегию для ответа на вопрос для любого подмножества, это потребует больше места для хранения, чем реально доступно на нашей планете. В общем случае, чтобы ответить на N разных вопросов, вам нужно выпустить не менее sqrt(N/2) листьев B-дерева, поэтому посчитайте ваши вопросы и определите, приемлема ли эта нижняя граница количества листьев.

Только для категорий и подкатегорий: если вы откажетесь от произвольных списков товаров и зададите вопросы только в форме "дайте мне значимые атрибуты в категории A, отфильтрованные по атрибутам B и C", то ваше количество выпускает капли на:

 AvgCategories * AvgAttr * 2 ^ (AvgAttr - 1) * 500,000

По сути, вы выдаете для каждого продукта ключи [Category,Attr,Attr,...] для всех категорий продукта и всех комбинаций атрибутов продукта, что позволяет выполнять запросы по категории + атрибутам. Если у вас есть в среднем 1 категория и 3 атрибута для каждого продукта, это составляет около 6 миллионов записей, что вполне приемлемо.

person Victor Nicollet    schedule 26.11.2010

arrow_upward
0
arrow_downward

Это должно быть довольно просто реализовать в чем-то вроде CouchDB. Пусть этап отображения вашего индекса выводит один ключ и пару значений для каждого атрибута, который имеет объект, со значением просто «1». Затем попросите фазу сокращения суммировать все входные значения и вывести сумму. Конечным результатом будет индекс формы, которую вы описываете.

person Nick Johnson    schedule 25.11.2010
comment
Разве это не будет работать только для полного списка продуктов, а не для подмножества? Это должно работать с любым произвольным и динамическим списком продуктов и выводить список интересных потенциальных атрибутов, которые будут использоваться в качестве фильтра для исходного списка элементов. - person Simon Labrecque; 26.11.2010