OpenRaiser/Intern-Atlas huggingface dataset:
An Efficient Analytical Solution to Thwart DDoS Attacks in Public Domain
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, an analytical model for DDoS attacks detection is proposed, in which propagation of abrupt traffic changes inside public domain is monitored to detect a wide range of DDoS attacks. Although, various statistical measures can be used to construct profile of the traffic normally seen in the network to identify anomalies whenever traffic goes out of profile, we have selected volume and flow measure. Consideration of varying tolerance factors make proposed detection system scalable to the varying network conditions and attack loads in real time. NS-2 network simulator on Linux platform is used as simulation testbed. Simulation results show that our proposed solution gives a drastic improvement in terms of detection rate and false positive rate. However, the mammoth volume generated by DDoS attacks pose the biggest challenge in terms of memory and computational overheads as far as monitoring and analysis of traffic at single point connecting victim is concerned. To address this problem, a distributed cooperative technique is proposed that distributes memory and computational overheads to all edge routers for detecting a wide range of DDoS attacks at early stage.
On the Usefulness of Predicates
Venue: arXiv cs.CC 2012
Year: 2012

Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate $P$ being \emph{useful} for a (real-valued) objective $Q$: given an almost satisfiable Max-$P$ instance, there is an algorithm that beats a random assignment on the corresponding Max-$Q$ instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for $P$ itself. We say that $P$ is useless if it is not useful for any $Q$. This turns out to be equivalent to the following pseudo-randomness property: given an almost satisfiable instance of Max-$P$ it is hard to find an assignment such that the induced distribution on $k$-bit strings defined by the instance is not essentially uniform. Under the Unique Games Conjecture, we give a complete and simple characterization of useful Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pairwise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.
A Bicriteria Approximation for the Reordering Buffer Problem
Venue: arXiv cs.DS 2012
Year: 2012

In the reordering buffer problem (RBP), a server is asked to process a sequence of requests lying in a metric space. To process a request the server must move to the corresponding point in the metric. The requests can be processed slightly out of order; in particular, the server has a buffer of capacity k which can store up to k requests as it reads in the sequence. The goal is to reorder the requests in such a manner that the buffer constraint is satisfied and the total travel cost of the server is minimized. The RBP arises in many applications that require scheduling with a limited buffer capacity, such as scheduling a disk arm in storage systems, switching colors in paint shops of a car manufacturing plant, and rendering 3D images in computer graphics. We study the offline version of RBP and develop bicriteria approximations. When the underlying metric is a tree, we obtain a solution of cost no more than 9OPT using a buffer of capacity 4k + 1 where OPT is the cost of an optimal solution with buffer capacity k. Constant factor approximations were known previously only for the uniform metric (Avigdor-Elgrabli et al., 2012). Via randomized tree embeddings, this implies an O(log n) approximation to cost and O(1) approximation to buffer size for general metrics. Previously the best known algorithm for arbitrary metrics by Englert et al. (2007) provided an O(log^2 k log n) approximation without violating the buffer constraint.
Geodesics in Heat
Venue: arXiv cs.GR 2012
Year: 2012

We introduce the heat method for computing the shortest geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The method represents a significant breakthrough in the practical computation of distance on a wide variety of geometric domains, since the resulting linear systems can be prefactored once and subsequently solved in near-linear time. In practice, distance can be updated via the heat method an order of magnitude faster than with state-of-the-art methods while maintaining a comparable level of accuracy. We provide numerical evidence that the method converges to the exact geodesic distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where more regularity is required.
A Corpus-based Evaluation of Lexical Components of a Domainspecific Text to Knowledge Mapping Prototype
Venue: arXiv cs.IR 2012
Year: 2012

The aim of this paper is to evaluate the lexical components of a Text to Knowledge Mapping (TKM) prototype. The prototype is domain-specific, the purpose of which is to map instructional text onto a knowledge domain. The context of the knowledge domain of the prototype is physics, specifically DC electrical circuits. During development, the prototype has been tested with a limited data set from the domain. The prototype now reached a stage where it needs to be evaluated with a representative linguistic data set called corpus. A corpus is a collection of text drawn from typical sources which can be used as a test data set to evaluate NLP systems. As there is no available corpus for the domain, we developed a representative corpus and annotated it with linguistic information. The evaluation of the prototype considers one of its two main components- lexical knowledge base. With the corpus, the evaluation enriches the lexical knowledge resources like vocabulary and grammar structure. This leads the prototype to parse a reasonable amount of sentences in the corpus.
Extending partial representations of function graphs and permutation graphs
Venue: arXiv cs.DS 2012
Year: 2012

Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability graphs. As such they are recognizable in polynomial time. Function graphs generalize permutation graphs, which arise when all functions considered are linear. We focus on the problem of extending partial representations, which generalizes the recognition problem. We observe that for permutation graphs an easy extension of Golumbic's comparability graph recognition algorithm can be exploited. This approach fails for function graphs. Nevertheless, we present a polynomial-time algorithm for extending a partial representation of a graph by functions defined on the entire interval [0,1] provided for some of the vertices. On the other hand, we show that if a partial representation consists of functions defined on subintervals of [0,1], then the problem of extending this representation to functions on the entire interval [0,1] becomes NP-complete.
Open Problems in Analysis of Boolean Functions
Venue: arXiv cs.DM 2012
Year: 2012

A list of open problems in the field of analysis of boolean functions, compiled February 2012 for the Simons Symposium.
Tradeoff Analysis of Delay-Power-CSIT Quality of Dynamic BackPressure Algorithm for Energy Efficient OFDM Systems
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, we analyze the fundamental power-delay tradeoff in point-to-point OFDM systems under imperfect channel state information quality and non-ideal circuit power. We consider the dynamic back- pressure (DBP) algorithm, where the transmitter determines the rate and power control actions based on the instantaneous channel state information (CSIT) and the queue state information (QSI). We exploit a general fluid queue dynamics using a continuous time dynamic equation. Using the sample-path approach and renewal theory, we decompose the average delay in terms of multiple unfinished works along a sample path, and derive an upper bound on the average delay under the DBP power control, which is asymptotically accurate at small delay regime. We show that despite imperfect CSIT quality and non-ideal circuit power, the average power (P) of the DBP policy scales with delay (D) as P = O(Dexp(1/D)) at small delay regime. While the impacts of CSIT quality and circuit power appears as the coefficients of the scaling law, they may be significant in some operating regimes.
A new job migration algorithm to improve data center efficiency
Venue: arXiv cs.DC 2012
Year: 2012

The under exploitation of the available resources risks to be one of the main problems for a computing center. The growing demand of computational power necessarily entails more complex approaches in the management of the computing resources, with particular attention to the batch queue system scheduler. In a heterogeneous batch queue system, available for both serial single core processes and parallel multi core jobs, it may happen that one or more computational nodes composing the cluster are not fully occupied, running a number of jobs lower than their actual capability. A typical case is represented by more single core jobs running each one over a different multi core server, while more parallel jobs - requiring all the available cores of a host - are queued. A job rearrangement executed at runtime is able to free extra resources, in order to host new processes. We present an efficient method to improve the computing resources exploitation.
Modelling the emergence of spatial patterns of economic activity
Venue: arXiv cs.MA 2012
Year: 2012

Understanding how spatial configurations of economic activity emerge is important when formulating spatial planning and economic policy. A simple model was proposed by Simon, who assumed that firms grow at a rate proportional to their size, and that new divisions of firms with certain probabilities relocate to other firms or to new centres of economic activity. Simon's model produces realistic results in the sense that the sizes of economic centres follow a Zipf distribution, which is also observed in reality. It lacks realism in the sense that mechanisms such as cluster formation, congestion (defined as an overly high density of the same activities) and dependence on the spatial distribution of external parties (clients, labour markets) are ignored. The present paper proposed an extension of the Simon model that includes both centripetal and centrifugal forces. Centripetal forces are included in the sense that firm divisions are more likely to settle in locations that offer a higher accessibility to other firms. Centrifugal forces are represented by an aversion of a too high density of activities in the potential location. The model is implemented as an agent-based simulation model in a simplified spatial setting. By running both the Simon model and the extended model, comparisons are made with respect to their effects on spatial configurations. To this end a series of metrics are used, including the rank-size distribution and indices of the degree of clustering and concentration.
Nonuniform Kolmogorov extractors
Venue: arXiv cs.CC 2012
Year: 2012

We establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness with lower randomness rate. More precisely, as instantiations of more general results, we show that while O(1) amount of advice regarding the source is not enough for extracting a string with randomness rate 1 from a source string with constant subunitary random rate, ω(1) amount of advice is.
OCT Segmentation Survey and Summary Reviews and a Novel 3D Segmentation Algorithm and a Proof of Concept Implementation
Venue: arXiv cs.CV 2012
Year: 2012

We overview the existing OCT work, especially the practical aspects of it. We create a novel algorithm for 3D OCT segmentation with the goals of speed and/or accuracy while remaining flexible in the design and implementation for future extensions and improvements. The document at this point is a running draft being iteratively "developed" as a progress report as the work and survey advance. It contains the review and summarization of select OCT works, the design and implementation of the OCTMARF experimentation application and some results.
Percolation Computation in Complex Networks
Venue: arXiv cs.SI 2012
Year: 2012

K-clique percolation is an overlapping community finding algorithm which extracts particular structures, comprised of overlapping cliques, from complex networks. While it is conceptually straightforward, and can be elegantly expressed using clique graphs, certain aspects of k-clique percolation are computationally challenging in practice. In this paper we investigate aspects of empirical social networks, such as the large numbers of overlapping maximal cliques contained within them, that make clique percolation, and clique graph representations, computationally expensive. We motivate a simple algorithm to conduct clique percolation, and investigate its performance compared to current best-in-class algorithms. We present improvements to this algorithm, which allow us to perform k-clique percolation on much larger empirical datasets. Our approaches perform much better than existing algorithms on networks exhibiting pervasively overlapping community structure, especially for higher values of k. However, clique percolation remains a hard computational problem; current algorithms still scale worse than some other overlapping community finding algorithms.
Optical Solver of Combinatorial Problems: Nano-Technological Approach
Venue: arXiv cs.ET 2012
Year: 2012

We report the first steps in creating an optical computing system. This system may solve NP-Hard problems by utilizing a setup of exponential sized masks. This is exponential space complexity but the production of those masks is done with a polynomial time preprocessing. These masks are later used to solve the problem in polynomial time. We propose to reduced the size of the masks to nano-scaled density. Simulations were done to choose a proper design, and actual implementations show the feasibility of such a system.
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank
Venue: arXiv cs.DS 2012
Year: 2012

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on methods for finding a solution to a system of polynomial inequalities (if one exists). Notably, the best algorithms for this task run in time exponential in the number of variables but polynomial in all of the other parameters (the number of inequalities and the maximum degree). Hence these algorithms motivate natural algebraic questions whose solution have immediate {\em algorithmic} implications: How many variables do we need to represent the decision problem, does $M$ have nonnegative rank at most $r$? A naive formulation uses $nr + mr$ variables and yields an algorithm that is exponential in $n$ and $m$ even for constant $r$. (Arora, Ge, Kannan, Moitra, STOC 2012) recently reduced the number of variables to $2r^2 2^r$, and here we exponentially reduce the number of variables to $2r^2$ and this yields our main algorithm. In fact, the algorithm that we obtain is nearly-optimal (under the Exponential Time Hypothesis) since an algorithm that runs in time $(nm)^{o(r)}$ would yield a subexponential algorithm for 3-SAT . Our main result is based on establishing a normal form for nonnegative matrix factorization - which in turn allows us to exploit algebraic dependence among a large collection of linear transformations with variable entries. Additionally, we also demonstrate that nonnegative rank cannot be certified by even a very large submatrix of $M$, and this property also follows from the intuition gained from viewing nonnegative rank through the lens of systems of polynomial inequalities.
Using parallel processing for file carving
Venue: arXiv cs.CR 2012
Year: 2012

File carving is one of the most important procedures in Digital Forensic Investigation (DFI). But it is also requires the most computational resources. Parallel processing on Graphics Processing Units have proven to be many times faster than when executed on standard CPU. This paper is inspecting the algorithms and methods to use parallel processing for development of file carving tools that will do their job much faster than the conventional DFI tools.
Using high performance computing and Monte Carlo simulation for pricing american options
Venue: arXiv cs.DC 2012
Year: 2012

High performance computing (HPC) is a very attractive and relatively new area of research, which gives promising results in many applications. In this paper HPC is used for pricing of American options. Although the American options are very significant in computational finance; their valuation is very challenging, especially when the Monte Carlo simulation techniques are used. For getting the most accurate price for these types of options we use Quasi Monte Carlo simulation, which gives the best convergence. Furthermore, this algorithm is implemented on both GPU and CPU. Additionally, the CUDA architecture is used for harnessing the power and the capability of the GPU for executing the algorithm in parallel which is later compared with the serial implementation on the CPU. In conclusion this paper gives the reasons and the advantages of applying HPC in computational finance.
Modelling spatial patterns of economic activity in the Netherlands
Venue: arXiv cs.MA 2012
Year: 2012

Understanding how spatial configurations of economic activity emerge is important when formulating spatial planning and economic policy. Not only micro-simulation and agent-based model such as UrbanSim, ILUMAS and SIMFIRMS, but also Simon's model of hierarchical concentration have widely applied, for this purpose. These models, however, have limitations with respect to simulating structural changes in spatial economic systems and the impact of proximity. The present paper proposes a model of firm development that is based on behavioural rules such as growth, closure, spin-off and relocation. An important aspect of the model is that locational preferences of firms are based on agglomeration advantages, accessibility of markets and congestion, allowing for a proper description of concentration and deconcentration tendencies. By comparing the outcomes of the proposed model with real world data, we will calibrate the parameters and assess how well the model predicts existing spatial configurations and decide. The model is implemented as an agent-based simulation model describing firm development in the Netherlands in 21 industrial sectors from 1950 to 2004.
Schedulability Test for Soft Real-Time Systems under Multiprocessor Environment by using an Earliest Deadline First Scheduling Algorithm
Venue: arXiv cs.OS 2012
Year: 2012

This paper deals with the study of Earliest Deadline First (EDF) which is an optimal scheduling algorithm for uniprocessor real time systems use for scheduling the periodic task in soft real-time multiprocessor systems. In hard real-time systems, a significant disparity exists EDF-based schemes and RMA scheduling (which is the only known way of optimally scheduling recurrent real-time tasks on multiprocessors): on M processors, all known EDF variants have utilization-based schedulability bounds of approximately M/2, while RMA algorithms can fully utilize all processors. This is unfortunate because EDF based algorithms entail lower scheduling and task migration overheads. In work on hard real-time systems, it has been shown that this disparity in Schedulability can be lessened by placing caps on per task utilizations. Our main contribution is a new EDF based scheme that ensures bounded deadline tardiness. In this scheme, per-task utilizations must be focused,but overall utilization need not be stricted. Our scheme should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization. Also propose techniques and heuristics that can be used to reduce tardiness as well as increase the efficiency of task.
Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
Venue: arXiv cs.DS 2012
Year: 2012

Motivation The Burrows-Wheeler transform (BWT) is the foundation of many algorithms for compression and indexing of text data, but the cost of computing the BWT of very large string collections has prevented these techniques from being widely applied to the large sets of sequences often encountered as the outcome of DNA sequencing experiments. In previous work, we presented a novel algorithm that allows the BWT of human genome scale data to be computed on very moderate hardware, thus enabling us to investigate the BWT as a tool for the compression of such datasets. Results We first used simulated reads to explore the relationship between the level of compression and the error rate, the length of the reads and the level of sampling of the underlying genome and compare choices of second-stage compression algorithm. We demonstrate that compression may be greatly improved by a particular reordering of the sequences in the collection and give a novel `implicit sorting' strategy that enables these benefits to be realised without the overhead of sorting the reads. With these techniques, a 45x coverage of real human genome sequence data compresses losslessly to under 0.5 bits per base, allowing the 135.3Gbp of sequence to fit into only 8.2Gbytes of space (trimming a small proportion of low-quality bases from the reads improves the compression still further). This is more than 4 times smaller than the size achieved by a standard BWT-based compressor (bzip2) on the untrimmed reads, but an important further advantage of our approach is that it facilitates the building of compressed full text indexes such as the FM-index on large-scale DNA sequence collections.
Shortest Path Set Induced Vertex Ordering and its Application to Distributed Distance Optimal Multi-agent Formation Path Planning
Venue: arXiv cs.RO 2012
Year: 2012

For the task of moving a group of indistinguishable agents on a connected graph with unit edge lengths into an arbitrary goal formation, it was previously shown that distance optimal paths can be scheduled to complete with a tight convergence time guarantee, using a fully centralized algorithm. In this study, we show that the problem formulation in fact induces a more fundamental ordering of the vertices on the underlying graph network, which directly leads to a more intuitive scheduling algorithm that assures the same convergence time and runs faster. More importantly, this structure enables a distributed scheduling algorithm once individual paths are assigned to the agents, which was not possible before. The vertex ordering also readily extends to more general graphs - those with non-unit capacities and edge lengths - for which we again guarantee the convergence time until the desired formation is achieved.