OpenRaiser/Intern-Atlas huggingface dataset:
On Detecting Messaging Abuse in Short Text Messages using Linguistic and Behavioral patterns
Venue: arXiv cs.CL 2014
Year: 2014

The use of short text messages in social media and instant messaging has become a popular communication channel during the last years. This rising popularity has caused an increment in messaging threats such as spam, phishing or malware as well as other threats. The processing of these short text message threats could pose additional challenges such as the presence of lexical variants, SMS-like contractions or advanced obfuscations which can degrade the performance of traditional filtering solutions. By using a real-world SMS data set from a large telecommunications operator from the US and a social media corpus, in this paper we analyze the effectiveness of machine learning filters based on linguistic and behavioral patterns in order to detect short text spam and abusive users in the network. We have also explored different ways to deal with short text message challenges such as tokenization and entity detection by using text normalization and substring clustering techniques. The obtained results show the validity of the proposed solution by enhancing baseline approaches.
Clearing Contamination in Large Networks
Venue: arXiv cs.SI 2014
Year: 2014

In this work, we study the problem of clearing contamination spreading through a large network where we model the problem as a graph searching game. The problem can be summarized as constructing a search strategy that will leave the graph clear of any contamination at the end of the searching process in as few steps as possible. We show that this problem is NP-hard even on directed acyclic graphs and provide an efficient approximation algorithm. We experimentally observe the performance of our approximation algorithm in relation to the lower bound on several large online networks including Slashdot, Epinions and Twitter. The experiments reveal that in most cases our algorithm performs near optimally.
Challenges and Issues in Adapting Web Contents on Small Screen Devices
Venue: arXiv cs.HC 2014
Year: 2014

In general, Web pages are intended for large screen devices using HTML technology. Admittance of such Web pages on Small Screen Devices (SSDs) like mobile phones, palmtops, tablets, PDA etc., is increasing with the support of the current wireless technologies. However, SSDs have limited screen size, memory capacity and bandwidth, which makes accessing the Website on SSDs extremely difficult. There are many approaches have been proposed in literature to regenerate HTML Web pages suitable for browsing on SSDs. These proposed methods involve segment the Web page based on its semantic structure, followed by noise removal based on block features and to utilize the hierarchy of the content element to regenerate a page suitable for Small Screen Devices. But World Wide Web consortium stated that, HTML does not provide a better description of semantic structure of the web page contents. To overcome this draw backs, Web developers started to develop Web pages using new technologies like XML, Flash etc. It makes a way for new research methods. Therefore, we require an approach to reconstruct these Web pages suitable for SSDs. However, existing approaches in literature do not perform well for Web pages erected using XML and Flash. In this paper, we have emphasized a few issues of the existing approaches on XML, Flash Datasets and propose an approach that performs better on data set comprising of Flash Web pages.
Continuous Yao Graphs
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < θ\leq 2π$, we define the continuous Yao graph $cY(θ)$ with vertex set $S$ and angle $θ$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(θ)$ if there exists a cone with apex $p$ and aperture $θ$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(θ)$ for different values of $θ$. Using a new algebraic technique, we show that $cY(θ)$ is a spanner when $θ\leq 2π/3$. We believe that this technique may be of independent interest. We also show that $cY(π)$ is not a spanner, and that $cY(θ)$ may be disconnected for $θ> π$.
Approximate Revenue Maximization in Interdependent Value Settings
Venue: arXiv cs.GT 2014
Year: 2014

We study revenue maximization in settings where agents' values are interdependent: each agent receives a signal drawn from a correlated distribution and agents' values are functions of all of the signals. We introduce a variant of the generalized VCG auction with reserve prices and random admission, and show that this auction gives a constant approximation to the optimal expected revenue in matroid environments. Our results do not require any assumptions on the signal distributions, however, they require the value functions to satisfy a standard single-crossing property and a concavity-type condition.
On Optimal Decision-Making in Ant Colonies
Venue: arXiv cs.DC 2014
Year: 2014

Colonies of ants can collectively choose the best of several nests, even when many of the active ants who organize the move visit only one site. Understanding such a behavior can help us design efficient distributed decision making algorithms. Marshall et al. propose a model for house-hunting in colonies of ant Temnothorax albipennis. Unfortunately, their model does not achieve optimal decision-making while laboratory experiments show that, in fact, colonies usually achieve optimality during the house-hunting process. In this paper, we argue that the model of Marshall et al. can achieve optimality by including nest size information in their mathematical model. We use lab results of Pratt et al. to re-define the differential equations of Marshall et al. Finally, we sketch our strategy for testing the optimality of the new model.
Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
Venue: arXiv cs.OH 2014
Year: 2014

We present a fundamentally different approach to orthogonal layout of data flow diagrams with ports. This is based on extending constrained stress majorization to cater for ports and flow layout. Because we are minimizing stress we are able to better display global structure, as measured by several criteria such as stress, edge-length variance, and aspect ratio. Compared to the layered approach, our layouts tend to exhibit symmetries, and eliminate inter-layer whitespace, making the diagrams more compact.
A non-commutative analogue of the Odlyzko bounds and bounds on performance for space-time lattice codes
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers space-time coding over several independently Rayleigh faded blocks. In particular we will concentrate on giving upper bounds for the coding gain of lattice space-time codes as the number of blocks grow. This problem was previously considered in the single antenna case by Bayer et al. in 2006. Crucial to their work was Odlyzko's bound on the discriminant of an algebraic number field, as this provides an upper bound for the normalized coding gain of number field codes. In the MIMO context natural codes are constructed from division algebras defined over number fields and the coding gain is measured by the discriminant of the corresponding (non-commutative) algebra. In this paper we will develop analogues of the Odlyzko bounds in this context and show how these bounds limit the normalized coding gain of a very general family of division algebra based space-time codes. These bounds can also be used as benchmarks in practical code design and as tools to analyze asymptotic bounds of performance as the number of independently faded blocks increases.
Constructive Multiuser Interference in Symbol Level Precoding for the MISO Downlink Channel
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the problem of interference among the simultaneous multiuser transmissions in the downlink of multiple antennas systems. Using symbol level precoding, a new approach towards the multiuser interference is discussed along this paper. The concept of exploiting the interference between the spatial multiuser transmissions by jointly utilizing the data information (DI) and channel state information (CSI), in order to design symbol-level precoders, is proposed. In this direction, the interference among the data streams is transformed under certain conditions to useful signal that can improve the signal to interference noise ratio (SINR) of the downlink transmissions. We propose a maximum ratio transmission (MRT) based algorithm that jointly exploits DI and CSI to glean the benefits from constructive multiuser interference. Subsequently, a relation between the constructive interference downlink transmission and physical layer multicasting is established. In this context, novel constructive interference precoding techniques that tackle the transmit power minimization (min power) with individual SINR constraints at each user's receivers is proposed. Furthermore, fairness through maximizing the weighted minimum SINR (max min SINR) of the users is addressed by finding the link between the min power and max min SINR problems. Moreover, heuristic precoding techniques are proposed to tackle the weighted sum rate problem. Finally, extensive numerical results show that the proposed schemes outperform other state of the art techniques.
A Covert Channel Using Named Resources
Venue: arXiv cs.CR 2014
Year: 2014

A network covert channel is created that uses resource names such as addresses to convey information, and that approximates typical user behavior in order to blend in with its environment. The channel correlates available resource names with a user defined code-space, and transmits its covert message by selectively accessing resources associated with the message codes. In this paper we focus on an implementation of the channel using the Hypertext Transfer Protocol (HTTP) with Uniform Resource Locators (URLs) as the message names, though the system can be used in conjunction with a variety of protocols. The covert channel does not modify expected protocol structure as might be detected by simple inspection, and our HTTP implementation emulates transaction level web user behavior in order to avoid detection by statistical or behavioral analysis.
Be Careful When Assuming the Obvious: Commentary on "The placement of the head that minimizes online memory: a complex systems approach"
Venue: arXiv cs.CL 2014
Year: 2014

Ferrer-i-Cancho (2015) presents a mathematical model of both the synchronic and diachronic nature of word order based on the assumption that memory costs are a never decreasing function of distance and a few very general linguistic assumptions. However, even these minimal and seemingly obvious assumptions are not as safe as they appear in light of recent typological and psycholinguistic evidence. The interaction of word order and memory has further depths to be explored.
Software Cloning in Extreme Programming Environment
Venue: arXiv cs.SE 2014
Year: 2014

Software systems are evolving by adding new functions and modifying existing functions over time. Through the evolution, the structure of software is becoming more complex and so the understandability and maintainability of software systems is deteriorating day by day. These are not only important but one of the most expensive activities in software development. Refactoring has often been applied to the software to improve them. One of the targets of refactoring is to limit Code Cloning because it hinders software maintenance and affects its quality. And in order to cope with the constant changes, refactoring is seen as an essential component of Extreme Programming. Agile Methods use refactoring as important key practice and are first choice for developing clone-free code. This paper summarizes my overview talk on software cloning analysis. It first discusses the notion of code cloning, types of clones, reasons, its consequences and analysis. It highlights Code Cloning in Extreme Programming Environment and finds Clone Detection as effective tool for Refactoring.
Speeding Up Graph Algorithms via Switching Classes
Venue: arXiv cs.DS 2014
Year: 2014

Given a graph $G$, a vertex switch of $v \in V(G)$ results in a new graph where neighbors of $v$ become nonneighbors and vice versa. This operation gives rise to an equivalence relation over the set of labeled digraphs on $n$ vertices. The equivalence class of $G$ with respect to the switching operation is commonly referred to as $G$'s switching class. The algebraic and combinatorial properties of switching classes have been studied in depth; however, they have not been studied as thoroughly from an algorithmic point of view. The intent of this work is to further investigate the algorithmic properties of switching classes. In particular, we show that switching classes can be used to asymptotically speed up several super-linear unweighted graph algorithms. The current techniques for speeding up graph algorithms are all somewhat involved insofar that they employ sophisticated pre-processing, data-structures, or use "word tricks" on the RAM model to achieve at most a $O(\log(n))$ speed up for sufficiently dense graphs. Our methods are much simpler and can result in super-polylogarithmic speedups. In particular, we achieve better bounds for diameter, transitive closure, bipartite maximum matching, and general maximum matching.
A Study of Proxies for Shapley Allocations of Transport Costs
Venue: arXiv cs.GT 2014
Year: 2014

We propose and evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Such cost to serve analysis has application both strategically and operationally in transportation. The problem is formally given by the traveling salesperson game (TSG), a cooperative total utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The cost to serve a location is an allocated portion of the cost of an optimal tour. The Shapley value is one of the most important normative division schemes in cooperative games, giving a principled and fair allocation both for the TSG and more generally. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and present the first proof that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we then develop six proxies for that value which are relatively easy to compute. We perform an experimental evaluation using Synthetic Euclidean games as well as games derived from real-world tours calculated for fast-moving consumer goods scenarios. Our experiments show that several computationally tractable allocation techniques correspond to good proxies for the Shapley value.
Embedding Four-directional Paths on Convex Point Sets
Venue: arXiv cs.CG 2014
Year: 2014

A directed path whose edges are assigned labels "up", "down", "right", or "left" is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four labels are used. A \emph{direction-consistent embedding} of an \mbox{$n$-vertex} four-directional path $P$ on a set $S$ of $n$ points in the plane is a straight-line drawing of $P$ where each vertex of $P$ is mapped to a distinct point of $S$ and every edge points to the direction specified by its label. We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.
Approximation algorithms for Capacitated Facility Location Problem with Penalties
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we address the problem of capacitated facility location problem with penalties (CapFLPP) paid per unit of unserved demand. In case of uncapacitated FLP with penalties demands of a client are either entirely met or are entirely rejected and penalty is paid. In the uncapacitated case, there is no reason to serve a client partially. Whereas, in case of CapFLPP, it may be beneficial to serve a client partially instead of not serving at all and, pay the penalty for the unmet demand. Charikar et. al. \cite{charikar2001algorithms}, Jain et. al. \cite{jain2003greedy} and Xu- Xu \cite{xu2009improved} gave $3$, $2$ and $1.8526$ approximation, respectively, for the uncapacitated case . We present $(5.83 + ε)$ factor for the case of uniform capacities and $(8.532 + ε)$ factor for non-uniform capacities.
Predicting academic success in Belgium and France Comparison and integration of variables related to student behavior
Venue: arXiv cs.CY 2014
Year: 2014

Having observed low success rates among first-year university students in both Belgium and France, we develop prediction models in this paper in order to identify, at the earliest possible stage, those students who are at risk of failing at the end of the academic year. We applied different data mining techniques to predict the students' academic success. We find that it is very difficult to predict success by only considering the variables related to behavior during classes, and that it is necessary to add variables related to personal history, involvement in and behavior during their studies, and perceptions of academic life, to obtain good-quality results.
An Automatic Mixed Software Hardware Pipeline Builder for CPU-FPGA Platforms
Venue: arXiv cs.DC 2014
Year: 2014

Our toolchain for accelerating application called Courier-FPGA, is designed for utilize the processing power of CPU-FPGA platforms for software programmers and non-expert users. It automatically gathers runtime information of library functions from a running target binary, and constructs the function call graph including input-output data. Then, it uses corresponding predefined hardware modules if these are ready for FPGA and prepares software functions on CPU by using Pipeline Generator. The Pipeline Generator builds a pipeline control program by using Intel Threading Building Block to run both hardware modules and software functions in parallel. Finally, Courier-FPGA dynamically replaces the original functions in the binary and accelerates it by using the built pipeline. Courier-FPGA performs these acceleration processes without user intervention, source code tweaks or re-compilations of the binary. We describe the technical details of this mixed software hardware pipeline on CPU-FPGA platforms in this paper. In our case study, Courier-FPGA was used to accelerate a corner detection using the Harris-Stephens method application binary on the Zynq platform. A series of functions were off-loaded, and speed up 15.36 times was achieved by using the built pipeline.
A Model of the Commit Size Distribution of Open Source
Venue: arXiv cs.SE 2014
Year: 2014

A fundamental unit of work in programming is the code contribution ("commit") that a developer makes to the code base of the project in work. We use statistical methods to derive a model of the probabilistic distribution of commit sizes in open source projects and we show that the model is applicable to different project sizes. We use both graphical as well as statistical methods to validate the goodness of fit of our model. By measuring and modeling a fundamental dimension of programming we help improve software development tools and our understanding of software development.
Is Evaluating Visual Search Interfaces in Digital Libraries Still an Issue?
Venue: arXiv cs.IR 2014
Year: 2014

Although various visual interfaces for digital libraries have been developed in prototypical systems, very few of these visual approaches have been integrated into today's digital libraries. In this position paper we argue that this is most likely due to the fact that the evaluation results of most visual systems lack comparability. There is no fix standard on how to evaluate visual interactive user interfaces. Therefore it is not possible to identify which approach is more suitable for a certain context. We feel that the comparability of evaluation results could be improved by building a common evaluation setup consisting of a reference system, based on a standardized corpus with fixed tasks and a panel for possible participants.
Enabling the Multi-User Generalized Degrees of Freedom in the Gaussian Cellular Channel
Venue: arXiv cs.IT 2014
Year: 2014

There has been major progress over the last decade in understanding the classical interference channel (IC). Recent key results show that constant bit gap capacity results can be obtained from linear deterministic models (LDMs). However, it is widely unrecognized that the time-invariant, frequency-flat cellular channel, which contains the IC as a special case, possesses some additional generalized degrees of freedom (GDoF) due to multi-user operation. This was proved for the LDM cellular channel very recently but is an open question for the corresponding Gaussian counterpart. In this paper, we close this gap and provide an achievable sum-rate for the Gaussian cellular channel which is within a constant bit gap of the LDM sum capacity. We show that the additional GDoFs from the LDM cellular channel carry over. This is enabled by signal scale alignment. In particular, the multi-user gain reduces the interference by half in the 2-user per cell case compared to the IC.
Uniform Sampling for Matrix Approximation
Venue: arXiv cs.DS 2014
Year: 2014

Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances. We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation. This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.
Improving the Interpretability of Support Vector Machines-based Fuzzy Rules
Venue: arXiv cs.LG 2014
Year: 2014

Support vector machines (SVMs) and fuzzy rule systems are functionally equivalent under some conditions. Therefore, the learning algorithms developed in the field of support vector machines can be used to adapt the parameters of fuzzy systems. Extracting fuzzy models from support vector machines has the inherent advantage that the model does not need to determine the number of rules in advance. However, after the support vector machine learning, the complexity is usually high, and interpretability is also impaired. This paper not only proposes a complete framework for extracting interpretable SVM-based fuzzy modeling, but also provides optimization issues of the models. Simulations examples are given to embody the idea of this paper.