OpenRaiser/Intern-Atlas huggingface dataset:
Co-Scheduling Algorithms for High-Throughput Workload Execution
Venue: arXiv cs.DS 2013
Year: 2013

This paper investigates co-scheduling algorithms for processing a set of parallel applications. Instead of executing each application one by one, using a maximum degree of parallelism for each of them, we aim at scheduling several applications concurrently. We partition the original application set into a series of packs, which are executed one by one. A pack comprises several applications, each of them with an assigned number of processors, with the constraint that the total number of processors assigned within a pack does not exceed the maximum number of available processors. The objective is to determine a partition into packs, and an assignment of processors to applications, that minimize the sum of the execution times of the packs. We thoroughly study the complexity of this optimization problem, and propose several heuristics that exhibit very good performance on a variety of workloads, whose application execution times model profiles of parallel scientific codes. We show that co-scheduling leads to to faster workload completion time and to faster response times on average (hence increasing system throughput and saving energy), for significant benefits over traditional scheduling from both the user and system perspectives.
Producibility in hierarchical self-assembly
Venue: arXiv cs.DS 2013
Year: 2013

Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly A is producible. The algorithm can be optimized to use O(|A| log^2 |A|) time. Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow showed that the problem of deciding if an assembly A is the unique producible terminal assembly of a tile system T can be solved in O(|A|^2 |T| + |A| |T|^2) time for the special case of noncooperative "temperature 1" systems. It is shown that this can be improved to O(|A| |T| log |T|) time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently -- i.e., if the positions that they share have the same tile type in each assembly -- then their union is also producible.
Vocalnayno: Designing a Game-Based Intervention to Support Reading Development in Primary Schools
Venue: arXiv cs.CY 2013
Year: 2013

Encouraging children to read frequently and helping them to develop their reading skills as effectively as possible can be a challenge for some primary schools. This research questions whether the use of a game-based intervention can integrate into the existing teaching culture to aid volunteer teaching assistants in achieving a more significant impact on pupil reading development. A prototype based on the initial process of requirements gathering is presented using Multimedia Fusion Developer 2. The design incorporates a game-like exercise where a foam volcano character releases bubbles containing letters and words. Pupils must read these aloud in order to burst them open, which is recorded as a metric of reading ability.
On the Complexity of Query Answering under Matching Dependencies for Entity Resolution
Venue: arXiv cs.DB 2013
Year: 2013

Matching Dependencies (MDs) are a relatively recent proposal for declarative entity resolution. They are rules that specify, given the similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The resolved answers to queries are those that are invariant under the resulting class of resolved instances. In previous work we identified some tractable cases (i.e. for certain classes of queries and MDs) of resolved query answering. In this paper we further investigate the complexity of this problem, identifying some intractable cases. For a special case we obtain a dichotomy complexity result.
A Step-Indexing Approach to Partial Functions
Venue: arXiv cs.LO 2013
Year: 2013

We describe an ACL2 package for defining partial recursive functions that also supports efficient execution. While packages for defining partial recursive functions already exist for other theorem provers, they often require inductive definitions or recursion operators which are not available in ACL2 and they provide little, if any, support for executing the resulting definitions. We use step-indexing as the underlying implementation technology, enabling the definitions to be carried out in first order logic. We also show how recent enhancements to ACL2's guard feature can be used to enable the efficient execution of partial recursive functions.
ACL2 Meets the GPU: Formalizing a CUDA-based Parallelizable All-Pairs Shortest Path Algorithm in ACL2
Venue: arXiv cs.LO 2013
Year: 2013

As Graphics Processing Units (GPUs) have gained in capability and GPU development environments have matured, developers are increasingly turning to the GPU to off-load the main host CPU of numerically-intensive, parallelizable computations. Modern GPUs feature hundreds of cores, and offer programming niceties such as double-precision floating point, and even limited recursion. This shift from CPU to GPU, however, raises the question: how do we know that these new GPU-based algorithms are correct? In order to explore this new verification frontier, we formalized a parallelizable all-pairs shortest path (APSP) algorithm for weighted graphs, originally coded in NVIDIA's CUDA language, in ACL2. The ACL2 specification is written using a single-threaded object (stobj) and tail recursion, as the stobj/tail recursion combination yields the most straightforward translation from imperative programming languages, as well as efficient, scalable executable specifications within ACL2 itself. The ACL2 version of the APSP algorithm can process millions of vertices and edges with little to no garbage generation, and executes at one-sixth the speed of a host-based version of APSP coded in C- a very respectable result for a theorem prover. In addition to formalizing the APSP algorithm (which uses Dijkstra's shortest path algorithm at its core), we have also provided capability that the original APSP code lacked, namely shortest path recovery. Path recovery is accomplished using a secondary ACL2 stobj implementing a LIFO stack, which is proven correct. To conclude the experiment, we ported the ACL2 version of the APSP kernels back to C, resulting in a less than 5% slowdown, and also performed a partial back-port to CUDA, which, surprisingly, yielded a slight performance increase.
Performance of a Multiple-Access DCSK-CC System over Nakagami-$m$ Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a novel cooperative scheme to enhance the performance of multiple-access (MA) differential-chaos-shift-keying (DCSK) systems. We provide the bit-error-rate (BER) performance and throughput analyses for the new system with a decode-and-forward (DF) protocol over Nakagami-$m$ fading channels. Our simulated results not only show that this system significantly improves the BER performance as compared to the existing DCSK non-cooperative (DCSK-NC) system and the multiple-input multiple-output DCSK (MIMO-DCSK) system, but also verify the theoretical analyses. Furthermore, we show that the throughput of this system approximately equals that of the DCSK-NC system, both of which have prominent improvements over the MIMO-DCSK system. We thus believe that the proposed system can be a good framework for chaos-modulation-based wireless communications.
GeoDBLP: Geo-Tagging DBLP for Mining the Sociology of Computer Science
Venue: arXiv cs.SI 2013
Year: 2013

Many collective human activities have been shown to exhibit universal patterns. However, the possibility of universal patterns across timing events of researcher migration has barely been explored at global scale. Here, we show that timing events of migration within different countries exhibit remarkable similarities. Specifically, we look at the distribution governing the data of researcher migration inferred from the web. Compiling the data in itself represents a significant advance in the field of quantitative analysis of migration patterns. Official and commercial records are often access restricted, incompatible between countries, and especially not registered across researchers. Instead, we introduce GeoDBLP where we propagate geographical seed locations retrieved from the web across the DBLP database of 1,080,958 authors and 1,894,758 papers. But perhaps more important is that we are able to find statistical patterns and create models that explain the migration of researchers. For instance, we show that the science job market can be treated as a Poisson process with individual propensities to migrate following a log-normal distribution over the researcher's career stage. That is, although jobs enter the market constantly, researchers are generally not "memoryless" but have to care greatly about their next move. The propensity to make k>1 migrations, however, follows a gamma distribution suggesting that migration at later career stages is "memoryless". This aligns well but actually goes beyond scientometric models typically postulated based on small case studies. On a very large, transnational scale, we establish the first general regularities that should have major implications on strategies for education and research worldwide.
Digenes: genetic algorithms to discover conjectures about directed and undirected graphs
Venue: arXiv cs.DM 2013
Year: 2013

We present Digenes, a new discovery system that aims to help researchers in graph theory. While its main task is to find extremal graphs for a given (function of) invariants, it also provides some basic support in proof conception. This has already been proved to be very useful to find new conjectures since the AutoGraphiX system of Caporossi and Hansen (Discrete Math. 212-2000). However, unlike existing systems, Digenes can be used both with directed or undirected graphs. In this paper, we present the principles and functionality of Digenes, describe the genetic algorithms that have been designed to achieve them, and give some computational results and open questions. This do arise some interesting questions regarding genetic algorithms design particular to this field, such as crossover definition.
Object Oriented Model for Evaluation of On-Chip Networks
Venue: arXiv cs.OH 2013
Year: 2013

The Network on Chip (NoC) paradigm is rapidly replacing bus based System on Chip (SoC) designs due to their inherent disadvantages such as non-scalability, saturation and congestion. Currently very few tools are available for the simulation and evaluation of on-chip architectures. This study proposes a generic object oriented model for performance evaluation of on-chip interconnect architectures and algorithms. The generic nature of the proposed model can help the researchers in evaluation of any kind of on-chip switching networks. The model was applied on 2D-Mesh and 2D-Diagonal-Mesh on-chip switching networks for verification and selection of best out of both the analyzed architectures. The results show the superiority of 2D-Diagonal-Mesh over 2D-Mesh in terms of average packet delay.
Recursive Estimation of Orientation Based on the Bingham Distribution
Venue: arXiv cs.SY 2013
Year: 2013

Directional estimation is a common problem in many tracking applications. Traditional filters such as the Kalman filter perform poorly because they fail to take the periodic nature of the problem into account. We present a recursive filter for directional data based on the Bingham distribution in two dimensions. The proposed filter can be applied to circular filtering problems with 180 degree symmetry, i.e., rotations by 180 degrees cannot be distinguished. It is easily implemented using standard numerical techniques and suitable for real-time applications. The presented approach is extensible to quaternions, which allow tracking arbitrary three-dimensional orientations. We evaluate our filter in a challenging scenario and compare it to a traditional Kalman filtering approach.
Secure Transmission of Password Using Speech Watermarking
Venue: arXiv cs.MM 2013
Year: 2013

Internet is one of the most valuable resources for information communication and retrievals. Most multimedia signals today are in digital formats. The digital data can be duplicated and edited with great ease which has led to a need for data integrity and protection of digital data. The security requirements such as integrity or data authentication can be met by implementing security measures using digital watermarking techniques. In this paper a blind speech watermarking algorithm that embeds the watermark signal data in the musical (sequence) host signal by using frequency masking is used. A different logarithmic approach is proposed. In this regard a logarithmic function is first applied to watermark data. Then the transformed signal is embedded to the converted version of host signal which is obtained by applying Fast Fourier transform method. Finally using inverse Fast Fourier Transform and antilogarithmic function watermark signal is retrieved.
From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we devise an optimal construction of fault-tolerant spanners for doubling metrics. Specifically, for any $n$-point doubling metric, any $\eps > 0$, and any integer $0 \le k \le n-2$, our construction provides a $k$-fault-tolerant $(1+\eps)$-spanner with optimal degree $O(k)$ within optimal time $O(n \log n + k n)$. We then strengthen this result to provide near-optimal (up to a factor of $\log k$) guarantees on the diameter and weight of our spanners, namely, diameter $O(\log n)$ and weight $O(k^2 + k \log n) \cdot ω(MST)$, while preserving the optimal guarantees on the degree $O(k)$ and the running time $O(n \log n + k n)$. Our result settles several fundamental open questions in this area, culminating a long line of research that started with the STOC'95 paper of Arya et al.\ and the STOC'98 paper of Levcopoulos et al. On the way to this result we develop a new technique for constructing spanners in doubling metrics. Our spanner construction is based on a novel \emph{hierarchical cover} of the metric, whereas most previous constructions of spanners for doubling and Euclidean metrics (such as the net-tree spanner) are based on \emph{hierarchical partitions} of the metric. We demonstrate the power of hierarchical covers in the context of geometric spanners by improving the state-of-the-art results in this area.
Truth versus information in logic programming
Venue: arXiv cs.LO 2013
Year: 2013

The semantics of logic programs was originally described in terms of two-valued logic. Soon, however, it was realised that three-valued logic had some natural advantages, as it provides distinct values not only for truth and falsehood, but also for "undefined". The three-valued semantics proposed by Fitting and by Kunen are closely related to what is computed by a logic program, the third truth value being associated with non-termination. A different three-valued semantics, proposed by Naish, shared much with those of Fitting and Kunen but incorporated allowances for programmer intent, the third truth value being associated with underspecification. Naish used an (apparently) novel "arrow" operator to relate the intended meaning of left and right sides of predicate definitions. In this paper we suggest that the additional truth values of Fitting/Kunen and Naish are best viewed as duals. We use Belnap's four-valued logic, also used elsewhere by Fitting, to unify the two three-valued approaches. The truth values are arranged in a bilattice which supports the classical ordering on truth values as well as the "information ordering". We note that the "arrow" operator of Naish (and our four-valued extension) is essentially the information ordering, whereas the classical arrow denotes the truth ordering. This allows us to shed new light on many aspects of logic programming, including program analysis, type and mode systems, declarative debugging and the relationships between specifications and programs, and successive executions states of a program. This paper is to appear in Theory and Practice of Logic Programming (TPLP).
Benefits of Semantics on Web Service Composition from a Complex Network Perspective
Venue: arXiv cs.SI 2013
Year: 2013

The number of publicly available Web services (WS) is continuously growing, and in parallel, we are witnessing a rapid development in semantic-related web technologies. The intersection of the semantic web and WS allows the development of semantic WS. In this work, we adopt a complex network perspective to perform a comparative analysis of the syntactic and semantic approaches used to describe WS. From a collection of publicly available WS descriptions, we extract syntactic and semantic WS interaction networks. We take advantage of tools from the complex network field to analyze them and determine their properties. We show that WS interaction networks exhibit some of the typical characteristics observed in real-world networks, such as short average distance between nodes and community structure. By comparing syntactic and semantic networks through their properties, we show the introduction of semantics in WS descriptions should improve the composition process.
Similartity Network For Semantic Web Services Substitution
Venue: arXiv cs.SE 2013
Year: 2013

Web services substitution is one of the most challenging tasks for automating the composition process of multiple Web services. It aims to improve performances and to deal efficiently with Web services failures. Many existing solutions have approached the problem through classification of substitutable Web services. To go a step further, we propose in this paper a network based approach where nodes are Web services operations and links join similar operations. Four similarity measures based on the comparison of input and output parameters values of Web services operations are presented. A comparative evaluation of the topological structure of the corresponding networks is performed on a benchmark of semantically annotated Web services. Results show that this approach allows a more detailed analysis of substitutable Web services.
Video Segmentation via Diffusion Bases
Venue: arXiv cs.CV 2013
Year: 2013

Identifying moving objects in a video sequence, which is produced by a static camera, is a fundamental and critical task in many computer-vision applications. A common approach performs background subtraction, which identifies moving objects as the portion of a video frame that differs significantly from a background model. A good background subtraction algorithm has to be robust to changes in the illumination and it should avoid detecting non-stationary background objects such as moving leaves, rain, snow, and shadows. In addition, the internal background model should quickly respond to changes in background such as objects that start to move or stop. We present a new algorithm for video segmentation that processes the input video sequence as a 3D matrix where the third axis is the time domain. Our approach identifies the background by reducing the input dimension using the \emph{diffusion bases} methodology. Furthermore, we describe an iterative method for extracting and deleting the background. The algorithm has two versions and thus covers the complete range of backgrounds: one for scenes with static backgrounds and the other for scenes with dynamic (moving) backgrounds.
Testing Hypotheses by Regularized Maximum Mean Discrepancy
Venue: arXiv cs.LG 2013
Year: 2013

Do two data samples come from different distributions? Recent studies of this fundamental problem focused on embedding probability distributions into sufficiently rich characteristic Reproducing Kernel Hilbert Spaces (RKHSs), to compare distributions by the distance between their embeddings. We show that Regularized Maximum Mean Discrepancy (RMMD), our novel measure for kernel-based hypothesis testing, yields substantial improvements even when sample sizes are small, and excels at hypothesis tests involving multiple comparisons with power control. We derive asymptotic distributions under the null and alternative hypotheses, and assess power control. Outstanding results are obtained on: challenging EEG data, MNIST, the Berkley Covertype, and the Flare-Solar dataset.
An $S$-adic characterization of minimal subshifts with first difference of complexity $1 \leq p(n+1) - p(n) \leq 2$
Venue: arXiv cs.DM 2013
Year: 2013

In [Ergodic Theory Dynam. System, 16 (1996) 663--682], S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is $S$-adic with $\card S \leq 3^{27}$. In this paper, we improve this result by giving an $S$-adic charaterization of these subshifts with a set $S$ of 5 morphisms, solving by this way the $S$-adic conjecture for this particular case.
Efficient routing on multilayered communication networks
Venue: arXiv cs.NI 2013
Year: 2013

We study the optimal routing on multilayered communication networks, which are composed of two layers of subnetworks. One is a wireless network, and the other is a wired network. We develop a simple recurrent algorithm to find an optimal routing on this kind of multilayered network, where the single-channel transmission mode and the multichannel transmission mode used on the wireless subnetwork are considered, respectively. Compared with the performance of the shortest path algorithm, our algorithm can significantly enhance the transport capacity. We show that our methods proposed in this letter could take advantage of the coupling of the two layers to the most extent, so that the wireless subnetwork could sufficiently utilize the wired subnetwork for transportation.
Hub-Accelerator: Fast and Exact Shortest Path Computation in Large Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Shortest path computation is one of the most fundamental operations for managing and analyzing large social networks. Though existing techniques are quite effective for finding the shortest path on large but sparse road networks, social graphs have quite different characteristics: they are generally non-spatial, non-weighted, scale-free, and they exhibit small-world properties in addition to their massive size. In particular, the existence of hubs, those vertices with a large number of connections, explodes the search space, making the shortest path computation surprisingly challenging. In this paper, we introduce a set of novel techniques centered around hubs, collectively referred to as the Hub-Accelerator framework, to compute the k-degree shortest path (finding the shortest path between two vertices if their distance is within k). These techniques enable us to significantly reduce the search space by either greatly limiting the expansion scope of hubs (using the novel distance- preserving Hub-Network concept) or completely pruning away the hubs in the online search (using the Hub2-Labeling approach). The Hub-Accelerator approaches are more than two orders of magnitude faster than BFS and the state-of-the-art approximate shortest path method Sketch for the shortest path computation. The Hub- Network approach does not introduce additional index cost with light pre-computation cost; the index size and index construction cost of Hub2-Labeling are also moderate and better than or comparable to the approximation indexing Sketch method.