Оптимизация декартовых запросов с аффинными затратами

https://stackoverflow.com/questions/1403933

05-07-2019
|

Вопрос

У меня есть запрос на оптимизацию затрат, но я не знаю, как это сделать, если есть литература по этому вопросу.Это немного сложно объяснить, поэтому я заранее приношу извинения за объем вопроса.

Есть сервер, к которому я обращаюсь, который работает таким образом:

запрос выполняется по записям (r1, ...rn) и полям (f1, ...fp).
вы можете запросить только декартово произведение (r1, ..., rp) x (f1,...fp)
Стоимость (время и деньги), связанная с таким запросом, зависит от размера запроса:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Без потери общности (просто путем нормализации) мы можем предположить, что b=1 таким образом, стоимость составляет:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

Мне нужно только запросить подмножество пар (r1, f(r1)), ... (rk, f(rk)), запрос, который поступает от пользователей.Моя программа действует как посредник между пользователем и сервером (который является внешним).У меня поступает много подобных запросов (десятки тысяч в день).

Графически мы можем представить это как разреженную матрицу n x p, для которой я хочу покрыть ненулевые значения прямоугольной подматрицей:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Имея:

количество подматриц поддерживается разумным из-за постоянной стоимости
все 'x' должны находиться внутри подматрицы
общая покрываемая площадь не должна быть слишком большой из-за линейной стоимости

Я назову g коэффициентом разреженности моей задачи (количество необходимых пар по сравнению с общим количеством возможных пар, g = k / (n * p).Я знаю этот коэффициент a.

Есть несколько очевидных наблюдений:

если a невелик, лучшим решением будет запросить каждую пару (запись, поле) независимо, а общая стоимость составит: k * (a + 1) = g * n * p * (a + 1)
если a велико, лучшим решением будет запросить все декартово произведение, и общая стоимость составит : a + n * p
второе решение лучше, как только g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
конечно, порядки в декартовых произведениях неважны, поэтому я могу транспонировать строки и столбцы моей матрицы, чтобы сделать ее более легко охватываемой, например:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

может быть переупорядочен как

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

И есть оптимальное решение, которое заключается в запросе (f1,f3) x (r1,r3) + (f2) x (r2)

Пробовать все решения и искать более низкую стоимость - это не вариант, потому что комбинаторика взрывается:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

поэтому я ищу приблизительное решение.У меня уже есть какой-то жадный алгоритм, который находит покрытие по заданной матрице (он начинается с унитарных ячеек, затем объединяет их, если доля пустой ячейки в слиянии ниже некоторого порога).

Чтобы запомнить некоторые цифры, мое n находится где-то между 1 и 1000, а мое p - где-то между 1 и 200.Шаблон покрытия действительно "блочный", потому что записи поступают в классы, для которых запрашиваемые поля похожи.К сожалению, я не могу получить доступ к классу записи...

Вопрос 1:Есть у кого-нибудь идея, умное упрощение или ссылка на статью, которая могла бы быть полезной?Поскольку у меня много запросов, алгоритм, который работает хорошо в среднем это то, что я ищу (но я не могу позволить, чтобы это работало очень плохо в каком-то крайнем случае, например, запрашивая всю матрицу, когда n и p большие, а запрос действительно довольно разреженный).

Вопрос 2:На самом деле, проблема еще сложнее:стоимость на самом деле больше похожа на форму: a + n * (p^b) + c * n' * p', где b - постоянная < 1 (как только у записи запрашивается поле, запрашивать другие поля не слишком дорого) и n' * p' = n * p * (1 - g) это количество ячеек, которые я не хочу запрашивать (потому что они недопустимы, а запрос недопустимых данных требует дополнительных затрат).Я даже не могу мечтать о быстром решении этой проблемы, но все же...у кого-нибудь есть идея?

Решение

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

То, что вы разрешаете переставлять строки и столбцы, не такая уж большая проблема, потому что вы можете просто рассматривать несвязанные подматрицы.Первая строка, столбцы с четвертого по седьмой и пятая строка, столбцы четыре два семь являются допустимым набором, потому что вы можете просто поменять местами вторую строку и пятую строку и получить подключенную подматрицу первая строка, четвертый столбец - вторая строка, седьмой столбец.Конечно, это добавит некоторые ограничения - не все наборы допустимы при всех перестановках, - но я не думаю, что это самая большая проблема.

В статье Википедии приводятся результаты неприменимости, согласно которым проблема не может быть решена за полиномиальное время лучше, чем с коэффициентом 0.5 * log2(n) где n это количество наборов.В вашем случае 2^(n * p) является (довольно пессимистичной) верхней границей для количества наборов и дает то, что вы можете найти решение только с точностью до коэффициента 0.5 * n * p за полиномиальное время (помимо N = NP и игнорирования меняющихся затрат).

Оптимистичная нижняя граница для количества наборов, игнорирующих перестановки строк и столбцов, равна 0.5 * n^2 * p^2 обеспечивая гораздо лучший коэффициент log2(n) + log2(p) - 0.5.Следовательно, вы можете рассчитывать найти решение только в вашем наихудшем случае n = 1000 и p = 200 до коэффициента примерно 17 в оптимистическом случае и с коэффициентом около 100.000 в пессимистичном случае (по-прежнему игнорируя различные затраты).

Поэтому лучшее, что вы можете сделать, это использовать эвристический алгоритм (в статье Википедии упоминается почти оптимальный жадный алгоритм) и принять, что будет случай, когда алгоритм будет работать (очень) плохо.Или вы идете другим путем и используете алгоритм оптимизации и пытаетесь найти хорошее решение, затратив на это больше времени.В этом случае я бы предложил попробовать использовать A* поиск.

Другие советы

Я уверен, что где-то есть действительно хороший алгоритм для этого, но вот мои собственные интуитивные идеи:

Подход с подбрасыванием нескольких прямоугольников:
- Определите "примерно оптимальный" размер прямоугольника на основе a.
- Разместите эти прямоугольники (возможно, случайным образом) поверх требуемых точек, пока не будут покрыты все точки.
- Теперь возьмите каждый прямоугольник и сожмите его как можно больше, не "теряя" ни одной точки данных.
- Найдите прямоугольники близко друг к другу и решите, будет ли их объединение дешевле, чем хранение по отдельности.
Расти
- Начните с каждой точки в отдельном прямоугольнике размером 1х1.
- Найдите все прямоугольники в пределах n строк / столбцов (где n может быть основано на a);посмотрите, сможете ли вы объединить их в один прямоугольник без каких-либо затрат (или отрицательных затрат : D).
- Повторяю.
Сжиматься
- Начните с одного большого прямоугольника, который охватывает ВСЕ точки.
- Найдите прямоугольник, который имеет общую пару сторон с большим прямоугольником, но содержит очень мало точек.
- Вырежьте его из большого, чтобы получились два прямоугольника поменьше.
- Повторяю.
Четырехъядерный
- Разделите плоскость на 4 прямоугольника.Для каждого из них посмотрите, получите ли вы более высокую стоимость, выполнив дальнейшую рекурсию или просто включив весь прямоугольник.
- Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любой из них с минимальными затратами.\

Также: имейте в виду что иногда будет лучше иметь два перекрывающиеся прямоугольники, чем один большой прямоугольник, который является их надмножеством.Например.тот случай, когда два прямоугольника просто перекрываются в одном углу.

Хорошо, мое понимание вопроса изменилось.Новые идеи:

Храните каждую строку в виде длинной битовой строки.И пары битовых строк вместе, пытаясь найти пары, которые максимизируют количество битов в 1.Разбейте эти пары на более крупные группы (отсортируйте и постарайтесь сопоставить действительно большие друг с другом).Затем создайте запрос, который попадет в самую большую группу, а затем забудьте обо всех этих битах.Повторяйте, пока все не будет готово.Может быть, иногда переключаться со строк на столбцы.
Найдите все строки / столбцы с нулем или несколькими точками в них."Удалите" их временно.Теперь вы смотрите на то, что было бы охвачено запросом, который их не учитывает.Теперь, возможно, примените один из других методов и впоследствии разберитесь с игнорируемыми строками / cols .Другой способ думать об этом - это:сначала разберитесь с более плотными точками, а затем переходите к более разреженным.

Поскольку ваши значения разрежены, может быть, многие пользователи запрашивают похожие значения?Возможно ли кэширование в вашем приложении?Запросы могут быть проиндексированы с помощью хэша, который является функцией позиции (x, y), чтобы вы могли легко идентифицировать кэшированные наборы, которые попадают в правильную область сетки.Например, хранение кэшированных наборов в виде дерева позволило бы вам очень быстро найти минимальные кэшированные подмножества, которые охватывают диапазон запросов.Затем вы можете выполнить линейный поиск по подмножеству, которое невелико.

Я бы рассмотрел n записей (строк) и p полей (столбцов), упомянутых в пользовательском запросе, заданном как n точек в p-мерном пространстве ({0,1} ^ p) с i-й координатой, равной 1, если у нее есть X, и определите иерархию кластеров, с самым грубым кластером в корне , включающим все X.Для каждого узла в иерархии кластеризации рассмотрите продукт, который охватывает все необходимые столбцы (это строки (любой подузел) x столбцы (любой подузел)).Затем решите снизу вверх, следует ли объединить дочерние покрытия (оплачивая все покрытие целиком) или сохранить их как отдельные запросы.(покрытия состоят не из смежных колонн, а именно из тех, которые необходимы;т. е.подумайте о битовом векторе)

Я согласен с Artelius в том, что дублирующие запросы на продукт могли бы быть дешевле;мой иерархический подход нуждался бы в улучшении, чтобы учесть это.

Я немного поработал над этим, и вот очевидный, O (n ^ 3) жадный алгоритм, нарушающий симметрию (записи и поля обрабатываются отдельно) в псевдокоде, подобном python.

Идея тривиальна:мы начинаем с попытки выполнения одного запроса для каждой записи и выполняем наиболее достойное слияние до тех пор, пока не останется ничего достойного для слияния.Этот алгоритм имеет очевидный недостаток в том, что он не допускает перекрывающихся запросов, но я ожидаю, что он будет достаточно хорошо работать в реальных условиях (с + n * (p^b) + c * n * p * (1 - g) функция затрат) :

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

Это O (n3 * p), потому что:

после инициализации мы начинаем с n Запросы
в while цикл удаляет ровно один запрос из пула на каждой итерации.
внутренний for цикл повторяется на (ni^2 - ni) / 2 отдельные пары запросов, причем в худшем случае ni переходит от n к единице (когда мы объединяем все в один большой запрос).
1. Кто-нибудь может помочь мне указать на очень плохие случаи работы алгоритма.Звучит ли разумно использовать этот вариант ?
2. Это O (n ^ 3), что слишком дорого для больших входных данных.Есть какие - нибудь идеи по его оптимизации ?

Заранее спасибо !

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow