OpenRaiser/Intern-Atlas huggingface dataset:
Mobile Beamforming & Spatially Controlled Relay Communications
Venue: arXiv cs.SY 2016
Year: 2016

We consider stochastic motion planning in single-source single-destination robotic relay networks, under a cooperative beamforming framework. Assuming that the communication medium constitutes a spatiotemporal stochastic field, we propose a 2-stage stochastic programming formulation of the problem of specifying the positions of the relays, such that the expected reciprocal of their total beamforming power is maximized. Stochastic decision making is made on the basis of random causal CSI. Recognizing the intractability of the original problem, we propose a lower bound relaxation, resulting to a nontrivial optimization problem with respect to the relay locations, which is equivalent to a small set of simple, tractable subproblems. Our formulation results in spatial controllers with a predictive character; at each time slot, the new relay positions should be such that the expected power reciprocal at the next time slot is maximized. Quite interestingly, the optimal control policy to the relaxed problem is purely selective; under a certain sense, only the best relay should move.
Combining the Best of Convolutional Layers and Recurrent Layers: A Hybrid Network for Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

State-of-the-art results of semantic segmentation are established by Fully Convolutional neural Networks (FCNs). FCNs rely on cascaded convolutional and pooling layers to gradually enlarge the receptive fields of neurons, resulting in an indirect way of modeling the distant contextual dependence. In this work, we advocate the use of spatially recurrent layers (i.e. ReNet layers) which directly capture global contexts and lead to improved feature representations. We demonstrate the effectiveness of ReNet layers by building a Naive deep ReNet (N-ReNet), which achieves competitive performance on Stanford Background dataset. Furthermore, we integrate ReNet layers with FCNs, and develop a novel Hybrid deep ReNet (H-ReNet). It enjoys a few remarkable properties, including full-image receptive fields, end-to-end training, and efficient network execution. On the PASCAL VOC 2012 benchmark, the H-ReNet improves the results of state-of-the-art approaches Piecewise, CRFasRNN and DeepParsing by 3.6%, 2.3% and 0.2%, respectively, and achieves the highest IoUs for 13 out of the 20 object classes.
Effects of Sensemaking Translucence on Distributed Collaborative Analysis
Venue: arXiv cs.HC 2016
Year: 2016

Collaborative sensemaking requires that analysts share their information and insights with each other, but this process of sharing runs the risks of prematurely focusing the investigation on specific suspects. To address this tension, we propose and test an interface for collaborative crime analysis that aims to make analysts more aware of their sensemaking processes. We compare our sensemaking translucence interface to a standard interface without special sensemaking features in a controlled laboratory study. We found that the sensemaking translucence interface significantly improved clue finding and crime solving performance, but that analysts rated the interface lower on subjective measures than the standard interface. We conclude that designing for distributed sensemaking requires balancing task performance vs. user experience and real-time information sharing vs. data accuracy.
Grand challenges in altmetrics: heterogeneity, data quality and dependencies
Venue: arXiv cs.DL 2016
Year: 2016

As uptake among researchers is constantly increasing, social media are finding their way into scholarly communication and, under the umbrella term altmetrics, were introduced to research evaluation. Fueled by technological possibilities and an increasing demand to demonstrate impact beyond the scientific community, altmetrics received great attention as potential democratizers of the scientific reward system and indicators of societal impact. This paper focuses on current challenges of altmetrics. Heterogeneity, data quality and particular dependencies are identified as the three major issues and discussed in detail with a particular emphasis on past developments in bibliometrics. The heterogeneity of altmetrics mirrors the diversity of the types of underlying acts, most of which take place on social media platforms. This heterogeneity has made it difficult to establish a common definition or conceptual framework. Data quality issues become apparent in the lack of accuracy, consistency and replicability of various altmetrics, which is largely affected by the dynamic nature of social media events. It is further highlighted that altmetrics are shaped by technical possibilities and depend particularly on the availability of APIs and DOIs, are strongly dependent on data providers and aggregators, and potentially influenced by technical affordances of underlying platforms.
An Integrated Spectrum and Information Market for Green Cognitive Communications
Venue: arXiv cs.GT 2016
Year: 2016

A database-assisted TV white space network can achieve the goal of green cognitive communication by effectively reducing the energy consumption in cognitive communications. The success of such a novel network relies on a proper business model that provides incentives for all parties involved. In this paper, we propose an integrated spectrum and information market for a database-assisted TV white space network, where the geo-location database serves as both the spectrum market platform and the information market platform. We study the interactions among the database, the spectrum licensee, and unlicensed users by modelling the system as a three-stage sequential decision process. In Stage I, the database and the licensee negotiate regarding the commission for the licensee to use the spectrum market platform. In Stage II, the database and the licensee compete for selling information or channels to unlicensed users. In Stage III, unlicensed users determine whether they should buy exclusive usage right of licensed channels from the licensee or information regarding unlicensed channels from the database. Analyzing such a three-stage model is challenging due to the co-existence of both positive and negative network externalities in the information market. Despite of this, we are able to characterize how the network externalities affect the equilibrium behaviors of all parties involved. We analytically show that in this integrated market, the licensee can never get a market share more than half. Our numerical results further show that the proposed integrated market can improve the network profit up to 87%, compared with a pure information market.
Benchmarking Concurrent Priority Queues: Performance of k-LSM and Related Data Structures
Venue: arXiv cs.DS 2016
Year: 2016

A number of concurrent, relaxed priority queues have recently been proposed and implemented. Results are commonly reported for a throughput benchmark that uses a uniform distribution of keys drawn from a large integer range, and mostly for single systems. We have conducted more extensive benchmarking of three recent, relaxed priority queues on four different types of systems with different key ranges and distributions. While we can show superior throughput and scalability for our own k-LSM priority queue for the uniform key distribution, the picture changes drastically for other distributions, both with respect to achieved throughput and relative merit of the priority queues. The throughput benchmark alone is thus not sufficient to characterize the performance of concurrent priority queues. Our benchmark code and k-LSM priority queue are publicly available to foster future comparison.
Are the discretised lognormal and hooked power law distributions plausible for citation data?
Venue: arXiv cs.DL 2016
Year: 2016

There is no agreement over which statistical distribution is most appropriate for modelling citation count data. This is important because if one distribution is accepted then the relative merits of different citation-based indicators, such as percentiles, arithmetic means and geometric means, can be more fully assessed. In response, this article investigates the plausibility of the discretised lognormal and hooked power law distributions for modelling the full range of citation counts, with an offset of 1. The citation counts from 23 Scopus subcategories were fitted to hooked power law and discretised lognormal distributions but both distributions failed a Kolmogorov-Smirnov goodness of fit test in over three quarters of cases. The discretised lognormal distribution also seems to have the wrong shape for citation distributions, with too few zeros and not enough medium values for all subjects. The cause of poor fits could be the impurity of the subject subcategories or the presence of interdisciplinary research. Although it is possible to test for subject subcategory purity indirectly through a goodness of fit test in theory with large enough sample sizes, it is probably not possible in practice. Hence it seems difficult to get conclusive evidence about the theoretically most appropriate statistical distribution.
RankSynd a PRNG Based on Rank Metric
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we consider a pseudo-random generator based on the difficulty of the syndrome decoding problem for rank metric codes. We also study the resistance of this problem against a quantum computer. Our results show that with rank metric it is possible to obtain fast PRNG with small public data, without considering additional structure for public matrices like quasi-cyclicity for Hamming distance.
Accelerating Data Regeneration for Distributed Storage Systems with Heterogeneous Link Capacities
Venue: arXiv cs.DC 2016
Year: 2016

Distributed storage systems provide large-scale reliable data storage services by spreading redundancy across a large group of storage nodes. In such a large system, node failures take place on a regular basis. When a storage node breaks down, a replacement node is expected to regenerate the redundant data as soon as possible in order to maintain the same level of redundancy. Previous results have been mainly focused on the minimization of network traffic in regeneration. However, in practical networks, where link capacities vary in a wide range, minimizing network traffic does not always yield the minimum regeneration time. In this paper, we investigate two approaches to the problem of minimizing regeneration time in networks with heterogeneous link capacities. The first approach is to download different amounts of repair data from the helping nodes according to the link capacities. The second approach generalizes the conventional star-structured regeneration topology to tree-structured topologies so that we can utilize the links between helping nodes with bypassing low-capacity links. Simulation results show that the flexible tree-structured regeneration scheme that combines the advantages of both approaches can achieve a substantial reduction in the regeneration time.
Fast Low-Complexity Decoders for Low-Rate Polar Codes
Venue: arXiv cs.IT 2016
Year: 2016

Polar codes are capacity-achieving error-correcting codes with an explicit construction that can be decoded with low-complexity algorithms. In this work, we show how the state-of-the-art low-complexity decoding algorithm can be improved to better accommodate low-rate codes. More constituent codes are recognized in the updated algorithm and dedicated hardware is added to efficiently decode these new constituent codes. We also alter the polar code construction to further decrease the latency and increase the throughput with little to no noticeable effect on error-correction performance. Rate-flexible decoders for polar codes of length 1024 and 2048 are implemented on FPGA. Over the previous work, they are shown to have from 22% to 28% lower latency and 26% to 34% greater throughput when decoding low-rate codes. On 65 nm ASIC CMOS technology, the proposed decoder for a (1024, 512) polar code is shown to compare favorably against the state-of-the-art ASIC decoders. With a clock frequency of 400 MHz and a supply voltage of 0.8 V, it has a latency of 0.41 $μ$s and an area efficiency of 1.8 Gbps/mm$^2$ for an energy efficiency of 77 pJ/info. bit. At 600 MHz with a supply of 1 V, the latency is reduced to 0.27 $μ$s and the area efficiency increased to 2.7 Gbps/mm$^2$ at 115 pJ/info. bit.
New Sufficient Conditions for Multiple-Access Channel with Correlated Sources
Venue: arXiv cs.IT 2016
Year: 2016

The problem of three-user Multiple-Access Channel (MAC) with correlated sources is investigated. An extension to the Cover-El Gamal-Salehi (CES) scheme is introduced. We use a combination of this scheme with linear codes and propose a new coding strategy. We derive new sufficient conditions to transmit correlated sources reliably. We consider an example of three-user MAC with binary inputs. Using this example, we show strict improvements over the CES scheme.
Stability and Control of Ad Hoc DC Microgrids
Venue: arXiv cs.SY 2016
Year: 2016

Ad hoc electrical networks are formed by connecting power sources and loads without pre-determining the network topology. These systems are well-suited to addressing the lack of electricity in rural areas because they can be assembled and modified by non-expert users without central oversight. There are two core aspects to ad hoc system design: 1) designing source and load units such that the microgrid formed from the arbitrary interconnection of many units is always stable and 2) developing control strategies to autonomously manage the microgrid (i.e., perform power dispatch and voltage regulation) in a decentralized manner and under large uncertainty. To address these challenges we apply a number of nonlinear control techniques---including Brayton-Moser potential theory and primal-dual dynamics---to obtain conditions under which an ad hoc dc microgrid will have a suitable and asymptotically stable equilibrium point. Further, we propose a new decentralized control scheme that coordinates many sources to achieve a specified power dispatch from each. A simulated comparison to previous research is included.
Hardware Acceleration for Boolean Satisfiability Solver by Applying Belief Propagation Algorithm
Venue: arXiv cs.AI 2016
Year: 2016

Boolean satisfiability (SAT) has an extensive application domain in computer science, especially in electronic design automation applications. Circuit synthesis, optimization, and verification problems can be solved by transforming original problems to SAT problems. However, the SAT problem is known as NP-complete, which means there is no efficient method to solve it. Therefore, an efficient SAT solver to enhance the performance is always desired. We propose a hardware acceleration method for SAT problems. By surveying the properties of SAT problems and the decoding of low-density parity-check (LDPC) codes, a special class of error-correcting codes, we discover that both of them are constraint satisfaction problems. The belief propagation algorithm has been successfully applied to the decoding of LDPC, and the corresponding decoder hardware designs are extensively studied. Therefore, we proposed a belief propagation based algorithm to solve SAT problems. With this algorithm, the SAT solver can be accelerated by hardware. A software simulator is implemented to verify the proposed algorithm and the performance improvement is estimated. Our experiment results show that time complexity does not increase with the size of SAT problems and the proposed method can achieve at least 30x speedup compared to MiniSat.
GeoReach: An Efficient Approach for Evaluating Graph Reachability Queries with Spatial Range Predicates
Venue: arXiv cs.DB 2016
Year: 2016

Graphs are widely used to model data in many application domains. Thanks to the wide spread use of GPS-enabled devices, many applications assign a spatial attribute to graph vertices (e.g., geo-tagged social media). Users may issue a Reachability Query with Spatial Range Predicate (abbr. RangeReach). RangeReach finds whether an input vertex can reach any spatial vertex that lies within an input spatial range. An example of a RangeReach query is: Given a social graph, find whether Alice can reach any of the venues located within the geographical area of Arizona State University. The paper proposes GeoReach an approach that adds spatial data awareness to a graph database management system (GDBMS). GeoReach allows efficient execution of RangeReach queries, yet without compromising a lot on the overall system scalability (measured in terms of storage size and initialization/maintenance time). To achieve that, GeoReach is equipped with a light-weight data structure, namely SPA-Graph, that augments the underlying graph data with spatial indexing directories. When a RangeReach query is issued, the system employs a pruned-graph traversal approach. Experiments based on real system implementation inside Neo4j proves that GEOREACH exhibits up to two orders of magnitude better query response time and up to four times less storage than the state-of-the-art spatial and reachability indexing approaches.
Conferencing in Wyner's Asymmetric Interference Network: Effect of Number of Rounds
Venue: arXiv cs.IT 2016
Year: 2016

Our goal is to study the effect of the number of conferencing rounds on the capacity of large interference networks. We do this at hand of the per-user multiplexing gain (MG) of Wyner's soft-handoff model with dedicated conferencing links between neighbouring transmitters and receivers. We present upper and lower bounds on the per-user MG of this network, which depend on the capacities of the transmitter- and receiver-conferencing links and on the number of allowed conferencing rounds. The bounds are tight when: the prelogs of the conferencing links are small or high; there is only transmitter conferencing or only receiver conferencing; or some symmetry conditions between transmitter-conferencing and receiver-conferencing hold. We also determine the per-user MG of the network when the number of conferencing rounds is unlimited. Our results show that for small conferencing prelogs around 1/6, a single conferencing round suffices to attain the maximum per-user MG when the number of conferencing rounds is unconstrained. In contrast, when the prelogs are large, then every additional conferencing round increases the maximum per-user MG.
Norm-1 Regularized Consensus-based ADMM for Imaging with a Compressive Antenna
Venue: arXiv cs.OH 2016
Year: 2016

This paper presents a novel norm-one-regularized, consensus-based imaging algorithm, based on the Alternating Direction Method of Multipliers (ADMM). This algorithm is capable of imaging composite dielectric and metallic targets by using limited amount of data. The distributed capabilities of the ADMM accelerates the convergence of the imaging. Recently, a Compressive Reflector Antenna (CRA) has been proposed as a way to provide high-sensing-capacity with a minimum cost and complexity in the hardware architecture. The ADMM algorithm applied to the imaging capabilities of the Compressive Antenna (CA) outperforms current state of the art iterative reconstruction algorithms, such as Nesterov-based methods, in terms of computational cost; and it ultimately enables the use of a CA in quasi-real-time, compressive sensing imaging applications.
A Soft Electronics-Free robot
Venue: arXiv cs.RO 2016
Year: 2016

Biomimetic entirely soft robots with animal-like behavior and integrated artificial nervous systems will open up totally new perspectives and applications. However, until now all presented studies on soft robots were limited to partly soft designs, since all designs at least needed conventional, stiff, electronics, to sense, process signals and activate actuators. We present the first soft robot with integrated artificial nervous system entirely made of dielectric elastomers - and without any conventional stiff electronic parts. Supplied with only one external DC voltage, the robot autonomously generates all signals necessary to drive its actuators, and translates an in-plane electromechanical oscillation into a crawling locomotion movement. Thereby, all functional parts are made of polymer materials and carbon. Besides the basic design of the world's first entirely soft robot we present prospects to control general behavior of such robots.
Streaming Algorithms for News and Scientific Literature Recommendation: Submodular Maximization with a d-Knapsack Constraint
Venue: arXiv cs.LG 2016
Year: 2016

Submodular maximization problems belong to the family of combinatorial optimization problems and enjoy wide applications. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a $d$-knapsack constraint, for which we propose a streaming algorithm that achieves a $\left(\frac{1}{1+2d}-ε\right)$-approximation of the optimal value, while it only needs one single pass through the dataset without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via two applications: news recommendation and scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.
Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication
Venue: arXiv cs.DC 2016
Year: 2016

We propose a fine-grained hypergraph model for sparse matrix-matrix multiplication (SpGEMM), a key computational kernel in scientific computing and data analysis whose performance is often communication bound. This model correctly describes both the interprocessor communication volume along a critical path in a parallel computation and also the volume of data moving through the memory hierarchy in a sequential computation. We show that identifying a communication-optimal algorithm for particular input matrices is equivalent to solving a hypergraph partitioning problem. Our approach is sparsity dependent, meaning that we seek the best algorithm for the given input matrices. In addition to our (3D) fine-grained model, we also propose coarse-grained 1D and 2D models that correspond to simpler SpGEMM algorithms. We explore the relations between our models theoretically, and we study their performance experimentally in the context of three applications that use SpGEMM as a key computation. For each application, we find that at least one coarse-grained model is as communication efficient as the fine-grained model. We also observe that different applications have affinities for different algorithms. Our results demonstrate that hypergraphs are an accurate model for reasoning about the communication costs of SpGEMM as well as a practical tool for exploring the SpGEMM algorithm design space.
An Implementation and Analysis of a Kernel Network Stack in Go with the CSP Style
Venue: arXiv cs.OS 2016
Year: 2016

Modern operating system kernels are written in lower-level languages such as C. Although the low-level functionalities of C are often useful within kernels, they also give rise to several classes of bugs. Kernels written in higher level languages avoid many of these potential problems, at the possible cost of decreased performance. This research evaluates the advantages and disadvantages of a kernel written in a higher level language. To do this, the network stack subsystem of the kernel was implemented in Go with the Communicating Sequential Processes (CSP) style. Go is a high-level programming language that supports the CSP style, which recommends splitting large tasks into several smaller ones running in independent "threads". Modules for the major networking protocols, including Ethernet, ARP, IPv4, ICMP, UDP, and TCP, were implemented. In this study, the implemented Go network stack, called GoNet, was compared to a representative network stack written in C. The GoNet code is more readable and generally performs better than that of its C stack counterparts. From this, it can be concluded that Go with CSP style is a viable alternative to C for the language of kernel implementations.