OpenRaiser/Intern-Atlas huggingface dataset:
Using Hankel Matrices for Dynamics-based Facial Emotion Recognition and Pain Detection
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a new approach to model the temporal dynamics of a sequence of facial expressions. To this purpose, a sequence of Face Image Descriptors (FID) is regarded as the output of a Linear Time Invariant (LTI) system. The temporal dynamics of such sequence of descriptors are represented by means of a Hankel matrix. The paper presents different strategies to compute dynamics-based representation of a sequence of FID, and reports classification accuracy values of the proposed representations within different standard classification frameworks. The representations have been validated in two very challenging application domains: emotion recognition and pain detection. Experiments on two publicly available benchmarks and comparison with state-of-the-art approaches demonstrate that the dynamics-based FID representation attains competitive performance when off-the-shelf classification tools are adopted.
Emotion Analysis of Songs Based on Lyrical and Audio Features
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, a method is proposed to detect the emotion of a song based on its lyrical and audio features. Lyrical features are generated by segmentation of lyrics during the process of data extraction. ANEW and WordNet knowledge is then incorporated to compute Valence and Arousal values. In addition to this, linguistic association rules are applied to ensure that the issue of ambiguity is properly addressed. Audio features are used to supplement the lyrical ones and include attributes like energy, tempo, and danceability. These features are extracted from The Echo Nest, a widely used music intelligence platform. Construction of training and test sets is done on the basis of social tags extracted from the last.fm website. The classification is done by applying feature weighting and stepwise threshold reduction on the k-Nearest Neighbors algorithm to provide fuzziness in the classification.
Analysing the Complexity of Functional Programs: Higher-Order Meets First-Order (Long Version)
Venue: arXiv cs.LO 2015
Year: 2015

We show how the complexity of higher-order functional programs can be analysed automatically by applying program transformations to a defunctionalized versions of them, and feeding the result to existing tools for the complexity analysis of first-order term rewrite systems. This is done while carefully analysing complexity preservation and reflection of the employed transformations such that the complexity of the obtained term rewrite system reflects on the complexity of the initial program. Further, we describe suitable strategies for the application of the studied transformations and provide ample experimental data for assessing the viability of our method.
Secure Shell (SSH): Public Key Authentication over Hypertext Transfer Protocol (HTTP)
Venue: arXiv cs.CR 2015
Year: 2015

Secure Shell (SSH) protocol requires all implementations to support public key authentication method ("publickey") for authentication purposes, so web applications which provide a SSH client over the web browser need to support "publickey". However, restrictions in Hypertext Transfer Protocol (HTTP), such as same origin policy, and limited access to local resources, make it difficult to perform such authentications. In this document, a system to perform "publickey" authentication over HTTP is provided. It is ensured that no compromise is made that would pose a security risk to SSH protocol.
All Permutations Supersequence is coNP-complete
Venue: arXiv cs.CC 2015
Year: 2015

We prove that deciding whether a given input word contains as subsequence every possible permutation of integers $\{1,2,\ldots,n\}$ is coNP-complete. The coNP-completeness holds even when given the guarantee that the input word contains as subsequences all of length $n-1$ sequences over the same set of integers. We also show NP-completeness of a related problem of Partially Non-crossing Perfect Matching in Bipartite Graphs, i.e. to find a perfect matching in an ordered bipartite graph where edges of the matching incident to selected vertices (even only from one side) are non-crossing.
On-line direct data driven controller design approach with automatic update for some of the tuning parameters
Venue: arXiv cs.SY 2015
Year: 2015

This manuscript contains technical details of recent results developed by the authors on the algorithm for direct design of controllers for nonlinear systems from data that has the ability to to automatically modify some of the tuning parameters in order to increase control performance over time.
jUCM: Universal Class Morphing (position paper)
Venue: arXiv cs.PL 2015
Year: 2015

We extend prior work on class-morphing to provide a more expressive pattern-based compile-time reflection language. Our MorphJ language offers a disciplined form of metaprogramming that produces types by statically iterating over and pattern-matching on fields and methods of other types. We expand such capabilities with "universal morphing", which also allows pattern-matching over types (e.g., all classes nested in another, all supertypes of a class) while maintaining modular type safety for our meta-programs. We present informal examples of the functionality and discuss a design for adding universal morphing to Java.
Partial Functional Correspondence
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a method for computing partial functional correspondence between non-rigid shapes. We use perturbation analysis to show how removal of shape parts changes the Laplace-Beltrami eigenfunctions, and exploit it as a prior on the spectral representation of the correspondence. Corresponding parts are optimization variables in our problem and are used to weight the functional correspondence; we are looking for the largest and most regular (in the Mumford-Shah sense) parts that minimize correspondence distortion. We show that our approach can cope with very challenging correspondence settings.
Formally Proved Security of Assembly Code Against Power Analysis: A Case Study on Balanced Logic
Venue: arXiv cs.CR 2015
Year: 2015

In his keynote speech at CHES 2004, Kocher advocated that side-channel attacks were an illustration that formal cryptography was not as secure as it was believed because some assumptions (e.g., no auxiliary information is available during the computation) were not modeled. This failure is caused by formal methods' focus on models rather than implementations. In this paper we present formal methods and tools for designing protected code and proving its security against power analysis. These formal methods avoid the discrepancy between the model and the implementation by working on the latter rather than on a high-level model. Indeed, our methods allow us (a) to automatically insert a power balancing countermeasure directly at the assembly level, and to prove the correctness of the induced code transformation; and (b) to prove that the obtained code is balanced with regard to a reasonable leakage model. We also show how to characterize the hardware to use the resources which maximize the relevancy of the model. The tools implementing our methods are then demonstrated in a case study on an 8-bit AVR smartcard for which we generate a provably protected present implementation that reveals to be at least 250 times more resistant to CPA attacks.
Using Application Data for SLA-aware Auto-scaling in Cloud Environments
Venue: arXiv cs.DC 2015
Year: 2015

With the establishment of cloud computing as the environment of choice for most modern applications, auto-scaling is an economic matter of great importance. For applications like stream computing that process ever changing amounts of data, modifying the number and configuration of resources to meet performance requirements becomes essential. Current solutions on auto-scaling are mostly rule-based using infrastructure level metrics such as CPU/memory/network utilization, and system level metrics such as throughput and response time. In this paper, we introduce a study on how effective auto-scaling can be using data generated by the application itself. To make this assessment, two algorithms are proposed that use a priori knowledge of the data stream and use sentiment analysis from soccer-related tweets, triggering auto-scaling operations according to rapid changes in the public sentiment about the soccer players that happens just before big bursts of messages. Our application-based auto-scaling was able to reduce the number of SLA violations by up to 95% and reduce resource requirements by up to 33%.
wHealth - Transforming Telehealth Services
Venue: arXiv cs.CY 2015
Year: 2015

A worldwide increase in proportions of older people in the population poses the challenge of managing their increasing healthcare needs within limited resources. To achieve this many countries are interested in adopting telehealth technology. Several shortcomings of state-of-the-art telehealth technology constrain widespread adoption of telehealth services. We present an ensemble-sensing framework - wHealth (short form of wireless health) for effective delivery of telehealth services. It extracts personal health information using sensors embedded in everyday devices and allows effective and seamless communication between patients and clinicians. Due to the non-stigmatizing design, ease of maintenance, simplistic interaction and seamless intervention, our wHealth platform has the potential to enable widespread adoption of telehealth services for managing elderly healthcare. We discuss the key barriers and potential solutions to make the wHealth platform a reality.
A Singleton Bound for Generalized Ferrers Diagram Rank Metric Codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we will employ the technique used in the proof of classical Singleton bound to derive upper bounds for rank metric codes and Ferrers diagram rank metric codes. These upper bounds yield the rank distance Singleton bound and an upper bound presented by Etzion and Silberstein respectively. Also we introduce generalized Ferrers diagram rank metric code which is a Ferrers diagram rank metric code where the underlying rank metric code is not necessarily linear. A new Singleton bound for generalized Ferrers diagram rank metric code is obtained using our technique.
Information Diffusion issues
Venue: arXiv cs.SI 2015
Year: 2015

In this report there will be a discussion for Information Diffusion. There will be discussions on what information diffusion is, its key characteristics and on several other aspects of these kinds of networks. This report will focus on peer to peer models in information diffusion. There will be discussions on epidemic model, OSN and other details related to information diffusion.
Topology-Aware Node Selection for Data Regeneration in Heterogeneous Distributed Storage Systems
Venue: arXiv cs.DC 2015
Year: 2015

Distributed storage systems introduce redundancy to protect data from node failures. After a storage node fails, the lost data should be regenerated at a replacement storage node as soon as possible to maintain the same level of redundancy. Minimizing such a regeneration time is critical to the reliability of distributed storage systems. Existing work commits to reduce the regeneration time by either minimizing the regenerating traffic, or adjusting the regenerating traffic patterns, whereas nodes participating data regeneration are generally assumed to be given beforehand. However, such regeneration time also depends heavily on the selection of the participating nodes. Selecting different participating nodes actually involve different data links between the nodes. Real-world distributed storage systems usually exhibit heterogeneous link capacities. It is possible to further reduce the regeneration time via exploiting such link capacity differences and avoiding the link bottlenecks. In this paper, we consider the minimization of the regeneration time by selecting the participating nodes in heterogeneous networks. We analyze the regeneration time and propose node selection algorithms for overlay networks and real-world topologies. Considering that the flexible amount of data blocks from each provider may deeply influence the regeneration time, several techniques are designed to enhance our schemes in overlay networks. Experimental results show that our node selection schemes can significantly reduce the regeneration time for each topology, especially in practical networks with heterogeneous link capacities.
An Open Science Platform for the Next Generation of Data
Venue: arXiv cs.CY 2015
Year: 2015

Imagine an online work environment where researchers have direct and immediate access to myriad data sources and tools and data management resources, useful throughout the research lifecycle. This is our vision for the next generation of the Dataverse Network: an Open Science Platform (OSP). For the first time, researchers would be able to seamlessly access and create primary and derived data from a variety of sources: prior research results, public data sets, harvested online data, physical instruments, private data collections, and even data from other standalone repositories. Researchers could recruit research participants and conduct research directly on the OSP, if desired, using readily available tools. Researchers could create private or shared workspaces to house data, access tools, and computation and could publish data directly on the platform or publish elsewhere with persistent, data citations on the OSP. This manuscript describes the details of an Open Science Platform and its construction. Having an Open Science Platform will especially impact the rate of new scientific discoveries and make scientific findings more credible and accountable.
A Fast Algorithm for Computing the p-Curvature
Venue: arXiv cs.SC 2015
Year: 2015

We design an algorithm for computing the $p$-curvature of a differential system in positive characteristic $p$. For a system of dimension $r$ with coefficients of degree at most $d$, its complexity is $\softO (p d r^ω)$ operations in the ground field (where $ω$ denotes the exponent of matrix multiplication), whereas the size of the output is about $p d r^2$. Our algorithm is then quasi-optimal assuming that matrix multiplication is (\emph{i.e.} $ω= 2$). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.
Pragmatic Side Effects
Venue: arXiv cs.CL 2015
Year: 2015

In the quest to give a formal compositional semantics to natural languages, semanticists have started turning their attention to phenomena that have been also considered as parts of pragmatics (e.g., discourse anaphora and presupposition projection). To account for these phenomena, the very kinds of meanings assigned to words and phrases are often revisited. To be more specific, in the prevalent paradigm of modeling natural language denotations using the simply-typed lambda calculus (higher-order logic) this means revisiting the types of denotations assigned to individual parts of speech. However, the lambda calculus also serves as a fundamental theory of computation, and in the study of computation, similar type shifts have been employed to give a meaning to side effects. Side effects in programming languages correspond to actions that go beyond the lexical scope of an expression (a thrown exception might propagate throughout a program, a variable modified at one point might later be read at an another) or even beyond the scope of the program itself (a program might interact with the outside world by e.g., printing documents, making sounds, operating robotic limbs...).
ModularityCheck: A Tool for Assessing Modularity using Co-Change Clusters
Venue: arXiv cs.SE 2015
Year: 2015

It is widely accepted that traditional modular structures suffer from the dominant decomposition problem. Therefore, to improve current modularity views, it is important to investigate the impact of design decisions concerning modularity in other dimensions, as the evolutionary view. In this paper, we propose the ModularityCheck tool to assess package modularity using co-change clusters, which are sets of classes that usually changed together in the past. Our tool extracts information from version control platforms and issue reports, retrieves co-change clusters, generates metrics related to co-change clusters, and provides visualizations for assessing modularity. We also provide a case study to evaluate the tool. http://youtu.be/7eBYa2dfIS8
A Faster Algorithm for Fully Dynamic Betweenness Centrality
Venue: arXiv cs.DS 2015
Year: 2015

We present a new fully dynamic algorithm for maintaining betweenness centrality (BC) of vertices in a directed graph $G=(V,E)$ with positive edge weights. BC is a widely used parameter in the analysis of large complex networks. We achieve an amortized $O((ν^*)^2 \log^2 n)$ time per update, where $n = |V| $ and $ν^*$ bounds the number of distinct edges that lie on shortest paths through any single vertex. This result improves on the amortized bound for fully dynamic BC in [Pontecorvi-Ramachandran2015] by a logarithmic factor. Our algorithm uses new data structures and techniques that are extensions of the method in the fully dynamic algorithm in Thorup [Thorup2004] for APSP in graphs with unique shortest paths. For graphs with $ν^* = O(n)$, our algorithm matches the fully dynamic APSP bound in [Thorup2004], which holds for graphs with $ν^* = n-1$, since it assumes unique shortest paths.
WiFi Assisted Multi-WiGig AP Coordination for Future Multi-Gbps WLANs
Venue: arXiv cs.NI 2015
Year: 2015

Wireless Gigabit (WiGig) access points (APs) using 60 GHz unlicensed frequency band are considered as key enablers for future Gbps wireless local area networks (WLANs). Exhaustive search analog beamforming (BF) is mainly used with WiGig transmissions to overcome channel propagation loss and accomplish high rate data transmissions. Due to its short range transmission with high susceptibility to path blocking, a multiple number of WiGig APs should be installed to fully cover a typical target environment. Therefore, coordination among the installed APs is highly needed for enabling WiGig concurrent transmissions while overcoming packet collisions and reducing interference, which highly increases the total throughput of WiGig WLANs. In this paper, we propose a comprehensive architecture for coordinated WiGig WLANs. The proposed WiGig WLAN is based on a tight coordination between the 5 GHz (WiFi) and the 60 GHz (WiGig) unlicensed frequency bands. By which, the wide coverage WiFi band is used to do the signaling required for organizing WiGig concurrent data transmissions using control/user (C/U) plane splitting. To reduce interference to existing WiGig data links while doing BF, a novel location based BF mechanism is also proposed based on WiFi fingerprinting. The proposed coordinated WiGig WLAN highly outperforms conventional un-coordinated one in terms of total throughput, average packet delay and packet dropping rate.
A Tight Runtime Analysis of the $(1+(λ, λ))$ Genetic Algorithm on OneMax
Venue: arXiv cs.NE 2015
Year: 2015

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably is useful, the $(1+(λ, λ))$ Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel: TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a $O(\max\{n\log(n)/λ, λn\})$ bound was proven for any offspring population size $λ\in [1..n]$. We improve this work in several ways, leading to sharper bounds and a better understanding of how the use of crossover speeds up the runtime in this algorithm. We first improve the upper bound on the runtime to $O(\max\{n\log(n)/λ, nλ\log\log(λ)/\log(λ)\})$. This improvement is made possible from observing that in the parallel generation of $λ$ offspring via crossover (but not mutation), the best of these often is better than the expected value, and hence several fitness levels can be gained in one iteration. We then present the first lower bound for this problem. It matches our upper bound for all values of $λ$. This allows to determine the asymptotically optimal value for the population size. It is $λ= Θ(\sqrt{\log(n)\log\log(n)/\log\log\log(n)})$, which gives an optimization time of $Θ(n \sqrt{\log(n)\log\log\log(n)/\log\log(n)})$. Hence the improved runtime analysis gives a better runtime guarantee along with a better suggestion for the parameter $λ$. We finally give a tail bound for the upper tail of the runtime distribution, which shows that the actual runtime exceeds our runtime guarantee by a factor of $(1+δ)$ with probability $O((n/λ^2)^{-δ})$ only.
Traffic Engineering with Segment Routing: SDN-based Architectural Design and Open Source Implementation
Venue: arXiv cs.NI 2015
Year: 2015

Traffic Engineering (TE) in IP carrier networks is one of the functions that can benefit from the Software Defined Networking paradigm. By logically centralizing the control of the network, it is possible to "program" per-flow routing based on TE goals. Traditional per-flow routing requires a direct interaction between the SDN controller and each node that is involved in the traffic paths. Depending on the granularity and on the temporal properties of the flows, this can lead to scalability issues for the amount of routing state that needs to be maintained in core network nodes and for the required configuration traffic. On the other hand, Segment Routing (SR) is an emerging approach to routing that may simplify the route enforcement delegating all the configuration and per-flow state at the border of the network. In this work we propose an architecture that integrates the SDN paradigm with SR-based TE, for which we have provided an open source reference implementation. We have designed and implemented a simple TE/SR heuristic for flow allocation and we show and discuss experimental results.
Crowd Flow Segmentation in Compressed Domain using CRF
Venue: arXiv cs.CV 2015
Year: 2015

Crowd flow segmentation is an important step in many video surveillance tasks. In this work, we propose an algorithm for segmenting flows in H.264 compressed videos in a completely unsupervised manner. Our algorithm works on motion vectors which can be obtained by partially decoding the compressed video without extracting any additional features. Our approach is based on modelling the motion vector field as a Conditional Random Field (CRF) and obtaining oriented motion segments by finding the optimal labelling which minimises the global energy of CRF. These oriented motion segments are recursively merged based on gradient across their boundaries to obtain the final flow segments. This work in compressed domain can be easily extended to pixel domain by substituting motion vectors with motion based features like optical flow. The proposed algorithm is experimentally evaluated on a standard crowd flow dataset and its superior performance in both accuracy and computational time are demonstrated through quantitative results.