Permutation parity needs lots of memory pattern detection fits in little
Parity and Pattern Detection in Permutation Streams
Data Structures and Algorithms
Summary
Figuring out whether a hidden order of numbers has an even or odd rearrangement (parity) needs a lot of memory, no matter how clever the method is. But spotting small patterns of three numbers in such sequences can be done in very little space and just one quick look. The researchers completed a clear picture showing when detecting patterns is easy or hard in terms of memory needed. This understanding also helps check if certain searches in binary search trees happened correctly, using very little memory.
What this means in practice
- •For database administrators: Use small memory streaming checks to verify correctness of database query traversals efficiently.
- •For algorithm engineers: Design streaming algorithms with guaranteed memory needs for detecting simple and complex patterns in data sequences.
A theory result. No direct application yet.
Authors
Mark Braverman, Or Zamir
Abstract
Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.