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

Question

Я пытаюсь выяснить, можно ли преобразовать конкретный алгоритм в тот тип индекса сокращения карт, который использует 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?Если нет, то почему именно (чтобы я мог определить такой алгоритм в будущем) и если да, то как?

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

Answer 1

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

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

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

CouchDB обеспечивает второй маленькийоптимизация с помощью запросов с префиксом ключа, что означает, что вы можете сжимать запросы [A], [A, B] и [A, B, C] в один ключ [A, B, C].Таким образом, вместо ваших 2 ^{250 000} возможностей вы получаете «простые» 2 ^249,999 ...

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

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

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

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

Answer 2

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