Input Pattern Classification Based on the Markov Property of the IMBT with Related Equations and Contingency Tables

Abstract

In this contribution, we provide a detailed analysis of the search operation for the Interval Merging Binary Tree (IMBT), an efficient data structure proposed earlier to handle typical anomalies in the transmission of data packets. A framework is provided to decide under which conditions IMBT outperforms other data structures typically used in the field, as a function of the statistical characteristics of the commonly occurring anomalies in the arrival of data packets. We use in the modeling Bernstein theorem, Markov property, Fibonacci sequences, bipartite multi-graphs, and contingency tables.

Keywords

• data structure
• balanced binary tree
• bipartite graph
• bernstein theorem, fibonacci sequence
• markov property
• state space
• contingency table