OpenRaiser/Intern-Atlas huggingface dataset:
Towards combinatorial clustering: preliminary research survey
Venue: arXiv cs.AI 2015
Year: 2015

The paper describes clustering problems from the combinatorial viewpoint. A brief systemic survey is presented including the following: (i) basic clustering problems (e.g., classification, clustering, sorting, clustering with an order over cluster), (ii) basic approaches to assessment of objects and object proximities (i.e., scales, comparison, aggregation issues), (iii) basic approaches to evaluation of local quality characteristics for clusters and total quality characteristics for clustering solutions, (iv) clustering as multicriteria optimization problem, (v) generalized modular clustering framework, (vi) basic clustering models/methods (e.g., hierarchical clustering, k-means clustering, minimum spanning tree based clustering, clustering as assignment, detection of clisue/quasi-clique based clustering, correlation clustering, network communities based clustering), Special attention is targeted to formulation of clustering as multicriteria optimization models. Combinatorial optimization models are used as auxiliary problems (e.g., assignment, partitioning, knapsack problem, multiple choice problem, morphological clique problem, searching for consensus/median for structures). Numerical examples illustrate problem formulations, solving methods, and applications. The material can be used as follows: (a) a research survey, (b) a fundamental for designing the structure/architecture of composite modular clustering software, (c) a bibliography reference collection, and (d) a tutorial.
Fast Computation of PERCLOS and Saccadic Ratio
Venue: arXiv cs.CV 2015
Year: 2015

This thesis describes the development of fast algorithms for the computation of PERcentage CLOSure of eyes (PERCLOS) and Saccadic Ratio (SR). PERCLOS and SR are two ocular parameters reported to be measures of alertness levels in human beings. PERCLOS is the percentage of time in which at least 80% of the eyelid remains closed over the pupil. Saccades are fast and simultaneous movement of both the eyes in the same direction. SR is the ratio of peak saccadic velocity to the saccadic duration. This thesis addresses the issues of image based estimation of PERCLOS and SR, prevailing in the literature such as illumination variation, poor illumination conditions, head rotations etc. In this work, algorithms for real-time PERCLOS computation has been developed and implemented on an embedded platform. The platform has been used as a case study for assessment of loss of attention in automotive drivers. The SR estimation has been carried out offline as real-time implementation requires high frame rates of processing which is difficult to achieve due to hardware limitations. The accuracy in estimation of the loss of attention using PERCLOS and SR has been validated using brain signals, which are reported to be an authentic cue for estimating the state of alertness in human beings. The major contributions of this thesis include database creation, design and implementation of fast algorithms for estimating PERCLOS and SR on embedded computing platforms.
Security-Reliability Trade-off Analysis of Multi-Relay Aided Decode-and-Forward Cooperation Systems
Venue: arXiv cs.IT 2015
Year: 2015

We consider a cooperative wireless network comprised of a source, a destination and multiple relays operating in the presence of an eavesdropper, which attempts to tap the source-destination transmission. We propose multi-relay selection scheme for protecting the source against eavesdropping. More specifically, multi-relay selection allows multiple relays to simultaneously forward the source's transmission to the destination, differing from the conventional single-relay selection where only the best relay is chosen to assist the transmission from the source to destination. For the purpose of comparison, we consider the classic direct transmission and single-relay selection as benchmark schemes. We derive closed-form expressions of the intercept probability and outage probability for the direct transmission as well as for the single-relay and multi-relay selection schemes over Rayleigh fading channels. It is demonstrated that as the outage requirement is relaxed, the intercept performance of the three schemes improves and vice versa, implying that there is a \emph{security versus reliability trade-off} (SRT). We also show that both the single-relay and multi-relay selection schemes outperform the direct transmission in terms of SRT, demonstrating the advantage of the relay selection schemes for protecting the source's transmission against the eavesdropping attacks. Finally, upon increasing the number of relays, the SRTs of both the single-relay and multi-relay selection schemes improve significantly and as expected, multi-relay selection outperforms single-relay selection.
Heisenberg-like and Fisher-information-based uncertainty relations for $N$-electron $d$-dimensional systems
Venue: arXiv cs.IT 2015
Year: 2015

Heisenberg-like and Fisher-information-based uncertainty relations which extend and generalize previous similar expressions are obtained for $N$-fermion $d$-dimensional systems. The contributions of both spatial and spin degrees of freedom are taken into account. The accuracy of some of these generalized spinned uncertainty-like relations is numerically examined for a large number of atomic and molecular systems.
Research on the fast Fourier transform of image based on GPU
Venue: arXiv cs.MS 2015
Year: 2015

Study of general purpose computation by GPU (Graphics Processing Unit) can improve the image processing capability of micro-computer system. This paper studies the parallelism of the different stages of decimation in time radix 2 FFT algorithm, designs the butterfly and scramble kernels and implements 2D FFT on GPU. The experiment result demonstrates the validity and advantage over general CPU, especially in the condition of large input size. The approach can also be generalized to other transforms alike.
The Research and Optimization of Parallel Finite Element Algorithm based on MiniFE
Venue: arXiv cs.DC 2015
Year: 2015

Finite element method (FEM) is one of the most important numerical methods in modern engineering design and analysis. Since traditional serial FEM is difficult to solve large FE problems efficiently and accurately, high-performance parallel FEM has become one of the essential way to solve practical engineering problems. Based on MiniFE program, which is released by National Energy Research Scientific Computing Center(NERSC), this work analyzes concrete steps, key computing pattern and parallel mechanism of parallel FEM. According to experimental results, this work analyzes the proportion of calculation amount of each module and concludes the main performance bottleneck of the program. Based on that, we optimize the MiniFE program on a server platform. The optimization focuses on the bottleneck of the program - SpMV kernel, and uses an efficient storage format named BCRS. Moreover, an improving plan of hybrid MPI+OpenMP programming is provided. Experimental results show that the optimized program performs better in both SpMV kernel and synchronization. It can increase the performance of the program, on average, by 8.31%. Keywords : finite element, parallel, MiniFE, SpMV, performance optimization
Efficient FFT mapping on GPU for radar processing application: modeling and implementation
Venue: arXiv cs.MS 2015
Year: 2015

General-purpose multiprocessors (as, in our case, Intel IvyBridge and Intel Haswell) increasingly add GPU computing power to the former multicore architectures. When used for embedded applications (for us, Synthetic aperture radar) with intensive signal processing requirements, they must constantly compute convolution algorithms, such as the famous Fast Fourier Transform. Due to its "fractal" nature (the typical butterfly shape, with larger FFTs defined as combination of smaller ones with auxiliary data array transpose functions), one can hope to compute analytically the size of the largest FFT that can be performed locally on an elementary GPU compute block. Then, the full application must be organized around this given building block size. Now, due to phenomena involved in the data transfers between various memory levels across CPUs and GPUs, the optimality of such a scheme is only loosely predictable (as communications tend to overcome in time the complexity of computations). Therefore a mix of (theoretical) analytic approach and (practical) runtime validation is here needed. As we shall illustrate, this occurs at both stage, first at the level of deciding on a given elementary FFT block size, then at the full application level.
Towards Trace Metrics via Functor Lifting
Venue: arXiv cs.LO 2015
Year: 2015

We investigate the possibility of deriving metric trace semantics in a coalgebraic framework. First, we generalize a technique for systematically lifting functors from the category Set of sets to the category PMet of pseudometric spaces, showing under which conditions also natural transformations, monads and distributive laws can be lifted. By exploiting some recent work on an abstract determinization, these results enable the derivation of trace metrics starting from coalgebras in Set. More precisely, for a coalgebra on Set we determinize it, thus obtaining a coalgebra in the Eilenberg-Moore category of a monad. When the monad can be lifted to PMet, we can equip the final coalgebra with a behavioral distance. The trace distance between two states of the original coalgebra is the distance between their images in the determinized coalgebra through the unit of the monad. We show how our framework applies to nondeterministic automata and probabilistic automata.
Formation Stabilization with Collision Avoidance of Complex Systems
Venue: arXiv cs.SY 2015
Year: 2015

Two different aspects of formation control of multiple agents subjected to linear transformation have been addressed in this paper. We consider a set of complex single integrator systems so that the dimension of the system reduces to half as opposed to the vector representation in Cartesian coordinate system. We first design a stable formation controller in an attempt to solve the formation control turned to stabilization problem and then find a collision avoidance controller in the transformed domain, respectively. Different linear transformations are used to facilitate the formation control task in a different way. For example Jacobi transformation is used to separate the shape control and trajectory control. The inverse of the transformation must have nonzero eigenvalues with both positive and negative real parts which may lead the system to instability. If the inverse of the transformation appears in closed loop then a diagonal stabilizing matrix is required to reassign the eigenvalues of the inverse of transformation in the right half of complex plane. The algorithm to find such stabilizing matrix is provided. We then define a matrix of potential in the actual domain which is the stepping stone to find a matrix of potential in the transformed domain. Thus collision avoidance controller can be designed directly in the transformed domain. The mathematical proof is given that both the actual and transformed system behaves identically. Simulation results are provided to support our claim.
Dynamic Modeling for Representing Access Control Policies Effect
Venue: arXiv cs.CR 2015
Year: 2015

In large databases, creating user interface for browsing or performing insertion, deletion or modification of data is very costly in terms of programming. In addition, each modification of an access control policy causes many potential and unpredictable side effects which cause rule conflicts or security breaches that affect the corresponding user interfaces as well. While changes to access control policies in databases are inevitable, having a dynamic system that generates interface according to the latest access control policies become increasingly valuable. Lack of such a system leads to unauthorized access to data and eventually violates the privacy of data owners. In this work, we discuss a dynamic interface that applies Role Based Access Control (RBAC) policies as the output of policy analysis and limits the amount of information that users have access according to the policies defined for roles. This interface also shows security administrators the effect of their changes from the user's point of view while minimizing the cost by generating the interface automatically.
Variance Analysis for Monte Carlo Integration: A Representation-Theoretic Perspective
Venue: arXiv cs.GR 2015
Year: 2015

In this report, we revisit the work of Pilleboue et al. [2015], providing a representation-theoretic derivation of the closed-form expression for the expected value and variance in homogeneous Monte Carlo integration. We show that the results obtained for the variance estimation of Monte Carlo integration on the torus, the sphere, and Euclidean space can be formulated as specific instances of a more general theory. We review the related representation theory and show how it can be used to derive a closed-form solution.
Linear Matrix Inequalities for Ultimate Boundedness of Dynamical Systems with Conic Uncertain/Nonlinear Terms
Venue: arXiv cs.SY 2015
Year: 2015

This note introduces a sufficient Linear Matrix Inequality (LMI) condition for the ultimate boundedness of a class of continuous-time dynamical systems with conic uncertain/nonlinear terms.
The Implementation of Hadoop-based Crawler System and Graphlite-based PageRank-Calculation In Search Engine
Venue: arXiv cs.DC 2015
Year: 2015

Nowadays, the size of the Internet is experiencing rapid growth. As of December 2014, the number of global Internet websites has more than 1 billion and all kinds of information resources are integrated together on the Internet, however,the search engine is to be a necessary tool for all users to retrieve useful information from vast amounts of web data. Generally speaking, a complete search engine includes the crawler system, index building systems, sorting systems and retrieval system. At present there are many open source implementation of search engine, such as lucene, solr, katta, elasticsearch, solandra and so on. The crawler system and sorting system is indispensable for any kind of search engine and in order to guarantee its efficiency, the former needs to update crawled vast amounts of data and the latter requires real-time to build index on newly crawled web pages and calculae its corresponding PageRank value. It is unlikely to accomplish such huge computation tasks depending on a single hardware implementation of the crawler system and sorting system,from which aspect, the distributed cluster technology is brought to the front. In this paper, we use the hadoop Map - Reduce computing framework to implement a distributed crawler system, and use the GraphLite, a distributed synchronous graph-computing framework, to achieve the real-time computation in getting the PageRank value of the new crawled web page.
A Deterministic Analysis of Decimation for Sigma-Delta Quantization of Bandlimited Functions
Venue: arXiv cs.IT 2015
Year: 2015

We study Sigma-Delta ($ΣΔ$) quantization of oversampled bandlimited functions. We prove that digitally integrating blocks of bits and then down-sampling, a process known as decimation, can efficiently encode the associated $ΣΔ$ bit-stream. It allows a large reduction in the bit-rate while still permitting good approximation of the underlying bandlimited function via an appropriate reconstruction kernel. Specifically, in the case of stable $r$th order $ΣΔ$ schemes we show that the reconstruction error decays exponentially in the bit-rate. For example, this result applies to the 1-bit, greedy, first-order $ΣΔ$ scheme.
Recurrent Neural Networks with External Memory for Language Understanding
Venue: arXiv cs.CL 2015
Year: 2015

Recurrent Neural Networks (RNNs) have become increasingly popular for the task of language understanding. In this task, a semantic tagger is deployed to associate a semantic label to each word in an input sequence. The success of RNN may be attributed to its ability to memorize long-term dependence that relates the current-time semantic label prediction to the observations many time instances away. However, the memory capacity of simple RNNs is limited because of the gradient vanishing and exploding problem. We propose to use an external memory to improve memorization capability of RNNs. We conducted experiments on the ATIS dataset, and observed that the proposed model was able to achieve the state-of-the-art results. We compare our proposed model with alternative models and report analysis results that may provide insights for future research.
Fair Packet Scheduling in Network on Chip
Venue: arXiv cs.DC 2015
Year: 2015

Interconnection networks of parallel systems are used for servicing traf- fic generated by different applications, often belonging to different users. When multiple traffic flows contend for channel bandwidth, the scheduling algorithm regulating the access to that channel plays a key role in ensur- ing that each flow obtains the required quality of service. Fairness is a highly desirable property for a scheduling algorithm. We show that using the Relative Fairness Bound as a fairness measure may lead to decrease in throughput and increase in latency. We propose an alternative metric to evaluate the fairness and avoid the drawback of Relative Fairness Bound.
Channel Equalization and Beamforming for Quaternion-Valued Wireless Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

Quaternion-valued wireless communication systems have been studied in the past. Although progress has been made in this promising area, a crucial missing link is lack of effective and efficient quaternion-valued signal processing algorithms for channel equalization and beamforming. With most recent developments in quaternion-valued signal processing, in this work, we fill the gap to solve the problem by studying two quaternion-valued adaptive algorithms: one is the reference signal based quaternion-valued least mean square (QLMS) algorithm and the other one is the quaternion-valued constant modulus algorithm (QCMA). The quaternion-valued Wiener solution for possible block-based calculation is also derived. Simulation results are provided to show the working of the system.
Critical and Maximum Independent Sets of a Graph
Venue: arXiv cs.DM 2015
Year: 2015

Let G be a simple graph with vertex set V(G). A subset S of V(G) is independent if no two vertices from S are adjacent. By Ind(G) we mean the family of all independent sets of G while core(G) and corona(G) denote the intersection and the union of all maximum independent sets, respectively. The number d(X)= |X|-|N(X)| is the difference of the set of vertices X, and an independent set A is critical if d(A)=max{d(I):I belongs to Ind(G)} (Zhang, 1990). Let ker(G) and diadem(G) be the intersection and union, respectively, of all critical independent sets of G (Levit and Mandrescu, 2012). In this paper, we present various connections between critical unions and intersections of maximum independent sets of a graph. These relations give birth to new characterizations of Koenig-Egervary graphs, some of them involving ker(G), core(G), corona(G), and diadem(G).
On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi
Venue: arXiv cs.AI 2015
Year: 2015

Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives over nonempty intersections. It has been proven for RCC5 and RCC8 that path consistent constraint network over a distributive subalgebra is always minimal and globally consistent (in the sense of strong $n$-consistency) in a qualitative sense. The well-known subclass of convex interval relations provides one such an example of distributive subalgebras. This paper first gives a characterisation of distributive subalgebras, which states that the intersection of a set of $n\geq 3$ relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for Point Algebra, Interval Algebra, RCC5 and RCC8, Cardinal Relation Algebra, and Rectangle Algebra. Lastly, we establish two nice properties which will play an important role in efficient reasoning with constraint networks involving a large number of variables.
CCNCheck: Enabling Checkpointed Distributed Applications in Content Centric Networks
Venue: arXiv cs.DC 2015
Year: 2015

We consider the problem of checkpointing a distributed application efficiently in Content Centric Networks so that it can withstand transient failures. We present CCNCheck, a system which enables a sender optimized way of checkpointing distributed applications in CCN's and provides an efficient mechanism for failure recovery in such applications. CCNCheck's checkpointing mechanism is a fork of DMTCP repository CCNCheck is capable of running any distributed application written in C/C++ language.
Joint Sparsity Pattern Recovery with 1-bit Compressive Sensing in Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of jointly sparse support recovery with 1-bit compressive measurements in a sensor network. Sensors are assumed to observe sparse signals having the same but unknown sparse support. Each sensor quantizes its measurement vector element-wise to 1-bit and transmits the quantized observations to a fusion center. We develop a computationally tractable support recovery algorithm which minimizes a cost function defined in terms of the likelihood function and the $l_{1,\infty}$ norm. We observe that even with noisy 1-bit measurements, jointly sparse support can be recovered accurately with multiple sensors each collecting only a small number of measurements.
Differential Geometric SLAM
Venue: arXiv cs.RO 2015
Year: 2015

The simultaneous localization and mapping (SLAM) problem is considered in three dimensions. The proposed algorithm, differential geometric SLAM (DG-SLAM), employs methods from differential geometry to propagate the state and map estimates. Unlike EKF SLAM, the proposed filter is provably asymptotically stable under the assumption of no measurement noise or biases. The robustness of the DG-SLAM algorithm is assessed in simulation with measurement noise. The simulation demonstrates successful localization and mapping.
GRADOOP: Scalable Graph Data Management and Analytics with Hadoop
Venue: arXiv cs.DB 2015
Year: 2015

Many Big Data applications in business and science require the management and analysis of huge amounts of graph data. Previous approaches for graph analytics such as graph databases and parallel graph processing systems (e.g., Pregel) either lack sufficient scalability or flexibility and expressiveness. We are therefore developing a new end-to-end approach for graph data management and analysis based on the Hadoop ecosystem, called Gradoop (Graph analytics on Hadoop). Gradoop is designed around the so-called Extended Property Graph Data Model (EPGM) supporting semantically rich, schema-free graph data within many distinct graphs. A set of high-level operators is provided for analyzing both single graphs and collections of graphs. Based on these operators, we propose a domain-specific language to define analytical workflows. The Gradoop graph store is currently utilizing HBase for distributed storage of graph data in Hadoop clusters. An initial version of Gradoop has been used to analyze graph data for business intelligence and social network analysis.