OpenRaiser/Intern-Atlas huggingface dataset:
Asymptotically Optimal Anomaly Detection via Sequential Testing
Venue: arXiv cs.IT 2014
Year: 2014

Sequential detection of independent anomalous processes among K processes is considered. At each time, only M processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. Each anomalous process incurs a cost per unit time until its anomaly is identified and fixed. Switching across processes and state declarations are allowed at all times, while decisions are based on all past observations and actions. The objective is a sequential search strategy that minimizes the total expected cost incurred by all the processes during the detection process under reliability constraints. Low-complexity algorithms are established to achieve asymptotically optimal performance as the error constraints approach zero. Simulation results demonstrate strong performance in the finite regime.
A Faster Algorithm for Computing Straight Skeletons
Venue: arXiv cs.CG 2014
Year: 2014

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with $n$ vertices, among which $r$ are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in $O(n (\log n)\log r)$ time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected $O(n \sqrt{h+1}\log^2 n)$ time for a polygon with $h$ holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in $O(n (\log n) \log r + r^{4/3+\varepsilon})$ time for any $\varepsilon>0$. On degenerate input, our time bound increases to $O(n (\log n) \log r + r^{17/11+\varepsilon})$.
It Doesn't Break Just on Twitter. Characterizing Facebook content During Real World Events
Venue: arXiv cs.SI 2014
Year: 2014

Multiple studies in the past have analyzed the role and dynamics of the Twitter social network during real world events. However, little work has explored the content of other social media services, or compared content across two networks during real world events. We believe that social media platforms like Facebook also play a vital role in disseminating information on the Internet during real world events. In this work, we study and characterize the content posted on the world's biggest social network, Facebook, and present a comparative analysis of Facebook and Twitter content posted during 16 real world events. Contrary to existing notion that Facebook is used mostly as a private network, our findings reveal that more than 30% of public content that was present on Facebook during these events, was also present on Twitter. We then performed qualitative analysis on the content spread by the most active users during these events, and found that over 10% of the most active users on both networks post spam content. We used stylometric features from Facebook posts and tweet text to classify this spam content, and were able to achieve an accuracy of over 99% for Facebook, and over 98% for Twitter. This work is aimed at providing researchers with an overview of Facebook content during real world events, and serve as basis for more in-depth exploration of its various aspects like information quality, and credibility during real world events.
Measuring Cost of Quality (CoQ) on SDLC Projects is Indispensible for Effective Software Quality Assurance
Venue: arXiv cs.SE 2014
Year: 2014

It is well known fact that was phrased by famous quality scholar P.B. Crosby that it is always cheaper to do the job right the first time. However, this statement must be reconsidered with respect to software development projects, because the concept of quality and associated costs measurements in software engineering discipline is not as matured as in manufacturing and other fields of the industry. Post delivery defects (i.e. software bugs) are very common and integral part of software industry. While the process of measuring and classifying quality cost components is visible, obvious and institutionalized in manufacturing industry, it is still evolving in software industry. In addition to this, the recommendations of British standard BS-6143-2:1990 for classifying quality-related costs into prevention costs, appraisal costs, and failure costs have been successfully adopted by many industries, by identifying the activities carried out within each of these categories, and measuring the costs connected with them, software industry has a long-way to go to have the same level of adoption and institutionalization of cost of quality measurements and visibility. Cost of Quality for software isn't the price of creating a quality software product or IT-service. It's actually the cost of NOT creating a quality software product or IT-service. The chronic affliction of majority of software development projects that are frequently found bleeding with cost overruns, schedule slippage, scope creep and poor quality of deliverables in the global IT industry, was the trigger for this research work. Lessons learnt from this study offer valuable prescriptive guidance for small and medium software businesses, who can benefit from this study by applying the same for their quality improvement initiatives using CoQ-metric, to enhance the capability and maturity of their SDLC-project performance.
An Algebraic Hardness Criterion for Surjective Constraint Satisfaction
Venue: arXiv cs.LO 2014
Year: 2014

The constraint satisfaction problem (CSP) on a relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is a assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic condition on the polymorphism clone of B and prove that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. To our knowledge, this is the first result that allows one to use algebraic information from a relational structure B to infer information on the complexity hardness of surjective constraint satisfaction on B. A corollary of our result is that, on any finite non-trivial structure having only essentially unary polymorphisms, surjective constraint satisfaction is NP-complete.
Steganalysis: Detecting LSB Steganographic Techniques
Venue: arXiv cs.MM 2014
Year: 2014

Steganalysis means analysis of stego images. Like cryptanalysis, steganalysis is used to detect messages often encrypted using secret key from stego images produced by steganography techniques. Recently lots of new and improved steganography techniques are developed and proposed by researchers which require robust steganalysis techniques to detect the stego images having minimum false alarm rate. This paper discusses about the different Steganalysis techniques and help to understand how, where and when this techniques can be used based on different situations.
Set Consensus: Captured by a Set of Runs with Ramifications
Venue: arXiv cs.DC 2014
Year: 2014

Are (set)-consensus objects necessary? This paper answer is negative. We show that the availability of consensus objects can be replaced by restricting the set of runs we consider. In particular we concentrate of the set of runs of the Immediate-Snapshot-Model (IIS), and given the object we identify this restricted subset of IIS runs. We further show that given an $(m,k)$-set consensus, an object that provides $k$-set consensus among $m$ processors, in a system of $n$, $n>m$ processors, we do not need to use the precise power of the objects but rather their effective cumulative set consensus power. E.g. when $n=3, m=2,$ and $k=1$ and all the 3 processors are active then we only use 2-set consensus among the 3 processors, as if 2-processors consensus is not available. We do this until at least one of the 3 processors obtains an output. We show that this suggests a new direction in the design of algorithms when consensus objects are involved.
Multi-ellipses detection on images inspired by collective animal behavior
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a novel and effective technique for extracting multiple ellipses from an image. The approach employs an evolutionary algorithm to mimic the way animals behave collectively assuming the overall detection process as a multi-modal optimization problem. In the algorithm, searcher agents emulate a group of animals that interact to each other using simple biological rules which are modeled as evolutionary operators. In turn, such operators are applied to each agent considering that the complete group has a memory to store optimal solutions (ellipses) seen so-far by applying a competition principle. The detector uses a combination of five edge points as parameters to determine ellipse candidates (possible solutions) while a matching function determines if such ellipse candidates are actually present in the image. Guided by the values of such matching functions, the set of encoded candidate ellipses are evolved through the evolutionary algorithm so that the best candidates can be fitted into the actual ellipses within the image. Just after the optimization process ends, an analysis over the embedded memory is executed in order to find the best obtained solution (the best ellipse) and significant local minima (remaining ellipses). Experimental results over several complex synthetic and natural images have validated the efficiency of the proposed technique regarding accuracy, speed and robustness.
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
Venue: arXiv cs.CL 2014
Year: 2014

Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tutorial gives an overview of the technique. We describe example algorithms, describe formal guarantees for the method, and describe practical issues in implementing the algorithms. While our examples are predominantly drawn from the NLP literature, the material should be of general relevance to inference problems in machine learning. A central theme of this tutorial is that Lagrangian relaxation is naturally applied in conjunction with a broad class of combinatorial algorithms, allowing inference in models that go significantly beyond previous work on Lagrangian relaxation for inference in graphical models.
The Affect of Lifestyle Factors on Eco-Visualization Design
Venue: arXiv cs.HC 2014
Year: 2014

As people become more concerned with the need to conserve their power consumption we need to find ways to inform them of how electricity is being consumed within the home. There are a number of devices that have been designed using different forms, sizes, and technologies. We are interested in large ambient displays that can be read at a glance and from a distance as informative art. However, from these objectives come a number of questions that need to be explored and answered. To what degree might lifestyle factors influence the design of eco-visualizations? To answer this we need to ask how people with varying lifestyle factors perceive the utility of such devices and their placement within a home. We explore these questions by creating four ambient display prototypes. We take our prototypes and subject them to a user study to gain insight as to the questions posed above. This paper discusses our prototypes in detail and the results and findings of our user study.
A Codon Frequency Obfuscation Heuristic for Raw Genomic Data Privacy
Venue: arXiv cs.CR 2014
Year: 2014

Genomic data provides clinical researchers with vast opportunities to study various patient ailments. Yet the same data contains revealing information, some of which a patient might want to remain concealed. The question then arises: how can an entity transact in full DNA data while concealing certain sensitive pieces of information in the genome sequence, and maintain DNA data utility? As a response to this question, we propose a codon frequency obfuscation heuristic, in which a redistribution of codon frequency values with highly expressed genes is done in the same amino acid group, generating an obfuscated DNA sequence. Our preliminary results show that it might be possible to publish an obfuscated DNA sequence with a desired level of similarity (utility) to the original DNA sequence.
Learning to Exploit Different Translation Resources for Cross Language Information Retrieval
Venue: arXiv cs.IR 2014
Year: 2014

One of the important factors that affects the performance of Cross Language Information Retrieval(CLIR)is the quality of translations being employed in CLIR. In order to improve the quality of translations, it is important to exploit available resources efficiently. Employing different translation resources with different characteristics has many challenges. In this paper, we propose a method for exploiting available translation resources simultaneously. This method employs Learning to Rank(LTR) for exploiting different translation resources. To apply LTR methods for query translation, we define different translation relation based features in addition to context based features. We use the contextual information contained in translation resources for extracting context based features.The proposed method uses LTR to construct a translation ranking model based on defined features. The constructed model is used for ranking translation candidates of query words. To evaluate the proposed method we do English-Persian CLIR, in which we employ the translation ranking model to find translations of English queries and employ the translations to retrieve Persian documents. Experimental results show that our approach significantly outperforms single resource based CLIR methods.
New Perspectives in Sinographic Language Processing Through the Use of Character Structure
Venue: arXiv cs.CL 2014
Year: 2014

Chinese characters have a complex and hierarchical graphical structure carrying both semantic and phonetic information. We use this structure to enhance the text model and obtain better results in standard NLP operations. First of all, to tackle the problem of graphical variation we define allographic classes of characters. Next, the relation of inclusion of a subcharacter in a characters, provides us with a directed graph of allographic classes. We provide this graph with two weights: semanticity (semantic relation between subcharacter and character) and phoneticity (phonetic relation) and calculate "most semantic subcharacter paths" for each character. Finally, adding the information contained in these paths to unigrams we claim to increase the efficiency of text mining methods. We evaluate our method on a text classification task on two corpora (Chinese and Japanese) of a total of 18 million characters and get an improvement of 3% on an already high baseline of 89.6% precision, obtained by a linear SVM classifier. Other possible applications and perspectives of the system are discussed.
Fast algorithm for Multiple-Circle detection on images using Learning Automata
Venue: arXiv cs.CV 2014
Year: 2014

Hough transform (HT) has been the most common method for circle detection exhibiting robustness but adversely demanding a considerable computational load and large storage. Alternative approaches include heuristic methods that employ iterative optimization procedures for detecting multiple circles under the inconvenience that only one circle can be marked at each optimization cycle demanding a longer execution time. On the other hand, Learning Automata (LA) is a heuristic method to solve complex multi-modal optimization problems. Although LA converges to just one global minimum, the final probability distribution holds valuable information regarding other local minima which have emerged during the optimization process. The detection process is considered as a multi-modal optimization problem, allowing the detection of multiple circular shapes through only one optimization procedure. The algorithm uses a combination of three edge points as parameters to determine circles candidates. A reinforcement signal determines if such circle candidates are actually present at the image. Guided by the values of such reinforcement signal, the set of encoded candidate circles are evolved using the LA so that they can fit into actual circular shapes over the edge-only map of the image. The overall approach is a fast multiple-circle detector despite facing complicated conditions.
Recommending Targeted Strangers from Whom to Solicit Information on Social Media
Venue: arXiv cs.SI 2014
Year: 2014

We present an intelligent, crowd-powered information collection system that automatically identifies and asks target-ed strangers on Twitter for desired information (e.g., cur-rent wait time at a nightclub). Our work includes three parts. First, we identify a set of features that characterize ones willingness and readiness to respond based on their exhibited social behavior, including the content of their tweets and social interaction patterns. Second, we use the identified features to build a statistical model that predicts ones likelihood to respond to information solicitations. Third, we develop a recommendation algorithm that selects a set of targeted strangers using the probabilities computed by our statistical model with the goal to maximize the over-all response rate. Our experiments, including several in the real world, demonstrate the effectiveness of our work.
Grammars with two-sided contexts
Venue: arXiv cs.FL 2014
Year: 2014

In a recent paper (M. Barash, A. Okhotin, "Defining contexts in context-free grammars", LATA 2012), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions and establishes the basic theory of such grammars, leading to a normal form and a parsing algorithm working in time O(n^4), where n is the length of the input string.
Measuring Communication in Parallel Communicating Finite Automata
Venue: arXiv cs.FL 2014
Year: 2014

Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. It is proved that an infinite hierarchy of language families exists, depending on the number of messages sent during their most economical recognitions. Moreover, several properties are shown to be not semi-decidable for the systems under consideration.
On Determinism and Unambiguity of Weighted Two-way Automata
Venue: arXiv cs.FL 2014
Year: 2014

In this paper, we first study the conversion of weighted two-way automata to one-way automata. We show that this conversion preserves the unambiguity but does not preserve the determinism. Yet, we prove that the conversion of an unambiguous weighted one-way automaton into a two-way automaton leads to a deterministic two-way automaton. As a consequence, we prove that unambiguous weighted two-way automata are equivalent to deterministic weighted two-way automata in commutative semirings.
Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes
Venue: arXiv cs.FL 2014
Year: 2014

We study cooperating distributed grammar systems working in hybrid modes in connection with the finite index restriction in two different ways: firstly, we investigate cooperating distributed grammar systems working in hybrid modes which characterize programmed grammars with the finite index restriction; looking at the number of components of such systems, we obtain surprisingly rich lattice structures for the inclusion relations between the corresponding language families. Secondly, we impose the finite index restriction on cooperating distributed grammar systems working in hybrid modes themselves, which leads us to new characterizations of programmed grammars of finite index.
Interactive Reference Point-Based Guided Local Search for the Bi-objective Inventory Routing Problem
Venue: arXiv cs.AI 2014
Year: 2014

Eliciting preferences of a decision maker is a key factor to successfully combine search and decision making in an interactive method. Therefore, the progressively integration and simulation of the decision maker is a main concern in an application. We contribute in this direction by proposing an interactive method based on a reference point-based guided local search to the bi-objective Inventory Routing Problem. A local search metaheuristic, working on the delivery intervals, and the Clarke & Wright savings heuristic is employed for the subsequently obtained Vehicle Routing Problem. To elicit preferences, the decision maker selects a reference point to guide the search in interesting subregions. Additionally, the reference point is used as a reservation point to discard solutions outside the cone, introduced as a convergence criterion. Computational results of the reference point-based guided local search are reported and analyzed on benchmark data in order to show the applicability of the approach.
A Variant of Earley Deduction With Partial Evaluation
Venue: arXiv cs.LO 2014
Year: 2014

We present an algorithm for query evaluation given a logic program consisting of function-free Datalog rules. It is based on Earley Deduction [4, 6] and uses a partial evaluation similar to the one we devel oped for our SLDMagic method [1]. With this, finite automata modeling the evaluation of given queries are generated. In certain cases, the new method is more efficient than SLDMagic and the standard Magic Set method since it can process several deduction steps as one.
Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
Venue: arXiv cs.AI 2014
Year: 2014

The minimum common string partition problem is an NP-hard combinatorial optimization problem with applications in computational biology. In this work we propose the first integer linear programming model for solving this problem. Moreover, on the basis of the integer linear programming model we develop a deterministic 2-phase heuristic which is applicable to larger problem instances. The results show that provenly optimal solutions can be obtained for problem instances of small and medium size from the literature by solving the proposed integer linear programming model with CPLEX. Furthermore, new best-known solutions are obtained for all considered problem instances from the literature. Concerning the heuristic, we were able to show that it outperforms heuristic competitors from the related literature.