OpenRaiser/Intern-Atlas huggingface dataset:
Policy-Carrying, Policy-Enforcing Digital Objects
Venue: arXiv cs.DL 2013
Year: 2013

We describe the motivation for moving policy enforcement for access control down to the digital object level. The reasons for this include handling of item-specific behaviors, adapting to evolution of digital objects, and permitting objects to move among repositories and portable devices. We then describe our experiments that integrate the Fedora architecture for digital objects and repositories and the PoET implementation of security automata to effect such objectcentric policy enforcement.
The self-assembly of paths and squares at temperature 1
Venue: arXiv cs.CC 2013
Year: 2013

We prove that the number of tile types required to build squares of size n x n, in Winfree's abstract Tile Assembly Model, when restricted to using only non-cooperative tile bindings, is at least 2n-1, which is also the best known upper bound. Non-cooperative self-assembly, also known as temperature 1, is where tiles bind to each other if they match on one or more sides, whereas in cooperative binding, some tiles can bind only if they match on multiple sides. Our proof introduces a new programming technique for temperature 1, that disproves the very intuitive and commonly held belief that, in the same model, assembling paths between two points A and B cannot be done with less tile types than the Manhattan distance between them. Then, we prove a necessary condition for these "efficient paths" to be assembled, and show that this necessary condition cannot hold in completely filled squares. This result proves the oldest conjecture in algorithmic self-assembly, published by Rothemund and Winfree in STOC 2000, in the case where growth starts from a corner of the square. As a corollary, we establish n as a lower bound on the tile complexity of the general case. The problem of determining the minimal number of tile types to self-assemble a shape is known to be Sigma^p_2-complete.
Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
Venue: arXiv cs.CG 2013
Year: 2013

We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese \cite{aw-asmwi-13, aw-qmwis-14} to polygons of arbitrary complexity. Surprisingly, the algorithm also works or computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length $4$ (i.e., $K_{2,2}$).
ABC-SG: A New Artificial Bee Colony Algorithm-Based Distance of Sequential Data Using Sigma Grams
Venue: arXiv cs.NE 2013
Year: 2013

The problem of similarity search is one of the main problems in computer science. This problem has many applications in text-retrieval, web search, computational biology, bioinformatics and others. Similarity between two data objects can be depicted using a similarity measure or a distance metric. There are numerous distance metrics in the literature, some are used for a particular data type, and others are more general. In this paper we present a new distance metric for sequential data which is based on the sum of n-grams. The novelty of our distance is that these n-grams are weighted using artificial bee colony; a recent optimization algorithm based on the collective intelligence of a swarm of bees on their search for nectar. This algorithm has been used in optimizing a large number of numerical problems. We validate the new distance experimentally.
Geometric Feature Based Face-Sketch Recognition
Venue: arXiv cs.CV 2013
Year: 2013

This paper presents a novel facial sketch image or face-sketch recognition approach based on facial feature extraction. To recognize a face-sketch, we have concentrated on a set of geometric face features like eyes, nose, eyebrows, lips, etc and their length and width ratio because it is difficult to match photos and sketches because they belong to two different modalities. In this system, first the facial features/components from training images are extracted, then ratios of length, width, and area etc. are calculated and those are stored as feature vectors for individual images. After that the mean feature vectors are computed and subtracted from each feature vector for centering of the feature vectors. In the next phase, feature vector for the incoming probe face-sketch is also computed in similar fashion. Here, K-NN classifier is used to recognize probe face-sketch. It is experimentally verified that the proposed method is robust against faces are in a frontal pose, with normal lighting and neutral expression and have no occlusions. The experiment has been conducted with 80 male and female face images from different face databases. It has useful applications for both law enforcement and digital entertainment.
A Gabor block based Kernel Discriminative Common Vector (KDCV) approach using cosine kernels for Human Face Recognition
Venue: arXiv cs.CV 2013
Year: 2013

In this paper a nonlinear Gabor Wavelet Transform (GWT) discriminant feature extraction approach for enhanced face recognition is proposed. Firstly, the low-energized blocks from Gabor wavelet transformed images are extracted. Secondly, the nonlinear discriminating features are analyzed and extracted from the selected low-energized blocks by the generalized Kernel Discriminative Common Vector (KDCV) method. The KDCV method is extended to include cosine kernel function in the discriminating method. The KDCV with the cosine kernels is then applied on the extracted low energized discriminating feature vectors to obtain the real component of a complex quantity for face recognition. In order to derive positive kernel discriminative vectors; we apply only those kernel discriminative eigenvectors that are associated with non-zero eigenvalues. The feasibility of the low energized Gabor block based generalized KDCV method with cosine kernel function models has been successfully tested for image classification using the L1, L2 distance measures; and the cosine similarity measure on both frontal and pose-angled face recognition. Experimental results on the FRAV2D and the FERET database demonstrate the effectiveness of this new approach.
Partial actions and automata
Venue: arXiv cs.FL 2013
Year: 2013

We use the notion of a partial action of a monoid to introduce a generalization of automata, which we call "a preautomaton". We study properties of preautomata and of languages recognized by preautomata.
Efficient construction of the lattice of frequent closed patterns and simultaneous extraction of generic bases of rules
Venue: arXiv cs.DS 2013
Year: 2013

In the last few years, the amount of collected data, in various computer science applications, has grown considerably. These large volumes of data need to be analyzed in order to extract useful hidden knowledge. This work focuses on association rule extraction. This technique is one of the most popular in data mining. Nevertheless, the number of extracted association rules is often very high, and many of them are redundant. In this paper, we propose a new algorithm, called PRINCE. Its main feature is the construction of a partially ordered structure for extracting subsets of association rules, called generic bases. Without loss of information these subsets form representation of the whole association rule set. To reduce the cost of such a construction, the partially ordered structure is built thanks to the minimal generators associated to frequent closed patterns. The closed ones are simultaneously derived with generic bases thanks to a simple bottom-up traversal of the obtained structure. The experimentations we carried out in benchmark and "worst case" contexts showed the efficiency of the proposed algorithm, compared to algorithms like CLOSE, A-CLOSE and TITANIC.
A fast and light stream cipher for smartphones
Venue: arXiv cs.CR 2013
Year: 2013

We present a stream cipher based on a chaotic dynamical system. Using a chaotic trajectory sampled under certain rules in order to avoid any attempt to reconstruct the original one, we create a binary pseudo-random keystream that can only be exactly reproduced by someone that has fully knowledge of the communication system parameters formed by a transmitter and a receiver and sharing the same initial conditions. The plaintext is XORed with the keystream creating the ciphertext, the encrypted message. This keystream passes the NISTs randomness test and has been implemented in a videoconference App for smartphones, in order to show the fast and light nature of the proposed encryption system.
Curriculum Learning for Handwritten Text Line Recognition
Venue: arXiv cs.LG 2013
Year: 2013

Recurrent Neural Networks (RNN) have recently achieved the best performance in off-line Handwriting Text Recognition. At the same time, learning RNN by gradient descent leads to slow convergence, and training times are particularly long when the training database consists of full lines of text. In this paper, we propose an easy way to accelerate stochastic gradient descent in this set-up, and in the general context of learning to recognize sequences. The principle is called Curriculum Learning, or shaping. The idea is to first learn to recognize short sequences before training on all available training sequences. Experiments on three different handwritten text databases (Rimes, IAM, OpenHaRT) show that a simple implementation of this strategy can significantly speed up the training of RNN for Text Recognition, and even significantly improve performance in some cases.
Exponential lower bounds on the size of approximate formulations in the natural encoding for Capacitated Facility Location
Venue: arXiv cs.DS 2013
Year: 2013

The metric capacitated facility location is a well-studied problem for which, while constant factor approximations are known, no efficient relaxation with constant integrality gap is known. The question whether there is such a relaxation is among the most important open problems of approximation algorithms \cite{ShmoysWbook}. In this paper we show that, if one is restricted to linear programs that use the natural encoding for facility location, at least an exponential number of constraints is needed to achieve a constant gap. Our proof does not assume any special property of the relaxation such as locality or symmetry.
FELFCNCA: Fast & Efficient Log File Compression Using Non Linear Cellular Automata Classifier
Venue: arXiv cs.OH 2013
Year: 2013

Log Files are created for Traffic Analysis, Maintenance, Software debugging, customer management at multiple places like System Services, User Monitoring Applications, Network servers, database management systems which must be kept for long periods of time. These Log files may grow to huge sizes in this complex systems and environments. For storage and convenience log files must be compressed. Most of the existing algorithms do not take temporal redundancy specific Log Files into consideration. We propose a Non Linear based Classifier which introduces a multidimensional log file compression scheme described in eight variants, differing in complexity and attained compression ratios. The FELFCNCA scheme introduces a transformation for log file whose compressible output is far better than general purpose algorithms. This proposed method was found lossless and fully automatic. It does not impose any constraint on the size of log file
A Review: Study of Handover Performance in Mobile IP
Venue: arXiv cs.NI 2013
Year: 2013

The Mobile Internet Protocol (Mobile IP) is an extension to the Internet Protocol proposed by the Internet Engineering Task Force (IETF) that addresses the mobility issues. In order to support un-interrupted services and seamless mobility of nodes across the networks (and/or sub-networks) with permanent IP addresses, handover is performed in mobile IP enabled networks. Handover in mobile IP is source cause of performance degradation as it results in increased latency and packet loss during handover. Other issues like scalability issues, ordered packet delivery issues, control plane management issues etc are also adversely affected by it. The paper provides a constructive survey by classifying, discussing and comparing different handover techniques that have been proposed so far, for enhancing the performance during handovers. Finally some general solutions that have been used to solve handover related problems are briefly discussed.
A composition theorem for parity kill number
Venue: arXiv cs.CC 2013
Year: 2013

In this work, we study the parity complexity measures ${\mathsf{C}^{\oplus}_{\min}}[f]$ and ${\mathsf{DT^{\oplus}}}[f]$. ${\mathsf{C}^{\oplus}_{\min}}[f]$ is the \emph{parity kill number} of $f$, the fewest number of parities on the input variables one has to fix in order to "kill" $f$, i.e. to make it constant. ${\mathsf{DT^{\oplus}}}[f]$ is the depth of the shortest \emph{parity decision tree} which computes $f$. These complexity measures have in recent years become increasingly important in the fields of communication complexity \cite{ZS09, MO09, ZS10, TWXZ13} and pseudorandomness \cite{BK12, Sha11, CT13}. Our main result is a composition theorem for ${\mathsf{C}^{\oplus}_{\min}}$. The $k$-th power of $f$, denoted $f^{\circ k}$, is the function which results from composing $f$ with itself $k$ times. We prove that if $f$ is not a parity function, then ${\mathsf{C}^{\oplus}_{\min}}[f^{\circ k}] \geq Ω({\mathsf{C}_{\min}}[f]^{k}).$ In other words, the parity kill number of $f$ is essentially supermultiplicative in the \emph{normal} kill number of $f$ (also known as the minimum certificate complexity). As an application of our composition theorem, we show lower bounds on the parity complexity measures of $\mathsf{Sort}^{\circ k}$ and $\mathsf{HI}^{\circ k}$. Here $\mathsf{Sort}$ is the sort function due to Ambainis \cite{Amb06}, and $\mathsf{HI}$ is Kushilevitz's hemi-icosahedron function \cite{NW95}. In doing so, we disprove a conjecture of Montanaro and Osborne \cite{MO09} which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of \cite{MO09,ZS10} and \cite{TWXZ13}.
Multipermutation Codes in the Ulam Metric for Nonvolatile Memories
Venue: arXiv cs.IT 2013
Year: 2013

We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges may share the same rank. Changes in the charges of cells manifest themselves as errors whose effects on the retrieved signal may be measured via the Ulam distance. As part of our analysis, we study multipermutation codes in the Hamming metric, known as constant composition codes. We then present bounds on the size of multipermutation codes and their capacity, for both the Ulam and the Hamming metrics. Finally, we present constructions and accompanying decoders for multipermutation codes in the Ulam metric.
Geometric graphs on convex point sets
Venue: arXiv cs.CG 2013
Year: 2013

In this note, we introduce a family of bipartite graphs called path restricted ordered bipartite graphs and present it as an abstract generalization of some well known geometric graphs like unit distance graphs on convex point sets. In the framework of convex point sets, we also focus on a generalized version of Gabriel graphs known as locally Gabriel graphs or $LGGs$. $LGGs$ can also be seen as the generalization of unit distance graphs. The path restricted ordered bipartite graph is also a generalization of $LGGs$. We study some structural properties of the path restricted ordered bipartite graphs and also show that such graphs have the maximum edge complexity of $θ(n \log n)$. It gives an alternate proof to the well known result that $UDGs$ and $LGGs$ on convex points have $O(n \log n)$ edges.
Clustering online social network communities using genetic algorithms
Venue: arXiv cs.SI 2013
Year: 2013

To analyze the activities in an Online Social network (OSN), we introduce the concept of "Node of Attraction" (NoA) which represents the most active node in a network community. This NoA is identified as the origin/initiator of a post/communication which attracted other nodes and formed a cluster at any point in time. In this research, a genetic algorithm (GA) is used as a data mining method where the main objective is to determine clusters of network communities in a given OSN dataset. This approach is efficient in handling different type of discussion topics in our studied OSN - comments, emails, chat expressions, etc. and can form clusters according to one or more topics. We believe that this work can be useful in finding the source for spread of this GA-based clustering of online interactions and reports some results of experiments with real-world data and demonstrates the performance of proposed approach.
IRCI Free Range Reconstruction for SAR Imaging with Arbitrary Length OFDM Pulse
Venue: arXiv cs.IT 2013
Year: 2013

Our previously proposed OFDM with sufficient cyclic prefix (CP) synthetic aperture radar (SAR) imaging algorithm is inter-range-cell interference (IRCI) free and achieves ideally zero range sidelobes for range reconstruction. In this OFDM SAR imaging algorithm, the minimum required CP length is almost equal to the number of range cells in a swath, while the number of subcarriers of an OFDM signal needs to be more than the CP length. This makes the length of a transmitted OFDM sequence at least almost twice of the number of range cells in a swath and for a wide swath imaging, the transmitted OFDM pulse length becomes long, which may cause problems in some radar applications. In this paper, we propose a CP based OFDM SAR imaging with arbitrary pulse length, which has IRCI free range reconstruction and its pulse length is independent of a swath width. We then present a novel design method for our proposed arbitrary length OFDM pulses. Simulation results are presented to illustrate the performances of the OFDM pulse design and the arbitrary pulse length CP based OFDM SAR imaging.
Finite automata with advice tapes
Venue: arXiv cs.FL 2013
Year: 2013

We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Quickest Search over Multiple Sequences with Mixed Observation
Venue: arXiv cs.IT 2013
Year: 2013

The problem of sequentially finding an independent and identically distributed (i.i.d.) sequence that is drawn from a probability distribution $f_1$ by searching over multiple sequences, some of which are drawn from $f_1$ and the others of which are drawn from a different distribution $f_0$, is considered. The observer is allowed to take one observation at a time. It has been shown in a recent work that if each observation comes from one sequence, the cumulative sum test is optimal. In this paper, we propose a new approach in which each observation can be a linear combination of samples from multiple sequences. The test has two stages. In the first stage, namely scanning stage, one takes a linear combination of a pair of sequences with the hope of scanning through sequences that are unlikely to be generated from $f_1$ and quickly identifying a pair of sequences such that at least one of them is highly likely to be generated by $f_1$. In the second stage, namely refinement stage, one examines the pair identified from the first stage more closely and picks one sequence to be the final sequence. The problem under this setup belongs to a class of multiple stopping time problems. In particular, it is an ordered two concatenated Markov stopping time problem. We obtain the optimal solution using the tools from the multiple stopping time theory. The optimal solution has a rather complex structure. For implementation purpose, a low complexity algorithm is proposed, in which the observer adopts the cumulative sum test in the scanning stage and adopts the sequential probability ratio test in the refinement stage. The performance of this low complexity algorithm is analyzed when the prior probability of $f_{1}$ occurring is small. Both analytical and numerical simulation results show that this search strategy can significantly reduce the searching time when $f_{1}$ is rare.
Strategy pattern: payment pattern for Internet banking
Venue: arXiv cs.SE 2013
Year: 2013

This paper brings out the design patterns according to the various services involved in internet banking. The Pattern oriented Software Architecture uses the pattern which eliminates the difficulty of reusability in a particular context. The patterns are to be designed using BPM (Business Process Model) for effective cross cutting on process level. For implementing the above said BPM, the Internet banking has been taken to implement the pattern into it. The Analysis and identification of various processes in Internet Banking have been done, to identify the effective cross cutting features. With this process the pattern has been designed, as a reusability component to be used by the Software Architect. The pattern help us to resolve recurring problems constructively and based on proven solutions and also support us in understanding the architecture of a given software system. Once the model is finalized by analyzing, we found payment in the process of internet banking has a strategy pattern.
Practical Design for Multiple-Antenna Cognitive Radio Networks with Coexistence Constraint
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we investigate the practical design for the multiple-antenna cognitive radio (CR) networks sharing the geographically used or unused spectrum. We consider a single cell network formed by the primary users (PU), which are half-duplex two-hop relay channels and the secondary users (SU) are single user additive white Gaussian noise channels. In addition, the coexistence constraint which requires PUs' coding schemes and rates unchanged with the emergence of SU, should be satisfied. The contribution of this paper are twofold. First, we explicitly design the scheme to pair the SUs to the existing PUs in a single cell network. Second, we jointly design the nonlinear precoder, relay beamformer, and the transmitter and receiver beamformers to minimize the sum mean square error of the SU system. In the first part, we derive an approximate relation between the relay ratio, chordal distance and strengths of the vector channels, and the transmit powers. Based on this relation, we are able to solve the optimal pairing between SUs and PUs efficiently. In the second part, considering the feasibility of implementation, we exploit the Tomlinson-Harashima precoding instead of the dirty paper coding to mitigate the interference at the SU receiver, which is known side information at the SU transmitter. To complete the design, we first approximate the optimization problem as a convex one. Then we propose an iterative algorithm to solve it with CVX. This joint design exploits all the degrees of design. To the best of our knowledge, both the two parts have never been considered in the literature. Numerical results show that the proposed pairing scheme outperforms the greedy and random pairing with low complexity. Numerical results also show that even if all the channel matrices are full rank, under which the simple zero forcing scheme is infeasible, the proposed scheme can still work well.