In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance me
asures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.
Though competitive analysis has been a very useful performance measure for the quality of online algorithms, it is recognized that it sometimes fails to distinguish between algorithms of different quality in practice. A number of alternative measures
have been proposed, but, with a few exceptions, these have generally been applied only to the online problem they were developed in connection with. Recently, a systematic study of performance measures for online algorithms was initiated [Boyar, Irani, Larsen: Eleventh International Algorithms and Data Structures Symposium 2009], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, Random Order, and Max/Max. In addition to drawing conclusions on this work, we also investigate the measures sensitivity to integral vs. real-valued domains, and as a part of this work, generalize some of the known performance measures. Finally, we have established the first optimality proof for Relative Interval Analysis.
Life and language are discrete combinatorial systems (DCSs) in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence and letters or words in a language. Different combinations of these finite uni
ts give rise to potentially infinite numbers of genes or sentences. This type of DCS can be represented as an Alphabetic Bipartite Network ($alpha$-BiN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. There is an edge between a node corresponding to an elementary unit $u$ and a node corresponding to a particular combination $v$ if $u$ is present in $v$. Naturally, the partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. Here, we extend recently analytical findings for $alpha$-BiNs derived in [Peruani et al., Europhys. Lett. 79, 28001 (2007)] and empirically investigate two real world systems: the codon-gene network and the phoneme-language network. The evolution equations for $alpha$-BiNs under different growth rules are derived, and the corresponding degree distributions computed. It is shown that asymptotically the degree distribution of $alpha$-BiNs can be described as a family of beta distributions. The one-mode projections of the theoretical as well as the real world $alpha$-BiNs are also studied. We propose a comparison of the real world degree distributions and our theoretical predictions as a means for inferring the mechanisms underlying the growth of real world systems.
