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

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

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

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

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

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

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

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

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

   • Определить «примерно оптимальный "размер прямоугольника на основе a .
   • Поместите эти прямоугольники (возможно, случайным образом) над вашими необходимыми точками, пока все точки не будут покрыты.
   • Теперь возьмите каждый прямоугольник и сожмите его как можно больше без "потеря" любых точек данных.
   • Найдите прямоугольники, расположенные близко друг к другу, и решите, будет ли их объединение дешевле, чем их разделение.

2. Рост

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

3. Сжатие

   • Начните с одного большого прямоугольника, который покрывает ВСЕ точки.
   • Ищите подпрямоугольник, который имеет общую пару сторон с большой, но содержит очень мало точек.
   • Обрежьте его. из большого, получится два меньших прямоугольника.
   • Повторить.

4. Quad

   • Разделите плоскость на 4 прямоугольника. Для каждого из них посмотрите, получите ли вы лучшую стоимость, продолжая рекурсию или просто включая весь прямоугольник.
   • Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любые из них с небольшими затратами / бесплатно. \

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

Найдите подпрямоугольник, у которого есть пара сторон с большим, но очень мало точек.

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

Повторите.

Quad

• Разделите плоскость на 4 прямоугольника. Для каждого из них посмотрите, получите ли вы лучшую стоимость, продолжая рекурсию или просто включая весь прямоугольник.
• Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любые из них с небольшими затратами / бесплатно. \

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

Найдите подпрямоугольник, у которого есть пара сторон с большим, но очень мало точек.

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

Повторите.

Quad

• Разделите плоскость на 4 прямоугольника. Для каждого из них посмотрите, получите ли вы лучшую стоимость, продолжая рекурсию или просто включая весь прямоугольник.
• Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любые из них с небольшими затратами / бесплатно. \

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

Quad

• Разделите плоскость на 4 прямоугольника. Для каждого из них посмотрите, получите ли вы лучшую стоимость, продолжая рекурсию или просто включив весь прямоугольник.
• Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любой из них с небольшими / бесплатными затратами. \

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

Quad

• Разделите плоскость на 4 прямоугольника. Для каждого из них посмотрите, получите ли вы лучшую стоимость, продолжая рекурсию или просто включая весь прямоугольник.
• Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любые из них с небольшими затратами / бесплатно. \

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

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

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

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

Идея тривиальна: мы начинаем с проверки одного запроса на запись и выполняем наиболее подходящее слияние, пока не останется ничего, достойного слияния. У этого алгоритма есть очевидный недостаток, заключающийся в том, что он не позволяет перекрывать запросы, но я ожидаю, что он будет работать достаточно хорошо в реальном случае (с 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 запрашивает
• , а цикл удаляет ровно один запрос из пула на каждой итерации.

• внутренний цикл for выполняет итерацию по ( ni ^ 2 - ni ) / 2 различных парах запросов, причем ni изменяется от n до единицы в худшем случае (когда мы объединить все в одну большую просьбу).

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

Заранее благодарим!