Optimized Red-Black Trees for the Most Frequent String Problem in Noisy Comparison Models
Faruk Ibrahimović · 2024
This study addresses the Most Frequent Item (MFI) problem with respect to noisy comparisons, which has implications of a quantum speed-up for this problem. We introduce two variants of noisy Red-Black trees that support efficient searching and addition operations which also mitigate the uncertainty inherent in quantum string comparisons. Through detailed complexity analysis and extensive experimental validation, we compare these structures with a probability-boosting approach. Our findings suggest that these data structures are well-suited for high-stakes applications in telecommunication, where efficient and accurate data structures and algorithms are critical.