Корсет и спаннер: сохраняем нужные запросы к данным

Если задаёшь семейство запросов и погрешность до удаления данных, листай до «Теперь сам».

Как думаешь, что значит «сохранить форму облака»

В потоке миллионы точек. Можно оставить каждую сотую, крайние точки или случайную выборку. Но пригодность зависит от задачи: для самого далёкого расстояния важны края, для суммы квадратов - распределение массы. Небольшой набор, идеально отвечающий одному запросу, может совершенно неверно отвечать другому. Уменьшение объёма без формулировки запроса ещё не образует корсет.

На что это похоже

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

Механизм: контракт по всем допустимым запросам

Пусть cost(P,q) - стоимость ответа на запрос q к исходным данным P. Сильный относительный ε-корсет требует для каждого допустимого q границы (1-ε)cost(P,q) ≤ cost(C,q) ≤ (1+ε)cost(P,q). Взвешенные точки позволяют сохранять массу удалённых элементов. Для других задач встречаются иные определения корсета, например приближение оптимального охватывающего шара: название без контракта недостаточно.

На прямой для запроса maxₓ∈P |x-c| достаточно двух крайних точек. Любая внутренняя точка ближе к c, чем хотя бы одна крайняя. Поэтому минимум и максимум образуют точную сводку для любого центра c. Но для суммы квадратов эта же пара уже не подходит: сто внутренних точек исчезают из стоимости.

Для графа G спаннер H хранит часть рёбер и требует dist_G(u,v) ≤ dist_H(u,v) ≤ t·dist_G(u,v). Левая граница следует из удаления рёбер. Для невзвешенного потока добавляй ребро (u,v), только если текущее расстояние больше t. Отвергнутое ребро уже заменяется путём длины не больше t; дальнейшие вставки этот путь не удаляют. Заменив каждое ребро кратчайшего пути, получаем верхнюю границу для любой пары.

Правило

Сводка должна сохранять явно выбранный запрос; спаннер сохраняет расстояния, а не все свойства исходного графа. Показанное жадное правило работает в модели вставок невзвешенных рёбер. Удаления требуют другого алгоритма: путь, оправдавший отказ от ребра, может исчезнуть.

Разбор: две точки вместо всего набора

from collections import deque
from itertools import combinations


def distances(graph, start):
    result = [float("inf")] * len(graph)
    result[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if result[v] == float("inf"):
                result[v] = result[u] + 1
                queue.append(v)
    return result


def spanner(n, edges, stretch):
    graph = [set() for _ in range(n)]
    kept = []
    for u, v in edges:
        if distances(graph, u)[v] > stretch:
            graph[u].add(v)
            graph[v].add(u)
            kept.append((u, v))
    return graph, kept


points = [0, 2, 5, 5, 7, 10]
summary = [min(points), max(points)]
for center in range(-5, 16):
    exact = max(abs(x-center) for x in points)
    compressed = max(abs(x-center) for x in summary)
    assert exact == compressed
print("Крайние точки:", summary)
n = 8
edges = list(combinations(range(n), 2))
graph, kept = spanner(n, edges, 3)
for start in range(n):
    values = distances(graph, start)
    assert all(x <= 3 for x in values)
print("Рёбер исходно:", len(edges))
print("Рёбер сохранено:", len(kept))
print("Максимальное расстояние:",
      max(max(distances(graph, u)) for u in range(n)))
print("Радиус от 4:", max(abs(x-4) for x in [0, 5, 10]))

Крайние точки: [0, 10]
Рёбер исходно: 28
Рёбер сохранено: 7
Максимальное расстояние: 2
Радиус от 4: 6

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

Разбор: размер - отдельная гарантия

Правильность расстояний сама по себе не гарантирует уменьшение: исходный граф всегда является своим спаннером. Для жадной конструкции при нечётном растяжении 2r-1 на невзвешенных графах известна граница числа рёбер порядка n^(1+1/r) при фиксированном r. Она требует отдельного комбинаторного доказательства; из замены каждого отвергнутого ребра коротким путём эта оценка ещё не следует.

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

Что ломается без этого

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

Зачем это в работе

Потоковые данные нельзя хранить целиком, а запрос известен заранее: радиус покрытия, стоимость кластеризации или расстояние в графе связности. Корсет либо спаннер сокращает память именно под этот запрос. При распределённой обработке дополнительно проверь, поддерживает ли выбранная конструкция слияние и сколько точности оно расходует.

Теперь сам

В множестве на прямой есть точки 0,5,10. Каков точный максимальный радиус относительно центра 4? Можно ли по одним крайним точкам восстановить сумму квадратов расстояний?