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

Выбор подматриц для покрытия запрошенных значений является формой проблемы покрытия набора и, следовательно, 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*.

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

1. Подход с броском прямоугольников:

   • Determine a "roughly optimal" rectangle size based on a.
   • Поместите эти прямоугольники (возможно, случайным образом) на требуемые точки, пока все точки не будут покрыты.
   • Теперь возьмите каждый прямоугольник и максимально уменьшите его, не «теряя» никаких точек данных.
   • Найдите прямоугольники, расположенные близко друг к другу, и решите, будет ли их объединение дешевле, чем хранение их по отдельности.

2. Расти

   • Start off with each point in its own 1x1 rectangle.
   • Найдите все прямоугольники в n строках/столбцах (где n может быть основано на a); посмотрите, сможете ли вы объединить их в один прямоугольник бесплатно (или с отрицательной стоимостью: D).
   • Повторить.

3. Сокращать

   • Start off with one big rectangle, that covers ALL points.
   • Найдите подпрямоугольник, у которого пара общих сторон с большим, но в котором очень мало точек.
   • Вырежьте его из большого, получив два меньших прямоугольника.
   • Повторить.

4. Четырехместный

   • Divide the plane into 4 rectangles. For each of these, see if you get a better cost by recursing further, or by just including the whole rectangle.
   • Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любой из них с небольшими/бесплатными затратами.\

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

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

• Сохраняйте каждую строку как длинную битовую строку. И пары битовых строк вместе, пытаясь найти пары, которые максимизируют количество битов 1. Объедините эти пары в более крупные группы (сортируйте и старайтесь сопоставить действительно большие пары друг с другом). Затем создайте запрос, который будет охватывать самую большую группу, а затем забудьте обо всех этих битах. Повторяйте, пока все не сделаете. Может быть, иногда переключаться со строк на столбцы.

• Ищите все строки/столбцы с нулем или несколькими точками в них. «Удалите» их временно. Теперь вы смотрите на то, что покрывается запросом, который не включает их. Теперь, возможно, примените один из других методов и впоследствии обработайте игнорируемые строки/столбцы. Другой способ думать об этом: сначала работать с более плотными точками, а затем переходить к более разреженным.

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

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

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

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

Идея тривиальна: мы начинаем с того, что пробуем один запрос на запись, и делаем самое достойное слияние до тех пор, пока не останется ничего достойного для слияния. У этого алгоритма есть очевидный недостаток, заключающийся в том, что он не допускает перекрывающихся запросов, но я ожидаю, что он будет работать достаточно хорошо в реальном случае (с функцией стоимости a + 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. Can someone help me pointing the very bad cases of the algorithm. Does it sound reasonnable to use this one ?
  2. Это O (n ^ 3), что слишком дорого для больших входных данных. Любая идея, чтобы оптимизировать его?

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