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

István Finta; Sándor Szénási; Lóránt Farkas

doi:10.3390/e22020245

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

Entropy (Basel). 2020 Feb 21;22(2):245. doi: 10.3390/e22020245.

Authors

István Finta¹, Sándor Szénási², Lóránt Farkas¹

Affiliations

¹ Nokia, Bell Labs, Bókay street 36-42, H-1083 Budapest, Hungary.
² Department of Informatics, J. Selye University, Bratislavská cesta 3322, SK-94501 Komárno, Slovakia.

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: Bernstein theorem, Fibonacci sequence; Markov property; balanced binary tree; bipartite graph; contingency table; data structure; state space.