OpenRaiser/Intern-Atlas huggingface dataset:
Experimental Study of A Novel Variant of Fiduccia Mattheyses(FM) Partitioning Algorithm
Venue: arXiv cs.DS 2014
Year: 2014

Partitioning is a well studied research problem in the area of VLSI physical design automation. In this problem, input is an integrated circuit and output is a set of almost equal disjoint blocks. The main objective of partitioning is to assign the components of circuit to blocks in order to minimize the numbers of inter-block connections. A partitioning algorithm using hypergraph was proposed by Fiduccia and Mattheyses with linear time complexity which has been popularly known as FM algorithm. Most of the hypergraph based partitioning algorithms proposed in the literature are variants of FM algorithm. In this paper, we have proposed a novel variant of FM algorithm by using pair wise swapping technique. We have performed a comparative experimental study of FM algorithm and our proposed algorithm using two dataset such as ISPD98 and ISPD99. Experimental results show that performance of our proposed algorithm is better than the FM algorithm using the above dataset.
Object Tracking via Non-Euclidean Geometry: A Grassmann Approach
Venue: arXiv cs.CV 2014
Year: 2014

A robust visual tracking system requires an object appearance model that is able to handle occlusion, pose, and illumination variations in the video stream. This can be difficult to accomplish when the model is trained using only a single image. In this paper, we first propose a tracking approach based on affine subspaces (constructed from several images) which are able to accommodate the abovementioned variations. We use affine subspaces not only to represent the object, but also the candidate areas that the object may occupy. We furthermore propose a novel approach to measure affine subspace-to-subspace distance via the use of non-Euclidean geometry of Grassmann manifolds. The tracking problem is then considered as an inference task in a Markov Chain Monte Carlo framework via particle filtering. Quantitative evaluation on challenging video sequences indicates that the proposed approach obtains considerably better performance than several recent state-of-the-art methods such as Tracking-Learning-Detection and MILtrack.
On the Complexity of Computing Two Nonlinearity Measures
Venue: arXiv cs.CC 2014
Year: 2014

We study the computational complexity of two Boolean nonlinearity measures: the nonlinearity and the multiplicative complexity. We show that if one-way functions exist, no algorithm can compute the multiplicative complexity in time $2^{O(n)}$ given the truth table of length $2^n$, in fact under the same assumption it is impossible to approximate the multiplicative complexity within a factor of $(2-ε)^{n/2}$. When given a circuit, the problem of determining the multiplicative complexity is in the second level of the polynomial hierarchy. For nonlinearity, we show that it is #P hard to compute given a function represented by a circuit.
Efficient Distributed Online Prediction and Stochastic Optimization with Approximate Distributed Averaging
Venue: arXiv cs.IT 2014
Year: 2014

We study distributed methods for online prediction and stochastic optimization. Our approach is iterative: in each round nodes first perform local computations and then communicate in order to aggregate information and synchronize their decision variables. Synchronization is accomplished through the use of a distributed averaging protocol. When an exact distributed averaging protocol is used, it is known that the optimal regret bound of $\mathcal{O}(\sqrt{m})$ can be achieved using the distributed mini-batch algorithm of Dekel et al. (2012), where $m$ is the total number of samples processed across the network. We focus on methods using approximate distributed averaging protocols and show that the optimal regret bound can also be achieved in this setting. In particular, we propose a gossip-based optimization method which achieves the optimal regret bound. The amount of communication required depends on the network topology through the second largest eigenvalue of the transition matrix of a random walk on the network. In the setting of stochastic optimization, the proposed gossip-based approach achieves nearly-linear scaling: the optimization error is guaranteed to be no more than $ε$ after $\mathcal{O}(\frac{1}{n ε^2})$ rounds, each of which involves $\mathcal{O}(\log n)$ gossip iterations, when nodes communicate over a well-connected graph. This scaling law is also observed in numerical experiments on a cluster.
Global solar irradiation prediction using a multi-gene genetic programming approach
Venue: arXiv cs.NE 2014
Year: 2014

In this paper, a nonlinear symbolic regression technique using an evolutionary algorithm known as multi-gene genetic programming (MGGP) is applied for a data-driven modelling between the dependent and the independent variables. The technique is applied for modelling the measured global solar irradiation and validated through numerical simulations. The proposed modelling technique shows improved results over the fuzzy logic and artificial neural network (ANN) based approaches as attempted by contemporary researchers. The method proposed here results in nonlinear analytical expressions, unlike those with neural networks which is essentially a black box modelling approach. This additional flexibility is an advantage from the modelling perspective and helps to discern the important variables which affect the prediction. Due to the evolutionary nature of the algorithm, it is able to get out of local minima and converge to a global optimum unlike the back-propagation (BP) algorithm used for training neural networks. This results in a better percentage fit than the ones obtained using neural networks by contemporary researchers. Also a hold-out cross validation is done on the obtained genetic programming (GP) results which show that the results generalize well to new data and do not over-fit the training samples. The multi-gene GP results are compared with those, obtained using its single-gene version and also the same with four classical regression models in order to show the effectiveness of the adopted approach.
Clustering Concept Chains from Ordered Data without Path Descriptions
Venue: arXiv cs.AI 2014
Year: 2014

This paper describes a process for clustering concepts into chains from data presented randomly to an evaluating system. There are a number of rules or guidelines that help the system to determine more accurately what concepts belong to a particular chain and what ones do not, but it should be possible to write these in a generic way. This mechanism also uses a flat structure without any hierarchical path information, where the link between two concepts is made at the level of the concept itself. It does not require related metadata, but instead, a simple counting mechanism is used. Key to this is a count for both the concept itself and also the group or chain that it belongs to. To test the possible success of the mechanism, concept chain parts taken randomly from a larger ontology were presented to the system, but only at a depth of 2 concepts each time. That is - root concept plus a concept that it is linked to. The results show that this can still lead to very variable structures being formed and can also accommodate some level of randomness.
Service-Fingerprinting mittels Fuzzing
Venue: arXiv cs.CR 2014
Year: 2014

Service fingerprinting (i.e. the identification of network services and other applications on computing systems) is an essential part of penetration tests. The main contribution of this paper is a study on the improvement of fingerprinting tools. By applying mutation-based fuzzing as a fingerprint generation method, subtle differences in response messages can be identified. These differences in response messages provide means for the differentiation and identification of network services. To prove the feasibility of the approach, an implementation of a fingerprinting tool for ftp servers is presented and compared to preexisting fingerprinting tools. As a result of this study it is shown that mutation-based fuzzing is an appropriate method for service fingerprinting that even offers advantages over preexisting methods.
A Metric for Modelling and Measuring Complex Behavioural Systems
Venue: arXiv cs.MA 2014
Year: 2014

This paper describes a metric for measuring the success of a complex system composed of agents performing autonomous behaviours. Because of the difficulty in evaluating such systems, this metric will help to give an initial indication as to how suitable the agents would be for solving the problem. The system is modelled as a script, or behavioural ontology, with a number of variables to represent each of the behaviour attributes. The set of equations can be used both for modeling and as part of the simulation evaluation. Behaviours can be nested, allowing for compound behaviours of arbitrary complexity to be built. There is also the capability for including rules or decision making into the script. The paper also gives some test examples to show how the metric might be used.
Is getting the right answer just about choosing the right words? The role of syntactically-informed features in short answer scoring
Venue: arXiv cs.CL 2014
Year: 2014

Developments in the educational landscape have spurred greater interest in the problem of automatically scoring short answer questions. A recent shared task on this topic revealed a fundamental divide in the modeling approaches that have been applied to this problem, with the best-performing systems split between those that employ a knowledge engineering approach and those that almost solely leverage lexical information (as opposed to higher-level syntactic information) in assigning a score to a given response. This paper aims to introduce the NLP community to the largest corpus currently available for short-answer scoring, provide an overview of methods used in the shared task using this data, and explore the extent to which more syntactically-informed features can contribute to the short answer scoring task in a way that avoids the question-specific manual effort of the knowledge engineering approach.
Large-Scale Geospatial Processing on Multi-Core and Many-Core Processors: Evaluations on CPUs, GPUs and MICs
Venue: arXiv cs.DB 2014
Year: 2014

Geospatial Processing, such as queries based on point-to-polyline shortest distance and point-in-polygon test, are fundamental to many scientific and engineering applications, including post-processing large-scale environmental and climate model outputs and analyzing traffic and travel patterns from massive GPS collections in transportation engineering and urban studies. Commodity parallel hardware, such as multi-core CPUs, many-core GPUs and Intel MIC accelerators, provide enormous computing power which can potentially achieve significant speedups on existing geospatial processing and open the opportunities for new applications. However, the realizable potential for geospatial processing on these new hardware devices is largely unknown due to the complexity in porting serial algorithms to diverse parallel hardware platforms. In this study, we aim at experimenting our data-parallel designs and implementations of point-to-polyline shortest distance computation (P2P) and point-in-polygon topological test (PIP) on different commodity hardware using real large-scale geospatial data, comparing their performance and discussing important factors that may significantly affect the performance. Our experiments have shown that, while GPUs can be several times faster than multi-core CPUs without utilizing the increasingly available SIMD computing power on Vector Processing Units (VPUs) that come with multi-core CPUs and MICs, multi-core CPUs and MICs can be several times faster than GPUs when VPUs are utilized. By adopting a Domain Specific Language (DSL) approach to exploiting the VPU computing power in geospatial processing, we are free from programming SIMD intrinsic functions directly which makes the new approach more effective, portable and scalable. Our designs, implementations and experiments can serve as case studies for parallel geospatial computing on modern commodity parallel hardware.
A Linear Category of Polynomial Functors (extensional part)
Venue: arXiv cs.LO 2014
Year: 2014

We construct a symmetric monoidal closed category of polynomial endofunctors (as objects) and simulation cells (as morphisms). This structure is defined using universal properties without reference to representing polynomial diagrams and is reminiscent of Day's convolution on presheaves. We then make this category into a model for intuitionistic linear logic by defining an additive and exponential structure.
Spectrum Sensing Via Reconfigurable Antennas: Fundamental Limits and Potential Gains
Venue: arXiv cs.NI 2014
Year: 2014

We propose a novel paradigm for spectrum sensing in cognitive radio networks that provides diversity and capacity benefits using a single antenna at the Secondary User (SU) receiver. The proposed scheme is based on a reconfigurable antenna: an antenna that is capable of altering its radiation characteristics by changing its geometric configuration. Each configuration is designated as an antenna mode or state and corresponds to a distinct channel realization. Based on an abstract model for the reconfigurable antenna, we tackle two different settings for the cognitive radio problem and present fundamental limits on the achievable diversity and throughput gains. First, we explore the (to cooperate or not to cooperate) tradeoff between the diversity and coding gains in conventional cooperative and noncooperative spectrum sensing schemes, showing that cooperation is not always beneficial. Based on this analysis, we propose two sensing schemes based on reconfigurable antennas that we term as state switching and state selection. It is shown that each of these schemes outperform both cooperative and non-cooperative spectrum sensing under a global energy constraint. Next, we study the (sensing-throughput) trade-off, and demonstrate that using reconfigurable antennas, the optimal sensing time is reduced allowing for a longer transmission time, and thus better throughput. Moreover, state selection can be applied to boost the capacity of SU transmission.
OCCA: A unified approach to multi-threading languages
Venue: arXiv cs.DC 2014
Year: 2014

The inability to predict lasting languages and architectures led us to develop OCCA, a C++ library focused on host-device interaction. Using run-time compilation and macro expansions, the result is a novel single kernel language that expands to multiple threading languages. Currently, OCCA supports device kernel expansions for the OpenMP, OpenCL, and CUDA platforms. Computational results using finite difference, spectral element and discontinuous Galerkin methods show OCCA delivers portable high performance in different architectures and platforms.
On Connectivity of Airborne Networks
Venue: arXiv cs.NI 2014
Year: 2014

Mobility pattern of nodes in a mobile network has significant impact on the connectivity properties of the network. One such mobile network that has drawn attention of researchers in the past few years is the Airborne Networks (AN) due to its importance in civil and military purpose and due to the several complex issues in these domains. Since the nodes in an airborne network (AN) are heterogeneous and mobile, the design of a reliable and robust AN is highly complex and challenging. In this paper a persistent backbone based architecture for an AN has been considered where a set of airborne networking platforms (ANPs - aircrafts, UAVs and satellites) form the backbone of the AN. End to end connectivity of the backbone nodes is crucial in providing the communication among the hosts. Since ANPs are prone to failure because of attacks like EMP attack or jamming, another important issue is to improve the robustness of the backbone network against these attacks. Such attacks will impact specific geographic regions at specific times and if an ANP is within the fault region during the time of attack, it will fail. This paper focuses on connectivity and fault-tolerance issues in ANs and studies algorithms to compute the minimum transmission range of ANPs in fault free and faulty scenarios to ensure network connectivity all the times. It also considers the scenario where the network may have to operate in a disconnected mode for some part of time and data transmissions may be tolerant to some amount of delay. Hence, ANPs may not need to have end-to-end paths all the time but they should be able to transmit data to each other within bounded time.
From abstract modelling to remote cyber-physical integration/interoperability testing
Venue: arXiv cs.SE 2014
Year: 2014

An appropriate system model gives developers a better overview, and the ability to fix more inconsistencies more effectively and earlier in system development, reducing overall effort and cost. However, modelling assumes abstraction of several aspects of the system and its environment, and this abstraction should be not overlooked, but properly taken into account during later development phases. This is especially especially important for the cases of remote integration, testing/verification, and manufacturing of cyber-physical systems. For this reason we introduce a development methodology for cyber-physical systems (CPS) with a focus on the abstraction levels of the system representation, based on the idea of refinement-based development of complex, interactive systems.
Frequency-Shift Filtering for OFDM Signal Recovery in Narrowband Power Line Communications
Venue: arXiv cs.OH 2014
Year: 2014

Power line communications (PLC) has been drawing considerable interest in recent years due to the growing interest in smart grid implementation. Specifically, network control and grid applications are allocated the frequency band of 0-500 kHz, commonly referred to as the narrowband PLC channel. This frequency band is characterized by strong periodic noise which results in low signal to noise ratio (SNR). In this work we propose a receiver which uses frequency shift filtering to exploit the cyclostationary properties of both the narrowband power line noise, as well as the information signal, digitally modulated using orthogonal frequency division multiplexing. An adaptive implementation for the proposed receiver is presented as well. The proposed receiver is compared to existing receivers via analysis and simulation. The results show that the receiver proposed in this work obtains a substantial performance gain over previously proposed receivers, without requiring any coordination with the transmitter.
Compressed Subsequence Matching and Packed Tree Coloring
Venue: arXiv cs.DS 2014
Year: 2014

We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size $n$ compressing a string of size $N$ and a pattern string of size $m$ over an alphabet of size $σ$, our algorithm uses $O(n+\frac{nσ}{w})$ space and $O(n+\frac{nσ}{w}+m\log N\log w\cdot occ)$ or $O(n+\frac{nσ}{w}\log w+m\log N\cdot occ)$ time. Here $w$ is the word size and $occ$ is the number of occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for $occ=o(\frac{n}{\log N})$ occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.
Analyzing a practitioner perspective on relevance of published empirical research in Requirements Engineering
Venue: arXiv cs.SE 2014
Year: 2014

Background: Relevance to industry and scientific rigor have long been an area of friction in IS research. However little work has been done on how to evaluate IS research relevance. Kitchenham et al [13] proposed one of the few relevance evaluating instruments in literature, later revised by Daneva et al [7]. Aim: To analyze the practitioner/consultant perspective checklist1 for relevance in order to evaluate its comprehensibility and applicability from the point of view of the practitioner/consultant in the context of an advanced university classroom. Method: Five master level students in the field of IS assessed a set of 24 papers using the relevance checklist1. For each question in the checklist, inter-rater agreement has been calculated and the reasoning that the practitioners applied has been reconstructed from comments. Results: Inter-rater agreement only showed to be slight for three questions and poor for all other questions. Analysis of comments provided by the practitioners showed only two questions that were interpreted in the same way by all practitioners. These two questions showed significantly higher inter-rater agreement than other questions. Conclusions: The generally low inter-rater agreement could be explained as an indication that the checklist1 is in its current form not appropriate for measuring industry relevance of IS research. The different interpretations found for the checklist questions provide useful insight for reformulation of questions. Reformulations are proposed for some questions.
A Taxonomy for Attack Patterns on Information Flows in Component-Based Operating Systems
Venue: arXiv cs.CR 2014
Year: 2014

We present a taxonomy and an algebra for attack patterns on component-based operating systems. In a multilevel security scenario, where isolation of partitions containing data at different security classifications is the primary security goal and security breaches are mainly defined as undesired disclosure or modification of classified data, strict control of information flows is the ultimate goal. In order to prevent undesired information flows, we provide a classification of information flow types in a component-based operating system and, by this, possible patterns to attack the system. The systematic consideration of informations flows reveals a specific type of operating system covert channel, the covert physical channel, which connects two former isolated partitions by emitting physical signals into the computer's environment and receiving them at another interface.
Multichannel RSS-based Device-Free Localization with Wireless Sensor Network
Venue: arXiv cs.NI 2014
Year: 2014

RSS-based device-free localization (DFL) is a very promising technique which allows localizing the target without attaching any electronic tags in wireless environments. In cluttered indoor environments, the performance of DFL degrades due to multipath interference. In this paper, we propose a multichannel obstructed link detection method based on the RSS variation on difference channels. Multichannel detection is proved to be very effective in multipath environments compared to the single channel detection. We also propose a new localization method termed as robust weighted least square (RWLS) method. RWLS first use spatial property to eliminate the interference links and then employ WLS method to localize the target. Since the spatial detection relies on the unknown position of the target. A coarse position estimation of target is also presented. RWLS is robust to interference links and has low computation complexity. Results from real experiments verify the effectiveness of the proposed method.
Estimation of Toeplitz Covariance Matrices in Large Dimensional Regime with Application to Source Detection
Venue: arXiv cs.IT 2014
Year: 2014

In this article, we derive concentration inequalities for the spectral norm of two classical sample estimators of large dimensional Toeplitz covariance matrices, demonstrating in particular their asymptotic almost sure consistence. The consistency is then extended to the case where the aggregated matrix of time samples is corrupted by a rank one (or more generally, low rank) matrix. As an application of the latter, the problem of source detection in the context of large dimensional sensor networks within a temporally correlated noise environment is studied. As opposed to standard procedures, this application is performed online, i.e. without the need to possess a learning set of pure noise samples.