OpenRaiser/Intern-Atlas huggingface dataset:
Towards the Solution of Power Dissipation in Electronics Systems through Thermodynamics
Venue: arXiv cs.OH 2012
Year: 2012

Power loss in the electronic system is a very crucial limiting factor that can be reduced or minimized with the help of using the reversible logics "a concept came from Thermodynamics". In this paper the authors shows the concept of reversible logics for the Electronics system. The logical and physical designing approach is given in the paper in detail. The contradiction of logical and physical reversibility with the conventional CMOS designing is also shows and the solution of that contradiction is also proposed by the authors using adiabatic logic. This Paper gives a complete and clear idea if the thermodynamical concept for the electronics industries for power reduction.
Lazy AC-Pattern Matching for Rewriting
Venue: arXiv cs.LO 2012
Year: 2012

We define a lazy pattern-matching mechanism modulo associativity and commutativity. The solutions of a pattern-matching problem are stored in a lazy list composed of a first substitution at the head and a non-evaluated object that encodes the remaining computations. We integrate the lazy AC-matching in a strategy language: rewriting rule and strategy application produce a lazy list of terms.
Cusp Points in the Parameter Space of Degenerate 3-RPR Planar Parallel Manipulators
Venue: arXiv cs.RO 2012
Year: 2012

This paper investigates the conditions in the design parameter space for the existence and distribution of the cusp locus for planar parallel manipulators. Cusp points make possible non-singular assembly-mode changing motion, which increases the maximum singularity-free workspace. An accurate algorithm for the determination is proposed amending some imprecisions done by previous existing algorithms. This is combined with methods of Cylindric Algebraic Decomposition, Gröbner bases and Discriminant Varieties in order to partition the parameter space into cells with constant number of cusp points. These algorithms will allow us to classify a family of degenerate 3-RPR manipulators.
The traveling salesman problem for lines and rays in the plane
Venue: arXiv cs.CG 2012
Year: 2012

In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of $n$ regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length $L$.
Distributed GraphLab: A Framework for Machine Learning in the Cloud
Venue: arXiv cs.DB 2012
Year: 2012

While high-level data parallel frameworks, like MapReduce, simplify the design and implementation of large-scale data processing systems, they do not naturally or efficiently support many important data mining and machine learning algorithms and can lead to inefficient learning systems. To help fill this critical void, we introduced the GraphLab abstraction which naturally expresses asynchronous, dynamic, graph-parallel computation while ensuring data consistency and achieving a high degree of parallel performance in the shared-memory setting. In this paper, we extend the GraphLab framework to the substantially more challenging distributed setting while preserving strong data consistency guarantees. We develop graph based extensions to pipelined locking and data versioning to reduce network congestion and mitigate the effect of network latency. We also introduce fault tolerance to the GraphLab abstraction using the classic Chandy-Lamport snapshot algorithm and demonstrate how it can be easily implemented by exploiting the GraphLab abstraction itself. Finally, we evaluate our distributed implementation of the GraphLab abstraction on a large Amazon EC2 deployment and show 1-2 orders of magnitude performance gains over Hadoop-based implementations.
Learning Semantic String Transformations from Examples
Venue: arXiv cs.DB 2012
Year: 2012

We address the problem of performing semantic transformations on strings, which may represent a variety of data types (or their combination) such as a column in a relational table, time, date, currency, etc. Unlike syntactic transformations, which are based on regular expressions and which interpret a string as a sequence of characters, semantic transformations additionally require exploiting the semantics of the data type represented by the string, which may be encoded as a database of relational tables. Manually performing such transformations on a large collection of strings is error prone and cumbersome, while programmatic solutions are beyond the skill-set of end-users. We present a programming by example technology that allows end-users to automate such repetitive tasks. We describe an expressive transformation language for semantic manipulation that combines table lookup operations and syntactic manipulations. We then present a synthesis algorithm that can learn all transformations in the language that are consistent with the user-provided set of input-output examples. We have implemented this technology as an add-in for the Microsoft Excel Spreadsheet system and have evaluated it successfully over several benchmarks picked from various Excel help-forums.
Understanding differential equations through diffusion point of view: non-symmetric discrete equations
Venue: arXiv cs.NA 2012
Year: 2012

In this paper, we propose a new adaptation of the D-iteration algorithm to numerically solve the differential equations. This problem can be reinterpreted in 2D or 3D (or higher dimensions) as a limit of a diffusion process where the boundary or initial conditions are replaced by fluid catalysts. It has been shown that pre-computing the diffusion process for an elementary catalyst case as a fundamental block of a class of differential equations, the computation efficiency can be greatly improved. Here, we explain how the diffusion point of view can be applied to decompose the fluid diffusion process per direction and how to handle non-symmetric discrete equations. The method can be applied on the class of problems that can be addressed by the Gauss-Seidel iteration, based on the linear approximation of the differential equations.
A 3D Segmentation Method for Retinal Optical Coherence Tomography Volume Data
Venue: arXiv cs.CV 2012
Year: 2012

With the introduction of spectral-domain optical coherence tomography (OCT), much larger image datasets are routinely acquired compared to what was possible using the previous generation of time-domain OCT. Thus, the need for 3-D segmentation methods for processing such data is becoming increasingly important. We present a new 3D segmentation method for retinal OCT volume data, which generates an enhanced volume data by using pixel intensity, boundary position information, intensity changes on both sides of the border simultaneously, and preliminary discrete boundary points are found from all A-Scans and then the smoothed boundary surface can be obtained after removing a small quantity of error points. Our experiments show that this method is efficient, accurate and robust.
Comparing Soft Computing Techniques For Early Stage Software Development Effort Estimations
Venue: arXiv cs.SE 2012
Year: 2012

Accurately estimating the software size, cost, effort and schedule is probably the biggest challenge facing software developers today. It has major implications for the management of software development because both the overestimates and underestimates have direct impact for causing damage to software companies. Lot of models have been proposed over the years by various researchers for carrying out effort estimations. Also some of the studies for early stage effort estimations suggest the importance of early estimations. New paradigms offer alternatives to estimate the software development effort, in particular the Computational Intelligence (CI) that exploits mechanisms of interaction between humans and processes domain knowledge with the intention of building intelligent systems (IS). Among IS, Artificial Neural Network and Fuzzy Logic are the two most popular soft computing techniques for software development effort estimation. In this paper neural network models and Mamdani FIS model have been used to predict the early stage effort estimations using the student dataset. It has been found that Mamdani FIS was able to predict the early stage efforts more efficiently in comparison to the neural network models based models.
Standing on the Shoulders of Their Peers: Success Factors for Massive Cooperation Among Children Creating Open Source Animations and Games on Their Smartphones
Venue: arXiv cs.CY 2012
Year: 2012

We developed a website for kids where they can share new as well as remixed animations and games, e.g., interactive music videos, which they created on their smartphones or tablets using a visual "LEGO-style" programming environment called Catroid. Online communities for children like our website have unique requirements, and keeping the commitment of kids on a high level is a continuous challenge. For instance, one key motivator for kids is the ability to entertain their friends. Another success factor is the ability to learn from and cooperate with other children. In this short position paper we attempt at identifying the requirements for the success of such an online community, both from the point of view of the kids as well as of their parents, and at finding ways to make it attractive for both.
FuGeIDS: Fuzzy Genetic paradigms in Intrusion Detection Systems
Venue: arXiv cs.CR 2012
Year: 2012

With the increase in the number of security threats, Intrusion Detection Systems have evolved as a significant countermeasure against these threats. And as such, the topic of Intrusion Detection Systems has become one of the most prominent research topics in recent years. This paper gives an overview of the Intrusion Detection System and looks at two major machine learning paradigms used in Intrusion Detection System, Genetic Algorithms and Fuzzy Logic and how to apply them for intrusion detection.
Off-Path Attacking the Web
Venue: arXiv cs.CR 2012
Year: 2012

We show how an off-path (spoofing-only) attacker can perform cross-site scripting (XSS), cross-site request forgery (CSRF) and site spoofing/defacement attacks, without requiring vulnerabilities in either web-browser or server and circumventing known defenses. Attacker can also launch devastating denial of service (DoS) attacks, even when the connection between the client and the server is secured with SSL/TLS. The attacks are practical and require a puppet (malicious script in browser sandbox) running on a the victim client machine, and attacker capable of IP-spoofing on the Internet. Our attacks use a technique allowing an off-path attacker to learn the sequence numbers of both client and server in a TCP connection. The technique exploits the fact that many computers, in particular those running Windows, use a global IP-ID counter, which provides a side channel allowing efficient exposure of the connection sequence numbers. We present results of experiments evaluating the learning technique and the attacks that exploit it. Finally, we present practical defenses that can be deployed at the firewall level; no changes to existing TCP/IP stacks are required.
Chromatic Clustering in High Dimensional Space
Venue: arXiv cs.CG 2012
Year: 2012

In this paper, we study a new type of clustering problem, called {\em Chromatic Clustering}, in high dimensional space. Chromatic clustering seeks to partition a set of colored points into groups (or clusters) so that no group contains points with the same color and a certain objective function is optimized. In this paper, we consider two variants of the problem, chromatic $k$-means clustering (denoted as $k$-CMeans) and chromatic $k$-medians clustering (denoted as $k$-CMedians), and investigate their hardness and approximation solutions. For $k$-CMeans, we show that the additional coloring constraint destroys several key properties (such as the locality property) used in existing $k$-means techniques (for ordinary points), and significantly complicates the problem. There is no FPTAS for the chromatic clustering problem, even if $k=2$. To overcome the additional difficulty, we develop a standalone result, called {\em Simplex Lemma}, which enables us to efficiently approximate the mean point of an unknown point set through a fixed dimensional simplex. A nice feature of the simplex is its independence with the dimensionality of the original space, and thus can be used for problems in very high dimensional space. With the simplex lemma, together with several random sampling techniques, we show that a $(1+ε)$-approximation of $k$-CMeans can be achieved in near linear time through a sphere peeling algorithm. For $k$-CMedians, we show that a similar sphere peeling algorithm exists for achieving constant approximation solutions.
Improving Achievable Rate for the Two-User SISO Interference Channel with Improper Gaussian Signaling
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the achievable rate region of the two-user single-input-single-output (SISO) Gaussian interference channel, when the improper Gaussian signaling is applied. Under the assumption that the interference is treated as additive Gaussian noise, we show that the user's achievable rate can be expressed as a summation of the rate achievable by the conventional proper Gaussian signaling, which depends on the users' input covariances only, and an additional term, which is a function of both the users' covariances and pseudo-covariances. The additional degree of freedom given by the pseudo-covariance, which is conventionally set to be zero for the case of proper Gaussian signaling, provides an opportunity to improve the achievable rate by employing the improper Gaussian signaling. Since finding the optimal solution for the joint covariance and pseudo-covariance optimization is difficult, we propose a sub-optimal but efficient algorithm by separately optimizing these two sets of parameters. Numerical results show that the proposed algorithm provides a close-to-optimal performance as compared to the exhaustive search method, and significantly outperforms the optimal proper Gaussian signaling and other existing improper Gaussian signaling schemes.
TH*:Scalable Distributed Trie Hashing
Venue: arXiv cs.DS 2012
Year: 2012

In today's world of computers, dealing with huge amounts of data is not unusual. The need to distribute this data in order to increase its availability and increase the performance of accessing it is more urgent than ever. For these reasons it is necessary to develop scalable distributed data structures. In this paper we propose a TH* distributed variant of the Trie Hashing data structure. First we propose Thsw new version of TH without node Nil in digital tree (trie), then this version will be adapted to multicomputer environment. The simulation results reveal that TH* is scalable in the sense that it grows gracefully, one bucket at a time, to a large number of servers, also TH* offers a good storage space utilization and high query efficiency special for ordering operations.
On the calculation of percentile-based bibliometric indicators
Venue: arXiv cs.DL 2012
Year: 2012

A percentile-based bibliometric indicator is an indicator that values publications based on their position within the citation distribution of their field. The most straightforward percentile-based indicator is the proportion of frequently cited publications, for instance the proportion of publications that belong to the top 10% most frequently cited of their field. Recently, more complex percentile-based indicators were proposed. A difficulty in the calculation of percentile-based indicators is caused by the discrete nature of citation distributions combined with the presence of many publications with the same number of citations. We introduce an approach to calculating percentile-based indicators that deals with this difficulty in a more satisfactory way than earlier approaches suggested in the literature. We show in a formal mathematical framework that our approach leads to indicators that do not suffer from biases in favor of or against particular fields of science.
Reed's conjecture on some special classes of graphs
Venue: arXiv cs.DM 2012
Year: 2012

Reed conjectured that for any graph $G$, $χ(G) \leq \lceil \frac{ω(G)+Δ(G)+1}{2}\rceil$, where $χ(G)$, $ω(G)$, and $Δ(G)$ respectively denote the chromatic number, the clique number and the maximum degree of $G$. In this paper, we verify this conjecture for some special classes of graphs, in particular for subclasses of $P_5$-free graphs or $Chair$-free graphs.
Towards a new metamodel for the Task Flow Model of the Discovery Method
Venue: arXiv cs.SE 2012
Year: 2012

This paper presents our proposal for the evolution of the metamodel for the Task Algebra in the Task Flow model for the Discovery Method. The original Task Algebra is based on simple and compound tasks structured using operators such as sequence, selection, and parallel composition. Recursion and encapsulation were also considered. We propose additional characteristics to improve the capabilities of the metamodel to represent accurately the Task Flow Model.
Method Study on the 3x+1 Problem
Venue: arXiv cs.DM 2012
Year: 2012

The 3x+1 problem is one of the most classical problems in computer science, related to many fields. As it is thought by scientists a highly hard problem, resolving it successfully not only can improve the research in many relating fields, but also be meaningful to the method study. By deep analyzing the 3x+1 calculation process with the input positive integer becoming greater, we find a useful way for solving this problem with high probability. By making use of the greater calculating ability of great computers and the internet, our way is a valid and powerful way for utterly solving the 3x+1 problem. This way can be expressed in three points: 1) If we can find a positive integer N, for any positive integer less than 2N, the times of dividing 2 out of its stopping time is less than or equal to N, then the 3x+1 conjecture is true; 2) This N may be big, so the calculation may be too big. Our way for solving this is: to find a positive integer K, for all positive integers less than 2K, not all the times of dividing 2 out of their stopping time for these integers are less than or equal to K, some part of these are greater than K, but the number of this part becomes less and less with the K increasing; 3) This K and the calculation may also be too big, our way for solving this is: to find a positive integer R, for all positive integers less than 2R, as above, out of their stopping time, the times of dividing 2 of some part of these integers are greater than R, also the number of this part integers does not become less immediately with the R increasing, but the increasing rate of this number is less and less until to below zero.
Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators
Venue: arXiv cs.SC 2012
Year: 2012

We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyze the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.
Scheduling Unrelated Machines of Few Different Types
Venue: arXiv cs.DS 2012
Year: 2012

A very well-known machine model in scheduling allows the machines to be unrelated, modelling jobs that might have different characteristics on each machine. Due to its generality, many optimization problems of this form are very difficult to tackle and typically APX-hard. However, in many applications the number of different types of machines, such as processor cores, GPUs, etc. is very limited. In this paper, we address this point and study the assignment of jobs to unrelated machines in the case that each machine belongs to one of a fixed number of types and the machines of each type are identical. We present polynomial time approximation schemes (PTASs) for minimizing the makespan for multidimensional jobs with a fixed number of dimensions and for minimizing the L_p-norm. In particular, our results subsume and generalize the existing PTASs for a constant number of unrelated machines and for an arbitrary number of identical machines for these problems. We employ a number of techniques which go beyond the previously known results, including a new counting argument and a method for making the concept of sparse extreme point solutions usable for a convex program.
Towards Ecology Inspired Software Engineering
Venue: arXiv cs.SE 2012
Year: 2012

Ecosystems are complex and dynamic systems. Over billions of years, they have developed advanced capabilities to provide stable functions, despite changes in their environment. In this paper, we argue that the laws of organization and development of ecosystems provide a solid and rich source of inspiration to lay the foundations for novel software construction paradigms that provide stability as much as openness.
A Durable Flash Memory Search Tree
Venue: arXiv cs.DS 2012
Year: 2012

We consider the task of optimizing the B-tree data structure, used extensively in operating systems and databases, for sustainable usage on multi-level flash memory. Empirical evidence shows that this new flash memory tree, or FM Tree, extends the operational lifespan of each block of flash memory by a factor of roughly 27 to 70 times, while still supporting logarithmic-time search tree operations.
Interactive Learning through Hands-on Practice using Electronic Mini - Lab (EML): a Case Study
Venue: arXiv cs.CY 2012
Year: 2012

-- In this paper, a new approach to impart practical skill based technical education is presented in comprehensive manner. An Electronic Mini-Lab (EML) is devised containing basic design and test instruments with electronic components, ICs, connecting wires and battery. Using the EML, students perform various formal and informal digital and analog circuit practicals as well as design prototype of projects. This gives them a hands-on experience, sense of belonging and sense of cooperation. The EML is useful for performing many practicals of various subjects. The EML also reduces the workload of college laboratories. Students have their own individual EML at their disposal anytime, which can be used to design hobby projects as a fun too. This will make them skilled engineers. This provides tremendous benefits in teaching learning process. It also boosted the interest, confidence of students and teachers. Incorporating active/ cooperative learning into traditional instruction can be a useful pedagogical tool to help students to perform practicals and project work any time anywhere. This concept is remarkably simple and cost effective but the dividends can be profound.
Divide-and-Conquer 3D Convex Hulls on the GPU
Venue: arXiv cs.DC 2012
Year: 2012

We describe a pure divide-and-conquer parallel algorithm for computing 3D convex hulls. We implement that algorithm on GPU hardware, and find a significant speedup over comparable CPU implementations.
Sequential-Access FM-Indexes
Venue: arXiv cs.DS 2012
Year: 2012

Previous authors have shown how to build FM-indexes efficiently in external memory, but querying them efficiently remains an open problem. Searching naïvely for a pattern $P$ requires (Θ(|P|)) random access. In this paper we show how, by storing a few small auxiliary tables, we can access data only in the order in which they appear on disk, which should be faster.