OpenRaiser/Intern-Atlas huggingface dataset:
Improved Solution to the Non-Domination Level Update Problem
Venue: arXiv cs.DS 2015
Year: 2015

Non-domination level update problem is to sort the non-dominated fronts after insertion or deletion of a solution. Generally the solution to this problem requires to perform the complete non-dominated sorting which is too expensive in terms of number of comparisons. Recently an Efficient Non-domination Level Update (ENLU) approach is proposed which does not perform the complete sorting. For this purpose, in this paper a space efficient version of ENLU approach is proposed without compromising the number of comparisons. However this approach does not work satisfactorily in all the cases. So we have also proposed another tree based approach for solving this non-domination level update problem. In case of insertion, the tree based approach always checks for same number of fronts unlike linear approach in which the number of fronts to be checked depends on the inserted solution. The result shows that in case where all the solutions are dominating in nature the maximum number of comparisons using tree based approach is $\mathcal{O}(\log N)$ as opposed to $\mathcal{O}(N)$ in ENLU approach. When all the solutions are equally divided into $K$ fronts such that each solution in a front is dominated by all the solutions in the previous front then the maximum number of comparisons to find a deleted solution in case of tree based approach is $K{-}\log K$ less than that of ENLU approach. Using these approaches an on-line sorting algorithm is also proposed and the competitive analysis of this algorithm is also presented.
Quantification in-the-wild: data-sets and baselines
Venue: arXiv cs.LG 2015
Year: 2015

Quantification is the task of estimating the class-distribution of a data-set. While typically considered as a parameter estimation problem with strict assumptions on the data-set shift, we consider quantification in-the-wild, on two large scale data-sets from marine ecology: a survey of Caribbean coral reefs, and a plankton time series from Martha's Vineyard Coastal Observatory. We investigate several quantification methods from the literature and indicate opportunities for future work. In particular, we show that a deep neural network can be fine-tuned on a very limited amount of data (25 - 100 samples) to outperform alternative methods.
A Probabilistic Framework for Structural Analysis in Directed Networks
Venue: arXiv cs.SI 2015
Year: 2015

In our recent works, we developed a probabilistic framework for structural analysis in undirected networks. The key idea of that framework is to sample a network by a symmetric bivariate distribution and then use that bivariate distribution to formerly define various notions, including centrality, relative centrality, community, and modularity. The main objective of this paper is to extend the probabilistic framework to directed networks, where the sampling bivariate distributions could be asymmetric. Our main finding is that we can relax the assumption from symmetric bivariate distributions to bivariate distributions that have the same marginal distributions. By using such a weaker assumption, we show that various notions for structural analysis in directed networks can also be defined in the same manner as before. However, since the bivariate distribution could be asymmetric, the community detection algorithms proposed in our previous work cannot be directly applied. For this, we show that one can construct another sampled graph with a symmetric bivariate distribution so that for any partition of the network, the modularity index remains the same as that of the original sampled graph. Based on this, we propose a hierarchical agglomerative algorithm that returns a partition of communities when the algorithm converges.
Data Allocation in a Heterogeneous Disk Array - HDA with Multiple RAID Levels for Database Applications
Venue: arXiv cs.DC 2015
Year: 2015

We consider the allocation of Virtual Arrays (VAs) in a Heterogeneous Disk Array (HDA). Each VA holds groups of related objects and datasets such as files, relational tables, which has similar performance and availability characteristics. We evaluate single-pass data allocation methods for HDA using a synthetic stream of allocation requests, where each VA is characterized by its RAID level, disk loads and space requirements. The goal is to maximize the number of allocated VAs and maintain high disk bandwidth and capacity utilization, while balancing disk loads. Although only RAID1 (basic mirroring) and RAID5 (rotated parity arrays) are considered in the experimental study, we develop the analysis required to estimate disk loads for other RAID levels. Since VA loads vary significantly over time, the VA allocation is carried out at the peak load period, while ensuring that disk bandwidth is not exceeded at other high load periods. Experimental results with a synthetic stream of allocation requests show that allocation methods minimizing the maximum disk bandwidth and capacity utilization or their variance across all disks yield the maximum number of allocated VAs. HDA saves disk bandwidth, since a single RAID level accommodating the most stringent availability requirements for a small subset of objects would incur an unnecessarily high overhead for updating check blocks or data replicas for all objects. The number of allocated VAs can be increased by adopting the clustered RAID5 paradigm, which exploits the tradeoff between redundancy and bandwidth utilization. Since rebuild can be carried out at the level of individual VAs, prioritizing rebuild of VAs with higher access rates can improve overall performance.
Refactoring Technical Support to Reduce Interrupts of Developers
Venue: arXiv cs.SI 2015
Year: 2015

In this paper an analysis of a technical support data with the goal of identifying process improvement actions for reducing interrupts is presented. A technical support chat is established and used to provide internal developer support to other development teams which use the software code developed by a core team. The paper shows how data analysis of a 6 months support time helped to identify gaps and action items for improving the technical support process to minimize interrupts from other developer teams. The paper also shows effects (advantages and drawbacks) of refactor actions taken based on this analysis.
Improving the Speed of Response of Learning Algorithms Using Multiple Models
Venue: arXiv cs.LG 2015
Year: 2015

This is the first of a series of papers that the authors propose to write on the subject of improving the speed of response of learning systems using multiple models. During the past two decades, the first author has worked on numerous methods for improving the stability, robustness, and performance of adaptive systems using multiple models and the other authors have collaborated with him on some of them. Independently, they have also worked on several learning methods, and have considerable experience with their advantages and limitations. In particular, they are well aware that it is common knowledge that machine learning is in general very slow. Numerous attempts have been made by researchers to improve the speed of convergence of algorithms in different contexts. In view of the success of multiple model based methods in improving the speed of convergence in adaptive systems, the authors believe that the same approach will also prove fruitful in the domain of learning. In this paper, a first attempt is made to use multiple models for improving the speed of response of the simplest learning schemes that have been studied. i.e. Learning Automata.
Considering Time in Designing Large-Scale Systems for Scientific Computing
Venue: arXiv cs.HC 2015
Year: 2015

High performance computing (HPC) has driven collaborative science discovery for decades. Exascale computing platforms, currently in the design stage, will be deployed around 2022. The next generation of supercomputers is expected to utilize radically different computational paradigms, necessitating fundamental changes in how the community of scientific users will make the most efficient use of these powerful machines. However, there have been few studies of how scientists work with exascale or close-to-exascale HPC systems. Time as a metaphor is so pervasive in the discussions and valuation of computing within the HPC community that it is worthy of close study. We utilize time as a lens to conduct an ethnographic study of scientists interacting with HPC systems. We build upon recent CSCW work to consider temporal rhythms and collective time within the HPC sociotechnical ecosystem and provide considerations for future system design.
Energy Model for Vesicle-Based Active Transport Molecular Communication
Venue: arXiv cs.ET 2015
Year: 2015

In active transport molecular communication (ATMC), information particles are actively transported from a transmitter to a receiver using special proteins. Prior work has demonstrated that ATMC can be an attractive and viable solution for on-chip applications. The energy consumption of an ATMC system plays a central role in its design and engineering. In this work, an energy model is presented for ATMC and the model is used to provide guidelines for designing energy efficient systems. The channel capacity per unit energy is analyzed and maximized. It is shown that based on the size of the symbol set and the symbol duration, there is a vesicle size that maximizes rate per unit energy. It is also demonstrated that maximizing rate per unit energy yields very different system parameters compared to maximizing the rate only.
Reasoning About Information Flow Security of Separation Kernels with Channel-based Communication
Venue: arXiv cs.SE 2015
Year: 2015

Assurance of information flow security by formal methods is mandated in security certification of separation kernels. As an industrial standard for separation kernels, ARINC 653 has been complied with by mainstream separation kernels. Security of functionalities defined in ARINC 653 is thus very important for the development and certification of separation kernels. This paper presents the first effort to formally specify and verify separation kernels with ARINC 653 channel-based communication. We provide a reusable formal specification and security proofs for separation kernels in Isabelle/HOL. During reasoning about information flow security, we find some security flaws in the ARINC 653 standard, which can cause information leakage, and fix them in our specification. We also validate the existence of the security flaws in two open-source ARINC 653 compliant separation kernels.
Altmetrics as traces of the computerization of the research process
Venue: arXiv cs.DL 2015
Year: 2015

I propose a broad, multi-dimensional conception of altmetrics, namely as traces of the computerization of the research process. Computerization should be conceived in its broadest sense, including all recent developments in ICT and software, taking place in society as a whole. I distinguish four aspects of the research process: the collection of research data and development of research methods; scientific information processing; communication and organization; and, last but not least, research assessment. I will argue that in each aspect, computerization plays a key role, and metrics are being developed to describe this process. I propose to label the total collection of such metrics as Altmetrics. I seek to provide a theoretical foundation of altmetrics, based on notions developed by Michael Nielsen in his monograph Reinventing Discovery: The New Era of Networked Science. Altmetrics can be conceived as tools for the practical realization of the ethos of science and scholarship in a computerized or digital age.
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders
Venue: arXiv cs.CC 2015
Year: 2015

We study the problem of approximating the quality of a disperser. A bipartite graph $G$ on $([N],[M])$ is a $(ρN,(1-δ)M)$-disperser if for any subset $S\subseteq [N]$ of size $ρN$, the neighbor set $Γ(S)$ contains at least $(1-δ)M$ distinct vertices. Our main results are strong integrality gaps in the Lasserre hierarchy and an approximation algorithm for dispersers. \begin{enumerate} \item For any $α>0$, $δ>0$, and a random bipartite graph $G$ with left degree $D=O(\log N)$, we prove that the Lasserre hierarchy cannot distinguish whether $G$ is an $(N^α,(1-δ)M)$-disperser or not an $(N^{1-α},δM)$-disperser. \item For any $ρ>0$, we prove that there exist infinitely many constants $d$ such that the Lasserre hierarchy cannot distinguish whether a random bipartite graph $G$ with right degree $d$ is a $(ρN, (1-(1-ρ)^d)M)$-disperser or not a $(ρN, (1-Ω(\frac{1-ρ}{ρd + 1-ρ}))M)$-disperser. We also provide an efficient algorithm to find a subset of size exact $ρN$ that has an approximation ratio matching the integrality gap within an extra loss of $\frac{\min\{\fracρ{1-ρ},\frac{1-ρ}ρ\}}{\log d}$. \end{enumerate} Our method gives an integrality gap in the Lasserre hierarchy for bipartite expanders with left degree~$D$. $G$ on $([N],[M])$ is a $(ρN,a)$-expander if for any subset $S\subseteq [N]$ of size $ρN$, the neighbor set $Γ(S)$ contains at least $a \cdot ρN$ distinct vertices. We prove that for any constant $ε>0$, there exist constants $ε'<ε,ρ,$ and $D$ such that the Lasserre hierarchy cannot distinguish whether a bipartite graph on $([N],[M])$ with left degree $D$ is a $(ρN, (1-ε')D)$-expander or not a $(ρN, (1-ε)D)$-expander.
Asymptotic Scaling Laws of Wireless Adhoc Network with Physical Layer Caching
Venue: arXiv cs.IT 2015
Year: 2015

We propose a physical layer (PHY) caching scheme for wireless adhoc networks. The PHY caching exploits cache-assisted multihop gain and cache-induced dual-layer CoMP gain, which substantially improves the throughput of wireless adhoc networks. In particular, the PHY caching scheme contains a novel PHY transmission mode called the cache-induced dual-layer CoMP which can support homogeneous opportunistic CoMP in the wireless adhoc network. Compared with traditional per-node throughput scaling results of Θ\left(1/\sqrt{N}\right), we can achieve O(1) per node throughput for a cached wireless adhoc network with N nodes. Moreover, we analyze the throughput of the PHY caching scheme for regular wireless adhoc networks and study the impact of various system parameters on the PHY caching gain.
Optimization of an electromagnetics code with multicore wavefront diamond blocking and multi-dimensional intra-tile parallelization
Venue: arXiv cs.CE 2015
Year: 2015

Understanding and optimizing the properties of solar cells is becoming a key issue in the search for alternatives to nuclear and fossil energy sources. A theoretical analysis via numerical simulations involves solving Maxwell's Equations in discretized form and typically requires substantial computing effort. We start from a hybrid-parallel (MPI+OpenMP) production code that implements the Time Harmonic Inverse Iteration Method (THIIM) with Finite-Difference Frequency Domain (FDFD) discretization. Although this algorithm has the characteristics of a strongly bandwidth-bound stencil update scheme, it is significantly different from the popular stencil types that have been exhaustively studied in the high performance computing literature to date. We apply a recently developed stencil optimization technique, multicore wavefront diamond tiling with multi-dimensional cache block sharing, and describe in detail the peculiarities that need to be considered due to the special stencil structure. Concurrency in updating the components of the electric and magnetic fields provides an additional level of parallelism. The dependence of the cache size requirement of the optimized code on the blocking parameters is modeled accurately, and an auto-tuner searches for optimal configurations in the remaining parameter space. We were able to completely decouple the execution from the memory bandwidth bottleneck, accelerating the implementation by a factor of three to four compared to an optimal implementation with pure spatial blocking on an 18-core Intel Haswell CPU.
The Scaling Relationship between Citation-Based Performance and Scientific Collaboration in Natural Sciences
Venue: arXiv cs.DL 2015
Year: 2015

The aim of this paper is to extend our knowledge about the power-law relationship between citation-based performance and collaboration patterns for papers of the Natural Sciences domain. We analyzed 829,924 articles that received 16,490,346 citations. The number of articles published through collaboration account for 89%. The citation-based performance and collaboration patterns exhibit a power-law correlation with a scaling exponent of 1.20, SD=0.07. We found that the Matthew effect is stronger for collaborated papers than for single-authored. This means that the citations to a field research areas articles increase 2.30 times each time it doubles the number of collaborative papers. The scaling exponent for the power-law relationship for single-authored papers was 0.85, SD=0.11. The citations to a field research area single-authored articles increase 1.89 times each time the research area doubles the number of non-collaborative papers.
A Proxy Acknowledgement Mechanism for TCP Variants in Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2015
Year: 2015

A sequence number checking technique is proposed to improve the performance of TCP connections in mobile ad hoc networks. While a TCP connection is initialized, a routing protocol takes the responsibility for checking the hop count between a source and destination pair. If the hop count is greater than a predefined value, the routing protocol decides to use a proxy node. The responsibility of a proxy node is to check the correctness of data packets and inform the missing packets by sending an acknowledgement from a proxy node to the source node. By doing so, the source node is able to retransmit any missing packet in advance without waiting until an end-to-end acknowledgement is received from the destination. Simulation results show that the proposed mechanism is able to increase throughput up to 55% in static network and decrease routing overhead up to 95% in mobile network.
The Virtual Splitter: Refactoring Web Applications for the Multiscreen Environment
Venue: arXiv cs.MM 2015
Year: 2015

Creating web applications for the multiscreen environment is still a challenge. One approach is to transform existing single-screen applications but this has not been done yet automatically or generically. This paper proposes a refactor-ing system. It consists of a generic and extensible mapping phase that automatically analyzes the application content based on a semantic or a visual criterion determined by the author or the user, and prepares it for the splitting process. The system then splits the application and as a result delivers two instrumented applications ready for distribution across devices. During runtime, the system uses a mirroring phase to maintain the functionality of the distributed application and to support a dynamic splitting process. Developed as a Chrome extension, our approach is validated on several web applications, including a YouTube page and a video application from Mozilla.
Preprocessing under uncertainty
Venue: arXiv cs.DS 2015
Year: 2015

In this work we study preprocessing for tractable problems when part of the input is unknown or uncertain. This comes up naturally if, e.g., the load of some machines or the congestion of some roads is not known far enough in advance, or if we have to regularly solve a problem over instances that are largely similar, e.g., daily airport scheduling with few charter flights. Unlike robust optimization, which also studies settings like this, our goal lies not in computing solutions that are (approximately) good for every instantiation. Rather, we seek to preprocess the known parts of the input, to speed up finding an optimal solution once the missing data is known. We present efficient algorithms that given an instance with partially uncertain input generate an instance of size polynomial in the amount of uncertain data that is equivalent for every instantiation of the unknown part. Concretely, we obtain such algorithms for Minimum Spanning Tree, Minimum Weight Matroid Basis, and Maximum Cardinality Bipartite Maxing, where respectively the weight of edges, weight of elements, and the availability of vertices is unknown for part of the input. Furthermore, we show that there are tractable problems, such as Small Connected Vertex Cover, for which one cannot hope to obtain similar results.
Towards Patterns for Heaps and Imperative Lambdas
Venue: arXiv cs.PL 2015
Year: 2015

In functional programming, point-free relation calculi have been fruitful for general theories of program construction, but for specific applications pointwise expressions can be more convenient and comprehensible. In imperative programming, refinement calculi have been tied to pointwise expression in terms of state variables, with the curious exception of the ubiquitous but invisible heap. To integrate pointwise with point-free, de Moor and Gibbons extended lambda calculus with non-injective pattern matching interpreted using relations. This article gives a semantics of that language using ``ideal relations'' between partial orders, and a second semantics using predicate transformers. The second semantics is motivated by its potential use with separation algebra, for pattern matching in programs acting on the heap. Laws including lax beta and eta are proved in these models and a number of open problems are posed.
Modern Gyrokinetic Particle-In-Cell Simulation of Fusion Plasmas on Top Supercomputers
Venue: arXiv cs.DC 2015
Year: 2015

The Gyrokinetic Toroidal Code at Princeton (GTC-P) is a highly scalable and portable particle-in-cell (PIC) code. It solves the 5D Vlasov-Poisson equation featuring efficient utilization of modern parallel computer architectures at the petascale and beyond. Motivated by the goal of developing a modern code capable of dealing with the physics challenge of increasing problem size with sufficient resolution, new thread-level optimizations have been introduced as well as a key additional domain decomposition. GTC-P's multiple levels of parallelism, including inter-node 2D domain decomposition and particle decomposition, as well as intra-node shared memory partition and vectorization have enabled pushing the scalability of the PIC method to extreme computational scales. In this paper, we describe the methods developed to build a highly parallelized PIC code across a broad range of supercomputer designs. This particularly includes implementations on heterogeneous systems using NVIDIA GPU accelerators and Intel Xeon Phi (MIC) co-processors and performance comparisons with state-of-the-art homogeneous HPC systems such as Blue Gene/Q. New discovery science capabilities in the magnetic fusion energy application domain are enabled, including investigations of Ion-Temperature-Gradient (ITG) driven turbulence simulations with unprecedented spatial resolution and long temporal duration. Performance studies with realistic fusion experimental parameters are carried out on multiple supercomputing systems spanning a wide range of cache capacities, cache-sharing configurations, memory bandwidth, interconnects and network topologies. These performance comparisons using a realistic discovery-science-capable domain application code provide valuable insights on optimization techniques across one of the broadest sets of current high-end computing platforms worldwide.