OpenRaiser/Intern-Atlas huggingface dataset:
A Graph-Partition-Based Scheduling Policy for Heterogeneous Architectures
Venue: arXiv cs.DC 2015
Year: 2015

In order to improve system performance efficiently, a number of systems choose to equip multi-core and many-core processors (such as GPUs). Due to their discrete memory these heterogeneous architectures comprise a distributed system within a computer. A data-flow programming model is attractive in this setting for its ease of expressing concurrency. Programmers only need to define task dependencies without considering how to schedule them on the hardware. However, mapping the resulting task graph onto hardware efficiently remains a challenge. In this paper, we propose a graph-partition scheduling policy for mapping data-flow workloads to heterogeneous hardware. According to our experiments, our graph-partition-based scheduling achieves comparable performance to conventional queue-base approaches.
Simple and Efficient Secret Sharing Schemes for Sharing Data and Image
Venue: arXiv cs.CR 2015
Year: 2015

Secret sharing is a new alternative for outsourcing data in a secure way.It avoids the need for time consuming encryption decryption process and also the complexity involved in key management.The data must also be protected from untrusted cloud service providers.Secret sharing based solution provides secure information dispersal by making shares of the original data and distribute them among different servers.Data from the threshold number of servers can be used to reconstruct the original data.It is often impractical to distribute data among large number of servers.We have to achieve a trade off between security and efficiency.An optimal choice is to use a $(2,3)$ or $(2,4)$ threshold secret sharing scheme, where the data are distributed as shares among three or four servers and shares from any two can be used to construct the original data.This provides both security,reliability and efficiency.We propose some efficient and easy to implement secret sharing schemes in this regard based on number theory and bitwise XOR.These schemes are also suitable for secure sharing of images.Secret image sharing based on Shamir's schemes are lossy and involves complicated Lagrange interpolation.So the proposed scheme can also be effectively utilized for lossless sharing of secret images.
Rainbow domination and related problems on some classes of perfect graphs
Venue: arXiv cs.DM 2015
Year: 2015

Let $k \in \mathbb{N}$ and let $G$ be a graph. A function $f: V(G) \rightarrow 2^{[k]}$ is a rainbow function if, for every vertex $x$ with $f(x)=\emptyset$, $f(N(x)) =[k]$. The rainbow domination number $γ_{kr}(G)$ is the minimum of $\sum_{x \in V(G)} |f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.
Object-Oriented Networking
Venue: arXiv cs.NI 2015
Year: 2015

We propose the object-oriented networking (OON) framework, for meeting the generalized interconnection, mobility and technology integration requirements underlining the Internet. In OON, the various objects that need to be accessed through the Internet (content, smart things, services, people, etc.) are viewed as network layer resources, rather than as application layer resources as in the IP communications model. By abstracting them as computing objects -with attributes and methods- they are identified by expressive, discoverable names, while data are exchanged between them in the context of their methods, based on suitably defined system-specific names. An OON-enabled Internet is not only a global data delivery medium but also a universal object discovery and service development platform; service-level interactions can be realized through native network means, without requiring standardized protocols. OON can be realized through existing software-defined networking or network functions virtualization technologies and it can be deployed in an incremental fashion.
Factorization of Motion Polynomials
Venue: arXiv cs.SC 2015
Year: 2015

In this paper, we consider the existence of a factorization of a monic, bounded motion polynomial. We prove existence of factorizations, possibly after multiplication with a real polynomial and provide algorithms for computing polynomial factor and factorizations. The first algorithm is conceptually simpler but may require a high degree of the polynomial factor. The second algorithm gives an optimal degree.
CppSs -- a C++ Library for Efficient Task Parallelism
Venue: arXiv cs.DC 2015
Year: 2015

We present the C++ library CppSs (C++ super-scalar), which provides efficient task-parallelism without the need for special compilers or other software. Any C++ compiler that supports C++11 is sufficient. CppSs features different directionality clauses for defining data dependencies. While the variable argument lists of the taskified functions are evaluated at compile time, the resulting task dependencies are fixed by the runtime value of the arguments and are thus analysed at runtime. With CppSs, we provide task-parallelism using merely native C++.
Landmark-Guided Elastic Shape Analysis of Human Character Motions
Venue: arXiv cs.CV 2015
Year: 2015

Motions of virtual characters in movies or video games are typically generated by recording actors using motion capturing methods. Animations generated this way often need postprocessing, such as improving the periodicity of cyclic animations or generating entirely new motions by interpolation of existing ones. Furthermore, search and classification of recorded motions becomes more and more important as the amount of recorded motion data grows. In this paper, we will apply methods from shape analysis to the processing of animations. More precisely, we will use the by now classical elastic metric model used in shape matching, and extend it by incorporating additional inexact feature point information, which leads to an improved temporal alignment of different animations.
Tracking an Object with Unknown Accelerations using a Shadowing Filter
Venue: arXiv cs.SY 2015
Year: 2015

A commonly encountered problem is the tracking of a physical object, like a maneuvering ship, aircraft, land vehicle, spacecraft or animate creature carrying a wireless device. The sensor data is often limited and inaccurate observations of range or bearing. This problem is more difficult than tracking a ballistic trajectory, because an operative affects unknown and arbitrarily changing accelerations. Although stochastic methods of filtering or state estimation (Kalman filters and particle filters) are widely used, out of vogue variational methods are more appropriate in this tracking context, because the objects do not typically display any significant random motions at the length and time scales of interest. This leads us to propose a rather elegant approach based on a \emph{shadowing filter}. The resulting filter is efficient (reduces to the solution of linear equations) and robust (uneffected by missing data and singular correlations that would cause catastrophic failure of Bayesian filters.) The tracking is so robust, that in some common situations it actually performs better by ignoring error correlations that are so vital to Kalman filters.
Anonymous HIBE with Short Ciphertexts: Full Security in Prime Order Groups
Venue: arXiv cs.CR 2015
Year: 2015

Anonymous Hierarchical Identity-Based Encryption (HIBE) is an extension of Identity-Based Encryption (IBE), and it provides not only a message hiding property but also an identity hiding property. Anonymous HIBE schemes can be applicable to anonymous communication systems and public key encryption systems with keyword searching. However, previous anonymous HIBE schemes have some disadvantages that the security was proven in the weaker model, the size of ciphertexts is not short, or the construction was based on composite order bilinear groups. In this paper, we propose the first efficient anonymous HIBE scheme with short ciphertexts in prime order (asymmetric) bilinear groups, and prove its security in the full model with an efficient reduction. To achieve this, we use the dual system encryption methodology of Waters. We also present the benchmark results of our scheme by measuring the performance of our implementation.
File Updates Under Random/Arbitrary Insertions And Deletions
Venue: arXiv cs.IT 2015
Year: 2015

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.
Inferring an Indeterminate String from a Prefix Graph
Venue: arXiv cs.DS 2015
Year: 2015

An \itbf{indeterminate string} (or, more simply, just a \itbf{string}) $\s{x} = \s{x}[1..n]$ on an alphabet $Σ$ is a sequence of nonempty subsets of $Σ$. We say that $\s{x}[i_1]$ and $\s{x}[i_2]$ \itbf{match} (written $\s{x}[i_1] \match \s{x}[i_2]$) if and only if $\s{x}[i_1] \cap \s{x}[i_2] \ne \emptyset$. A \itbf{feasible array} is an array $\s{y} = \s{y}[1..n]$ of integers such that $\s{y}[1] = n$ and for every $i \in 2..n$, $\s{y}[i] \in 0..n\- i\+ 1$. A \itbf{prefix table} of a string $\s{x}$ is an array $\sπ = \sπ[1..n]$ of integers such that, for every $i \in 1..n$, $\sπ[i] = j$ if and only if $\s{x}[i..i\+ j\- 1]$ is the longest substring at position $i$ of \s{x} that matches a prefix of \s{x}. It is known from \cite{CRSW13} that every feasible array is a prefix table of some indetermintate string. A \itbf{prefix graph} $\mathcal{P} = \mathcal{P}_{\s{y}}$ is a labelled simple graph whose structure is determined by a feasible array \s{y}. In this paper we show, given a feasible array \s{y}, how to use $\mathcal{P}_{\s{y}}$ to construct a lexicographically least indeterminate string on a minimum alphabet whose prefix table $\sπ = \s{y}$.
Is Nearly-linear the same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver
Venue: arXiv cs.DS 2015
Year: 2015

Linear system solving is one of the main workhorses in applied mathematics. Recently, theoretical computer scientists have contributed sophisticated algorithms for solving linear systems with symmetric diagonally dominant matrices (a class to which Laplacian matrices belong) in provably nearly-linear time. While these algorithms are highly interesting from a theoretical perspective, there are no published results how they perform in practice. With this paper we address this gap. We provide the first implementation of the combinatorial solver by [Kelner et al., STOC 2013], which is particularly appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix corresponds to a graph; solving Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our comprehensive experimental study are ambivalent. They confirm a nearly-linear running time, but for reasonable inputs the constant factors make the solver much slower than methods with higher asymptotic complexity. One other aspect predicted by theory is confirmed by our findings, though: Spanning trees with lower stretch indeed reduce the solver's running time. Yet, simple spanning tree algorithms perform in practice better than those with a guaranteed low stretch.
A Convex Feasibility Approach to Anytime Model Predictive Control
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes to decouple performance optimization and enforcement of asymptotic convergence in Model Predictive Control (MPC) so that convergence to a given terminal set is achieved independently of how much performance is optimized at each sampling step. By embedding an explicit decreasing condition in the MPC constraints and thanks to a novel and very easy-to-implement convex feasibility solver proposed in the paper, it is possible to run an outer performance optimization algorithm on top of the feasibility solver and optimize for an amount of time that depends on the available CPU resources within the current sampling step (possibly going open-loop at a given sampling step in the extreme case no resources are available) and still guarantee convergence to the terminal set. While the MPC setup and the solver proposed in the paper can deal with quite general classes of functions, we highlight the synthesis method and show numerical results in case of linear MPC and ellipsoidal and polyhedral terminal sets.
Infinigons of the hyperbolic plane and grossone
Venue: arXiv cs.DM 2015
Year: 2015

In this paper, we study the contribution of the theory of grossone to the study of infinigons in the hyperbolic plane. We can see that the theory of grossone can help us to obtain much more classification for these objects than in the traditional setting.
Secret Image Sharing Based CTS with Cheating Detection
Venue: arXiv cs.CR 2015
Year: 2015

Cheque Truncation System(CTS) is an automatic cheque clearance system implemented by RBI.CTS uses cheque image, instead of the physical cheque itself, for cheque clearance thus reducing the turn around time drastically. This approach holds back the physical movement of cheque from presenting bank to the drawee bank. In CTS, digital image of the cheque is protected using standard public key and symmetric key encryptions like RSA, triple DES etc. This involves a lot of computation overhead and key management. The security also depends on the hard mathematical problem and is only computationally secure.Information theoretically secure, secret image sharing techniques can be used in the CTS for the secure and efficient processing of cheque image .In this paper, we propose two simple and efficient secret image sharing schemes and a Cheque Truncation System based on these algorithms . In the proposed scheme,the presenting bank is acting as the dealer and the participants are the customer, and the drawee bank.The dealer should generate the shares of cheque and distributes it to customer and drawee bank.The validity of the shares are important during the reconstruction process. The proposed scheme also suggests a method for cheating detection which identify any invalid shares submitted by the customers, using the hashing technique. The experimental results shows that the proposed scheme is efficient and secure compared with the existing scheme.
An Effective Private Data storage and Retrieval System using Secret sharing scheme based on Secure Multi-party Computation
Venue: arXiv cs.CR 2015
Year: 2015

Privacy of the outsourced data is one of the major challenge.Insecurity of the network environment and untrustworthiness of the service providers are obstacles of making the database as a service.Collection and storage of personally identifiable information is a major privacy concern.On-line public databases and resources pose a significant risk to user privacy, since a malicious database owner may monitor user queries and infer useful information about the customer.The challenge in data privacy is to share data with third-party and at the same time securing the valuable information from unauthorized access and use by third party.A Private Information Retrieval(PIR) scheme allows a user to query database while hiding the identity of the data retrieved.The naive solution for confidentiality is to encrypt data before outsourcing.Query execution,key management and statistical inference are major challenges in this case.The proposed system suggests a mechanism for secure storage and retrieval of private data using the secret sharing technique.The idea is to develop a mechanism to store private information with a highly available storage provider which could be accessed from anywhere using queries while hiding the actual data values from the storage provider.The private information retrieval system is implemented using Secure Multi-party Computation(SMC) technique which is based on secret sharing. Multi-party Computation enable parties to compute some joint function over their private inputs.The query results are obtained by performing a secure computation on the shares owned by the different servers.
Sparse Time-Frequency Representation for Signals with Fast Varying Instantaneous Frequency
Venue: arXiv cs.IT 2015
Year: 2015

Time-frequency distributions have been used to provide high resolution representation in a large number of signal processing applications. However, high resolution and accurate instantaneous frequency (IF) estimation usually depend on the employed distribution and complexity of signal phase function. To ensure an efficient IF tracking for various types of signals, the class of complex time distributions has been developed. These distributions facilitate analysis in the cases when standard distributions cannot provide satisfactory results (e.g., for highly nonstationary signal phase). In that sense, an ambiguity based form of the forth order complex-time distribution is considered, in a new compressive sensing (CS) context. CS is an intensively growing approach in signal processing that allows efficient analysis and reconstruction of randomly undersampled signals. In this paper, the randomly chosen ambiguity domain coefficients serve as CS measurements. By exploiting sparsity in the time-frequency plane, it is possible to obtain highly concentrated IF using just small number of random coefficients from ambiguity domain. Moreover, in noisy signal case, this CS approach can be efficiently combined with the L-statistics producing robust time-frequency representations. Noisy coefficients are firstly removed using the L-statistics and then reconstructed by using CS algorithm. The theoretical considerations are illustrated using experimental results.
On the Energy Complexity of LDPC Decoder Circuits
Venue: arXiv cs.IT 2015
Year: 2015

It is shown that in a sequence of randomly generated bipartite configurations with number of left nodes approaching infinity, the probability that a particular configuration in the sequence has a minimum bisection width proportional to the number of vertices in the configuration approaches $1$ so long as a sufficient condition on the node degree distribution is satisfied. This graph theory result implies an almost sure $Ω\left(n^{2}\right)$ scaling rule for the energy of capacity-approaching LDPC decoder circuits that directly instantiate their Tanner Graphs and are generated according to a uniform configuration model, where $n$ is the block length of the code. For a sequence of circuits that have a full set of check nodes but do not necessarily directly instantiate a Tanner graph, this implies an $Ω\left(n^{1.5}\right)$ scaling rule. In another theorem, it is shown that all (as opposed to almost all) capacity-approaching LDPC decoding circuits that directly implement their Tanner graphs must have energy that scales as $Ω\left(n\left(\log n\right)^{2}\right)$. These results further imply scaling rules for the energy of LDPC decoder circuits as a function of gap to capacity.
Tropical differential equations
Venue: arXiv cs.SC 2015
Year: 2015

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed. We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is $NP$-hard, and this problem for arbitrary number of variables belongs to $NP$. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.
Activity Recognition Using A Combination of Category Components And Local Models for Video Surveillance
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a novel approach for automatic recognition of human activities for video surveillance applications. We propose to represent an activity by a combination of category components, and demonstrate that this approach offers flexibility to add new activities to the system and an ability to deal with the problem of building models for activities lacking training data. For improving the recognition accuracy, a Confident-Frame- based Recognition algorithm is also proposed, where the video frames with high confidence for recognizing an activity are used as a specialized local model to help classify the remainder of the video frames. Experimental results show the effectiveness of the proposed approach.
Task-Oriented Learning of Word Embeddings for Semantic Relation Classification
Venue: arXiv cs.CL 2015
Year: 2015

We present a novel learning method for word embeddings designed for relation classification. Our word embeddings are trained by predicting words between noun pairs using lexical relation-specific features on a large unlabeled corpus. This allows us to explicitly incorporate relation-specific information into the word embeddings. The learned word embeddings are then used to construct feature vectors for a relation classification model. On a well-established semantic relation classification task, our method significantly outperforms a baseline based on a previously introduced word embedding method, and compares favorably to previous state-of-the-art models that use syntactic information or manually constructed external resources.
Task Allocation in Robotic Swarms: Explicit Communication Based Approaches
Venue: arXiv cs.MA 2015
Year: 2015

In this paper we study multi robot cooperative task allocation issue in a situation where a swarm of robots is deployed in a confined unknown environment where the number of colored spots which represent tasks and the ratios of them are unknown. The robots should cover this spots as far as possible to do cleaning and sampling actions desirably. It means that they should discover the spots cooperatively and spread proportional to the spots area and avoid from remaining idle. We proposed 4 self-organized distributed methods which are called hybrid methods for coping with this scenario. In two different experiments the performance of the methods is analyzed. We compared them with each other and investigated their scalability and robustness in term of single point of failure.
Distributed Cloud Association in Downlink Multicloud Radio Access Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a multicloud radio access network (M-CRAN), wherein each cloud serves a cluster of base-stations (BS's) which are connected to the clouds through high capacity digital links. The network comprises several remote users, where each user can be connected to one (and only one) cloud. This paper studies the user-to-cloud-assignment problem by maximizing a network-wide utility subject to practical cloud connectivity constraints. The paper solves the problem by using an auction-based iterative algorithm, which can be implemented in a distributed fashion through a reasonable exchange of information between the clouds. The paper further proposes a centralized heuristic algorithm, with low computational complexity. Simulations results show that the proposed algorithms provide appreciable performance improvements as compared to the conventional cloud-less assignment solutions.