Monoid-Augmented FIFOs, Deamortised
4 days ago
- #data-structures
- #streaming-analytics
- #monoids
- Augmented FIFOs are useful in streaming analytics for computing windowed aggregates.
- The data structure maintains aggregates over monoids (associative operators) efficiently.
- A deamortized algorithm (DABA) is presented for constant-time operations on monoid-augmented FIFOs.
- The algorithm uses ingestion and excretion lists with incremental suffix product updates.
- Python implementation provided with worst-case constant-time operations.
- Use cases include tracking top-K values, min/max, and other statistical sketches.