OpenRaiser/Intern-Atlas huggingface dataset:
Horton Law in Self-Similar Trees
Venue: arXiv cs.DM 2015
Year: 2015

Self-similarity of random trees is related to the operation of pruning. Pruning $R$ cuts the leaves and their parental edges and removes the resulting chains of degree-two nodes from a finite tree. A Horton-Strahler order of a vertex $v$ and its parental edge is defined as the minimal number of prunings necessary to eliminate the subtree rooted at $v$. A branch is a group of neighboring vertices and edges of the same order. The Horton numbers $N_k[K]$ and $N_{ij}[K]$ are defined as the expected number of branches of order $k$, and the expected number of order-$i$ branches that merged order-$j$ branches, $j>i$, respectively, in a finite tree of order $K$. The Tokunaga coefficients are defined as $T_{ij}[K]=N_{ij}[K]/N_j[K]$. The pruning decreases the orders of tree vertices by unity. A rooted full binary tree is said to be mean-self-similar if its Tokunaga coefficients are invariant with respect to pruning: $T_k:=T_{i,i+k}[K]$. We show that for self-similar trees, the condition $\limsup(T_k)^{1/k}<\infty$ is necessary and sufficient for the existence of the strong Horton law: $N_k[K]/N_1[K] \rightarrow R^{1-k}$, as $K \rightarrow \infty$ for some $R>0$ and every $k\geq 1$. This work is a step toward providing rigorous foundations for the Horton law that, being omnipresent in natural branching systems, has escaped so far a formal explanation.
Formalization of Quantum Protocols using Coq
Venue: arXiv cs.LO 2015
Year: 2015

Quantum Information Processing, which is an exciting area of research at the intersection of physics and computer science, has great potential for influencing the future development of information processing systems. The building of practical, general purpose Quantum Computers may be some years into the future. However, Quantum Communication and Quantum Cryptography are well developed. Commercial Quantum Key Distribution systems are easily available and several QKD networks have been built in various parts of the world. The security of the protocols used in these implementations rely on information-theoretic proofs, which may or may not reflect actual system behaviour. Moreover, testing of implementations cannot guarantee the absence of bugs and errors. This paper presents a novel framework for modelling and verifying quantum protocols and their implementations using the proof assistant Coq. We provide a Coq library for quantum bits (qubits), quantum gates, and quantum measurement. As a step towards verifying practical quantum communication and security protocols such as Quantum Key Distribution, we support multiple qubits, communication and entanglement. We illustrate these concepts by modelling the Quantum Teleportation Protocol, which communicates the state of an unknown quantum bit using only a classical channel.
Symmetry-invariant optimization in deep networks
Venue: arXiv cs.LG 2015
Year: 2015

Recent works have highlighted scale invariance or symmetry that is present in the weight space of a typical deep network and the adverse effect that it has on the Euclidean gradient based stochastic gradient descent optimization. In this work, we show that these and other commonly used deep networks, such as those which use a max-pooling and sub-sampling layer, possess more complex forms of symmetry arising from scaling based reparameterization of the network weights. We then propose two symmetry-invariant gradient based weight updates for stochastic gradient descent based learning. Our empirical evidence based on the MNIST dataset shows that these updates improve the test performance without sacrificing the computational efficiency of the weight updates. We also show the results of training with one of the proposed weight updates on an image segmentation problem.
Computational Intractability of Dictionary Learning for Sparse Representation
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we consider the dictionary learning problem for sparse representation. We first show that this problem is NP-hard by polynomial time reduction of the densest cut problem. Then, using successive convex approximation strategies, we propose efficient dictionary learning schemes to solve several practical formulations of this problem to stationary points. Unlike many existing algorithms in the literature, such as K-SVD, our proposed dictionary learning scheme is theoretically guaranteed to converge to the set of stationary points under certain mild assumptions. For the image denoising application, the performance and the efficiency of the proposed dictionary learning scheme are comparable to that of K-SVD algorithm in simulation.
On the Cost of Concurrency in Transactional Memory
Venue: arXiv cs.DC 2015
Year: 2015

Traditional techniques for synchronization are based on \emph{locking} that provides threads with exclusive access to shared data. \emph{Coarse-grained} locking typically forces threads to access large amounts of data sequentially and, thus, does not fully exploit hardware concurrency. Program-specific \emph{fine-grained} locking or \emph{non-blocking} (\emph{i.e.}, not using locks) synchronization, on the other hand, is a dark art to most programmers and trusted to the wisdom of a few computing experts. Thus, it is appealing to seek a middle ground between these two extremes: a synchronization mechanism that relieves the programmer of the overhead of reasoning about data conflicts that may arise from concurrent operations without severely limiting the program's performance. The \emph{Transactional Memory (TM)} abstraction is proposed as such a mechanism: it intends to combine an easy-to-use programming interface with an efficient utilization of the concurrent-computing abilities provided by multicore architectures. TM allows the programmer to \emph{speculatively} execute sequences of shared-memory operations as \emph{atomic transactions} with \emph{all-or-nothing} semantics: the transaction can either \emph{commit}, in which case it appears as executed sequentially, or \emph{abort}, in which case its update operations do not take effect. Thus, the programmer can design software having only sequential semantics in mind and let TM take care, at run-time, of resolving the conflicts in concurrent executions. Intuitively, we want TMs to allow for as much \emph{concurrency} as possible: in the absence of severe data conflicts, transactions should be able to progress in parallel. But what are the inherent costs associated with providing high degrees of concurrency in TMs? This is the central question of the thesis.
Queueing Analysis of Unicast IPTV With User Mobility and Adaptive Modulation and Coding in Wireless Cellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

Unicast IPTV services that can support live TV, video-on-demand (VoD), video conferencing, and online gaming applications over broadband wireless cellular networks have been becoming popular in recent years. However, video streaming services significantly impact the performance of wireless cellular networks because they are bandwidth hogs. To maintain the system performance, effective admission control and resource allocation mechanisms based on an accurate mathematical analysis are required. On the other hand, the quality of a wireless link usually changes with time due to the user mobility or time-varying channel characteristics. To counteract such time-varying channels and improve the spectral efficiency, adaptive modulation and coding (AMC) scheme can be adopted in offering unicast IPTV services for mobile users. In this paper, closed-form solutions for the bandwidth usage, blocking rate, and dropping rate of unicast IPTV services over wireless cellular networks were derived based on the novel queueing model that considers both user mobility and AMC. Simulations were also conducted to validate the accuracy of analytical results. Numerical results demonstrate that the presented analytical results are accurate. Based on the accurate closed-form solutions, network providers can implement precise admission control and resource allocation for their networks to enhance the system performance.
A Hierarchical Key Management Scheme for Wireless Sensor Networks Based on Identity-based Encryption
Venue: arXiv cs.CR 2015
Year: 2015

Limited resources (such as energy, computing power, storage, and so on) make it impractical for wireless sensor networks (WSNs) to deploy traditional security schemes. In this paper, a hierarchical key management scheme is proposed on the basis of identity-based encryption (IBE).This proposed scheme not only converts the distributed flat architecture of the WSNs to a hierarchical architecture for better network management but also ensures the independence and security of the sub-networks. This paper firstly reviews the identity-based encryption, particularly, the Boneh-Franklin algorithm. Then a novel hierarchical key management scheme based on the basic Boneh-Franklin and Diffie-Hellman (DH) algorithms is proposed. At last, the security and efficiency of our scheme is discussed by comparing with other identity-based schemes for flat architecture of WSNs.
On Intra Prediction for Screen Content Video Coding
Venue: arXiv cs.GR 2015
Year: 2015

Screen content coding (SCC) is becoming increasingly important in various applications, such as desktop sharing, video conferencing, and remote education. When compared to natural camera- captured content, screen content has different characteristics, in particular sharper edges. In this paper, we propose a novel intra prediction scheme for screen content video. In the proposed scheme, bilinear interpolation in angular intra prediction in HEVC is selectively replaced by nearest-neighbor intra prediction to preserve the sharp edges in screen content video. We present three different variants of the proposed nearest neighbor prediction algorithm: two implicit methods where both the encoder, and the decoder derive whether to perform nearest neighbor prediction or not based on either (a) the sum of the absolute difference, or (b) the difference between the boundary pixels from which prediction is performed; and another variant where Rate-Distortion-Optimization (RDO) search is performed at the encoder to decide whether or not to use the nearest neighbor interpolation, and explicitly signaled to the decoder. We also discuss the various underlying trade-offs in terms of the complexity of the three variants. All the three proposed variants provide significant gains over HEVC, and simulation results show that average gains of 3.3% BD-bitrate in Intra-frame coding are achieved by the RDO variant for screen content video. To the best of our knowledge, this is the first paper that 1) points out current HEVC intra prediction scheme with bilinear interpolation does not work efficiently for screen content video and 2) uses different filters adaptively in the HEVC intra prediction interpolation.
One Cyclic Codes over $\mathbb{F}_{p^k} + v\mathbb{F}_{p^k} + v^2\mathbb{F}_{p^k} + ... + v^r\mathbb{F}_{p^k}$
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate cyclic code over the ring $\mathbb{F}_{p^k} + v\mathbb{F}_{p^k} + v^2\mathbb{F}_{p^k} + ... + v^r\mathbb{F}_{p^k}$, where $v^{r+1}=v$, $p$ a prime number, $r>1$ and $\gcd(r,p)=1$, we prove as generalisation of P. Solé et al. in 2015 that these codes are principally generated, give generator polynomial and idempotent depending on idempotents over this ring as response to an open problem related by J. QIAN et al. in 2005. we also give a gray map and proprieties of the related dual code.
Joint Investment and Operation of Microgrid
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a theoretical framework for the joint optimization of investment and operation of a microgrid, taking the impact of energy storage, renewable energy integration, and demand response into consideration. We first study the renewable energy generations in Hong kong, and identify the potential benefit of mixed deployment of solar and wind energy generations. Then we model the joint investment and operation as a two-period stochastic programming program. In period-1, the microgrid operator makes the optimal investment decisions on the capacities of solar power generation, wind power generation, and energy storage. In period-2, the operator coordinates the power supply and demand in the microgrid to minimize the operating cost. We design a decentralized algorithm for computing the optimal pricing and power consumption in period-2, based on which we solve the optimal investment problem in period-1. We also study the impact of prediction error of renewable energy generation on the portfolio investment using robust optimization framework. Using realistic meteorological data obtained from the Hong Kong observatory, we numerically characterize the optimal portfolio investment decisions, optimal day-ahead pricing and power scheduling, and demonstrate the advantage of using mixed renewable energy and demand response in terms of reducing investment cost.
Depth, balancing, and limits of the Elo model
Venue: arXiv cs.GT 2015
Year: 2015

-Much work has been devoted to the computational complexity of games. However, they are not necessarily relevant for estimating the complexity in human terms. Therefore, human-centered measures have been proposed, e.g. the depth. This paper discusses the depth of various games, extends it to a continuous measure. We provide new depth results and present tool (given-first-move, pie rule, size extension) for increasing it. We also use these measures for analyzing games and opening moves in Y, NoGo, Killall Go, and the effect of pie rules.
Introducing SKYSET - a Quintuple Approach for Improving Instructions
Venue: arXiv cs.CL 2015
Year: 2015

A new approach called SKYSET (Synthetic Knowledge Yield Social Entities Translation) is proposed to validate completeness and to reduce ambiguity from written instructional documentation. SKYSET utilizes a quintuple set of standardized categories, which differs from traditional approaches that typically use triples. The SKYSET System defines the categories required to form a standard template for representing information that is portable across different domains. It provides a standardized framework that enables sentences from written instructions to be translated into sets of category typed entities on a table or database. The SKYSET entities contain conceptual units or phrases that represent information from the original source documentation. SKYSET enables information concatenation where multiple documents from different domains can be translated and combined into a single common filterable and searchable table of entities.
Pooling the Convolutional Layers in Deep ConvNets for Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Deep ConvNets have shown its good performance in image classification tasks. However it still remains as a problem in deep video representation for action recognition. The problem comes from two aspects: on one hand, current video ConvNets are relatively shallow compared with image ConvNets, which limits its capability of capturing the complex video action information; on the other hand, temporal information of videos is not properly utilized to pool and encode the video sequences. Towards these issues, in this paper, we utilize two state-of-the-art ConvNets, i.e., the very deep spatial net (VGGNet) and the temporal net from Two-Stream ConvNets, for action representation. The convolutional layers and the proposed new layer, called frame-diff layer, are extracted and pooled with two temporal pooling strategy: Trajectory pooling and line pooling. The pooled local descriptors are then encoded with VLAD to form the video representations. In order to verify the effectiveness of the proposed framework, we conduct experiments on UCF101 and HMDB51 datasets. It achieves the accuracy of 93.78\% on UCF101 which is the state-of-the-art and the accuracy of 65.62\% on HMDB51 which is comparable to the state-of-the-art.
Accelerating Adaptive IDW Interpolation Algorithm on a Single GPU
Venue: arXiv cs.DC 2015
Year: 2015

This paper focuses on the design and implementing of GPU-accelerated Adaptive Inverse Distance Weighting (AIDW) interpolation algorithm. The AIDW is an improved version of the standard IDW, which can adaptively determine the power parameter according to the spatial points distribution pattern and achieve more accurate predictions than those by IDW. In this paper, we first present two versions of the GPU accelerated AIDW, the naive version without profiting from shared memory and the tiled version taking advantage of shared memory. We also implement the naive version and the tiled version using the data layouts, Structure of Arrays (AoS) and Array of aligned Structures (AoaS), on single and double precision. We then evaluate the performance of the GPU-accelerated AIDW by comparing it with its original CPU version. Experimental results show that: on single precision the naive version and the tiled version can achieve the speedups of approximately 270 and 400, respectively. In addition, on single precision the implementations using the layout SoA are always slightly faster than those using layout AoaS. However, on double precision, the speedup is only about 8; and we have also observed that: (1) there are no performance gains obtained from the tiled version against the naive version; and (2) the use of SoA and AoaS does not lead to significant differences in computational efficiency.
Iterative Joint Beamforming Training with Constant-Amplitude Phased Arrays in Millimeter-Wave Communication
Venue: arXiv cs.IT 2015
Year: 2015

In millimeter-wave communications (MMWC), in order to compensate for high propagation attenuation, phased arrays are favored to achieve array gain by beamforming, where transmitting and receiving antenna arrays need to be jointly trained to obtain appropriate antenna weight vectors (AWVs). Since the amplitude of each element of the AWV is usually constraint constant to simplify the design of phased arrays in MMWC, the existing singular vector based beamforming training scheme cannot be used for such devices. Thus, in this letter, a steering vector based iterative beamforming training scheme, which exploits the directional feature of MMWC channels, is proposed for devices with constant-amplitude phased arrays. Performance evaluations show that the proposed scheme achieves a fast convergence rate as well as a near optimal array gain.
Quorum-based Localized Scheme for Duty Cycling in Asynchronous Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Many TDMA- and CSMA-based protocols try to obtain fair channel access and to increase channel utilization. It is still challenging and crucial in Wireless Sensor Networks (WSNs), especially when the time synchronization cannot be well guaranteed and consumes much extra energy. This paper presents a localized and ondemand scheme ADC to adaptively adjust duty cycle based on quorum systems. ADC takes advantages of TDMA and CSMA and guarantees that (1) each node can fairly access channel based on its demand, (2) channel utilization can be increased by reducing competition for channel access among neighboring nodes, (3) every node has at least one rendezvous active time slot with each of its neighboring nodes even under asynchronization. The latency bound of data aggregation is analyzed under ADC to show that ADC can bound the latency under both synchronization and asynchronization. We conduct extensive experiments in TinyOS on a real test-bed with TelosB nodes to evaluate the performance of ADC. Comparing with B-MAC, ADC substantially reduces the contention for channel access and energy consumption, and improves network throughput.
A Micro-foundation of Social Capital in Evolving Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

A social network confers benefits and advantages on individuals (and on groups), the literature refers to these advantages as social capital. This paper presents a micro-founded mathematical model of the evolution of a social network and of the social capital of individuals within the network. The evolution of the network is influenced by the extent to which individuals are homophilic, structurally opportunistic, socially gregarious and by the distribution of types in the society. In the analysis, we identify different kinds of social capital: bonding capital, popularity capital, and bridging capital. Bonding capital is created by forming a circle of connections, homophily increases bonding capital because it makes this circle of connections more homogeneous. Popularity capital leads to preferential attachment: individuals who become popular tend to become more popular because others are more likely to link to them. Homophily creates asymmetries in the levels of popularity attained by different social groups, more gregarious types of agents are more likely to become popular. However, in homophilic societies, individuals who belong to less gregarious, less opportunistic, or major types are likely to be more central in the network and thus acquire a bridging capital.
Hardness and Approximation for Network Flow Interdiction
Venue: arXiv cs.DS 2015
Year: 2015

In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem despite decades of interest in it. We present the first approximation hardness, showing that Network Flow Interdiction and several of its variants cannot be much easier to approximate than Densest k-Subgraph. In particular, any $n^{o(1)}$-approximation algorithm for Network Flow Interdiction would imply an $n^{o(1)}$-approximation algorithm for Densest k-Subgraph. We complement this hardness results with the first approximation algorithm for Network Flow Interdiction, which has approximation ratio 2(n-1). We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives the first approximation hardness and algorithm for that problem, as well.
Properties of Relationships among objects in Object-Oriented Software Design
Venue: arXiv cs.SE 2015
Year: 2015

One of the modern paradigms to develop a system is object oriented analysis and design. In this paradigm, there are several objects and each object plays some specific roles. After identifying objects, the various relationships among objects must be identified. This paper makes a literature review over relationships among objects. Mainly, the relationships are three basic types, including generalization/specialization, aggregation and association.This paper presents five taxonomies for properties of the relationships. The first taxonomy is based on temporal view. The second taxonomy is based on structure and the third one relies on behavioral. The fourth taxonomy is specified on mathematical view and fifth one related to the interface. Additionally, the properties of the relationships are evaluated in a case study and several recommendations are proposed.