OpenRaiser/Intern-Atlas huggingface dataset:
The Optimization of Running Queries in Relational Databases Using ANT-Colony Algorithm
Venue: arXiv cs.DB 2013
Year: 2013

The issue of optimizing queries is a cost-sensitive process and with respect to the number of associated tables in a query, its number of permutations grows exponentially. On one hand, in comparison with other operators in relational database, join operator is the most difficult and complicated one in terms of optimization for reducing its runtime. Accordingly, various algorithms have so far been proposed to solve this problem. On the other hand, the success of any database management system (DBMS) means exploiting the query model. In the current paper, the heuristic ant algorithm has been proposed to solve this problem and improve the runtime of join operation. Experiments and observed results reveal the efficiency of this algorithm compared to its similar algorithms.
Lattice-cell : Hybrid approach for text categorization
Venue: arXiv cs.IR 2013
Year: 2013

In this paper, we propose a new text categorization framework based on Concepts Lattice and cellular automata. In this framework, concept structure are modeled by a Cellular Automaton for Symbolic Induction (CASI). Our objective is to reduce time categorization caused by the Concept Lattice. We examine, by experiments the performance of the proposed approach and compare it with other algorithms such as Naive Bayes and k nearest neighbors. The results show performance improvement while reducing time categorization.
AnaDroid: Malware Analysis of Android with User-supplied Predicates
Venue: arXiv cs.PL 2013
Year: 2013

Today's mobile platforms provide only coarse-grained permissions to users with regard to how third- party applications use sensitive private data. Unfortunately, it is easy to disguise malware within the boundaries of legitimately-granted permissions. For instance, granting access to "contacts" and "internet" may be necessary for a text-messaging application to function, even though the user does not want contacts transmitted over the internet. To understand fine-grained application use of permissions, we need to statically analyze their behavior. Even then, malware detection faces three hurdles: (1) analyses may be prohibitively expensive, (2) automated analyses can only find behaviors that they are designed to find, and (3) the maliciousness of any given behavior is application-dependent and subject to human judgment. To remedy these issues, we propose semantic-based program analysis, with a human in the loop as an alternative approach to malware detection. In particular, our analysis allows analyst-crafted semantic predicates to search and filter analysis results. Human-oriented semantic-based program analysis can systematically, quickly and concisely characterize the behaviors of mobile applications. We describe a tool that provides analysts with a library of the semantic predicates and the ability to dynamically trade speed and precision. It also provides analysts the ability to statically inspect details of every suspicious state of (abstract) execution in order to make a ruling as to whether or not the behavior is truly malicious with respect to the intent of the application. In addition, permission and profiling reports are generated to aid analysts in identifying common malicious behaviors.
Most Complex Regular Right-Ideal Languages
Venue: arXiv cs.FL 2013
Year: 2013

A right ideal is a language L over an alphabet A that satisfies L = LA*. We show that there exists a stream (sequence) (R_n : n \ge 3) of regular right ideal languages, where R_n has n left quotients and is most complex under the following measures of complexity: the state complexities of the left quotients, the number of atoms (intersections of complemented and uncomplemented left quotients), the state complexities of the atoms, the size of the syntactic semigroup, the state complexities of the operations of reversal, star, and product, and the state complexities of all binary boolean operations. In that sense, this stream of right ideals is a universal witness.
An O(M log M) Algorithm for Bipartite Matching with Roadmap Distances
Venue: arXiv cs.DS 2013
Year: 2013

An algorithm is presented which produces the minimum cost bipartite matching between two sets of M points each, where the cost of matching two points is proportional to the minimum distance by which a particle could reach one point from the other while constrained to travel on a connected set of curves, or roads. Given any such roadmap, the algorithm obtains O(M log M) total runtime in terms of M, which is the best possible bound in the sense that any algorithm for minimal matching has runtime Omega(M log M). The algorithm is strongly polynomial and is based on a capacity-scaling approach to the [minimum] convex cost flow problem. The result generalizes the known Theta(M log M) complexity of computing optimal matchings between two sets of points on (i) a line segment, and (ii) a circle.
Post-Proceedings of the First International Workshop on Learning and Nonmonotonic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Knowledge Representation and Reasoning and Machine Learning are two important fields in AI. Nonmonotonic logic programming (NMLP) and Answer Set Programming (ASP) provide formal languages for representing and reasoning with commonsense knowledge and realize declarative problem solving in AI. On the other side, Inductive Logic Programming (ILP) realizes Machine Learning in logic programming, which provides a formal background to inductive learning and the techniques have been applied to the fields of relational learning and data mining. Generally speaking, NMLP and ASP realize nonmonotonic reasoning while lack the ability of learning. By contrast, ILP realizes inductive learning while most techniques have been developed under the classical monotonic logic. With this background, some researchers attempt to combine techniques in the context of nonmonotonic ILP. Such combination will introduce a learning mechanism to programs and would exploit new applications on the NMLP side, while on the ILP side it will extend the representation language and enable us to use existing solvers. Cross-fertilization between learning and nonmonotonic reasoning can also occur in such as the use of answer set solvers for ILP, speed-up learning while running answer set solvers, learning action theories, learning transition rules in dynamical systems, abductive learning, learning biological networks with inhibition, and applications involving default and negation. This workshop is the first attempt to provide an open forum for the identification of problems and discussion of possible collaborations among researchers with complementary expertise. The workshop was held on September 15th of 2013 in Corunna, Spain. This post-proceedings contains five technical papers (out of six accepted papers) and the abstract of the invited talk by Luc De Raedt.
On 'A Kalman Filter-Based Algorithm for IMU-Camera Calibration: Observability Analysis and Performance Evaluation'
Venue: arXiv cs.RO 2013
Year: 2013

The above-mentioned work [1] in IEEE-TR'08 presented an extended Kalman filter for calibrating the misalignment between a camera and an IMU. As one of the main contributions, the locally weakly observable analysis was carried out using Lie derivatives. The seminal paper [1] is undoubtedly the cornerstone of current observability work in SLAM and a number of real SLAM systems have been developed on the observability result of this paper, such as [2, 3]. However, the main observability result of this paper [1] is founded on an incorrect proof and actually cannot be acquired using the local observability technique therein, a fact that is apparently not noticed by the SLAM community over a number of years.
Computing the Coverage of an Opaque Forest
Venue: arXiv cs.CG 2013
Year: 2013

We consider the problem of taking an opaque forest and determining the regions that are covered by it. We provide a tight upper bound on the complexity of this problem, and an algorithm for computing this area, which is worst-case optimal.
On the impact of explicit or semi-implicit integration methods over the stability of real-time numerical simulations
Venue: arXiv cs.GR 2013
Year: 2013

Physics-based animation of soft or rigid bodies for real-time applications often suffers from numerical instabilities. We analyse one of the most common sources of unwanted behaviour: the numerical integration strategy. To assess the impact of popular integration methods, we consider a scenario where soft and hard constraints are added to a custom designed deformable linear object. Since the goal for this class of simulation methods is to attain interactive frame-rates, we present the drawbacks of using explicit integration methods over inherently stable, implicit integrators. To help numerical solver designers better understand the impact of an integrator on a certain simulated world, we have conceived a method of benchmarking the efficiency of an integrator with respect to its speed, stability and symplecticity.
Gromov-Hausdorff stability of linkage-based hierarchical clustering methods
Venue: arXiv cs.LG 2013
Year: 2013

A hierarchical clustering method is stable if small perturbations on the data set produce small perturbations in the result. These perturbations are measured using the Gromov-Hausdorff metric. We study the problem of stability on linkage-based hierarchical clustering methods. We obtain that, under some basic conditions, standard linkage-based methods are semi-stable. This means that they are stable if the input data is close enough to an ultrametric space. We prove that, apart from exotic examples, introducing any unchaining condition in the algorithm always produces unstable methods.
Spectrum-Sharing Multi-Hop Cooperative Relaying: Performance Analysis Using Extreme Value Theory
Venue: arXiv cs.IT 2013
Year: 2013

In spectrum-sharing cognitive radio systems, the transmit power of secondary users has to be very low due to the restrictions on the tolerable interference power dictated by primary users. In order to extend the coverage area of secondary transmission and reduce the corresponding interference region, multi-hop amplify-and-forward (AF) relaying can be implemented for the communication between secondary transmitters and receivers. This paper addresses the fundamental limits of this promising technique. Specifically, the effect of major system parameters on the performance of spectrum-sharing multi-hop AF relaying is investigated. To this end, the optimal transmit power allocation at each node along the multi-hop link is firstly addressed. Then, the extreme value theory is exploited to study the limiting distribution functions of the lower and upper bounds on the end-to-end signal-to-noise ratio of the relaying path. Our results disclose that the diversity gain of the multi-hop link is always unity, regardless of the number of relaying hops. On the other hand, the coding gain is proportional to the water level of the optimal water-filling power allocation at secondary transmitter and to the large-scale path-loss ratio of the desired link to the interference link at each hop, yet is inversely proportional to the accumulated noise, i.e. the product of the number of relays and the noise variance, at the destination. These important findings do not only shed light on the performance of the secondary transmissions but also benefit system designers improving the efficiency of future spectrum-sharing cooperative systems.
Influence Diffusion in Social Networks under Time Window Constraints
Venue: arXiv cs.DS 2013
Year: 2013

We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model, agents change behaviors/opinions on the basis of information collected from their neighbors in a time interval of bounded size whereas agents are assumed to have unbounded memory in previously studied scenarios. In our mathematical framework, one is given a network $G=(V,E)$, an integer value $t(v)$ for each node $v\in V$, and a time window size $λ$. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node $v$ becomes influenced if the number of its neighbors that have been influenced in the previous $λ$ rounds is greater than or equal to $t(v)$. We prove that the problem of finding a minimum cardinality target set that influences the whole network $G$ is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, trees, and complete graphs.
Bi-Criteria and Approximation Algorithms for Restricted Matchings
Venue: arXiv cs.DS 2013
Year: 2013

In this work we study approximation algorithms for the \textit{Bounded Color Matching} problem (a.k.a. Restricted Matching problem) which is defined as follows: given a graph in which each edge $e$ has a color $c_e$ and a profit $p_e \in \mathbb{Q}^+$, we want to compute a maximum (cardinality or profit) matching in which no more than $w_j \in \mathbb{Z}^+$ edges of color $c_j$ are present. This kind of problems, beside the theoretical interest on its own right, emerges in multi-fiber optical networking systems, where we interpret each unique wavelength that can travel through the fiber as a color class and we would like to establish communication between pairs of systems. We study approximation and bi-criteria algorithms for this problem which are based on linear programming techniques and, in particular, on polyhedral characterizations of the natural linear formulation of the problem. In our setting, we allow violations of the bounds $w_j$ and we model our problem as a bi-criteria problem: we have two objectives to optimize namely (a) to maximize the profit (maximum matching) while (b) minimizing the violation of the color bounds. We prove how we can "beat" the integrality gap of the natural linear programming formulation of the problem by allowing only a slight violation of the color bounds. In particular, our main result is \textit{constant} approximation bounds for both criteria of the corresponding bi-criteria optimization problem.
Evolution of Communities with Focus on Stability (extended abstract)
Venue: arXiv cs.SI 2013
Year: 2013

The detection of communities is an important tool used to analyze the social graph of mobile phone users. Within each community, customers are susceptible of attracting new ones, retaining old ones and/or accepting new products or services through the leverage of mutual influences. The communities of users are smaller units, easier to grasp, and allow for example the computation of role analysis -- based on the centrality of an actor within his community. The problem of finding communities in static graphs has been widely studied. However, from the point of view of a telecom analyst, to be really useful, the detected communities must evolve as the social graph of communications changes over time -- for example, in order to perform marketing actions on communities and track the results of those actions over time. Additionally the behaviors of communities of users over time can be used to predict future activity that interests the telecom operators, such as subscriber churn or handset adoption. Similary group evolution can provide insights for designing strategies, such as the early warning of group churn. Stability is a crucial issue: the analysis performed on a given community will be lost, if the analyst cannot keep track of this community in the following time steps. This is the particular use case that we tackle in this paper: tracking the evolution of communities in dynamic scenarios with focus on stability. We propose two modifications to a widely used static community detection algorithm. We then describe experiments to study the stability and quality of the resulting partitions on real-world social networks, represented by monthly call graphs for millions of subscribers.
On Constructing Constrained Tree Automata Recognizing Ground Instances of Constrained Terms
Venue: arXiv cs.FL 2013
Year: 2013

An inductive theorem proving method for constrained term rewriting systems, which is based on rewriting induction, needs a decision procedure for reduction-completeness of constrained terms. In addition, the sufficient complete property of constrained term rewriting systems enables us to relax the side conditions of some inference rules in the proving method. These two properties can be reduced to intersection emptiness problems related to sets of ground instances for constrained terms. This paper proposes a method to construct deterministic, complete, and constraint-complete constrained tree automata recognizing ground instances of constrained terms.
Random Generation of Nondeterministic Finite-State Tree Automata
Venue: arXiv cs.FL 2013
Year: 2013

Algorithms for (nondeterministic) finite-state tree automata (FTAs) are often tested on random FTAs, in which all internal transitions are equiprobable. The run-time results obtained in this manner are usually overly optimistic as most such generated random FTAs are trivial in the sense that the number of states of an equivalent minimal deterministic FTA is extremely small. It is demonstrated that nontrivial random FTAs are obtained only for a narrow band of transition probabilities. Moreover, an analytic analysis yields a formula to approximate the transition probability that yields the most complex random FTAs, which should be used in experiments.
Automated and Weighted Self-Organizing Time Maps
Venue: arXiv cs.NE 2013
Year: 2013

This paper proposes schemes for automated and weighted Self-Organizing Time Maps (SOTMs). The SOTM provides means for a visual approach to evolutionary clustering, which aims at producing a sequence of clustering solutions. This task we denote as visual dynamic clustering. The implication of an automated SOTM is not only a data-driven parametrization of the SOTM, but also the feature of adjusting the training to the characteristics of the data at each time step. The aim of the weighted SOTM is to improve learning from more trustworthy or important data with an instance-varying weight. The schemes for automated and weighted SOTMs are illustrated on two real-world datasets: (i) country-level risk indicators to measure the evolution of global imbalances, and (ii) credit applicant data to measure the evolution of firm-level credit risks.
Text Classification and Distributional features techniques in Datamining and Warehousing
Venue: arXiv cs.IR 2013
Year: 2013

Text Categorization is traditionally done by using the term frequency and inverse document frequency.This type of method is not very good because, some words which are not so important may appear in the document .The term frequency of unimportant words may increase and document may be classified in the wrong category.For reducing the error of classifying of documents in wrong category. The Distributional features are introduced. In the Distribuional Features, the Distribution of the words in the whole document is analyzed. Whole Document is very closely analyzed for different measures like FirstAppearence, Last Appearance, Centriod, Count, etc.The measures are calculated and they are used in tf*idf equation and result is used in k- nearest neighbor and K-means algorithm for classifying the documents.
Event Evolution Tracking from Streaming Social Posts
Venue: arXiv cs.SI 2013
Year: 2013

Online social post streams such as Twitter timelines and forum discussions have emerged as important channels for information dissemination. They are noisy, informal, and surge quickly. Real life events, which may happen and evolve every minute, are perceived and circulated in post streams by social users. Intuitively, an event can be viewed as a dense cluster of posts with a life cycle sharing the same descriptive words. There are many previous works on event detection from social streams. However, there has been surprisingly little work on tracking the evolution patterns of events, e.g., birth/death, growth/decay, merge/split, which we address in this paper. To define a tracking scope, we use a sliding time window, where old posts disappear and new posts appear at each moment. Following that, we model a social post stream as an evolving network, where each social post is a node, and edges between posts are constructed when the post similarity is above a threshold. We propose a framework which summarizes the information in the stream within the current time window as a ``sketch graph'' composed of ``core'' posts. We develop incremental update algorithms to handle highly dynamic social streams and track event evolution patterns in real time. Moreover, we visualize events as word clouds to aid human perception. Our evaluation on a real data set consisting of 5.2 million posts demonstrates that our method can effectively track event dynamics in the whole life cycle from very large volumes of social streams on the fly.
Skin Texture Recognition Using Neural Networks
Venue: arXiv cs.CV 2013
Year: 2013

Skin recognition is used in many applications ranging from algorithms for face detection, hand gesture analysis, and to objectionable image filtering. In this work a skin recognition system was developed and tested. While many skin segmentation algorithms relay on skin color, our work relies on both skin color and texture features (features derives from the GLCM) to give a better and more efficient recognition accuracy of skin textures. We used feed forward neural networks to classify input textures images to be skin or non skin textures. The system gave very encouraging results during the neural network generalization face.
Games and Full Completeness for Multiplicative Linear Logic
Venue: arXiv cs.LO 2013
Year: 2013

We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of {\em history-free} strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass et al.