OpenRaiser/Intern-Atlas huggingface dataset:
Randomized approximate nearest neighbor search with limited adaptivity
Venue: arXiv cs.DS 2016
Year: 2016

We study the fundamental problem of approximate nearest neighbor search in $d$-dimensional Hamming space $\{0,1\}^d$. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe model with limited adaptivity, where the algorithm makes $k$ rounds of parallel accesses to the data structure for a given $k$. For any $k\ge 1$, we give a simple randomized algorithm solving the approximate nearest neighbor search using $k$ rounds of parallel memory accesses, with $O(k(\log d)^{1/k})$ accesses in total. We also give a more sophisticated randomized algorithm using $O(k+(\frac{1}{k}\log d)^{O(1/k)})$ memory accesses in $k$ rounds for large enough $k$. Both algorithms use data structures of size polynomial in $n$, the number of points in the database. For the lower bound, we prove an $Ω(\frac{1}{k}(\log d)^{1/k})$ lower bound for the total number of memory accesses required by any randomized algorithm solving the approximate nearest neighbor search within $k\le\frac{\log\log d}{2\log\log\log d}$ rounds of parallel memory accesses on any data structures of polynomial size. This lower bound shows that our first algorithm is asymptotically optimal for any constant round $k$. And our second algorithm approaches the asymptotically optimal tradeoff between rounds and memory accesses, in a sense that the lower bound of memory accesses for any $k_1$ rounds can be matched by the algorithm within $k_2=O(k_1)$ rounds. In the extreme, for some large enough $k=Θ\left(\frac{\log\log d}{\log\log\log d}\right)$, our second algorithm matches the $Θ\left(\frac{\log\log d}{\log\log\log d}\right)$ tight bound for fully adaptive algorithms for approximate nearest neighbor search due to Chakrabarti and Regev.
Exploiting Lists of Names for Named Entity Identification of Financial Institutions from Unstructured Documents
Venue: arXiv cs.CL 2016
Year: 2016

There is a wealth of information about financial systems that is embedded in document collections. In this paper, we focus on a specialized text extraction task for this domain. The objective is to extract mentions of names of financial institutions, or FI names, from financial prospectus documents, and to identify the corresponding real world entities, e.g., by matching against a corpus of such entities. The tasks are Named Entity Recognition (NER) and Entity Resolution (ER); both are well studied in the literature. Our contribution is to develop a rule-based approach that will exploit lists of FI names for both tasks; our solution is labeled Dict-based NER and Rank-based ER. Since the FI names are typically represented by a root, and a suffix that modifies the root, we use these lists of FI names to create specialized root and suffix dictionaries. To evaluate the effectiveness of our specialized solution for extracting FI names, we compare Dict-based NER with a general purpose rule-based NER solution, ORG NER. Our evaluation highlights the benefits and limitations of specialized versus general purpose approaches, and presents additional suggestions for tuning and customization for FI name extraction. To our knowledge, our proposed solutions, Dict-based NER and Rank-based ER, and the root and suffix dictionaries, are the first attempt to exploit specialized knowledge, i.e., lists of FI names, for rule-based NER and ER.
Large-Scale Reasoning with OWL
Venue: arXiv cs.AI 2016
Year: 2016

With the growth of the Semantic Web in size and importance, more and more knowledge is stored in machine-readable formats such as the Web Ontology Language OWL. This paper outlines common approaches for efficient reasoning on large-scale data consisting of billions ($10^9$) of triples. Therefore, OWL and its sublanguages, as well as forward and backward chaining techniques are presented. The WebPIE reasoner is discussed in detail as an example for forward chaining using MapReduce for materialisation. Moreover, the QueryPIE reasoner is presented as a backward chaining/hybrid approach which uses query rewriting. Furthermore, an overview on other reasoners is given such as OWLIM and TrOWL.
Quasi-4-Connected Components
Venue: arXiv cs.DM 2016
Year: 2016

We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3 that remove a single vertex. Moreover, we give a cubic time algorithm computing the decomposition of a given graph. Our decomposition into quasi-4-connected components refines the well-known decompositions of graphs into biconnected and triconnected components. We relate our decomposition to Robertson and Seymour's theory of tangles by establishing a correspondence between the quasi-4-connected components of a graph and its tangles of order 4.
Towards reducing the multidimensionality of OLAP cubes using the Evolutionary Algorithms and Factor Analysis Methods
Venue: arXiv cs.AI 2016
Year: 2016

Data Warehouses are structures with large amount of data collected from heterogeneous sources to be used in a decision support system. Data Warehouses analysis identifies hidden patterns initially unexpected which analysis requires great memory and computation cost. Data reduction methods were proposed to make this analysis easier. In this paper, we present a hybrid approach based on Genetic Algorithms (GA) as Evolutionary Algorithms and the Multiple Correspondence Analysis (MCA) as Analysis Factor Methods to conduct this reduction. Our approach identifies reduced subset of dimensions from the initial subset p where p'<p where it is proposed to find the profile fact that is the closest to reference. GAs identify the possible subsets and the Khi formula of the ACM evaluates the quality of each subset. The study is based on a distance measurement between the reference and n facts profile extracted from the Warehouses.
Hyperbolae Are No Hyperbole: Modelling Communities That Are Not Cliques
Venue: arXiv cs.SI 2016
Year: 2016

Cliques are frequently used to model communities: a community is a set of nodes where each pair is equally likely to be connected. But studying real-world communities reveals that they have more structure than that. In particular, the nodes can be ordered in such a way that (almost) all edges in the community lie below a hyperbola. In this paper we present three new models for communities that capture this phenomenon. Our models explain the structure of the communities differently, but we also prove that they are identical in their expressive power. Our models fit to real-world data much better than traditional block models or previously-proposed hyperbolic models, both of which are a special case of our model. Our models also allow for intuitive interpretation of the parameters, enabling us to summarize the shapes of the communities in graphs effectively.
DroidNative: Semantic-Based Detection of Android Native Code Malware
Venue: arXiv cs.CR 2016
Year: 2016

According to the Symantec and F-Secure threat reports, mobile malware development in 2013 and 2014 has continued to focus almost exclusively ~99% on the Android platform. Malware writers are applying stealthy mutations (obfuscations) to create malware variants, thwarting detection by signature based detectors. In addition, the plethora of more sophisticated detectors making use of static analysis techniques to detect such variants operate only at the bytecode level, meaning that malware embedded in native code goes undetected. A recent study shows that 86% of the most popular Android applications contain native code, making this a plausible threat. This paper proposes DroidNative, an Android malware detector that uses specific control flow patterns to reduce the effect of obfuscations, provides automation and platform independence, and as far as we know is the first system that operates at the Android native code level, allowing it to detect malware embedded in both native code and bytecode. When tested with traditional malware variants it achieves a detection rate (DR) of 99.48%, compared to academic and commercial tools' DRs that range from 8.33% -- 93.22%. When tested with a dataset of 2240 samples DroidNative achieves a DR of 99.16%, a false positive rate of 0.4% and an average detection time of 26.87 sec/sample.
Iran's scientific dominance and the emergence of South-East Asian countries as scientific collaborators in the Persian Gulf Region
Venue: arXiv cs.DL 2016
Year: 2016

A longitudinal bibliometric analysis of publications indexed in Thomson Reuters' Incites and Elsevier's Scopus, and published from Persian Gulf States and neighbouring Middle East countries, shows clear effects of major political events during the past 35 years. Predictions made in 2006 by the US diplomat Richard N. Haass on political changes in the Middle East have come true in the Gulf States' national scientific research systems, to the extent that Iran has become in 2015 by far the leading country in the Persian Gulf, and South-East Asian countries including China, Malaysia and South Korea have become major scientific collaborators, displacing the USA and other large Western countries. But collaborations patterns among Persian Gulf States show no apparent relationship with differences in Islam denominations.
Training of spiking neural networks based on information theoretic costs
Venue: arXiv cs.NE 2016
Year: 2016

Spiking neural network is a type of artificial neural network in which neurons communicate between each other with spikes. Spikes are identical Boolean events characterized by the time of their arrival. A spiking neuron has internal dynamics and responds to the history of inputs as opposed to the current inputs only. Because of such properties a spiking neural network has rich intrinsic capabilities to process spatiotemporal data. However, because the spikes are discontinuous 'yes or no' events, it is not trivial to apply traditional training procedures such as gradient descend to the spiking neurons. In this thesis we propose to use stochastic spiking neuron models in which probability of a spiking output is a continuous function of parameters. We formulate several learning tasks as minimization of certain information-theoretic cost functions that use spiking output probability distributions. We develop a generalized description of the stochastic spiking neuron and a new spiking neuron model that allows to flexibly process rich spatiotemporal data. We formulate and derive learning rules for the following tasks: - a supervised learning task of detecting a spatiotemporal pattern as a minimization of the negative log-likelihood (the surprisal) of the neuron's output - an unsupervised learning task of increasing the stability of neurons output as a minimization of the entropy - a reinforcement learning task of controlling an agent as a modulated optimization of filtered surprisal of the neuron's output. We test the derived learning rules in several experiments such as spatiotemporal pattern detection, spatiotemporal data storing and recall with autoassociative memory, combination of supervised and unsupervised learning to speed up the learning process, adaptive control of simple virtual agents in changing environments.
On Alternation and the Union Theorem
Venue: arXiv cs.CC 2016
Year: 2016

Under the assumption $P=Σ_2^p$, we prove a new variant of the Union Theorem of McCreight and Meyer for the class $Σ_2^p$. This yields a union function $F$ which is computable in time $F(n)^c$ for some constant $c$ and satisfies $P=DTIME(F)=Σ_2(F)=Σ_2^p$ with respect to a subfamily $(\tilde{S}_i)$ of $Σ_2$-machines. We show that this subfamily does not change the complexity classes $P$ and $Σ_2^p$. Moreover, a padding construction shows that this also implies $DTIME(F^c)=Σ_2(F^c)$. On the other hand, we prove a variant of Gupta's result who showed that $DTIME(t)\subsetneqΣ_2(t)$ for time-constructible functions $t(n)$. Our variant of this result holds with respect to the subfamily $(\tilde{S}_i)$ of $Σ_2$-machines. We show that these two results contradict each other. Hence the assumption $P=Σ_2^p$ cannot hold.
State Space Analysis of Memristor Based Series and Parallel RLCM Circuits
Venue: arXiv cs.ET 2016
Year: 2016

The present paper investigates state space analysis of memristor based series and parallel RLCM circuits. The stability analysis is carried out with the help of eigenvalues formulation method, pole-zero plot and transient response of system. The state space analysis is successfully applied and eigenvalues of the two circuits are calculated. It is found that the, system follows negative real part of eigenvalues. The result clearly shows that addition of memristor in circuits will not alter the stability of system. It is found that systems poles located at left hand side of the S plane, which indicates stable performance of system. It clearly evident that eigenvalues has negative real part hence two systems are internally stable.
Cutset Width and Spacing for Reduced Cutset Coding of Markov Random Fields
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we explore tradeoffs, regarding coding performance, between the thickness and spacing of the cutset used in Reduced Cutset Coding (RCC) of a Markov random field image model. Considering MRF models on a square lattice of sites, we show that under a stationarity condition, increasing the thickness of the cutset reduces coding rate for the cutset, increasing the spacing between components of the cutset increases the coding rate of the non-cutset pixels, though the coding rate of the latter is always strictly less than that of the former. We show that the redundancy of RCC can be decomposed into two terms, a correlation redundancy due to coding the components of the cutset independently, and a distribution redundancy due to coding the cutset as a reduced MRF. We provide analysis of these two sources of redundancy. We present results from numerical simulations with a homogeneous Ising model that bear out the analytical results. We also present a consistent estimation algorithm for the moment-matching reduced MRF on the cutset.
Faster Bottleneck Non-crossing Matchings of Points in Convex Position
Venue: arXiv cs.CG 2016
Year: 2016

Given an even number of points in a plane, we are interested in matching all the points by straight line segments so that the segments do not cross. Bottleneck matching is a matching that minimizes the length of the longest segment. For points in convex position, we present a quadratic-time algorithm for finding a bottleneck non-crossing matching, improving upon the best previously known algorithm of cubic time complexity.
Parallel Linear Search with no Coordination for a Randomly Placed Treasure
Venue: arXiv cs.DC 2016
Year: 2016

In STOC'16, Fraigniaud et al. consider the problem of finding a treasure hidden in one of many boxes that are ordered by importance. That is, if a treasure is in a more important box, then one would like to find it faster. Assuming there are many searchers, the authors suggest that using an algorithm that requires no coordination between searchers can be highly beneficial. Indeed, besides saving the need for a communication and coordination mechanism, such algorithms enjoy inherent robustness. The authors proceed to solve this linear search problem in the case of countably many boxes and an adversary placed treasure, and prove that the best speed-up possible by $k$ non-coordinating searchers is precisely $\frac{k}{4}(1+1/k)^2$. In particular, this means that asymptotically, the speed-up is four times worse compared to the case of full coordination. We suggest an important variant of the problem, where the treasure is placed uniformly at random in one of a finite, large, number of boxes. We devise non-coordinating algorithms that achieve a speed-up of $6/5$ for two searchers, a speed-up of $3/2$ for three searchers, and in general, a speed-up of $k(k+1)/(3k-1)$ for any $k \geq 1$ searchers. Thus, as $k$ grows to infinity, the speed-up approaches three times worse compared to the case of full coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm for $k$ searchers can achieve better speed-ups. We also devise non-coordinating algorithms that use only logarithmic memory in the size of the search domain, and yet, asymptotically, achieve the optimal speed-up. Finally, we note that all our algorithms are extremely simple and hence applicable.
Performance Analysis of RFDMRP:River Formation Dynamics based Multi-Hop Routing Protocol in WSNs
Venue: arXiv cs.NI 2016
Year: 2016

In Wireless sensor networks, sensor nodes sense the data from environment according to its functionality and forwards to its base station. This process is called Data collection. The Data collection process is done either directly or by multi-hop routing. In direct routing, every sensor node directly transfers its sensed data to base station which has an impact on energy consumption from sensor node due to the far distance between the sensor node and base station. In multi-hop routing, the sensed data is relayed through multiple nodes to the base station, it consumes less energy. This paper presents and analyzes the performance of a data collection routing protocol called RFDMRP: River Formation Dynamics based multi-hop routing protocol. The performance of RFDMRP is tested and analyzed for network parameters such as Network lifetime, Energy usage, and Node density & data aggregation impact on network lifetime. The simulated results are compared with two algorithms LEACH and MOD_LEACH. The comparison reveals that the proposed algorithm performs better than LEACH and MOD_LEACH with respect to Network lifetime.
On the Density of non-Simple 3-Planar Graphs
Venue: arXiv cs.CG 2016
Year: 2016

A \emph{$k$-planar graph} is a graph that can be drawn in the plane such that every edge is crossed at most $k$ times. For $k \leq 4$, Pach and Tóth proved a bound of $(k+3)(n-2)$ on the total number of edges of a $k$-planar graph, which is tight for $k=1,2$. For $k=3$, the bound of $6n-12$ has been improved to $\frac{11}{2}n-11$ and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of $\frac{11}{2}n-11$ edges also holds for non-simple $3$-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of \emph{optimal $3$-planar graphs} (that is, $3$-planar graphs with $n$ vertices and exactly $\frac{11}{2}n-11$ edges) might be possible, as to the best of our knowledge the densest known simple $3$-planar is not known to be optimal.
Higher-Order Recursion Abstraction: How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking
Venue: arXiv cs.LO 2016
Year: 2016

The Ackermann function is a famous total recursive binary function on the natural numbers. It is the archetypal example of such a function that is not primitive recursive, in the sense of classical recursion theory. However, and in seeming contradiction, there are generalized notions of total recursion, for which the Ackermann function is in fact primitive recursive, and often featured as a witness for the additional power gained by the generalization. Here, we investigate techniques for finding and analyzing the primitive form of complicated recursive functions, namely also Knuth's and Conway's arrow notations, in particular by recursion abstraction, in a framework of functional program transformation.
Optimizing Transmission Lengths for Limited Feedback with Non-Binary LDPC Examples
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a general approach for optimizing the number of symbols in increments (packets of incremental redundancy) in a feedback communication system with a limited number of increments. This approach is based on a tight normal approximation on the rate for successful decoding. Applying this approach to a variety of feedback systems using non-binary (NB) low-density parity-check (LDPC) codes shows that greater than 90% of capacity can be achieved with average blocklengths fewer than 500 transmitted bits. One result is that the performance with ten increments closely approaches the performance with an infinite number of increments. The paper focuses on binary- input additive-white Gaussian noise (BI-AWGN) channels but also demonstrates that the normal approximation works well on examples of fading channels as well as high-SNR AWGN channels that require larger QAM constellations. The paper explores both variable-length feedback codes with termination (VLFT) and the more practical variable length feedback (VLF) codes without termination that require no assumption of noiseless transmitter confirmation. For VLF we consider both a two-phase scheme and CRC-based scheme.
A Matching Game for Data Trading in Operator-Supervised User-Provided Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we consider a recent cellular network connection paradigm, known as user-provided network (UPN), where users share their connectivity and act as an access point for other users. To incentivize user participation in this network, we allow the users to trade their data plan and obtain some profits by selling and buying leftover data capacities (caps) from each other. We formulate the buyers and sellers association for data trading as a matching game. In this game, buyers and sellers rank one another based on preference functions that capture buyers' data demand and QoS requirements, sellers' available data and energy resources. We show that these preferences are interdependent and influenced by the existing network-wide matching. For this reason, the game can be classified as a one-to-many matching game with externalities. To solve this game, a distributed algorithm that combines notions from matching theory and market equilibrium is proposed. The algorithm enables the players to self-organize into a stable matching and dynamic adaptation of price to data demand and supply. The properties of the resulting matching are discussed. Moreover, the price benchmark for the users to join the UPN and the operator gain are also determined. Simulation results show that the proposed algorithm yields an improvement of the average utility per user up to 25% and 50% relative to random matching and worst case utility, respectively.
Protection of heterogeneous architectures on FPGAs: An approach based on hardware firewalls
Venue: arXiv cs.CR 2016
Year: 2016

Embedded systems are parts of our daily life and used in many fields. They can be found in smartphones or in modern cars including GPS, light/rain sensors and other electronic assistance mechanisms. These systems may handle sensitive data (such as credit card numbers, critical information about the host system and so on) which must be protected against external attacks as these data may be transmitted through a communication link where attackers can connect to extract sensitive information or inject malicious code within the system. This work presents an approach to protect communications in multiprocessor architectures. This approach is based on hardware security enhancements acting as firewalls. These firewalls filter all data going through the system communication bus and an additional flexible cryptographic block aims to protect external memory from attacks. Benefits of our approach are demonstrated using a case study and some custom software applications implemented in a Field-Programmable Gate Array (FPGA). Firewalls implemented in the target architecture allow getting a low-latency security layer with flexible cryptographic features. To illustrate the benefit of such a solution, implementations are discussed for different MPSoCs implemented on Xilinx Virtex-6 FPGAs. Results demonstrate a reduction up to 33% in terms of latency overhead compared to existing efforts.