OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative Study of SIP Overload Control Algorithms
Venue: arXiv cs.NI 2014
Year: 2014

Recent collapses of SIP servers in the carrier networks indicates two potential problems of SIP: (1) the current SIP design does not easily scale up to large network sizes, and (2) the built-in SIP overload control mechanism cannot handle overload conditions effectively. In order to help carriers prevent widespread SIP network failure effectively, this chapter presents a systematic investigation of current state-of-the-art overload control algorithms. To achieve this goal, this chapter first reviews two basic mechanisms of SIP, and summarizes numerous experiment results reported in the literatures which demonstrate the impact of overload on SIP networks. After surveying the approaches for modeling the dynamic behaviour of SIP networks experiencing overload, the chapter presents a comparison and assessment of different types of SIP overload control solutions. Finally it outlines some research opportunities for managing SIP overload control.
Better Space Bounds for Parameterized Range Majority and Minority
Venue: arXiv cs.DS 2014
Year: 2014

Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length $n$ such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold $τ$. Subsequent authors have reduced their time and space bounds such that, when $τ$ is given at preprocessing time, we need either $\Oh{n \log (1 / τ)}$ space and optimal $\Oh{1 / τ}$ query time or linear space and $\Oh{(1 / τ) \log \log σ}$ query time, where $σ$ is the alphabet size. In this paper we give the first linear-space solution with optimal $\Oh{1 / τ}$ query time. For the case when $τ$ is given at query time, we significantly improve previous bounds, achieving either $\Oh{n \log \log σ}$ space and optimal $\Oh{1 / τ}$ query time or compressed space and $\Oh{(1 / τ) \log \frac{\log (1 / τ)}{\log w}}$ query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by Chan et al.\ (2012), who achieved linear space and $\Oh{1 / τ}$ query time even for variable $τ$. We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest.
Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations
Venue: arXiv cs.LO 2014
Year: 2014

Motivated by applications in databases, this paper considers various fragments of the calculus of binary relations. The fragments are obtained by leaving out, or keeping in, some of the standard operators, along with some derived operators such as set difference, projection, coprojection, and residuation. For each considered fragment, a characterization is obtained for when two given binary relational structures are indistinguishable by expressions in that fragment. The characterizations are based on appropriately adapted notions of simulation and bisimulation.
A simple model clarifies the complicated relationships of complex networks
Venue: arXiv cs.SI 2014
Year: 2014

Real-world networks such as the Internet and WWW have many common traits. Until now, hundreds of models were proposed to characterize these traits for understanding the networks. Because different models used very different mechanisms, it is widely believed that these traits origin from different causes. However, we find that a simple model based on optimisation can produce many traits, including scale-free, small-world, ultra small-world, Delta-distribution, compact, fractal, regular and random networks. Moreover, by revising the proposed model, the community-structure networks are generated. By this model and the revised versions, the complicated relationships of complex networks are illustrated. The model brings a new universal perspective to the understanding of complex networks and provide a universal method to model complex networks from the viewpoint of optimisation.
Shortest, Fastest, and Foremost Broadcast in Dynamic Networks
Venue: arXiv cs.DC 2014
Year: 2014

Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called {\em journeys}). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), and foremost (earliest arrival) journeys. Efficient centralized algorithms exists to compute all cases, when the full knowledge of the network evolution is given. In this paper, we study the {\em distributed} counterparts of these problems, i.e. shortest, fastest, and foremost broadcast with termination detection (TDB), with minimal knowledge on the topology. We show that the feasibility of each of these problems requires distinct features on the evolution, through identifying three classes of dynamic graphs wherein the problems become gradually feasible: graphs in which the re-appearance of edges is {\em recurrent} (class R), {\em bounded-recurrent} (B), or {\em periodic} (P), together with specific knowledge that are respectively $n$ (the number of nodes), $Δ$ (a bound on the recurrence time), and $p$ (the period). In these classes it is not required that all pairs of nodes get in contact -- only that the overall {\em footprint} of the graph is connected over time. Our results, together with the strict inclusion between $P$, $B$, and $R$, implies a feasibility order among the three variants of the problem, i.e. TDB[foremost] requires weaker assumptions on the topology dynamics than TDB[shortest], which itself requires less than TDB[fastest]. Reversely, these differences in feasibility imply that the computational powers of $R_n$, $B_Δ$, and $P_p$ also form a strict hierarchy.
Reputation Aggregation in Peer-to-Peer Network Using Differential Gossip Algorithm
Venue: arXiv cs.NI 2014
Year: 2014

Reputation aggregation in peer to peer networks is generally a very time and resource consuming process. Moreover, most of the methods consider that a node will have same reputation with all the nodes in the network, which is not true. This paper proposes a reputation aggregation algorithm that uses a variant of gossip algorithm called differential gossip. In this paper, estimate of reputation is considered to be having two parts, one common component which is same with every node, and the other one is information received from immediate neighbours based on the neighbours' direct interaction with the node. The differential gossip is fast and requires less amount of resources. This mechanism allows computation of independent reputation value by a node, of every other node in the network, for each node. The differential gossip trust has been investigated for a power law network formed using preferential attachment \emph{(PA)} Model. The reputation computed using differential gossip trust shows good amount of immunity to the collusion. We have verified the performance of the algorithm on the power law networks of different sizes ranging from 100 nodes to 50,000 nodes.
Gender identity and lexical variation in social media
Venue: arXiv cs.CL 2014
Year: 2014

We present a study of the relationship between gender, linguistic style, and social networks, using a novel corpus of 14,000 Twitter users. Prior quantitative work on gender often treats this social variable as a female/male binary; we argue for a more nuanced approach. By clustering Twitter users, we find a natural decomposition of the dataset into various styles and topical interests. Many clusters have strong gender orientations, but their use of linguistic resources sometimes directly conflicts with the population-level language statistics. We view these clusters as a more accurate reflection of the multifaceted nature of gendered language styles. Previous corpus-based work has also had little to say about individuals whose linguistic styles defy population-level gender patterns. To identify such individuals, we train a statistical classifier, and measure the classifier confidence for each individual in the dataset. Examining individuals whose language does not match the classifier's model for their gender, we find that they have social networks that include significantly fewer same-gender social connections and that, in general, social network homophily is correlated with the use of same-gender language markers. Pairing computational methods and social theory thus offers a new perspective on how gender emerges as individuals position themselves relative to audiences, topics, and mainstream gender norms.
A density-sensitive hierarchical clustering method
Venue: arXiv cs.LG 2014
Year: 2014

We define a hierarchical clustering method: $α$-unchaining single linkage or $SL(α)$. The input of this algorithm is a finite metric space and a certain parameter $α$. This method is sensitive to the density of the distribution and offers some solution to the so called chaining effect. We also define a modified version, $SL^*(α)$, to treat the chaining through points or small blocks. We study the theoretical properties of these methods and offer some theoretical background for the treatment of chaining effects.
The automatic creation of concept maps from documents written using morphologically rich languages
Venue: arXiv cs.IR 2014
Year: 2014

Concept map is a graphical tool for representing knowledge. They have been used in many different areas, including education, knowledge management, business and intelligence. Constructing of concept maps manually can be a complex task; an unskilled person may encounter difficulties in determining and positioning concepts relevant to the problem area. An application that recommends concept candidates and their position in a concept map can significantly help the user in that situation. This paper gives an overview of different approaches to automatic and semi-automatic creation of concept maps from textual and non-textual sources. The concept map mining process is defined, and one method suitable for the creation of concept maps from unstructured textual sources in highly inflected languages such as the Croatian language is described in detail. Proposed method uses statistical and data mining techniques enriched with linguistic tools. With minor adjustments, that method can also be used for concept map mining from textual sources in other morphologically rich languages.
Near Optimal Leader Election in Multi-Hop Radio Networks
Venue: arXiv cs.DS 2014
Year: 2014

We present distributed randomized leader election protocols for multi-hop radio networks that elect a leader in almost the same time $T_{BC}$ required for broadcasting a message. For the setting without collision detection, our algorithm runs with high probability in $O(D \log \frac{n}{D} + \log^3 n) \min\{\log\log n,\log \frac{n}{D}\}$ rounds on any $n$-node network with diameter $D$. Since $T_{BC} = Θ(D \log \frac{n}{D} + \log^2 n)$ is a lower bound, our upper bound is optimal up to a factor of at most $\log \log n$ and the extra $\log n$ factor on the additive term. This algorithm is furthermore the first $O(n)$ time algorithm for this setting. Our algorithms improve over a 25 year old simulation approach of Bar-Yehuda, Goldreich and Itai with a $O(T_{BC} \log n)$ running time: In 1987 they designed a fast broadcast protocol and subsequently in 1989 they showed how it can be used to simulate one round of a single-hop network that has collision detection in $T_{BC}$ time. The prime application of this simulation was to simulate Willards single-hop leader election protocol, which elects a leader in $O(\log n)$ rounds with high probability and $O(\log \log n)$ rounds in expectation. While it was subsequently shown that Willards bounds are tight, it was unclear whether the simulation approach is optimal. Our results break this barrier and essentially remove the logarithmic slowdown over the broadcast time $T_{BC}$ by going away from the simulation approach. We also give a distributed randomized leader election algorithm for the setting with collision detection that runs in $O(D + \log n \log \log n) \cdot \min\{\log \log n, \log \frac{n}{D}\}$ rounds. This round complexity is optimal up to $O(\log \log n)$ factors and improves over a deterministic algorithm that requires $Θ(n)$ rounds independently of the diameter $D$.
Venn-Abers predictors
Venue: arXiv cs.LG 2014
Year: 2014

This paper continues study, both theoretical and empirical, of the method of Venn prediction, concentrating on binary prediction problems. Venn predictors produce probability-type predictions for the labels of test objects which are guaranteed to be well calibrated under the standard assumption that the observations are generated independently from the same distribution. We give a simple formalization and proof of this property. We also introduce Venn-Abers predictors, a new class of Venn predictors based on the idea of isotonic regression, and report promising empirical results both for Venn-Abers predictors and for their more computationally efficient simplified version.
Self-improving Algorithms for Coordinate-Wise Maxima and Convex Hulls
Venue: arXiv cs.CG 2014
Year: 2014

Finding the coordinate-wise maxima and the convex hull of a planar point set are probably the most classic problems in computational geometry. We consider these problems in the self-improving setting. Here, we have $n$ distributions $\mathcal{D}_1, \ldots, \mathcal{D}_n$ of planar points. An input point set $(p_1, \ldots, p_n)$ is generated by taking an independent sample $p_i$ from each $\mathcal{D}_i$, so the input is distributed according to the product $\mathcal{D} = \prod_i \mathcal{D}_i$. A self-improving algorithm repeatedly gets inputs from the distribution $\mathcal{D}$ (which is a priori unknown), and it tries to optimize its running time for $\mathcal{D}$. The algorithm uses the first few inputs to learn salient features of the distribution $\mathcal{D}$, before it becomes fine-tuned to $\mathcal{D}$. Let $\text{OPTMAX}_\mathcal{D}$ (resp. $\text{OPTCH}_\mathcal{D}$) be the expected depth of an \emph{optimal} linear comparison tree computing the maxima (resp. convex hull) for $\mathcal{D}$. Our maxima algorithm eventually achieves expected running time $O(\text{OPTMAX}_\mathcal{D} + n)$. Furthermore, we give a self-improving algorithm for convex hulls with expected running time $O(\text{OPTCH}_\mathcal{D} + n\log\log n)$. Our results require new tools for understanding linear comparison trees. In particular, we convert a general linear comparison tree to a restricted version that can then be related to the running time of our algorithms. Another interesting feature is an interleaved search procedure to determine the likeliest point to be extremal with minimal computation. This allows our algorithms to be competitive with the optimal algorithm for $\mathcal{D}$.
Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices
Venue: arXiv cs.IT 2014
Year: 2014

Polarization phenomenon over any finite field $\mathbb{F}_{q}$ with size $q$ being a power of a prime is considered. This problem is a generalization of the original proposal of channel polarization by Arikan for the binary field, as well as its extension to a prime field by Sasoglu, Telatar, and Arikan. In this paper, a necessary and sufficient condition of a matrix over a finite field $\mathbb{F}_q$ is shown under which any source and channel are polarized. Furthermore, the result of the speed of polarization for the binary alphabet obtained by Arikan and Telatar is generalized to arbitrary finite field. It is also shown that the asymptotic error probability of polar codes is improved by using the Reed-Solomon matrix, which can be regarded as a natural generalization of the $2\times 2$ binary matrix used in the original proposal by Arikan.
Impact of blood rheology on wall shear stress in a model of the middle cerebral artery
Venue: arXiv cs.CE 2014
Year: 2014

Perturbations to the homeostatic distribution of mechanical forces exerted by blood on the endothelial layer have been correlated with vascular pathologies including intracranial aneurysms and atherosclerosis. Recent computational work suggests that in order to correctly characterise such forces, the shear-thinning properties of blood must be taken into account. To the best of our knowledge, these findings have never been compared against experimentally observed pathological thresholds. In the current work, we apply the three-band diagram (TBD) analysis due to Gizzi et al. to assess the impact of the choice of blood rheology model on a computational model of the right middle cerebral artery. Our results show that, in the model under study, the differences between the wall shear stress predicted by a Newtonian model and the well known Carreau-Yasuda generalized Newtonian model are only significant if the vascular pathology under study is associated with a pathological threshold in the range 0.94 Pa to 1.56 Pa, where the results of the TBD analysis of the rheology models considered differs. Otherwise, we observe no significant differences.
Interference Alignment with Incomplete CSIT Sharing
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we study the impact of having only incomplete channel state information at the transmitters (CSIT) over the feasibility of interference alignment (IA) in a K-user MIMO interference channel (IC). Incompleteness of CSIT refers to the perfect knowledge at each transmitter (TX) of only a sub-matrix of the global channel matrix, where the sub-matrix is specific to each TX. This paper investigates the notion of IA feasibility for CSIT configurations being as incomplete as possible, as this leads to feedback overhead reductions in practice. We distinguish between antenna configurations where (i) removing a single antenna makes IA unfeasible, referred to as tightly-feasible settings, and (ii) cases where extra antennas are available, referred to as super-feasible settings. We show conditions for which IA is feasible in strictly incomplete CSIT scenarios, even in tightly-feasible settings. For such cases, we provide a CSIT allocation policy preserving IA feasibility while reducing significantly the amount of CSIT required. For super-feasible settings, we develop a heuristic CSIT allocation algorithm which exploits the additional antennas to further reduce the size of the CSIT allocation. As a byproduct of our approach, a simple and intuitive algorithm for testing feasibility of single stream IA is provided.
Keyhole and Reflection Effects in Network Connectivity Analysis
Venue: arXiv cs.IT 2014
Year: 2014

Recent research has demonstrated the importance of boundary effects on the overall connection probability of wireless networks, but has largely focused on convex domains. We consider two generic scenarios of practical importance to wireless communications, in which one or more nodes are located outside the convex space where the remaining nodes reside. Consequently, conventional approaches with the underlying assumption that only line-of-sight (LOS) or direct connections between nodes are possible, fail to provide the correct analysis for the connectivity. We present an analytical framework that explicitly considers the effects of reflections from the system boundaries on the full connection probability. This study provides a different strategy to ray tracing tools for predicting the wireless propagation environment. A simple two-dimensional geometry is first considered, followed by a more practical three-dimensional system. We investigate the effects of different system parameters on the connectivity of the network though analysis corroborated by numerical simulations, and highlight the potential of our approach for more general non-convex geometries.t system parameters on the connectivity of the network through simulation and analysis.
New Approach for CCA2-Secure Post-Quantum Cryptosystem Using Knapsack Problem
Venue: arXiv cs.CR 2014
Year: 2014

Chosen-ciphertext security, which guarantees confidentiality of encrypted messages even in the presence of a decryption oracle, has become the defacto notion of security for public-key encryption under active attack. In this manuscript, for the first time, we propose a new approach for constructing post-quantum cryptosystems secure against adaptive chosen ciphertext attack (CCA2-secure) in the standard model using the knapsack problem. The computational version of the knapsack problem is NP-hard. Thus, this problem is expected to be difficult to solve using quantum computers. Our construction is a precoding-based encryption algorithm and uses the knapsack problem to perform a permutation and pad some random fogged data to the message bits. Compared to other approaches were introduced today, our approach is very simple and more efficient.
Generalized Cayley Graphs and Cellular Automata over them
Venue: arXiv cs.DM 2014
Year: 2014

Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations; to name all vertices relative to a point; and the fact that they have a well-defined notion of translation. We propose a notion of graph associated to a language, which conserves or generalizes these features. Whereas Cayley graphs are very regular; associated graphs are arbitrary, although of a bounded degree. Moreover, it is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions for a distance on the set of configurations that makes it a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Similarly, we extend their definition to these arbitrary, bounded degree, time-varying graphs. The obtained notion of Cellular Automata over generalized Cayley graphs is stable under composition and under inversion. KEYWORDS: Causal Graph Dynamics, Curtis-Hedlund-Lyndon, Dynamical networks, Boolean networks, Generative networks automata, Graph Automata, Graph rewriting automata, L-systems, parallel graph transformations, Amalgamated graph transformations, Time-varying graphs, Regge calculus, Local, No-signalling, Reversibility.
Onboard Dynamic Rail Track Safety Monitoring System
Venue: arXiv cs.MA 2014
Year: 2014

This proposal aims at solving one of the long prevailing problems in the Indian Railways. This simple method of continuous monitoring and assessment of the condition of the rail tracks can prevent major disasters and save precious human lives. Our method is capable of alerting the train in case of any dislocations in the track or change in strength of the soil. Also it can avert the collisions of the train with other or with the vehicles trying to move across the unmanned level crossings.