OpenRaiser/Intern-Atlas huggingface dataset:
A Method for Group Extraction and Analysis in Multilayer Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

The main subject studied in this dissertation is a multi-layered social network (MSN) and its analysis. One of the crucial problems in multi-layered social network analysis is community extraction. To cope with this problem the CLECC measure (Cross Layered Edge Clustering Coefficient) was proposed in the thesis. It is an edge measure which expresses how much the neighbors of two given users are similar each other. Based on this measure the CLECC algorithm for community extraction in the multi-layered social networks was designed. The algorithm was tested on the real single-layered social networks (SSN) and multi-layered social networks (MSN), as well as on benchmark networks from GN Benchmark (SSN), LFR Benchmark (SSN) and mLFR Benchmark (MSN) a special extension of LFR Benchmark, designed as a part of this thesis, which is able to produce multi-layered benchmark networks. The second research problem considered in the thesis was group evolution discovery. Studies on this problem have led to the development of the inclusion measure and the Group Evolution Discovery (GED) method, which is designed to identify events between two groups in successive time frames in the social network. The method was tested on a real social network and compared with two well-known algorithms regarding accuracy, execution time, flexibility and ease of implementation. Finally, a new approach to prediction of group evolution in the social network was developed. The new approach involves usage of the outputs of the GED method. It is shown, that using even a simple sequence, which consists of several preceding groups sizes and events, as an input for the classifier, the learned model can produce very good results also for simple classifiers.
An Efficient Algorithm for the Piecewise-Smooth Model with Approximately Explicit Solutions
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents an efficient approach to image segmentation that approximates the piecewise-smooth (PS) functional in [12] with explicit solutions. By rendering some rational constraints on the initial conditions and the final solutions of the PS functional, we propose two novel formulations which can be approximated to be the explicit solutions of the evolution partial differential equations (PDEs) of the PS model, in which only one PDE needs to be solved efficiently. Furthermore, an energy term that regularizes the level set function to be a signed distance function is incorporated into our evolution formulation, and the time-consuming re-initialization is avoided. Experiments on synthetic and real images show that our method is more efficient than both the PS model and the local binary fitting (LBF) model [4], while having similar segmentation accuracy as the LBF model.
Sorting Data on Ultra-Large Scale with RADULS. New Incarnation of Radix Sort
Venue: arXiv cs.DS 2016
Year: 2016

The paper introduces RADULS, a new parallel sorter based on radix sort algorithm, intended to organize ultra-large data sets efficiently. For example 4G 16-byte records can be sorted with 16 threads in less than 15 seconds on Intel Xeon-based workstation. The implementation of RADULS is not only highly optimized to gain such an excellent performance, but also parallelized in a cache friendly manner to make the most of modern multicore architectures. Besides, our parallel scheduler launches a few different procedures at runtime, according to the current parameters of the execution, for proper workload management. All experiments show RADULS to be superior to competing algorithms.
Nonlinear 1-Bit Precoding for Massive MU-MIMO with Higher-Order Modulation
Venue: arXiv cs.IT 2016
Year: 2016

Massive multi-user (MU) multiple-input multiple- output (MIMO) is widely believed to be a core technology for the upcoming fifth-generation (5G) wireless communication standards. The use of low-precision digital-to-analog converters (DACs) in MU-MIMO base stations is of interest because it reduces the power consumption, system costs, and raw baseband data rates. In this paper, we develop novel algorithms for downlink precoding in massive MU-MIMO systems with 1-bit DACs that support higher-order modulation schemes such as 8-PSK or 16-QAM. Specifically, we present low-complexity nonlinear precoding algorithms that achieve low error rates when combined with blind or training-based channel-estimation algorithms at the user equipment. These results are in stark contrast to linear-quantized precoding algorithms, which suffer from a high error floor if used with high-order modulation schemes and 1-bit DACs.
Effects of online group exercises for older adults on physical, psychological and social wellbeing: a pilot trial
Venue: arXiv cs.CY 2016
Year: 2016

Background. There are many factors that can make of group exercises a challenging setting for older adults. A major one in the elderly population is the difference in the level of skills. In this paper we report on the physical, psychological and social wellbeing outcomes of a novel virtual gym that enables online group-exercises in older adults with different levels of skills. Methods. A total of 37 older adults (65-87 years old) followed a personalized exercise program based on the OTAGO program for fall prevention, for a period of eight weeks. Participants could join online group exercises using a tablet-based application. Participants were assigned either to a Control group (individual training) or Social group (online group-exercising). Pre- and post- measurements were taken to analyze the physical, psychological and social wellbeing outcomes. The study received ethical approval from the CREATE-NET Ethics Committee on ICT Research Involving Human Beings (Application N. 2014-001). Results. There were improvements in both the Social and Control groups in terms of physical outcomes. Interestingly though, while in the Control group fitter individuals tended to adhere more to the training, this was not the case for the Social group, where the initial level had no effect on adherence. For psychological and social wellbeing outcomes there were improvements on both groups, regardless of the application used. Conclusion. Group exercising in a virtual gym can be effective in motivating and enabling individuals who are less fit to train as much as fitter individuals. This not only indicates the feasibility of training together despite differences in physical skills but also suggests that online exercise can reduce the effect of skills on adherence in a social context. Longer term interventions with more participants are instead recommended to assess impacts on wellbeing.
Discovering Conversational Dependencies between Messages in Dialogs
Venue: arXiv cs.CL 2016
Year: 2016

We investigate the task of inferring conversational dependencies between messages in one-on-one online chat, which has become one of the most popular forms of customer service. We propose a novel probabilistic classifier that leverages conversational, lexical and semantic information. The approach is evaluated empirically on a set of customer service chat logs from a Chinese e-commerce website. It outperforms heuristic baselines.
Dynamic Network Probes: A Stepping Stone to Omni Network Visibility
Venue: arXiv cs.NI 2016
Year: 2016

Effective SDN control relies on the network data collecting capability as well as the quality and timeliness of the data. As open programmable data plane is becoming a reality, we further enhance it with the support of runtime interactive programming in order to cope with application dynamics, optimize data plane resource allocation, and reduce control-plane processing pressure. Based on the latest technologies, we propose the Dynamic Network Probes (DNP) as a means to support real-time and on-demand network visibility. DNPs serve as an important building block of an integrated networking data analytics platform which involves the network data plane as an active component for in-network computing. In this paper, we show the types of DNPs and their role in the big picture. We have implemented an NP-based hardware prototype to demonstrate the feasibility and efficiency of DNPs. We lay out the research challenges and our future work to realize the omni network visibility based on DNPs.
Moore's Law in CLEAR Light
Venue: arXiv cs.ET 2016
Year: 2016

The inability of Moore's Law and other figure-of-merits (FOMs) to accurately explain the technology development of the semiconductor industry demands a holistic merit to guide the industry. Here we introduce a FOM termed CLEAR that accurately postdicts technology developments since the 1940's until today, and predicts photonics as a logical extension to keep-up the pace of information-handling machines. We show that CLEAR (Capability-to-Latency-Energy-Amount-Resistance) is multi-hierarchical applying to the device, interconnect, and system level. Being a holistic FOM, we show that empirical trends such as Moore's Law and the Makimoto's wave are special cases of the universal CLEAR merit. Looking ahead, photonic board- and chip-level technologies are able to continue the observed doubling rate of the CLEAR value every 12 months, while electronic technologies are unable to keep pace.
On Fault-Tolerant Design of Exclusive-OR Gates in QCA
Venue: arXiv cs.ET 2016
Year: 2016

Design paradigms of logic circuits with Quantum-dot Cellular Automata (QCA) have been extensively studied in the recent past. Unfortunately, due to the lack of mature fabrication support, QCA-based circuits often suffer from various types of manufacturing defects and variations, and therefore, are unreliable and error-prone. QCA-based Exclusive-OR (XOR) gates are frequently used in the construction of several computing subsystems such as adders, linear feedback shift registers, parity generators and checkers. However, none of the existing designs for QCA XOR gates have considered the issue of ensuring fault-tolerance. Simulation results also show that these designs can hardly tolerate any fault. We investigate the applicability of various existing fault-tolerant schemes such as triple modular redundancy (TMR), NAND multiplexing, and majority multiplexing in the context of practical realization of QCA XOR gate. Our investigations reveal that these techniques incur prohibitively large area and delay and hence, they are unsuitable for practical scenarios. We propose here realistic designs of QCA XOR gates (in terms of area and delay) with significantly high fault-tolerance against all types of cell misplacement defects such as cell omission, cell displacement, cell misalignment and extra/additional cell deposition. Furthermore, the absence of any crossing in the proposed designs facilitates low-cost fabrication of such systems.
Vertex Sparsification in Trees
Venue: arXiv cs.DS 2016
Year: 2016

Given an unweighted tree $T=(V,E)$ with terminals $K \subset V$, we show how to obtain a $2$-quality vertex flow and cut sparsifier $H$ with $V_H = K$. We prove that our result is essentially tight by providing a $2-o(1)$ lower-bound on the quality of any cut sparsifier for stars. In addition we give improved results for quasi-bipartite graphs. First, we show how to obtain a $2$-quality flow sparsifier with $V_H = K$ for such graphs. We then consider the other extreme and construct exact sparsifiers of size $O(2^{k})$, when the input graph is unweighted.
Analyzing the Synergy between Broadcast Polling and Piggybacking in WiMAX Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this work we present a model for analyzing the combined use of broadcast polling and piggybacking in Worldwide Interoperability for Microwave Access (WiMAX) networks. For an accurate analysis of piggybacking, the model focuses on the realistic case of limited up-link bandwidth and non-trivial queueing capability at the subscriber stations. We first model the activity of a subscriber station using a Markov chain and its queue as an M/G/1 system with vacations in order to facilitate the analysis of the piggyback mechanism. We then derive a set of fixed point equations that describe not only the contention process at the network level but also bandwidth allocation to contending and piggybacked requests. Our model uses a minimal set of assumptions and is generic in the sense that it is customizable through a set of parameters. It can also reproduce the system performance in both saturated and non-saturated conditions. After validating our analysis through extensive simulations, we shed light on the aspects of the synergy between broadcast polling and piggybacking and unveil the pros and cons of using the latter.
Measuring Adverse Drug Effects on Multimorbity using Tractable Bayesian Networks
Venue: arXiv cs.AI 2016
Year: 2016

Managing patients with multimorbidity often results in polypharmacy: the prescription of multiple drugs. However, the long-term effects of specific combinations of drugs and diseases are typically unknown. In particular, drugs prescribed for one condition may result in adverse effects for the other. To investigate which types of drugs may affect the further progression of multimorbidity, we query models of diseases and prescriptions that are learned from primary care data. State-of-the-art tractable Bayesian network representations, on which such complex queries can be computed efficiently, are employed for these large medical networks. Our results confirm that prescriptions may lead to unintended negative consequences in further development of multimorbidity in cardiovascular diseases. Moreover, a drug treatment for one disease group may affect diseases of another group.
Low-rank matrix recovery via rank one tight frame measurements
Venue: arXiv cs.IT 2016
Year: 2016

The task of reconstructing a low rank matrix from incomplete linear measurements arises in areas such as machine learning, quantum state tomography and in the phase retrieval problem. In this note, we study the particular setup that the measurements are taken with respect to rank one matrices constructed from the elements of a random tight frame. We consider a convex optimization approach and show both robustness of the reconstruction with respect to noise on the measurements as well as stability with respect to passing to approximately low rank matrices. This is achieved by establishing a version of the null space property of the corresponding measurement map.
An Efficient Algorithm for Monitoring Practical TPTL Specifications
Venue: arXiv cs.LO 2016
Year: 2016

We provide a dynamic programming algorithm for the monitoring of a fragment of Timed Propositional Temporal Logic (TPTL) specifications. This fragment of TPTL, which is more expressive than Metric Temporal Logic, is characterized by independent time variables which enable the elicitation of complex real-time requirements. For this fragment, we provide an efficient polynomial time algorithm for off-line monitoring of finite traces. Finally, we provide experimental results on a prototype implementation of our tool in order to demonstrate the feasibility of using our tool in practical applications.
Optimized Execution of Business Processes on Blockchain
Venue: arXiv cs.SE 2016
Year: 2016

Blockchain technology enables the execution of collaborative business processes involving untrusted parties without requiring a central authority. Specifically, a process model comprising tasks performed by multiple parties can be coordinated via smart contracts operating on the blockchain. The consensus mechanism governing the blockchain thereby guarantees that the process model is followed by each party. However, the cost required for blockchain use is highly dependent on the volume of data recorded and the frequency of data updates by smart contracts. This paper proposes an optimized method for executing business processes on top of commodity blockchain technology. The paper presents a method for compiling a process model into a smart contract that encodes the preconditions for executing each task in the process using a space-optimized data structure. The method is empirically compared to a previously proposed baseline by replaying execution logs, including one from a real-life business process, and measuring resource consumption.
On Higher Order Query Languages which on Relational Databases Collapse to Second Order Logic
Venue: arXiv cs.LO 2016
Year: 2016

In the framework of computable queries in Database Theory, there are many examples of queries to (properties of) relational database instances that can be expressed by simple and elegant third order logic ($\mathrm{TO}$) formulae. In many of those properties the expressive power of $\mathrm{TO}$ is not required, but the equivalent second order logic ($\mathrm{SO}$) formulae can be very complicated or unintuitive. From the point of view of the study of highly expressive query languages, it is then relevant to identify fragments of $\mathrm{TO}$ (and, in general, of higher-order logics of order $\geq 3$) which do have an $\mathrm{SO}$ equivalent formula. In this article we investigate this precise problem as follows. Firstly, we define a general schema of $\exists$TO formulas which consists of existentially quantifying a third-order linear digraph of polynomial length, that is, a sequence of structures that represents a computation, by explicitly stating which operations are the ones which can be involved in the construction of a given structure in the sequence, when applied to the previous one. Then we give a constructive proof of the fact that all $\exists$TO sub formulas of that schema can be translated into an equivalent SO formula. Secondly, aiming to formally characterize the fragment of TO which can be translated to SO, we define a restriction of TO, which we denote TO$^{P}$, for polynomial TO, and we give a constructive proof on the fact that it collapses to SO. We define TO$^{P}$ as the fragment of TO where valuations can assign to TO relation variables only TO relations whose cardinalities are bounded by a polynomial that depends on the quantifier. Moreover, we define a similar restriction for every higher order logic of order $i \geq 4$, which we denote $\mathrm{HO}^{i,P}$, and give a constructive proof of the fact that for all $i \geq 4$, $\mathrm{HO}^{i,P}$ collapses to SO.
Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
Venue: arXiv cs.LG 2016
Year: 2016

We show that the square Hellinger distance between two Bayesian networks on the same directed graph, $G$, is subadditive with respect to the neighborhoods of $G$. Namely, if $P$ and $Q$ are the probability distributions defined by two Bayesian networks on the same DAG, our inequality states that the square Hellinger distance, $H^2(P,Q)$, between $P$ and $Q$ is upper bounded by the sum, $\sum_v H^2(P_{\{v\} \cup Π_v}, Q_{\{v\} \cup Π_v})$, of the square Hellinger distances between the marginals of $P$ and $Q$ on every node $v$ and its parents $Π_v$ in the DAG. Importantly, our bound does not involve the conditionals but the marginals of $P$ and $Q$. We derive a similar inequality for more general Markov Random Fields. As an application of our inequality, we show that distinguishing whether two Bayesian networks $P$ and $Q$ on the same (but potentially unknown) DAG satisfy $P=Q$ vs $d_{\rm TV}(P,Q)>ε$ can be performed from $\tilde{O}(|Σ|^{3/4(d+1)} \cdot n/ε^2)$ samples, where $d$ is the maximum in-degree of the DAG and $Σ$ the domain of each variable of the Bayesian networks. If $P$ and $Q$ are defined on potentially different and potentially unknown trees, the sample complexity becomes $\tilde{O}(|Σ|^{4.5} n/ε^2)$, whose dependence on $n, ε$ is optimal up to logarithmic factors. Lastly, if $P$ and $Q$ are product distributions over $\{0,1\}^n$ and $Q$ is known, the sample complexity becomes $O(\sqrt{n}/ε^2)$, which is optimal up to constant factors.
Arch2030: A Vision of Computer Architecture Research over the Next 15 Years
Venue: arXiv cs.AR 2016
Year: 2016

Application trends, device technologies and the architecture of systems drive progress in information technologies. However, the former engines of such progress - Moore's Law and Dennard Scaling - are rapidly reaching the point of diminishing returns. The time has come for the computing community to boldly confront a new challenge: how to secure a foundational future for information technology's continued progress. The computer architecture community engaged in several visioning exercises over the years. Five years ago, we released a white paper, 21st Century Computer Architecture, which influenced funding programs in both academia and industry. More recently, the IEEE Rebooting Computing Initiative explored the future of computing systems in the architecture, device, and circuit domains. This report stems from an effort to continue this dialogue, reach out to the applications and devices/circuits communities, and understand their trends and vision. We aim to identify opportunities where architecture research can bridge the gap between the application and device domains.
Active Learning for Speech Recognition: the Power of Gradients
Venue: arXiv cs.CL 2016
Year: 2016

In training speech recognition systems, labeling audio clips can be expensive, and not all data is equally valuable. Active learning aims to label only the most informative samples to reduce cost. For speech recognition, confidence scores and other likelihood-based active learning methods have been shown to be effective. Gradient-based active learning methods, however, are still not well-understood. This work investigates the Expected Gradient Length (EGL) approach in active learning for end-to-end speech recognition. We justify EGL from a variance reduction perspective, and observe that EGL's measure of informativeness picks novel samples uncorrelated with confidence scores. Experimentally, we show that EGL can reduce word errors by 11\%, or alternatively, reduce the number of samples to label by 50\%, when compared to random sampling.
When multiplicative noise stymies control
Venue: arXiv cs.SY 2016
Year: 2016

We consider the stabilization of an unstable discrete-time linear system that is observed over a channel corrupted by continuous multiplicative noise. Our main result shows that if the system growth is large enough, then the system cannot be stabilized in a second-moment sense. This is done by showing that the probability that the state magnitude remains bounded must go to zero with time. Our proof technique recursively bounds the conditional density of the system state (instead of focusing on the second moment) to bound the progress the controller can make. This sidesteps the difficulty encountered in using the standard data-rate theorem style approach; that approach does not work because the mutual information per round between the system state and the observation is potentially unbounded. It was known that a system with multiplicative observation noise can be stabilized using a simple memoryless linear strategy if the system growth is suitably bounded. In this paper, we show that while memory cannot improve the performance of a linear scheme, a simple non-linear scheme that uses one-step memory can do better than the best linear scheme.