OpenRaiser/Intern-Atlas huggingface dataset:
Volumetric Mapping of Genus Zero Objects via Mass Preservation
Venue: arXiv cs.CG 2012
Year: 2012

In this work, we present a technique to map any genus zero solid object onto a hexahedral decomposition of a solid cube. This problem appears in many applications ranging from finite element methods to visual tracking. From this, one can then hopefully utilize the proposed technique for shape analysis, registration, as well as other related computer graphics tasks. More importantly, given that we seek to establish a one-to-one correspondence of an input volume to that of a solid cube, our algorithm can naturally generate a quality hexahedral mesh as an output. In addition, we constrain the mapping itself to be volume preserving allowing for the possibility of further mesh simplification. We demonstrate our method both qualitatively and quantitatively on various 3D solid models
Detecting Spammers via Aggregated Historical Data Set
Venue: arXiv cs.CR 2012
Year: 2012

The battle between email service providers and senders of mass unsolicited emails (Spam) continues to gain traction. Vast numbers of Spam emails are sent mainly from automatic botnets distributed over the world. One method for mitigating Spam in a computationally efficient manner is fast and accurate blacklisting of the senders. In this work we propose a new sender reputation mechanism that is based on an aggregated historical data-set which encodes the behavior of mail transfer agents over time. A historical data-set is created from labeled logs of received emails. We use machine learning algorithms to build a model that predicts the \emph{spammingness} of mail transfer agents in the near future. The proposed mechanism is targeted mainly at large enterprises and email service providers and can be used for updating both the black and the white lists. We evaluate the proposed mechanism using 9.5M anonymized log entries obtained from the biggest Internet service provider in Europe. Experiments show that proposed method detects more than 94% of the Spam emails that escaped the blacklist (i.e., TPR), while having less than 0.5% false-alarms. Therefore, the effectiveness of the proposed method is much higher than of previously reported reputation mechanisms, which rely on emails logs. In addition, the proposed method, when used for updating both the black and white lists, eliminated the need in automatic content inspection of 4 out of 5 incoming emails, which resulted in dramatic reduction in the filtering computational load.
Preservation under Substructures modulo Bounded Cores
Venue: arXiv cs.LO 2012
Year: 2012

We investigate a model-theoretic property that generalizes the classical notion of "preservation under substructures". We call this property \emph{preservation under substructures modulo bounded cores}, and present a syntactic characterization via $Σ_2^0$ sentences for properties of arbitrary structures definable by FO sentences. As a sharper characterization, we further show that the count of existential quantifiers in the $Σ_2^0$ sentence equals the size of the smallest bounded core. We also present our results on the sharper characterization for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the sharper characterization fails, but for which the classical Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.
Almost Universal Hash Families are also Storage Enforcing
Venue: arXiv cs.IT 2012
Year: 2012

We show that every almost universal hash function also has the storage enforcement property. Almost universal hash functions have found numerous applications and we show that this new storage enforcement property allows the application of almost universal hash functions in a wide range of remote verification tasks: (i) Proof of Secure Erasure (where we want to remotely erase and securely update the code of a compromised machine with memory-bounded adversary), (ii) Proof of Ownership (where a storage server wants to check if a client has the data it claims to have before giving access to deduplicated data) and (iii) Data possession (where the client wants to verify whether the remote storage server is storing its data). Specifically, storage enforcement guarantee in the classical data possession problem removes any practical incentive for the storage server to cheat the client by saving on storage space. The proof of our result relies on a natural combination of Kolmogorov Complexity and List Decoding. To the best of our knowledge this is the first work that combines these two techniques. We believe the newly introduced storage enforcement property of almost universal hash functions will open promising avenues of exciting research under memory-bounded (bounded storage) adversary model.
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Venue: arXiv cs.DS 2012
Year: 2012

Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented; the algorithm can add a few elements to the incrementally constructed set, and reaps a reward equal to the value of the new weighted rank function on the current set. The goal of the algorithm as it builds this independent set online is to maximize the sum of these (weighted rank) rewards. As in regular online analysis, we compare the rewards of our online algorithm to that of an offline optimum, namely a single independent set of the matroid that maximizes the sum of the weighted rank rewards that arrive over time. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint. In this paper, we present the first randomized online algorithms for this problem with poly-logarithmic competitive ratio. To do this, we employ the LP formulation of a scaled reward version of the problem. Then we extend a weighted-majority type update rule along with uncrossing properties of tight sets in the matroid polytope to find an approximately optimal fractional LP solution. We use the fractional solution values as probabilities for a online randomized rounding algorithm. To show that our rounding produces a sufficiently large reward independent set, we prove and use new covering properties for randomly rounded fractional solutions in the matroid polytope that may be of independent interest.
A Tail Bound for Read-k Families of Functions
Venue: arXiv cs.DM 2012
Year: 2012

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,...,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,...,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,...,Y_r$.
Optimal Algorithms for Near-Hitless Network Restoration via Diversity Coding
Venue: arXiv cs.NI 2012
Year: 2012

Diversity coding is a network restoration technique which offers near-hitless restoration, while other state-of-the art techniques are significantly slower. Furthermore, the extra spare capacity requirement of diversity coding is competitive with the others. Previously, we developed heuristic algorithms to employ diversity coding structures in networks with arbitrary topology. This paper presents two algorithms to solve the network design problems using diversity coding in an optimal manner. The first technique pre-provisions static traffic whereas the second technique carries out the dynamic provisioning of the traffic on-demand. In both cases, diversity coding results in smaller restoration time, simpler synchronization, and much reduced signaling complexity than the existing techniques in the literature. A Mixed Integer Programming (MIP) formulation and an algorithm based on Integer Linear Programming (ILP) are developed for pre-provisioning and dynamic provisioning, respectively. Simulation results indicate that diversity coding has significantly higher restoration speed than Shared Path Protection (SPP) and p-cycle techniques. It requires more extra capacity than the p-cycle technique and SPP. However, the increase in the total capacity is negligible compared to the increase in the restoration speed.
Characterizing Ranked Chinese Syllable-to-Character Mapping Spectrum: A Bridge Between the Spoken and Written Chinese Language
Venue: arXiv cs.CL 2012
Year: 2012

One important aspect of the relationship between spoken and written Chinese is the ranked syllable-to-character mapping spectrum, which is the ranked list of syllables by the number of characters that map to the syllable. Previously, this spectrum is analyzed for more than 400 syllables without distinguishing the four intonations. In the current study, the spectrum with 1280 toned syllables is analyzed by logarithmic function, Beta rank function, and piecewise logarithmic function. Out of the three fitting functions, the two-piece logarithmic function fits the data the best, both by the smallest sum of squared errors (SSE) and by the lowest Akaike information criterion (AIC) value. The Beta rank function is the close second. By sampling from a Poisson distribution whose parameter value is chosen from the observed data, we empirically estimate the $p$-value for testing the two-piece-logarithmic-function being better than the Beta rank function hypothesis, to be 0.16. For practical purposes, the piecewise logarithmic function and the Beta rank function can be considered a tie.
CSHURI - Modified HURI algorithm for Customer Segmentation and Transaction Profitability
Venue: arXiv cs.DB 2012
Year: 2012

Association rule mining (ARM) is the process of generating rules based on the correlation between the set of items that the customers purchase.Of late, data mining researchers have improved upon the quality of association rule mining for business development by incorporating factors like value (utility), quantity of items sold (weight) and profit. The rules mined without considering utility values (profit margin) will lead to a probable loss of profitable rules. The advantage of wealth of the customers' needs information and rules aids the retailer in designing his store layout[9]. An algorithm CSHURI, Customer Segmentation using HURI, is proposed, a modified version of HURI [6], finds customers who purchase high profitable rare items and accordingly classify the customers based on some criteria; for example, a retail business may need to identify valuable customers who are major contributors to a company's overall profit. For a potential customer arriving in the store, which customer group one should belong to according to customer needs, what are the preferred functional features or products that the customer focuses on and what kind of offers will satisfy the customer, etc., finds the key in targeting customers to improve sales [9], which forms the base for customer utility mining.
Visitor schedule management system- an intelligent decision support system
Venue: arXiv cs.OH 2012
Year: 2012

Travelling salesman problem is a problem which is of high interest for researchers, industry professionals, and academicians. Visitor or salesman used to face lot of problems with respect to scheduling based on meeting top ranked clients. Even excel sheet made the work tedious. So these flaws propelled us to design an intelligent decision support system. This paper reports the problem definition we tried to address and possible solution to this problem. We even explained the project design and implementation of our visitor schedule management system.. Our system made a major contribution in terms of valuable resources such as time and satisfying high ranked clients efficiently. We used optimization via mathematical programming to solve these issues.
Traductor Writing System Web
Venue: arXiv cs.OH 2012
Year: 2012

A compilator is a program which is development in a programming language that read a file known as source. After this file have to translate and have to convert in other program known as object or to generate a exit. The best way for to know any programming language is analizing a compilation process which is same in all programming paradigm existents. To like to generate a tool that permit a learning in university course. This course could explain in any plataform such as Linux o Windows. This goal is posible through development a Web aplication which is unite with a compilator, it is Traductor Writing System (Sistema de Escritura de Traductores). This system is complete and permit extend and modify the compilator. The system is a module in Moodle which is a Course Management System (CMS) that help teachers for to create comunities of learning in line. This software is in free software license (GPL).
Power control in reactive routing protocol for Mobile Ad Hoc Network
Venue: arXiv cs.NI 2012
Year: 2012

The aim of this work is to change the routing strategy of AODV protocol (Ad hoc On Demand Vector) in order to improve the energy consumption in mobile ad hoc networks (MANET). The purpose is to minimize the regular period of HELLO messages generated by the AODV protocol used for the research, development and maintenance of routes. This information is useful to have an idea about battery power levels of different network hosts. After storing this information, the node elect the shortest path following the classical model used this information to elect safest path (make a compromise) in terms of energy. Transmitter node does not select another node as its battery will be exhausted soon. Any node of the network can have the same information's about the neighborhoods as well as other information about the energy level of the different terminal to avoid routing using a link that will be lost due to an exhausted battery of a node in this link. Analytical study and simulations by Jist/SWANS have been conducted to note that no divergence relatively to the classical AODV, a node can have this type of information that improves the energy efficiency in ad hoc networks.
Improved Fair-Zone technique using Mobility Prediction in WSN
Venue: arXiv cs.NI 2012
Year: 2012

The self-organizational ability of ad-hoc Wireless Sensor Networks (WSNs) has led them to be the most popular choice in ubiquitous computing. Clustering sensor nodes organizing them hierarchically have proven to be an effective method to provide better data aggregation and scalability for the sensor network while conserving limited energy. It has some limitation in energy and mobility of nodes. In this paper we propose a mobility prediction technique which tries overcoming above mentioned problems and improves the life time of the network. The technique used here is Exponential Moving Average for online updates of nodal contact probability in cluster based network.
Rainbow Colouring of Split and Threshold Graphs
Venue: arXiv cs.DM 2012
Year: 2012

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k larger than 2, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.
A Network-Coded Diversity Protocol for Collision Recovery in Slotted ALOHA Networks
Venue: arXiv cs.NI 2012
Year: 2012

We propose a collision recovery scheme for symbol-synchronous slotted ALOHA (SA) based on physical layer network coding over extended Galois Fields. Information is extracted from colliding bursts allowing to achieve higher maximum throughput with respect to previously proposed collision recovery schemes. An energy analysis is also performed, and it is shown that, by adjusting the transmission probability, high energy efficiency can be achieved. The paper also addresses several practical aspects, namely frequency, phase, and amplitude estimation, as well as partial symbol asynchronism. A performance evaluation is carried out using the proposed algorithms, revealing remarkable performance in terms of normalized throughput.
A comparative study of clusterhead selection algorithms in wireless sensor networks
Venue: arXiv cs.NI 2012
Year: 2012

In Wireless Sensor Network, sensor nodes life time is the most critical parameter. Many researches on these lifetime extension are motivated by LEACH scheme, which by allowing rotation of cluster head role among the sensor nodes tries to distribute the energy consumption over all nodes in the network. Selection of clusterhead for such rotation greatly affects the energy efficiency of the network. Different communication protocols and algorithms are investigated to find ways to reduce power consumption. In this paper brief survey is taken from many proposals, which suggests different clusterhead selection strategies and a global view is presented. Comparison of their costs of clusterhead selection in different rounds, transmission method and other effects like cluster formation, distribution of clusterheads and creation of clusters shows a need of a combined strategy for better results.
Finite-time and Asymptotic Convergence of Distributed Averaging and Maximizing Algorithms
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we formulate and investigate a generalized consensus algorithm which makes an attempt to unify distributed averaging and maximizing algorithms considered in the literature. Each node iteratively updates its state as a time-varying weighted average of its own state, the minimal state, and the maximal state of its neighbors. We prove that finite-time consensus is almost impossible for averaging under this uniform model. Both time-dependent and state-dependent graphs are considered, and various necessary and/or sufficient conditions are presented on the consensus convergence. For time-dependent graphs, we show that quasi-strong connectivity is critical for averaging, as is strong connectivity for maximizing. For state-dependent graphs defined by a $μ$-nearest-neighbor rule, where each node interacts with its $μ$ nearest smaller neighbors and the $μ$ nearest larger neighbors, we show that $μ+1$ is a critical threshold on the total number of nodes for the transit from finite-time to asymptotic convergence for averaging, in the absence of node self-confidence. The threshold is $2μ$ if each node chooses to connect only to neighbors with unique values. Numerical examples illustrate the tightness of the conditions. The results characterize some fundamental similarities and differences between distributed averaging and maximizing algorithms.
The non-algorithmic side of the mind
Venue: arXiv cs.AI 2012
Year: 2012

The existence of a non-algorithmic side of the mind, conjectured by Penrose on the basis of Gödel's first incompleteness theorem, is investigated here in terms of a quantum metalanguage. We suggest that, besides human ordinary thought, which can be formalized in a computable, logical language, there is another important kind of human thought, which is Turing-non-computable. This is methatought, the process of thinking about ordinary thought. Metathought can be formalized as a metalanguage, which speaks about and controls the logical language of ordinary thought. Ordinary thought has two computational modes, the quantum mode and the classical mode, the latter deriving from decoherence of the former. In order to control the logical language of the quantum mode, one needs to introduce a quantum metalanguage, which in turn requires a quantum version of Tarski Convention T.
Plücker Embedding of Cyclic Orbit Codes
Venue: arXiv cs.IT 2012
Year: 2012

Cyclic orbit codes are a family of constant dimension codes used for random network coding. We investigate the Plücker embedding of these codes and show how to efficiently compute the Grassmann coordinates of the code words.
The Natural Gradient by Analogy to Signal Whitening, and Recipes and Tricks for its Use
Venue: arXiv cs.LG 2012
Year: 2012

The natural gradient allows for more efficient gradient descent by removing dependencies and biases inherent in a function's parameterization. Several papers present the topic thoroughly and precisely. It remains a very difficult idea to get your head around however. The intent of this note is to provide simple intuition for the natural gradient and its use. We review how an ill conditioned parameter space can undermine learning, introduce the natural gradient by analogy to the more widely understood concept of signal whitening, and present tricks and specific prescriptions for applying the natural gradient to learning problems.
Distributed Multicell Beamforming Design Approaching Pareto Boundary with Max-Min Fairness
Venue: arXiv cs.IT 2012
Year: 2012

This paper addresses coordinated downlink beamforming optimization in multicell time-division duplex (TDD) systems where a small number of parameters are exchanged between cells but with no data sharing. With the goal to reach the point on the Pareto boundary with max-min rate fairness, we first develop a two-step centralized optimization algorithm to design the joint beamforming vectors. This algorithm can achieve a further sum-rate improvement over the max-min optimal performance, and is shown to guarantee max-min Pareto optimality for scenarios with two base stations (BSs) each serving a single user. To realize a distributed solution with limited intercell communication, we then propose an iterative algorithm by exploiting an approximate uplink-downlink duality, in which only a small number of positive scalars are shared between cells in each iteration. Simulation results show that the proposed distributed solution achieves a fairness rate performance close to the centralized algorithm while it has a better sum-rate performance, and demonstrates a better tradeoff between sum-rate and fairness than the Nash Bargaining solution especially at high signal-to-noise ratio.
Factors affecting acceptance of web-based training system: Using extended UTAUT and structural equation modeling
Venue: arXiv cs.OH 2012
Year: 2012

Advancement in information system leads organizations to apply e-learning system to train their employees in order to enhance its performance. In this respect, applying web based training will enable the organization to train their employees quickly, efficiently and effectively anywhere at any time. This research aims to extend Unified Theory of Acceptance and Use Technology (UTAUT) using some factors such flexibility of web based training system, system interactivity and system enjoyment, in order to explain the employees' intention to use web based training system. A total of 290 employees have participated in this study. The findings of the study revealed that performance expectancy, facilitating conditions, social influence and system flexibility have direct effect on the employees' intention to use web based training system, while effort expectancy, system enjoyment and system interactivity have indirect effect on employees' intention to use the system.