OpenRaiser/Intern-Atlas huggingface dataset:
Sub-Nyquist Sampling and Fourier Domain Beamforming in Volumetric Ultrasound Imaging
Venue: arXiv cs.IT 2015
Year: 2015

One of the key steps in ultrasound image formation is digital beamforming of signals sampled by several transducer elements placed upon an array. High-resolution digital beamforming introduces the demand for sampling rates significantly higher than the signals' Nyquist rate, which greatly increases the volume of data that must be transmitted from the system's front end. In 3D ultrasound imaging, 2D transducer arrays rather than 1D arrays are used, and more scan-lines are needed. This implies that the amount of sampled data is vastly increased with respect to 2D imaging. In this work we show that a considerable reduction in data rate can be achieved by applying the ideas of Xampling and frequency domain beamforming, leading to a sub-Nyquist sampling rate, which uses only a portion of the bandwidth of the ultrasound signals to reconstruct the image. We extend previous work on frequency domain beamforming for 2D ultrasound imaging to accommodate the geometry imposed by volumetric scanning and a 2D grid of transducer elements. We demonstrate high image quality from low-rate samples by simulation of a phantom image comprised of several small reflectors. We also apply our technique on raw data of a heart ventricle phantom obtained by a commercial 3D ultrasound system. We show that by performing 3D beamforming in the frequency domain, sub-Nyquist sampling and low processing rate are achievable, while maintaining adequate image quality.
Cohesiveness Relationships to Empower Keyword Search on Tree Data on the Web
Venue: arXiv cs.DB 2015
Year: 2015

Keyword search is the most popular querying technique on semistructured data. Keyword queries are simple and con- venient. However, as a consequence of their imprecision, the quality of their answers is poor and the existing algorithms do not scale satisfactorily. In this paper, we introduce the novel concept of cohesive keyword queries for tree data. Intuitively, a cohesiveness relationship on keywords indicates that they should form a cohesive whole in a query result. Cohesive keyword queries allow term nesting and keyword repetition. Although more expressive, they are as simple as flat keyword queries. We provide formal semantics for cohesive keyword queries rank- ing query results on the proximity of the keyword instances. We design a stack based algorithm which efficiently evaluates cohesive keyword queries. Our experiments demonstrate that our approach outperforms in quality previous filtering semantics and our algorithm scales smoothly on queries of even 20 keywords on large datasets.
nanopub-java: A Java Library for Nanopublications
Venue: arXiv cs.DL 2015
Year: 2015

The concept of nanopublications was first proposed about six years ago, but it lacked openly available implementations. The library presented here is the first one that has become an official implementation of the nanopublication community. Its core features are stable, but it also contains unofficial and experimental extensions: for publishing to a decentralized server network, for defining sets of nanopublications with indexes, for informal assertions, and for digitally signing nanopublications. Most of the features of the library can also be accessed via an online validator interface.
HoneyMesh: Preventing Distributed Denial of Service Attacks using Virtualized Honeypots
Venue: arXiv cs.CR 2015
Year: 2015

Today, internet and web services have become an inseparable part of our lives. Hence, ensuring continuous availability of service has become imperative to the success of any organization. But these services are often hampered by constant threats from myriad types of attacks. One such attack is called distributed denial of service attack that results in issues ranging from temporary slowdown of servers to complete non-availability of service. Honeypot, which is a sort of a trap, can be used to interact with potential attackers to deflect, detect or prevent such attacks and ensure continuous availability of service. This paper gives insights into the problems posed by distributed denial of service attacks, existing solutions that use honeypots and how a mesh of virtualized honeypots can be used to prevent distributed denial of service attacks.
Message Passing and Combinatorial Optimization
Venue: arXiv cs.AI 2015
Year: 2015

Graphical models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying only local factors. This thesis studies inference in discrete graphical models from an algebraic perspective and the ways inference can be used to express and approximate NP-hard combinatorial problems. We investigate the complexity and reducibility of various inference problems, in part by organizing them in an inference hierarchy. We then investigate tractable approximations for a subset of these problems using distributive law in the form of message passing. The quality of the resulting message passing procedure, called Belief Propagation (BP), depends on the influence of loops in the graphical model. We contribute to three classes of approximations that improve BP for loopy graphs A) loop correction techniques; B) survey propagation, another message passing technique that surpasses BP in some settings; and C) hybrid methods that interpolate between deterministic message passing and Markov Chain Monte Carlo inference. We then review the existing message passing solutions and provide novel graphical models and inference techniques for combinatorial problems under three broad classes: A) constraint satisfaction problems such as satisfiability, coloring, packing, set / clique-cover and dominating / independent set and their optimization counterparts; B) clustering problems such as hierarchical clustering, K-median, K-clustering, K-center and modularity optimization; C) problems over permutations including assignment, graph morphisms and alignment, finding symmetries and traveling salesman problem. In many cases we show that message passing is able to find solutions that are either near optimal or favourably compare with today's state-of-the-art approaches.
Steps Toward Deep Kernel Methods from Infinite Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

Contemporary deep neural networks exhibit impressive results on practical problems. These networks generalize well although their inherent capacity may extend significantly beyond the number of training examples. We analyze this behavior in the context of deep, infinite neural networks. We show that deep infinite layers are naturally aligned with Gaussian processes and kernel methods, and devise stochastic kernels that encode the information of these networks. We show that stability results apply despite the size, offering an explanation for their empirical success.
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Venue: arXiv cs.CC 2015
Year: 2015

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection. To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangement problem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.
Genetic Algorithms for multimodal optimization: a review
Venue: arXiv cs.NE 2015
Year: 2015

In this article we provide a comprehensive review of the different evolutionary algorithm techniques used to address multimodal optimization problems, classifying them according to the nature of their approach. On the one hand there are algorithms that address the issue of the early convergence to a local optimum by differentiating the individuals of the population into groups and limiting their interaction, hence having each group evolve with a high degree of independence. On the other hand other approaches are based on directly addressing the lack of genetic diversity of the population by introducing elements into the evolutionary dynamics that promote new niches of the genotypical space to be explored. Finally, we study multi-objective optimization genetic algorithms, that handle the situations where multiple criteria have to be satisfied with no penalty for any of them. Very rich literature has arised over the years on these topics, and we aim at offering an overview of the most important techniques of each branch of the field.
Pricing Queries Approximately Optimally
Venue: arXiv cs.GT 2015
Year: 2015

Data as a commodity has always been purchased and sold. Recently, web services that are data marketplaces have emerged that match data buyers with data sellers. So far there are no guidelines how to price queries against a database. We consider the recently proposed query-based pricing framework of Koutris et al and ask the question of computing optimal input prices in this framework by formulating a buyer utility model. We establish the interesting and deep equivalence between arbitrage-freeness in the query-pricing framework and envy-freeness in pricing theory for appropriately chosen buyer valuations. Given the approximation hardness results from envy-free pricing we then develop logarithmic approximation pricing algorithms exploiting the max flow interpretation of the arbitrage-free pricing for the restricted query language proposed by Koutris et al. We propose a novel polynomial-time logarithmic approximation pricing scheme and show that our new scheme performs better than the existing envy-free pricing algorithms instance-by-instance. We also present a faster pricing algorithm that is always greater than the existing solutions, but worse than our previous scheme. We experimentally show how our pricing algorithms perform with respect to the existing envy-free pricing algorithms and to the optimal exponentially computable solution, and our experiments show that our approximation algorithms consistently arrive at about 99% of the optimal.
Synthesis of Linear Nearest Neighbor Quantum Circuits
Venue: arXiv cs.ET 2015
Year: 2015

This paper presents models for transforming standard reversible circuits into Linear Nearest Neighbor (LNN) architecture without inserting SWAP gates. Templates to optimize the transformed LNN circuits are proposed. All minimal LNN circuits for all 3-qubit functions have been generated to serve as benchmarks to evaluate heuristic optimization algorithms. The minimal results generated are compared with optimized LNN circuits obtained from the post synthesis algorithm --- template matching with LNN templates. Experiments show that the suggested synthesis flow significantly improves the quantum cost of circuits.
CudaChain: A Practical GPU-accelerated 2D Convex Hull Algorithm
Venue: arXiv cs.CG 2015
Year: 2015

This paper presents a practical GPU-accelerated convex hull algorithm and a novel Sorting-based Preprocessing Approach (SPA) for planar point sets. The proposed algorithm consists of two stages: (1) two rounds of preprocessing performed on the GPU and (2) the finalization of calculating the expected convex hull on the CPU. We first discard the interior points that locate inside a quadrilateral formed by four extreme points, and then distribute the remaining points into several (typically four) sub regions. For each subset of points, we first sort them in parallel, then perform the second round of discarding using SPA, and finally form a simple chain for the current remaining points. A simple polygon can be easily generated by directly connecting all the chains in sub regions. We at last obtain the expected convex hull of the input points by calculating the convex hull of the simple polygon. We use the library Thrust to realize the parallel sorting, reduction, and partitioning for better efficiency and simplicity. Experimental results show that our algorithm achieves 5x ~ 6x speedups over the Qhull implementation for 20M points. Thus, this algorithm is competitive in practical applications for its simplicity and satisfied efficiency.
Skolem Functions for Factored Formulas
Venue: arXiv cs.LO 2015
Year: 2015

Given a propositional formula F(x,y), a Skolem function for x is a function Ψ(y), such that substituting Ψ(y) for x in F gives a formula semantically equivalent to \exists F. Automatically generating Skolem functions is of significant interest in several applications including certified QBF solving, finding strategies of players in games, synthesising circuits and bit-vector programs from specifications, disjunctive decomposition of sequential circuits etc. In many such applications, F is given as a conjunction of factors, each of which depends on a small subset of variables. Existing algorithms for Skolem function generation ignore any such factored form and treat F as a monolithic function. This presents scalability hurdles in medium to large problem instances. In this paper, we argue that exploiting the factored form of F can give significant performance improvements in practice when computing Skolem functions. We present a new CEGAR style algorithm for generating Skolem functions from factored propositional formulas. In contrast to earlier work, our algorithm neither requires a proof of QBF satisfiability nor uses composition of monolithic conjunctions of factors. We show experimentally that our algorithm generates smaller Skolem functions and outperforms state-of-the-art approaches on several large benchmarks.
New infinite families of p-ary weakly regular bent functions
Venue: arXiv cs.IT 2015
Year: 2015

The characterization and construction of bent functions are challenging problems. The paper generalizes the constructions of Boolean bent functions by Mesnager \cite{M2014}, Xu et al. \cite{XCX2015} and $p$-ary bent functions by Xu et al. \cite{XC2015} to the construction of $p$-ary weakly regular bent functions and presents new infinite families of $p$-ary weakly regular bent functions from some known weakly regular bent functions (square functions, Kasami functions, and the Maiorana-McFarland class of bent functions). Further, new infinite families of $p$-ary bent idempotents are obtained.
Impact of CFO Estimation on the Performance of ZF Receiver in Massive MU-MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the impact of carrier frequency offset (CFO) estimation/compensation on the information rate performance of the zero-forcing (ZF) receiver in the uplink of a multi-user massive multiple-input multiple-output (MIMO) system. Analysis of the derived closed-form expression of the per-user information rate reveals that with increasing number of BS antennas $M$, an $\mathcal{O}(\sqrt{M})$ array gain is achievable, which is same as that achieved in the ideal zero CFO scenario. Also it is observed that compared to the ideal zero CFO case, the performance degradation in the presence of residual CFO (after CFO compensation) is the same for both ZF and MRC.
When Six Gates are Not Enough
Venue: arXiv cs.CC 2015
Year: 2015

We apply the pigeonhole principle to show that there must exist Boolean functions on 7 inputs with a multiplicative complexity of at least 7, i.e., that cannot be computed with only 6 multiplications in the Galois field with two elements.
An evolutionary approach to the identification of Cellular Automata based on partial observations
Venue: arXiv cs.NE 2015
Year: 2015

In this paper we consider the identification problem of Cellular Automata (CAs). The problem is defined and solved in the context of partial observations with time gaps of unknown length, i.e. pre-recorded, partial configurations of the system at certain, unknown time steps. A solution method based on a modified variant of a Genetic Algorithm (GA) is proposed and illustrated with brief experimental results.
A Universal Point Set for 2-Outerplanar Graphs
Venue: arXiv cs.CG 2015
Year: 2015

A point set $S \subseteq \mathbb{R}^2$ is universal for a class $\cal G$ if every graph of ${\cal G}$ has a planar straight-line embedding on $S$. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size $O(n \log n)$.
Andriod Based Punjabi TTS System
Venue: arXiv cs.CY 2015
Year: 2015

The usage of mobile phones is nearly 3.5 times more than that of personal computers. Android has the largest share among its counter parts like IOS, Windows and Symbian Android applications have a very few restrictions on them. TTS systems on Android are available for many languages but a very few systems of this type are available for Punjabi language. Our research work had the aim to develop an application that will be able to produce synthetic Punjabi speech. The paper examines the methodology used to develop speech synthesis TTS system for the Punjabi content, which is written in Gurmukhi script. For the development of this system, we use concatenative speech synthesis method with phonemes as the basic units of concatenation. Some challenges like application size, processing time, must be considered, while porting this TTS system to resource-limited devices like mobile phones.
Tactical Network Modeller Simulation Tool Combined discrete event and network back-ends
Venue: arXiv cs.NI 2015
Year: 2015

This paper discusses the implementation of a tactical network simulation tool. The tool is called Tactical Network Modeller (TNM). TNM uses some novel techniques to simplify the building of the network model using graph theory constrained by a hierarchical tree which reflects the organisation structure. TNM allows models to be constructed using an Application Programming Interface (API) or a node based User Interface (UI). When the model is constructed, different simulation back-ends can be applied to it. A discrete event simulation and a network emulation back-end are implemented building on top of open source tools. TNM is simple to create models for non technical users. The model can be used to analyse information flows. The same model can be used for a full network emulation. This allows real software and protocols to be tested in a realistic simulated environment. The flexibility of the software allows its use from engineering up to campaign planning.
An algorithm for Left Atrial Thrombi detection using Transesophageal Echocardiography
Venue: arXiv cs.CV 2015
Year: 2015

Transesophageal echocardiography (TEE) is widely used to detect left atrium (LA)/left atrial appendage (LAA) thrombi. In this paper, the local binary pattern variance (LBPV) features are extracted from region of interest (ROI). And the dynamic features are formed by using the information of its neighbor frames in the sequence. The sequence is viewed as a bag, and the images in the sequence are considered as the instances. Multiple-instance learning (MIL) method is employed to solve the LAA thrombi detection. The experimental results show that the proposed method can achieve better performance than that by using other methods.
ERBlox: Combining Matching Dependencies with Machine Learning for Entity Resolution
Venue: arXiv cs.DB 2015
Year: 2015

Entity resolution (ER), an important and common data cleaning problem, is about detecting data duplicate representations for the same external entities, and merging them into single representations. Relatively recently, declarative rules called matching dependencies (MDs) have been proposed for specifying similarity conditions under which attribute values in database records are merged. In this work we show the process and the benefits of integrating three components of ER: (a) Classifiers for duplicate/non-duplicate record pairs built using machine learning (ML) techniques, (b) MDs for supporting both the blocking phase of ML and the merge itself; and (c) The use of the declarative language LogiQL -an extended form of Datalog supported by the LogicBlox platform- for data processing, and the specification and enforcement of MDs.
A similarity-based community detection method with multiple prototype representation
Venue: arXiv cs.SI 2015
Year: 2015

Communities are of great importance for understanding graph structures in social networks. Some existing community detection algorithms use a single prototype to represent each group. In real applications, this may not adequately model the different types of communities and hence limits the clustering performance on social networks. To address this problem, a Similarity-based Multi-Prototype (SMP) community detection approach is proposed in this paper. In SMP, vertices in each community carry various weights to describe their degree of representativeness. This mechanism enables each community to be represented by more than one node. The centrality of nodes is used to calculate prototype weights, while similarity is utilized to guide us to partitioning the graph. Experimental results on computer generated and real-world networks clearly show that SMP performs well for detecting communities. Moreover, the method could provide richer information for the inner structure of the detected communities with the help of prototype weights compared with the existing community detection models.
GATE: Greening At The Edge
Venue: arXiv cs.NI 2015
Year: 2015

Dramatic data traffic growth, especially wireless data, is driving a significant surge in energy consumption in the last mile access of the telecommunications infrastructure. The growing energy consumption not only escalates the operators' operational expenditures (OPEX) but also leads to a significant rise of carbon footprints. Therefore, enhancing the energy efficiency of broadband access networks is becoming a necessity to bolster social, environmental, and economic sustainability. This article provides an overview on the design and optimization of energy efficient broadband access networks, analyzes the energy efficient design of passive optical networks, discusses the enabling technologies for next generation broadband wireless access networks, and elicits the emerging technologies for enhancing the energy efficiency of the last mile access of the network infrastructure.