OpenRaiser/Intern-Atlas huggingface dataset:
A Loop-Based Methodology for Reducing Computational Redundancy in Workload Sets
Venue: arXiv cs.PF 2017
Year: 2017

The design of general purpose processors relies heavily on a workload gathering step in which representative programs are collected from various application domains. Processor performance, when running the workload set, is profiled using simulators that model the targeted processor architecture. However, simulating the entire workload set is prohibitively time-consuming, which precludes considering a large number of programs. To reduce simulation time, several techniques in the literature have exploited the internal program repetitiveness to extract and execute only representative code segments. Existing so- lutions are based on reducing cross-program computational redundancy or on eliminating internal-program redundancy to decrease execution time. In this work, we propose an orthogonal and complementary loop- centric methodology that targets loop-dominant programs by exploiting internal-program characteristics to reduce cross-program computational redundancy. The approach employs a newly developed framework that extracts and analyzes core loops within workloads. The collected characteristics model memory behavior, computational complexity, and data structures of a program, and are used to construct a signature vector for each program. From these vectors, cross-workload similarity metrics are extracted, which are processed by a novel heuristic to exclude similar programs and reduce redundancy within the set. Finally, a reverse engineering approach that synthesizes executable micro-benchmarks having the same instruction mix as the loops in the original workload is introduced. A tool that automates the flow steps of the proposed methodology is developed. Simulation results demonstrate that applying the proposed methodology to a set of workloads reduces the set size by half, while preserving the main characterizations of the initial workloads.
Content Placement in Cache Networks Using Graph-Coloring
Venue: arXiv cs.IT 2017
Year: 2017

Small cell densification is one of the effective ideas addressing the demand for higher capacity in cellular networks. The major problem faced in such networks is the wireless backhaul link and its limited capacity. Caching most popular files in the memories of small cells base station (SBSs) is an effective solution to this problem. One of the main challenges in caching is choosing the files that are going to be stored in the memory of SBS. In this paper, we model the described caching problem as a graph. This graph is divided into four sub-graphs including placement, access, SBSs and delivery graphs. By making some modifications to the SBS graph, we convert it to a graph that can be colored. Coloring of the generated graph is NP-hard and we use an algorithm proposed in graph-coloring area to color it. To overcome the complexity of above coloring technique, we then propose a simple graph-coloring method based on two point processes, Matern Core-type I and II. We model our network with a new weighted graph which simply can be colored and after that the files are cached accordingly. We evaluate the performance of our proposed methods through simulations. Our results show that by employing out proposed method in a typical considered SBSs network, the load on the macro base station can be reduced by around $25 \%$, at the distribution parameter of popularity of files equals to $0.6$, compared to conventional policy which caches the most popular content every where.
A Real-time and Registration-free Framework for Dynamic Shape Instantiation
Venue: arXiv cs.CV 2017
Year: 2017

Real-time 3D navigation during minimally invasive procedures is an essential yet challenging task, especially when considerable tissue motion is involved. To balance image acquisition speed and resolution, only 2D images or low-resolution 3D volumes can be used clinically. In this paper, a real-time and registration-free framework for dynamic shape instantiation, generalizable to multiple anatomical applications, is proposed to instantiate high-resolution 3D shapes of an organ from a single 2D image intra-operatively. Firstly, an approximate optimal scan plane was determined by analyzing the pre-operative 3D statistical shape model (SSM) of the anatomy with sparse principal component analysis (SPCA) and considering practical constraints . Secondly, kernel partial least squares regression (KPLSR) was used to learn the relationship between the pre-operative 3D SSM and a synchronized 2D SSM constructed from 2D images obtained at the approximate optimal scan plane. Finally, the derived relationship was applied to the new intra-operative 2D image obtained at the same scan plane to predict the high-resolution 3D shape intra-operatively. A major feature of the proposed framework is that no extra registration between the pre-operative 3D SSM and the synchronized 2D SSM is required. Detailed validation was performed on studies including the liver and right ventricle (RV) of the heart. The derived results (mean accuracy of 2.19mm on patients and computation speed of 1ms) demonstrate its potential clinical value for real-time, high-resolution, dynamic and 3D interventional guidance.
Maximum Throughput of Multiple Access Channels in Adversarial Environments
Venue: arXiv cs.NI 2017
Year: 2017

We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. The maximum injection rate that an algorithm can handle in a stable manner is called the throughput of the algorithm. We develop an algorithm that achieves throughput $1$ for any number of stations against leaky-bucket adversaries. The algorithm has $O(n^2+\text{burstiness})$ packets queued simultaneously at any time, where $n$ is the number of stations; this upper bound is proved to be best possible. An algorithm is called fair when each packet is eventually broadcast. We show that no algorithm can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit differences in quality of broadcast among classes of algorithms. For two stations, we show that fair latency can be achieved by a full sensing algorithm, while there is no stable acknowledgment based algorithm. For three stations, we show that fair latency can be achieved by a general algorithm, while no full sensing algorithm can be stable. Finally, we show that algorithms that either are fair or do not have the queue sizes affect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.
Efficient priority queueing routing strategy on mobile networks
Venue: arXiv cs.NI 2017
Year: 2017

Mobile networks are intriguing in recent years due to their practical implications. Previous routing strategies for improving transport efficiency have little attention what order should the packets be forwarded, just simply used first-in-first-out queue discipline. Here we apply priority queueing discipline to shortest distance routing strategy on mobile networks. Numerical experiments show it not only remarkably improves network throughput and the packet arriving rate, but also reduces average end-to-end delay and the rate of queueing delay. Our work may be helpful in routing strategy designing on mobile networks.
Time-Aware Publish/Subscribe for Networks of Mobile Devices
Venue: arXiv cs.DC 2017
Year: 2017

Smart mobile devices are increasingly ubiquitous and are the primary source of user-generated content, and current communication infrastructures are failing in keeping up with the rising demand for the avid sharing of such content. To alleviate this problem and fully harness the amount of resources currently available at the network edge, mobile edge paradigms started to emerge. Though, application developers still struggle to tap that potential at the edge due to the lack of adequate communication and interaction abstractions. Thus, we propose a high-level abstraction that can be easily exploited by developers to design mobile edge applications focused on data dissemination. In this paper, we propose Thyme, a novel extended topic-based, time-aware publish/subscribe system for networks of mobile devices. In Thyme, time is a rst order dimension. Each subscription has an associated time frame, starting and ending either in the future, present, or past. Making the past available requires both subscriptions and publications to be persistently stored. We present the design of Thyme and evaluate it using simulation, discussing and characterizing the scenarios best suited for its use.
Blackboard Meets Dijkstra for Optimization of Web Service Workflows
Venue: arXiv cs.DC 2017
Year: 2017

This paper presents the integration of Dijkstra's algorithm within a Blackboard framework to optimize the selection of web services from service providers. In addition, methods are presented how dynamic changes during the workflow execution can be handled; specifically, how changes of the service parameters have effects on the system. For justification of our approach, and to show practical feasibility, a sample implementation is presented.
Multi-Objective Vehicle Routing Problem Applied to Large Scale Post Office Deliveries
Venue: arXiv cs.AI 2017
Year: 2017

The number of optimization techniques in the combinatorial domain is large and diversified. Nevertheless, real-world based benchmarks for testing algorithms are few. This work creates an extensible real-world mail delivery benchmark to the Vehicle Routing Problem (VRP) in a planar graph embedded in the 2D Euclidean space. Such problem is multi-objective on a roadmap with up to 25 vehicles and 30,000 deliveries per day. Each instance models one generic day of mail delivery, allowing both comparison and validation of optimization algorithms for routing problems. The benchmark may be extended to model other scenarios.
Cooperative Training of Deep Aggregation Networks for RGB-D Action Recognition
Venue: arXiv cs.CV 2017
Year: 2017

A novel deep neural network training paradigm that exploits the conjoint information in multiple heterogeneous sources is proposed. Specifically, in a RGB-D based action recognition task, it cooperatively trains a single convolutional neural network (named c-ConvNet) on both RGB visual features and depth features, and deeply aggregates the two kinds of features for action recognition. Differently from the conventional ConvNet that learns the deep separable features for homogeneous modality-based classification with only one softmax loss function, the c-ConvNet enhances the discriminative power of the deeply learned features and weakens the undesired modality discrepancy by jointly optimizing a ranking loss and a softmax loss for both homogeneous and heterogeneous modalities. The ranking loss consists of intra-modality and cross-modality triplet losses, and it reduces both the intra-modality and cross-modality feature variations. Furthermore, the correlations between RGB and depth data are embedded in the c-ConvNet, and can be retrieved by either of the modalities and contribute to the recognition in the case even only one of the modalities is available. The proposed method was extensively evaluated on two large RGB-D action recognition datasets, ChaLearn LAP IsoGD and NTU RGB+D datasets, and one small dataset, SYSU 3D HOI, and achieved state-of-the-art results.
Ghanaian Consumers Online Privacy Concerns: Causes and its Effects on E-Commerce Adoption
Venue: arXiv cs.CY 2017
Year: 2017

Online privacy has gradually become a concern for internet users over the years as a result of the interconnection of customers devices with other devices supporting the internet technology. This research investigates and discusses the factors that influence the privacy concerns faced by online consumers of internet services and the possible outcomes of these privacy concerns on the African online market with Ghana being the primary focus. Results from this study indicated that only 10.1 percent of respondents felt that the internet was safe for purchase and payment transaction in Ghana. However, respondents were willing to shop online if e-Commerce was the only means of getting their products. Respondents also had a high sense of perceived vulnerability and their perceived vulnerability to unauthorized data collection and misuse of personal information could affect Ghanaian e-Commerce platform adoption. The perceived ability of users of e-Commerce platforms in Ghana to control data collection and its subsequent use by other third parties was also found to negatively impact customers willingness to wholly transact and share their personal information online. The perceived vulnerability was found to be affected by the high levels of internet illiteracy whiles the perceived ability to control the collection of information and use was influenced by both the internet literacy level as well as the level of social awareness of the Ghanaian internet consumer.
Inferring propagation paths for sparsely observed perturbations on complex networks
Venue: arXiv cs.SI 2017
Year: 2017

In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.
Uncovering Hierarchical Structure in Social Networks using Isospectral Reductions
Venue: arXiv cs.SI 2017
Year: 2017

We employ the recently developed theory of isospectral network reductions to analyze multi-mode social networks. This procedure allows us to uncover the hierarchical structure of the networks we consider as well as the hierarchical structure of each mode of the network. Additionally, by performing a dynamical analysis of these networks we are able to analyze the evolution of their structure allowing us to find a number of other network features. We apply both of these approaches to the Southern Women Data Set, one of the most studied social networks and demonstrate that these techniques provide new information, which complements previous findings.
Optimal Weighting for Exam Composition
Venue: arXiv cs.CY 2017
Year: 2017

A problem faced by many instructors is that of designing exams that accurately assess the abilities of the students. Typically these exams are prepared several days in advance, and generic question scores are used based on rough approximation of the question difficulty and length. For example, for a recent class taught by the author, there were 30 multiple choice questions worth 3 points, 15 true/false with explanation questions worth 4 points, and 5 analytical exercises worth 10 points. We describe a novel framework where algorithms from machine learning are used to modify the exam question weights in order to optimize the exam scores, using the overall class grade as a proxy for a student's true ability. We show that significant error reduction can be obtained by our approach over standard weighting schemes, and we make several new observations regarding the properties of the "good" and "bad" exam questions that can have impact on the design of improved future evaluation methods.
Engagement in Foundational Computer Science Courses Through Supplementary Content for Algorithms
Venue: arXiv cs.CY 2017
Year: 2017

Engaging students in teaching foundational Computer Science concepts is vital for the student's continual success in more advanced topics in the field. An idea of a series of Jupyter notebooks was conceived as a way of using Bloom's Taxonomy to reinforce concepts taught in an introductory algorithms class. The idea of the notebook is to keep the student's engaged in the lesson and in turn motivate them to persevere through the end of the course.
An Average Case NP-Complete Graph Coloring Problem
Venue: arXiv cs.CC 2017
Year: 2017

NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proven easy. We show the intractability of random instances of a graph coloring problem: this graph problem is hard on average unless all NP problem under all samplable (i.e., generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial distortion of probabilities.
The Coarsest Precongruences Respecting Safety and Liveness Properties
Venue: arXiv cs.LO 2018
Year: 2018

This paper characterises the coarsest refinement preorders on labelled transition systems that are precongruences for renaming and partially synchronous interleaving operators, and respect all safety, liveness, and conditional liveness properties, respectively.
Scikit-learn: Machine Learning in Python
Venue: arXiv cs.LG 2018
Year: 2018

Scikit-learn is a Python module integrating a wide range of state-of-the-art machine learning algorithms for medium-scale supervised and unsupervised problems. This package focuses on bringing machine learning to non-specialists using a general-purpose high-level language. Emphasis is put on ease of use, performance, documentation, and API consistency. It has minimal dependencies and is distributed under the simplified BSD license, encouraging its use in both academic and commercial settings. Source code, binaries, and documentation can be downloaded from http://scikit-learn.org.
Strongly universal string hashing is fast
Venue: arXiv cs.DB 2018
Year: 2018

We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families---though they require a large buffer of random numbers---are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-powered processors. Our tests include hash functions designed for processors with the Carry-Less Multiplication (CLMUL) instruction set. We also prove, using accessible proofs, the strong universality of our families.
Java Source-code Clustering: Unifying Syntactic and Semantic Features
Venue: arXiv cs.SE 2018
Year: 2018

This is a companion draft to paper 'Software Clustering: Unifying Syntactic and Semantic Features', in proceedings of the 19th Working Conference on Reverse Engineering (WCRE 2012). It discusses the clustering process in detail, which appeared in the paper in an abridged form. It also contains certain additional process steps which were not covered in the WCRE paper. The clustering process is described for applications with Java source-code. However, as argued in the WCRE paper, it can be seamlessly adapted to many other programming paradigms.
Strong Bounds for Evolution in Undirected Graphs
Venue: arXiv cs.DS 2018
Year: 2018

This work studies the generalized Moran process, as introduced by Lieberman et al. [Nature, 433:312-316, 2005]. We introduce the parameterized notions of selective amplifiers and selective suppressors of evolution, i.e. of networks (graphs) with many "strong starts" and many "weak starts" for the mutant, respectively. We first prove the existence of strong selective amplifiers and of (quite) strong selective suppressors. Furthermore we provide strong upper bounds and almost tight lower bounds (by proving the "Thermal Theorem") for the traditional notion of fixation probability of Lieberman et al., i.e. assuming a random initial placement of the mutant.
Recognizing Interval Bigraphs by Forbidden Patterns
Venue: arXiv cs.DS 2018
Year: 2018

Let H be a connected bipartite graph with n nodes and m edges. We give an O(nm) time algorithm to decide whether H is an interval bigraph. The best known algorithm has time complexity O(nm^6(m + n) \log n) and it was developed in 1997 [18]. Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang [13]. We transform the problem of finding the desired ordering to choosing strong components of a pair-digraph without creating conflicts. We make use of the structure of the pair-digraph as well as decomposition of bigraph H based on the special components of the pair-digraph. This way we make explicit what the difficult cases are and gain efficiency by isolating such situations.
Blind Deconvolution using Convex Programming
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of recovering two unknown vectors, $\boldsymbol{w}$ and $\boldsymbol{x}$, of length $L$ from their circular convolution. We make the structural assumption that the two vectors are members of known subspaces, one with dimension $N$ and the other with dimension $K$. Although the observed convolution is nonlinear in both $\boldsymbol{w}$ and $\boldsymbol{x}$, it is linear in the rank-1 matrix formed by their outer product $\boldsymbol{w}\boldsymbol{x}^*$. This observation allows us to recast the deconvolution problem as low-rank matrix recovery problem from linear measurements, whose natural convex relaxation is a nuclear norm minimization program. We prove the effectiveness of this relaxation by showing that for "generic" signals, the program can deconvolve $\boldsymbol{w}$ and $\boldsymbol{x}$ exactly when the maximum of $N$ and $K$ is almost on the order of $L$. That is, we show that if $\boldsymbol{x}$ is drawn from a random subspace of dimension $N$, and $\boldsymbol{w}$ is a vector in a subspace of dimension $K$ whose basis vectors are "spread out" in the frequency domain, then nuclear norm minimization recovers $\boldsymbol{w}\boldsymbol{x}^*$ without error. We discuss this result in the context of blind channel estimation in communications. If we have a message of length $N$ which we code using a random $L\times N$ coding matrix, and the encoded message travels through an unknown linear time-invariant channel of maximum length $K$, then the receiver can recover both the channel response and the message when $L\gtrsim N+K$, to within constant and log factors.
Spectral Condition-Number Estimation of Large Sparse Matrices
Venue: arXiv cs.NA 2018
Year: 2018

We describe a randomized Krylov-subspace method for estimating the spectral condition number of a real matrix A or indicating that it is numerically rank deficient. The main difficulty in estimating the condition number is the estimation of the smallest singular value σ_{\min} of A. Our method estimates this value by solving a consistent linear least-squares problem with a known solution using a specific Krylov-subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a right singular vector corresponding to σ_{\min}. Extensive experiments show that the method is able to estimate well the condition number of a wide array of matrices. It can sometimes estimate the condition number when running a dense SVD would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR) and it works equally well on square and rectangular matrices.