OpenRaiser/Intern-Atlas huggingface dataset:
Chaotic Memory Randomization for Securing Embedded Systems
Venue: arXiv cs.CR 2016
Year: 2016

Embedded systems permeate through nearly all aspects of modern society. From cars to refrigerators to nuclear refineries, securing these systems has never been more important. Intrusions, such as the Stuxnet malware which broke the centrifuges in Iran's Natanz refinery, can be catastrophic to not only the infected systems, but even to the wellbeing of the surrounding population. Modern day protection mechanisms for these embedded systems generally look only at protecting the network layer, and those that try to discover malware already existing on a system typically aren't efficient enough to run on a standalone embedded system. As such, we present a novel way to ensure that no malware has been inserted into an embedded system. We chaotically randomize the entire memory space of the application, interspersing watchdog-monitor programs throughout, to monitor that the core application hasn't been infiltrated. By validating the original program through conventional methods and creating a clean reset, we can ensure that any inserted malware is purged from the system with minimal effect on the given system. We also present a software prototype to validate the possibility of this approach, but given the limitations and vulnerabilities of the prototype, we also suggest a hardware alternative to the system.
Temporal Matrix Completion with Locally Linear Latent Factors for Medical Applications
Venue: arXiv cs.LG 2016
Year: 2016

Regular medical records are useful for medical practitioners to analyze and monitor patient health status especially for those with chronic disease, but such records are usually incomplete due to unpunctuality and absence of patients. In order to resolve the missing data problem over time, tensor-based model is suggested for missing data imputation in recent papers because this approach makes use of low rank tensor assumption for highly correlated data. However, when the time intervals between records are long, the data correlation is not high along temporal direction and such assumption is not valid. To address this problem, we propose to decompose a matrix with missing data into its latent factors. Then, the locally linear constraint is imposed on these factors for matrix completion in this paper. By using a publicly available dataset and two medical datasets collected from hospital, experimental results show that the proposed algorithm achieves the best performance by comparing with the existing methods.
Below all subsets for Minimal Connected Dominating Set
Venue: arXiv cs.DS 2016
Year: 2016

A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not contained in $S$ has a neighbor in $S$. A dominating set $S$ is a connected dominating set if the subgraph $G[S]$ induced by $S$ is connected. A connected dominating set $S$ is a minimal connected dominating set if no proper subset of $S$ is also a connected dominating set. We prove that there exists a constant $\varepsilon > 10^{-50}$ such that every graph $G$ on $n$ vertices has at most $O(2^{(1-\varepsilon)n})$ minimal connected dominating sets. For the same $\varepsilon$ we also give an algorithm with running time $2^{(1-\varepsilon)n}\cdot n^{O(1)}$ to enumerate all minimal connected dominating sets in an input graph $G$.
Deep Convolutional Neural Network Design Patterns
Venue: arXiv cs.LG 2016
Year: 2016

Recent research in the deep learning field has produced a plethora of new architectures. At the same time, a growing number of groups are applying deep learning to new applications. Some of these groups are likely to be composed of inexperienced deep learning practitioners who are baffled by the dizzying array of architecture choices and therefore opt to use an older architecture (i.e., Alexnet). Here we attempt to bridge this gap by mining the collective knowledge contained in recent deep learning research to discover underlying principles for designing neural network architectures. In addition, we describe several architectural innovations, including Fractal of FractalNet network, Stagewise Boosting Networks, and Taylor Series Networks (our Caffe code and prototxt files is available at https://github.com/iPhysicist/CNNDesignPatterns). We hope others are inspired to build on our preliminary work.
Emerging Wireless Technologies in the Internet of Things: a Comparative Study
Venue: arXiv cs.NI 2016
Year: 2016

The Internet of Things (IoT) incorporates multiple long-range, short-range, and personal area wireless networks and technologies into the designs of IoT applications. This enables numerous business opportunities in fields as diverse as e-health, smart cities, smart homes, among many others. This research analyses some of the major evolving and enabling wireless technologies in the IoT. Particularly, it focuses on ZigBee, 6LoWPAN, Bluetooth Low Energy, LoRa, and the different versions of Wi-Fi including the recent IEEE 802.11ah protocol. The studies evaluate the capabilities and behaviours of these technologies regarding various metrics including the data range and rate, network size, RF Channels and Bandwidth, and power consumption. It is concluded that there is a need to develop a multifaceted technology approach to enable interoperable and secure communications in the IoT.
DecreaseKeys are Expensive for External Memory Priority Queues
Venue: arXiv cs.DS 2016
Year: 2016

One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing $O((N/B)\lg_{M/B} N)$ I/Os over a sequence of $N$ operations, where $B$ is the disk block size in number of words and $M$ is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only $O((N/B) \lg_2 N)$ I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of $Ω((N/B) \lg_{\lg N} B)$ I/Os for processing a sequence of $N$ intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.
Rough Set Based Color Channel Selection
Venue: arXiv cs.CV 2016
Year: 2016

Color channel selection is essential for accurate segmentation of sky and clouds in images obtained from ground-based sky cameras. Most prior works in cloud segmentation use threshold based methods on color channels selected in an ad-hoc manner. In this letter, we propose the use of rough sets for color channel selection in visible-light images. Our proposed approach assesses color channels with respect to their contribution for segmentation, and identifies the most effective ones.
Adaptive mixed norm optical flow estimation
Venue: arXiv cs.CV 2016
Year: 2016

The pel-recursive computation of 2-D optical flow has been extensively studied in computer vision to estimate motion from image sequences, but it still raises a wealth of issues, such as the treatment of outliers, motion discontinuities and occlusion. It relies on spatio-temporal brightness variations due to motion. Our proposed adaptive regularized approach deals with these issues within a common framework. It relies on the use of a data-driven technique called Mixed Norm (MN) to estimate the best motion vector for a given pixel. In our model, various types of noise can be handled, representing different sources of error. The motion vector estimation takes into consideration local image properties and it results from the minimization of a mixed norm functional with a regularization parameter depending on the kurtosis. This parameter determines the relative importance of the fourth norm and makes the functional convex. The main advantage of the developed procedure is that no knowledge of the noise distribution is necessary. Experiments indicate that this approach provides robust estimates of the optical flow.
Using a Deep Reinforcement Learning Agent for Traffic Signal Control
Venue: arXiv cs.LG 2016
Year: 2016

Ensuring transportation systems are efficient is a priority for modern society. Technological advances have made it possible for transportation systems to collect large volumes of varied data on an unprecedented scale. We propose a traffic signal control system which takes advantage of this new, high quality data, with minimal abstraction compared to other proposed systems. We apply modern deep reinforcement learning methods to build a truly adaptive traffic signal control agent in the traffic microsimulator SUMO. We propose a new state space, the discrete traffic state encoding, which is information dense. The discrete traffic state encoding is used as input to a deep convolutional neural network, trained using Q-learning with experience replay. Our agent was compared against a one hidden layer neural network traffic signal control agent and reduces average cumulative delay by 82%, average queue length by 66% and average travel time by 20%.
Visualisation of massive data from scholarly Article and Journal Database A Novel Scheme
Venue: arXiv cs.HC 2016
Year: 2016

Scholarly articles publishing and getting cited has become a way of life for academicians. These scholarly publications shape up the career growth of not only the authors but also of the country, continent and the technological domains. Author affiliations, country and other information of an author coupled with data analytics can provide useful and insightful results. However, massive and complete data is required to perform this research. Google scholar which is a comprehensive and free repository of scholarly articles has been used as a data source for this purpose. Data scraped from Google scholar when stored as a graph and visualized in the form of nodes and relationships, can offer discerning and concealed information. Such as, evident domain shift of an author, various research domains spread for an author, prediction of emerging domain and sub domains, detection of journal and author level citation cartel behaviors etc. The data from graph database is also used in computation of scholastic indicators for the journals. Eventually, econometric model, named Cobb Douglas model is used to compute the journals Modeling "Internationality" Index based on these scholastic indicators.
Phi-Entropic Measures of Correlation
Venue: arXiv cs.IT 2016
Year: 2016

A measure of correlation is said to have the tensorization property if it is unchanged when computed for i.i.d.\ copies. More precisely, a measure of correlation between two random variables $(X, Y)$ denoted by $ρ(X, Y)$, has the tensorization property if $ρ(X^n, Y^n)=ρ(X, Y)$ where $(X^n, Y^n)$ is $n$ i.i.d.\ copies of $(X, Y)$.Two well-known examples of such measures are the maximal correlation and the hypercontractivity ribbon (HC~ribbon). We show that the maximal correlation and HC ribbons are special cases of $Φ$-ribbon, defined in this paper for any function $Φ$ from a class of convex functions ($Φ$-ribbon reduces to HC~ribbon and the maximal correlation for special choices of $Φ$). Any $Φ$-ribbon is shown to be a measures of correlation with the tensorization property. We show that the $Φ$-ribbon also characterizes the $Φ$-strong data processing inequality constant introduced by Raginsky. We further study the $Φ$-ribbon for the choice of $Φ(t)=t^2$ and introduce an equivalent characterization of this ribbon.
The Polytope-Collision Problem
Venue: arXiv cs.CC 2016
Year: 2016

The Orbit Problem consists of determining, given a matrix $A\in \mathbb{R}^{d\times d}$ and vectors $x,y\in \mathbb{R}^d$, whether there exists $n\in \mathbb{N}$ such that $A^n=y$. This problem was shown to be decidable in a seminal work of Kannan and Lipton in the 1980s. Subsequently, Kannan and Lipton noted that the Orbit Problem becomes considerably harder when the target $y$ is replaced with a subspace of $\mathbb{R}^d$. Recently, it was shown that the problem is decidable for vector-space targets of dimension at most three, followed by another development showing that the problem is in PSPACE for polytope targets of dimension at most three. In this work, we take a dual look at the problem, and consider the case where the initial vector $x$ is replaced with a polytope $P_1$, and the target is a polytope $P_2$. Then, the question is whether there exists $n\in \mathbb{N}$ such that $A^n P_1\cap P_2\neq \emptyset$. We show that the problem can be decided in PSPACE for dimension at most three. As in previous works, decidability in the case of higher dimensions is left open, as the problem is known to be hard for long-standing number-theoretic open problems. Our proof begins by formulating the problem as the satisfiability of a parametrized family of sentences in the existential first-order theory of real-closed fields. Then, after removing quantifiers, we are left with instances of simultaneous positivity of sums of exponentials. Using techniques from transcendental number theory, and separation bounds on algebraic numbers, we are able to solve such instances in PSPACE.
Learning to Rank Scientific Documents from the Crowd
Venue: arXiv cs.IR 2016
Year: 2016

Finding related published articles is an important task in any science, but with the explosion of new work in the biomedical domain it has become especially challenging. Most existing methodologies use text similarity metrics to identify whether two articles are related or not. However biomedical knowledge discovery is hypothesis-driven. The most related articles may not be ones with the highest text similarities. In this study, we first develop an innovative crowd-sourcing approach to build an expert-annotated document-ranking corpus. Using this corpus as the gold standard, we then evaluate the approaches of using text similarity to rank the relatedness of articles. Finally, we develop and evaluate a new supervised model to automatically rank related scientific articles. Our results show that authors' ranking differ significantly from rankings by text-similarity-based models. By training a learning-to-rank model on a subset of the annotated corpus, we found the best supervised learning-to-rank model (SVM-Rank) significantly surpassed state-of-the-art baseline systems.
More Than Peer Production: Fanfiction Communities as Sites of Distributed Mentoring
Venue: arXiv cs.HC 2016
Year: 2016

From Harry Potter to American Horror Story, fanfiction is extremely popular among young people. Sites such as Fanfiction.net host millions of stories, with thousands more posted each day. Enthusiasts are sharing their writing and reading stories written by others. Exactly how does a generation known more for videogame expertise than long-form writing become so engaged in reading and writing in these communities? Via a nine-month ethnographic investigation of fanfiction communities that included participant observation, interviews, a thematic analysis of 4,500 reader reviews and an in-depth case study of a discussion group, we found that members of fanfiction communities spontaneously mentor each other in open forums, and that this mentoring builds upon previous interactions in a way that is distinct from traditional forms of mentoring and made possible by the affordances of networked publics. This work extends and develops the theory of distributed mentoring. Our findings illustrate how distributed mentoring supports fanfiction authors as they work to develop their writing skills. We believe distributed mentoring holds potential for supporting learning in a variety of formal and informal learning environments.
Class-prior Estimation for Learning from Positive and Unlabeled Data
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of estimating the class prior in an unlabeled dataset. Under the assumption that an additional labeled dataset is available, the class prior can be estimated by fitting a mixture of class-wise data distributions to the unlabeled data distribution. However, in practice, such an additional labeled dataset is often not available. In this paper, we show that, with additional samples coming only from the positive class, the class prior of the unlabeled dataset can be estimated correctly. Our key idea is to use properly penalized divergences for model fitting to cancel the error caused by the absence of negative samples. We further show that the use of the penalized $L_1$-distance gives a computationally efficient algorithm with an analytic solution. The consistency, stability, and estimation error are theoretically analyzed. Finally, we experimentally demonstrate the usefulness of the proposed method.
MetaFlow: a Scalable Metadata Lookup Service for Distributed File Systems in Data Centers
Venue: arXiv cs.DC 2016
Year: 2016

In large-scale distributed file systems, efficient meta- data operations are critical since most file operations have to interact with metadata servers first. In existing distributed hash table (DHT) based metadata management systems, the lookup service could be a performance bottleneck due to its significant CPU overhead. Our investigations showed that the lookup service could reduce system throughput by up to 70%, and increase system latency by a factor of up to 8 compared to ideal scenarios. In this paper, we present MetaFlow, a scalable metadata lookup service utilizing software-defined networking (SDN) techniques to distribute lookup workload over network components. MetaFlow tackles the lookup bottleneck problem by leveraging B-tree, which is constructed over the physical topology, to manage flow tables for SDN-enabled switches. Therefore, metadata requests can be forwarded to appropriate servers using only switches. Extensive performance evaluations in both simulations and testbed showed that MetaFlow increases system throughput by a factor of up to 3.2, and reduce system latency by a factor of up to 5 compared to DHT-based systems. We also deployed MetaFlow in a distributed file system, and demonstrated significant performance improvement.
LipNet: End-to-End Sentence-level Lipreading
Venue: arXiv cs.LG 2016
Year: 2016

Lipreading is the task of decoding text from the movement of a speaker's mouth. Traditional approaches separated the problem into two stages: designing or learning visual features, and prediction. More recent deep lipreading approaches are end-to-end trainable (Wand et al., 2016; Chung & Zisserman, 2016a). However, existing work on models trained end-to-end perform only word classification, rather than sentence-level sequence prediction. Studies have shown that human lipreading performance increases for longer words (Easton & Basala, 1982), indicating the importance of features capturing temporal context in an ambiguous communication channel. Motivated by this observation, we present LipNet, a model that maps a variable-length sequence of video frames to text, making use of spatiotemporal convolutions, a recurrent network, and the connectionist temporal classification loss, trained entirely end-to-end. To the best of our knowledge, LipNet is the first end-to-end sentence-level lipreading model that simultaneously learns spatiotemporal visual features and a sequence model. On the GRID corpus, LipNet achieves 95.2% accuracy in sentence-level, overlapped speaker split task, outperforming experienced human lipreaders and the previous 86.4% word-level state-of-the-art accuracy (Gergen et al., 2016).
Energy-Efficient Resource Allocation for Multi-User Mobile Edge Computing
Venue: arXiv cs.IT 2016
Year: 2016

To increase mobile batteries' lifetime and improve quality of experience for computation-intensive and latency-sensitive applications, mobile edge computing has received significant interest. Designing energy-efficient mobile edge computing systems requires joint optimization of communication and computation resources. In this paper, we consider energy-efficient resource allocation for a multi-user mobile edge computing system. First, we establish on two computation-efficient models with negligible and non-negligible base station (BS) executing durations, respectively. Then, under each model, we formulate the overall weighted sum energy consumption minimization problem by optimally allocating communication and computation resources. The optimization problem for negligible BS executing duration is convex, and we obtain the optimal solution in closed-form to this problem. The optimization problem for non-negligible BS executing duration is NP-hard in general, and we obtain a sub-optimal solution with low-complexity to this problem, by connecting it to a three-stage flow-shop scheduling problem and wisely utilizing Johnson's algorithm. Finally, numerical results show that the proposed solutions outperform some baseline schemes.
MTS Sketch for Accurate Estimation of Set-Expression Cardinalities from Small Samples
Venue: arXiv cs.DB 2016
Year: 2016

Sketch-based streaming algorithms allow efficient processing of big data. These algorithms use small fixed-size storage to store a summary ("sketch") of the input data, and use probabilistic algorithms to estimate the desired quantity. However, in many real-world applications it is impractical to collect and process the entire data stream, the common practice is thus to sample and process only a small part of it. While sampling is crucial for handling massive data sets, it may reduce accuracy. In this paper we present a new framework that can accurately estimate the cardinality of any set expression between any number of streams using only a small sample of each stream. The proposed framework consists of a new sketch, called Maximal-Term with Subsample (MTS), and a family of algorithms that use this sketch. An example of a possible query that can be efficiently answered using the proposed sketch is, How many distinct tuples appear in tables $T_1$ and $T_2$, but not in $T_3$? The algorithms presented in this paper answer such queries accurately, processing only a small sample of the tuples in each table and using a constant amount of memory. Such estimations are useful for the optimization of queries over very large database systems. We show that all our algorithms are unbiased, and we analyze their asymptotic variance.
Marciani Normal Form of context-free grammars
Venue: arXiv cs.FL 2016
Year: 2016

In this paper, we prove the semidecidability of the problem of saying whether or not a context-free grammar generates a regular language. We introduce the notion of context-free grammar in Marciani Normal Form. We prove that a context-free grammar in Marciani Normal Form always generates a regular language.
Skewness of citation impact data and covariates of citation distributions: A large-scale empirical analysis based on Web of Science data
Venue: arXiv cs.DL 2016
Year: 2016

Using percentile shares, one can visualize and analyze the skewness in bibliometric data across disciplines and over time. The resulting figures can be intuitively interpreted and are more suitable for detailed analysis of the effects of independent and control variables on distributions than regression analysis. We show this by using percentile shares to analyze so-called "factors influencing citation impact" (FICs; e.g., the impact factor of the publishing journal) across year and disciplines. All articles (n= 2,961,789) covered by WoS in 1990 (n= 637,301), 2000 (n= 919,485), and 2010 (n= 1,405,003) are used. In 2010, nearly half of the citation impact is accounted for by the 10% most-frequently cited papers; the skewness is largest in the humanities (68.5% in the top-10% layer) and lowest in agricultural sciences (40.6%). The comparison of the effects of the different FICs (the number of cited references, number of authors, number of pages, and JIF) on citation impact shows that JIF has indeed the strongest correlations with the citation scores. However, the correlation between FICs and citation impact is lower, if citations are normalized instead of using raw citation counts.