Вот что видит пользователь, когда мы рисуем график давления в скважине за два года — 50 миллионов точек:
Мы решаем эту задачу через матричный фильтр. На датасете в 50 млн точек это даёт ~100% Coverage, ~100% Visual Score. LTTB на тех же данных — 16.4% и 40.8% соответственно. По производительности мы остаёмся в тех же пределах.
Под катом — почему стандартные алгоритмы фундаментально не подходят для scatter-графиков, как устроен наш подход и результаты бенчмарка на ~3 000 реальных промышленных датасетах от 19 тысяч до 50+ миллионов точек.
Сразу важный дисклеймер: для примера выше мы намерено выбрали худший кейс, чтобы отобразить проблему наглядно.
Большинство систем визуализации работают с линейными графиками — и для них классические алгоритмы даунсемплинга справляются. При правильном подборе алгоритма и бюджета точек артефакты минимальны или незаметны.
Проблема начинается там, где линия — это не упрощение, а искажение. Она соединяет точки, между которыми ничего не происходило, сглаживает разрывы и создаёт ложную непрерывность. В таких случаях единственный честный способ визуализации — scatter-график.
Почему мы используем scatter, а не line chart
Наш контекст — исследование нефтяных скважин: десятки лет данных в одной куче, где ручные единичные замеры соседствуют со старой нестабильной телеметрией и современными высокоточными датчиками. У нас три конкретные причины:
Технические пропуски — не пустота, а слепая зона. Когда запись прерывается из-за сбоя, давление в этот момент могло вести себя как угодно. Линия соединит точки до и после разрыва плавным переходом — и исследователь увидит «стабильную работу» там, где была авария. Точки честно показывают: здесь данных нет.
Нерегулярная дискретность делает алгоритм соединения невозможным. Разные датчики, разные эпохи, разные частоты записи. Чтобы корректно рвать линию там, где пропуск слишком большой — нужен порог. Универсального порога не существует. Точкам правила соединения не нужны вообще.
Паттерны лучше видны без линий. Мы ищем конкретные режимы и аномалии. На scatter-графике глаз сразу считывает плотность, кластеры и выбросы. Линии создают визуальный шум, который эти паттерны скрывает.
Стандартные алгоритмы проектировались под line chart — они оптимизируют сохранение формы кривой, а не структуры данных.
Как работают классические алгоритмы даунсемплинга
Почти все популярные алгоритмы работают по одному принципу: разбивают ось времени на интервалы («корзины») и по определённой логике выбирают из каждой корзины одну или несколько точек.
MinMax — самый простой и быстрый. Из каждого интервала берёт две точки: минимум и максимум по Y. Все пики и провалы сохраняются, но распределение данных внутри корзины полностью теряется.
M4 — разбивает время на интервалы шириной в один пиксель и для каждого берёт четыре точки: первую, последнюю, минимум и максимум. Для линейных графиков даёт практически pixel-perfect результат.
LTTB (Largest Triangle Three Buckets) — де-факто стандарт для фронтенда. В каждой корзине ищет точку, которая образует треугольник наибольшей площади с соседними корзинами. Отлично сохраняет визуальный «силуэт» линии.
MinMaxLTTB — гибрид: сначала MinMax фиксирует критические экстремумы, затем LTTB сглаживает результат. Попытка совместить точность пиков и визуальную гладкость.
Van Der Donckt J., Van Der Donckt J., Van Hoecke S. tsdownsample: high-performance time series downsampling for scalable visualization // SoftwareX. — 2025. — arXiv:2307.05389
Все они работают только вдоль оси X. Возьмём пиксельный столбец, в который попало 100 точек, разбросанных по всей высоте экрана: MinMax оставит 2, M4 — 4, LTTB — 1. Для линейного графика этого достаточно — линия сама закроет вертикаль между крайними точками. На scatter-графике мы потеряем 96–99% данных в этом столбце: плотное облако схлопнется в редкий скелет из экстремумов. Форма кривой сохранится, внутренняя структура — нет.
Матричный фильтр: двумерное прореживание
Принцип, который мы используем, давно известен в компьютерной графике под названием Voxel Grid Filter. Ключевой принцип: пространство разбивается на дискретную сетку ячеек, внутри каждой сохраняется только одна точка, избыточная плотность отсекается. Мы проецируем эту логику на плоскость, где роль вокселей играют физические пиксели экрана.
Входные данные: два массива double[] times, double[] values. Разрешение области построения W × H в пикселях. Порядок точек роли не играет — в отличие от LTTB и M4, алгоритму не нужна сортировка по времени.
Шаг 1 — Границы. Один проход по массивам: находим tMin, tMax, vMin, vMax. Если метаданные уже известны из БД, шаг пропускается.
Шаг 2 — Сетка. Создаём плоский булев массив размером W × H. Это виртуальная проекция будущего графика на пиксели экрана, изначально пустая.
Шаг 3 — Фильтрация. Для каждой точки вычисляем её пиксельные координаты (px, py) и проверяем ячейку grid[py * W + px]. Если пиксель свободен — точка попадает в результат, пиксель помечается занятым. Если занят — точка отбрасывается.
public static void downsample( double[] times, double[] values, int width, int height, List<double[]> result) { int n = times.length; if (n == 0) return; // Шаг 1: границы double tMin = times[0], tMax = times[0]; double vMin = values[0], vMax = values[0]; for (int i = 1; i < n; i++) { if (times[i] < tMin) tMin = times[i]; if (times[i] > tMax) tMax = times[i]; if (values[i] < vMin) vMin = values[i]; if (values[i] > vMax) vMax = values[i]; } double tRange = Math.max(tMax - tMin, 1e-10); double vRange = Math.max(vMax - vMin, 1e-10); // Шаг 2: сетка boolean[] grid = new boolean[width * height]; // Шаг 3: фильтрация for (int i = 0; i < n; i++) { int px = (int) Math.min(width - 1, (times[i] - tMin) / tRange * (width - 1)); int py = (int) Math.min(height - 1, (values[i] - vMin) / vRange * (height - 1)); int idx = py * width + px; if (!grid[idx]) { grid[idx] = true; result.add(new double[]{times[i], values[i]}); } } }
Максимальный размер выходного массива ограничен W × H — числом пикселей экрана. На практике он всегда меньше: точки распределены неравномерно, и большинство пикселей остаются пустыми.
Почему это работает: рендеринг против математики
Секрет визуального сходства в том, что матричный фильтр решает задачу не математического сжатия ряда, а прямого рендеринга.
Классические алгоритмы прореживают данные вдоль оси X, сохраняя форму кривой. В плотных участках они неизбежно оставляют пустоты. Матричный фильтр переносит задачу в плоскость монитора: вычисляет, какие пиксели активировались бы при отрисовке всех точек, и оставляет ровно по одной точке на каждый такой пиксель.
Из этого следует важное ограничение. Метод оптимизирован под отрисовку — и только под неё. Какая именно точка остаётся из группы, попавшей в один пиксель, определяется порядком обхода, а не аналитической значимостью. Для задач, где важна выборка как таковая — статистика, дальнейшие вычисления, экспорт — этот подход не подходит. Его область применения строго одна: показать данные так, как они выглядели бы при полной отрисовке.
Методология тестирования: как измерить «идеальность» графика
Все тесты проводились на реальной исторической телеметрии — логах забойного давления нефтяных скважин. В этих данных есть всё: долгие базовые линии, плавные тренды, периодические колебания, резкие пики от остановок и запусков и большие пропуски в записях.
Тестовый стенд
Тесты запускались в один поток:
CPU: Intel Core i7-7700K (4.20 GHz)
RAM: 32 ГБ
ОС: Windows 10 Pro
Стек: Java 17 (OpenJDK), тесты через JUnit 5
Каждый датасет прогонялся через 6 алгоритмов: MatrixFilter 1920×1080 (эталон), MatrixFilter 800×600 (оценка работы при меньшем разрешении), M4, MinMax, LTTB и MinMaxLTTB (×4).
Бюджет точек для классических алгоритмов определялся через сам матричный фильтр: сначала запускается MatrixFilter 1920×1080, и количество точек на его выходе становится targetSize для всех остальных. Это заведомо щедрый лимит — классическим алгоритмам для качественного line chart достаточно числа точек, соизмеримого с количеством пиксельных столбцов на изображении. Мы даём им больше: столько, сколько нужно для полного двумерного покрытия.
Как мы оценивали качество визуализации
Для каждого алгоритма мы строили график в виртуальном буфере и сравнивали его попиксельно с графиком по сырым, непрореженным данным.
Сравнение проводилось в двух режимах рендера:
Scatter — точки размером 2×2 пикселя, без соединительных линий.
Lines — классические линии толщиной 1px.
Метрики:
Coverage — процент пикселей оригинала, которые покрыл алгоритм. Не потеряли ли мы данные?
Precision — процент закрашенных пикселей алгоритма, присутствующих в оригинале. Не нарисовали ли мы лишнего?
F1-score — гармоническое среднее Coverage и Precision.
Visual Score — тот же F1, но с допуском ±1 пиксель. Из-за округлений координат точка может сдвинуться на субпиксель: строгий F1 это фиксирует, глаз — нет. Visual Score ближе к реальному восприятию.
Датасеты
Данные разбиты на 3 группы:
Regular (2 930 файлов, в среднем ~20 000 точек). Основной датасет для оценки качества: широкий охват разных типов кривых, датчиков и режимов записи. Акцент здесь не на скорости — на том, как точно алгоритмы воспроизводят scatter и line chart после прореживания.
Medium (24 файла, в среднем ~500 000 точек). Данные за периоды от нескольких месяцев до года непрерывной записи.
Large (13 файлов, в среднем ~25 000 000 точек, максимум — более 50 млн). Проверка поведения алгоритмов на предельных объёмах: качество картинки и замер производительности.
Результаты тестирования: цифры и визуализация
Ниже — результаты прогонов по каждой из трёх групп. В таблицах оставлена только суть:
Avg Out — среднее количество точек на выходе алгоритма;
Total ms — суммарное время работы на всём датасете;
Cover, Prec, F1 — строгие попиксельные метрики (полнота, точность, их баланс);
Visual — F1-score с допуском ±1 пиксель, ближе к реальному восприятию глазом.
Этап 1: Базовый датасет (Regular)
Параметры: 2 930 файлов | В среднем ~20 000 точек на файл. Стандартный сценарий: данные с манометров за 1–12 месяцев, низкая дискретность.
Scatter-графики (Точечные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 4 939 | 695 | 100% | 100% | 100% | 100% |
MatrixFilter 800×600 | 2 867 | 497 | 84.6% | 100% | 99.6% | 91.5% |
MinMaxLTTB (x4) | 4 932 | 494 | 84.1% | 100% | 95.2% | 90.9% |
LTTB | 4 939 | 366 | 82.2% | 100% | 94.2% | 89.6% |
MinMax | 4 027 | 251 | 76.0% | 100% | 91.8% | 85.5% |
M4 | 3 311 | 258 | 63.5% | 100% | 87.4% | 76.5% |
Наблюдения по Scatter: На большой выборке реальных данных классические алгоритмы в среднем теряют около 20% покрытия, хотя визуально потери ощущаются мягче — на уровне 5–10%. Матричный фильтр 800×600 показал почти идеальное визуальное качество, вернув при этом вдвое меньше точек. Разница во времени работы на этом объёме незначительна: сами алгоритмы отрабатывают за миллисекунды, и накладные расходы влияют сильнее, чем выбор метода.
Line-графики (Линейные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 4 939 | 693 | 99.8% | 99.3% | 100% | 99.5% |
MinMaxLTTB (x4) | 4 932 | 462 | 91.9% | 94.1% | 99.1% | 93.0% |
LTTB | 4 939 | 331 | 90.0% | 93.0% | 98.2% | 91.4% |
MinMax | 4 027 | 250 | 87.8% | 90.8% | 98.9% | 89.2% |
MatrixFilter 800×600 | 2 867 | 493 | 85.6% | 93.0% | 99.4% | 89.0% |
M4 | 3 311 | 254 | 80.4% | 85.9% | 97.4% | 82.9% |
Наблюдения по Line: При отрисовке линий разрыв между матричным фильтром и классическими алгоритмами минимален. Visual Score у всех — выше 97%. Соединительная линия закрашивает вертикальные пустоты, которые на scatter-графике были бы заметны.
Этап 2: Данные среднего размера (Medium)
Параметры: 24 файла | В среднем 500 000 точек на файл. Более плотные данные: непрерывная запись за периоды до года.
Scatter-графики (Точечные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 4 744 | 91 | 100% | 100% | 100% | 100% |
MatrixFilter 800×600 | 2 571 | 91 | 82.9% | 100% | 99.5% | 90.6% |
MinMaxLTTB (x4) | 3 249 | 29 | 38.5% | 100% | 68.8% | 54.3% |
LTTB | 4 744 | 37 | 31.5% | 100% | 60.3% | 45.8% |
MinMax | 1 584 | 33 | 24.6% | 100% | 51.2% | 37.9% |
M4 | 1 328 | 35 | 20.1% | 100% | 45.4% | 32.2% |
Наблюдения по Scatter: С ростом плотности классические алгоритмы начинают терять покрытие. LTTB сохраняет лишь 31.5% исходного облака, M4 — 20.1%. Визуально графики становятся разреженными: плотные области теряют структуру. Матричный фильтр остаётся стабильным независимо от объёма.
Line-графики (Линейные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 4 744 | 97 | 99.0% | 99.0% | 99.8% | 99.0% |
MinMaxLTTB (x4) | 3 249 | 29 | 95.6% | 96.3% | 99.7% | 95.9% |
MatrixFilter 800×600 | 2 571 | 80 | 92.3% | 96.6% | 99.5% | 94.4% |
MinMax | 1 584 | 39 | 87.0% | 89.1% | 98.7% | 88.0% |
M4 | 1 328 | 35 | 79.9% | 85.8% | 98.5% | 82.7% |
LTTB | 4 744 | 38 | 66.6% | 75.0% | 83.0% | 70.2% |
Наблюдения по Line: На линейных графиках ситуация принципиально иная. Вертикальные отрезки линий компенсируют потерю отдельных точек, показывая почти идеальную визуализацию - Visual > 98%.
Отдельного внимания заслуживает просадка чистого LTTB до 83% по визуализации. Причина — в механике алгоритма: он оставляет строго по одной точке на корзину. В зонах с высокой плотностью и большим разбросом по вертикали одной точки недостаточно, чтобы передать «толщину» зашумлённого сигнала — линия начинает отклоняться от оригинала.
Этап 3: Большие данные (Large)
Параметры: 13 файлов | В среднем 25 000 000 точек на файл (максимум — более 50 млн). Стресс-тест на предельных объёмах.
Примечание: выборка на этом этапе малая, поэтому процентные метрики следует воспринимать как оценочные. Основная цель — замер производительности.
Scatter-графики (Точечные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 13 216 | 1 657 | 100% | 100% | 100% | 100% |
MatrixFilter 800×600 | 5 545 | 1 606 | 79.9% | 100% | 99.4% | 88.8% |
MinMaxLTTB (x4) | 12 670 | 636 | 37.8% | 100% | 70.5% | 54.5% |
LTTB | 13 216 | 643 | 33.0% | 100% | 63.2% | 49.2% |
MinMax | 5 745 | 649 | 28.9% | 100% | 59.7% | 44.1% |
M4 | 5 520 | 742 | 24.2% | 100% | 53.8% | 38.3% |
Line-графики (Линейные)
Algorithm | Avg Out | Total ms | Cover | Prec | Visual | F1 |
|---|---|---|---|---|---|---|
MatrixFilter 1920×1080 | 13 216 | 1 691 | 99.6% | 98.4% | 99.9% | 98.9% |
MinMaxLTTB (x4) | 12 670 | 634 | 95.1% | 96.7% | 98.4% | 95.9% |
MinMax | 5 745 | 615 | 94.9% | 96.1% | 99.9% | 95.5% |
M4 | 5 520 | 738 | 91.4% | 94.3% | 100% | 92.8% |
MatrixFilter 800×600 | 5 545 | 1 600 | 84.5% | 95.8% | 99.5% | 89.7% |
LTTB | 13 216 | 637 | 71.8% | 83.6% | 81.2% | 76.0% |
Наблюдения: Результаты подтверждают тенденцию предыдущего этапа. На scatter-графиках классические алгоритмы продолжают терять покрытие — у LTTB оно составляет 33%. На линейных графиках ситуация выравнивается: M4 выдаёт 100% Visual Score, выполняя именно ту задачу, под которую проектировался. На этом объёме показательна степень сжатия: все алгоритмы укладывают 25 миллионов точек в 5–13 тысяч — разница лишь в том, что именно из исходной картины сохраняется.
Ключевой показатель на этом этапе — время работы. Матричный фильтр обрабатывает 13 файлов (около 324 млн точек суммарно) за 1657 мс — примерно в 2.5–3 раза медленнее классических алгоритмов. Это прямое следствие двойного прохода: сначала поиск экстремумов для границ сетки, затем растеризация. Размер матрицы (1920×1080 против 800×600) на скорость практически не влияет — меньшая сетка экономит только память и количество возвращаемых точек.
Главные выводы
Результаты всех прогонов сводятся к нескольким фактам:
Классические алгоритмы непригодны для scatter. Одномерные алгоритмы (LTTB, M4, MinMax) деградируют на точечных графиках пропорционально росту данных. Они отбрасывают 10–30% визуально значимой информации, разрежая плотные области до скелета из экстремумов.
Матричный фильтр сохраняет плотность. На точечных графиках он абсолютно стабилен. Опора на физические пиксели, а не на ось времени, гарантирует 100% покрытие независимо от объёма данных на входе.
Линейные графики компенсируют потери. Для line chart разрыв в качестве минимален. Соединительная линия закрашивает вертикальные пустоты в пиксельных столбцах, вытягивая метрики классических алгоритмов.
M4 решает свою задачу. На линейных графиках и больших объёмах M4 показал 100% Visual Score. Для line chart это по-прежнему быстрое и точное решение.
Слабость чистого LTTB. На зашумлённых данных, где в один пиксельный столбец попадают сотни точек с большим разбросом амплитуды, LTTB проседает даже на линейных графиках. Одна точка на корзину — недостаточно для передачи визуальной «толщины» сигнала.
Размер матрицы — рычаг для трафика. Уменьшение сетки с 1920×1080 до 800×600 практически не снижает визуальное качество (~99% Visual Score), но возвращает в 2–2.5 раза меньше точек.
Размер матрицы не влияет на скорость. Фильтр 800×600 работает за то же время, что и Full HD. Меньшая сетка экономит память, но не процессорное время.
Матричный фильтр медленнее в 2–3 раза. Это следствие двойного прохода по массиву: сначала поиск границ, затем растеризация.
В абсолютных величинах скорость достаточна. 25 миллионов точек обрабатываются примерно за 130 мс в один поток. На таких объёмах разница легко растворяется в накладных расходах: сериализация, сеть, рендеринг в браузере.
Единый подход. Матричный фильтр одинаково точно работает и на scatter, и на line chart. Это позволяет использовать один алгоритм вместо набора специализированных — при условии, что задача сводится к визуализации.
Заключение
Если продукт отображает исключительно линейные графики, матричный фильтр, вероятно, не нужен. M4 или MinMaxLTTB работают в один проход, считают быстрее и дают отличный результат на непрерывных кривых.
Но в промышленной телеметрии — где данные рвутся, датчики шумят, а scatter-график остаётся основным инструментом аналитика — одномерные алгоритмы систематически искажают картину, отбрасывая визуально значимую плотность. Для таких задач двумерное прореживание оказывается более релевантным.
Матричный фильтр медленнее в 2–3 раза. На практике это десятки миллисекунд, которые растворяются в накладных расходах стека. Взамен мы получаем пиксельно точную визуализацию и единый алгоритм, одинаково пригодный для любого типа графика.
Исходный код
Код эксперимента — все фильтры и тестовые стенды — выделен в открытый репозиторий. Алгоритм реализован на Java без сторонних библиотек, легко читается и переносится на любой другой язык.
Исходный код на GitHub: https://github.com/gearquicker/time-series-filter
