🔵Streaming и инкрементальные обновления

В реальности, при потоковой обработке невозможно(ну точнее возможно конечно, но просто нелогично из за огромных затрат на вычисления) полностью перестроить комплекс при новом наблюдении.
Наверное многие уже догадались, что здесь так же будет использоваться скользящее окно: фиксируется окно длиной T последних наблюдений, при выходе наблюдения за границу окна выполняется откат соответствующих включений симплексов.
Логика обновления может выглядеть примерно так:

from collections import deque

class StreamingWitnessComplex:
    def __init__(self, landmarks, window_size, epsilon):
        self.landmarks = landmarks
        self.window = deque(maxlen=window_size)
        self.epsilon = epsilon
        self.simplex_witnesses = {}

    def update(self, point):
        if len(self.window) == self.window.maxlen:
            old = self.window[0]
            self._retract_witness(old)

        self.window.append(point)
        self._add_witness(point)

    def _add_witness(self, point):
        dists = np.linalg.norm(self.landmarks - point, axis=1)
        order = np.argsort(dists)
        k_nearest = order[:3]
        for i in range(len(k_nearest)):
            for j in range(i + 1, len(k_nearest)):
                edge = tuple(sorted([k_nearest[i], k_nearest[j]]))
                if dists[k_nearest[j]] <= dists[order[2]] + self.epsilon:
                    self.simplex_witnesses.setdefault(edge, set()).add(id(point))

    def _retract_witness(self, point):
        pid = id(point)
        for edge in list(self.simplex_witnesses):
            self.simplex_witnesses[edge].discard(pid)
            if not self.simplex_witnesses[edge]:
                del self.simplex_witnesses[edge]



Алгоритм инкрементального persistent homology основан на vineyards Cohen-Steiner-Edelsbrunner-Morozov(я честно не могу это нормально перевести на русский) - отслеживании изменений persistence diagram при непрерывной деформации фильтрации. Применительно к нашей логике каждый такт состоит из трёх фаз, а именно из insertion новых симплексов, образованных свежим наблюдением + deletion симплексов, потерявших свидетелей + restoration через swap-операции.
В железе все это выполняется по очереди, то есть пока persistence computation block обрабатывает прошлое окно, distance computation unit и witness identification logic unit начинают обрабатывать новое.