Annotated Sequence Diagrams with Complexity Analysis

This document contains sequence diagrams showing the data flow through PySuricata's streaming algorithms, annotated with time and space complexity for each operation.

Pandas Data Processing Flow

sequenceDiagram
    participant User
    participant Profile
    participant Adapter as PandasAdapter
    participant Accumulator as NumericAccumulator
    participant KMV
    participant Reservoir as ReservoirSampler
    participant Extreme as ExtremeTracker
    participant MG as MisraGries

    User->>Profile: profile(data, config)
    Note over Profile: O(1) - Configuration setup

    Profile->>Adapter: process_chunk(chunk)
    Note over Adapter: O(n) - Iterate through rows

    loop For each numeric column
        Adapter->>Accumulator: update(values)
        Note over Accumulator: O(n) - Process n values

        Accumulator->>KMV: add(value)
        Note over KMV: O(log k) - Binary search insert<br/>Space: O(k) bounded

        Accumulator->>Reservoir: add(value)
        Note over Reservoir: O(1) - Constant time<br/>Space: O(s) bounded

        Accumulator->>Extreme: update(values, indices)
        Note over Extreme: O(n log k) - Process n values<br/>Space: O(k) bounded

        Accumulator->>MG: add(value)
        Note over MG: O(1) - Constant time<br/>Space: O(k) bounded
    end

    Accumulator->>Profile: finalize()
    Note over Accumulator: O(k log k) - Extract results<br/>Space: O(k) bounded

    Profile->>User: Report
    Note over Profile: O(1) - Return results

Polars Data Processing Flow

sequenceDiagram
    participant User
    participant Profile
    participant Adapter as PolarsAdapter
    participant Accumulator as NumericAccumulator
    participant KMV
    participant Reservoir as ReservoirSampler
    participant Extreme as ExtremeTracker
    participant MG as MisraGries

    User->>Profile: profile(data, config)
    Note over Profile: O(1) - Configuration setup

    Profile->>Adapter: process_chunk(chunk)
    Note over Adapter: O(n) - Iterate through rows

    loop For each numeric column
        Adapter->>Accumulator: update(values)
        Note over Accumulator: O(n) - Process n values

        Accumulator->>KMV: add(value)
        Note over KMV: O(log k) - Binary search insert<br/>Space: O(k) bounded

        Accumulator->>Reservoir: add(value)
        Note over Reservoir: O(1) - Constant time<br/>Space: O(s) bounded

        Accumulator->>Extreme: update(values, indices)
        Note over Extreme: O(n log k) - Process n values<br/>Space: O(k) bounded

        Accumulator->>MG: add(value)
        Note over MG: O(1) - Constant time<br/>Space: O(k) bounded
    end

    Accumulator->>Profile: finalize()
    Note over Accumulator: O(k log k) - Extract results<br/>Space: O(k) bounded

    Profile->>User: Report
    Note over Profile: O(1) - Return results

KMV Sketch Memory Optimization

sequenceDiagram
    participant KMV
    participant ExactCounter as _exact_counter
    participant Values as _values
    participant Hash as _u64

    Note over KMV: Before Fix: O(n) memory growth<br/>After Fix: O(k) bounded memory

    KMV->>ExactCounter: add(value)
    Note over ExactCounter: O(1) - Dict lookup<br/>Space: O(min(n, max_exact_tracking))

    alt Exact mode (count < max_exact_tracking)
        ExactCounter->>ExactCounter: increment counter
        Note over ExactCounter: O(1) - Dict update
    else Transition to approximation mode
        ExactCounter->>Values: convert to hashes
        Note over Values: O(k) - Convert exact values<br/>Space: O(k) bounded

        ExactCounter->>ExactCounter: clear()
        Note over ExactCounter: O(1) - Free memory

        Values->>Values: sort()
        Note over Values: O(k log k) - Sort hashes
    end

    alt Approximation mode
        KMV->>Hash: _u64(value)
        Note over Hash: O(1) - Hash computation

        Hash->>Values: insert if smaller
        Note over Values: O(log k) - Binary search insert<br/>Space: O(k) bounded
    end

    KMV->>Values: estimate()
    Note over Values: O(1) - Direct calculation<br/>Space: O(k) bounded

ExtremeTracker Memory Optimization

sequenceDiagram
    participant Extreme as ExtremeTracker
    participant MinHeap as _min_heap
    participant MaxHeap as _max_heap
    participant Heapq

    Note over Extreme: Before Fix: O(k × chunks) temporary growth<br/>After Fix: O(k) constant space

    Extreme->>Extreme: update(values, indices)
    Note over Extreme: O(n log k) - Process n values

    loop For each value
        Extreme->>MinHeap: _add_to_min_heap(index, value)
        Note over MinHeap: O(log k) - Heap insert<br/>Space: O(k) bounded

        Extreme->>MaxHeap: _add_to_max_heap(index, value)
        Note over MaxHeap: O(log k) - Heap insert<br/>Space: O(k) bounded
    end

    alt Min heap not full
        MinHeap->>Heapq: heappush(value, index)
        Note over Heapq: O(log k) - Heap insert
    else Min heap full
        MinHeap->>MinHeap: find largest value
        Note over MinHeap: O(k) - Linear search

        alt New value smaller
            MinHeap->>MinHeap: replace largest
            Note over MinHeap: O(k) - Find and replace
            MinHeap->>Heapq: heapify()
            Note over Heapq: O(k) - Restore heap property
        end
    end

    alt Max heap not full
        MaxHeap->>Heapq: heappush(-value, index)
        Note over Heapq: O(log k) - Heap insert (negated)
    else Max heap full
        MaxHeap->>MaxHeap: find smallest original value
        Note over MaxHeap: O(k) - Linear search

        alt New value larger
            MaxHeap->>MaxHeap: replace smallest
            Note over MaxHeap: O(k) - Find and replace
            MaxHeap->>Heapq: heapify()
            Note over Heapq: O(k) - Restore heap property
        end
    end

    Extreme->>Extreme: get_extremes()
    Note over Extreme: O(k log k) - Extract and sort<br/>Space: O(k) bounded

Chunk Metadata Optimization

sequenceDiagram
    participant Accumulator as NumericAccumulator
    participant Config as NumericConfig
    participant Boundaries as _chunk_boundaries
    participant Missing as _chunk_missing
    participant Counter as _chunk_count

    Note over Accumulator: Before Fix: O(num_chunks) unbounded growth<br/>After Fix: O(min(num_chunks, max_chunks)) bounded

    Accumulator->>Config: check enable_chunk_metadata
    Note over Config: O(1) - Configuration check

    alt Chunk metadata enabled
        Accumulator->>Counter: check _chunk_count < max_chunks
        Note over Counter: O(1) - Counter check

        alt Under limit
            Accumulator->>Boundaries: append(cumulative_rows)
            Note over Boundaries: O(1) - List append<br/>Space: O(chunk_count)

            Accumulator->>Missing: append(missing_count)
            Note over Missing: O(1) - List append<br/>Space: O(chunk_count)

            Accumulator->>Counter: increment()
            Note over Counter: O(1) - Counter increment
        else Over limit
            Accumulator->>Config: disable chunk metadata
            Note over Config: O(1) - Switch to summary mode

            Accumulator->>Boundaries: stop tracking
            Note over Boundaries: O(1) - Stop appending<br/>Space: O(max_chunks) bounded
        end
    else Chunk metadata disabled
        Accumulator->>Accumulator: skip tracking
        Note over Accumulator: O(1) - No memory usage<br/>Space: O(1) constant
    end

    Accumulator->>Accumulator: finalize()
    Note over Accumulator: O(chunk_count) - Process metadata<br/>Space: O(min(chunk_count, max_chunks)) bounded

Complexity Summary

Time

• Per element: O(1) for the moments and the sketch updates; O(log k) where a heap is involved
• Per chunk: O(n) in the chunk size
• Total: O(N) in the dataset — a single pass, each row read once

Space

Every bound below is per column:

structure	space	set by
streaming moments	O(1)	—
reservoir sample	O(s)	numeric_sample_size (20,000)
KMV sketch	O(k)	max_uniques (2,048)
Misra-Gries table	O(k)	top_k (50)
extreme tracker	O(k)	—
chunk metadata	O(min(chunks, max_chunks))	—

Total: O(cols × (s + k)). Nothing in that expression is the row count, which is the whole claim — memory is flat in rows.

It is not flat in columns. Multiplying by cols is not a rounding error: at roughly 529 KB per column, a 20,000 × 600 frame peaks at 631 MB against 344 MB for a 1,000,000 × 14 one on more cells. That is a known limit, tracked in #207, and it is the honest reading of the table above.

Measure it rather than taking a figure from this page: python -m benchmarks.kernels prints the per-kernel memory roofline, and tests/test_memory_stress.py asserts the row-axis flatness in subprocesses on every run.