OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Decomposition and Recombination of Isostatic Geometric Constraint Systems for Designing Layered Materials
Venue: arXiv cs.CG 2015
Year: 2015

Optimal recursive decomposition (or DR-planning) is crucial for analyzing, designing, solving or finding realizations of geometric constraint sytems. While the optimal DR-planning problem is NP-hard even for general 2D bar-joint constraint systems, we describe an O(n^3) algorithm for a broad class of constraint systems that are isostatic or underconstrained. The algorithm achieves optimality by using the new notion of a canonical DR-plan that also meets various desirable, previously studied criteria. In addition, we leverage recent results on Cayley configuration spaces to show that the indecomposable systems---that are solved at the nodes of the optimal DR-plan by recombining solutions to child systems---can be minimally modified to become decomposable and have a small DR-plan, leading to efficient realization algorithms. We show formal connections to well-known problems such as completion of underconstrained systems. Well suited to these methods are classes of constraint systems that can be used to efficiently model, design and analyze quasi-uniform (aperiodic) and self-similar, layered material structures. We formally illustrate by modeling silica bilayers as body-hyperpin systems and cross-linking microfibrils as pinned line-incidence systems. A software implementation of our algorithms and videos demonstrating the software are publicly available online (visit http://cise.ufl.edu/~tbaker/drp/index.html.)
APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items
Venue: arXiv cs.CC 2015
Year: 2015

We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.
A Review On The Strategic Use Of IT Applications In Achieving And Sustaining Competitive Advantage
Venue: arXiv cs.CY 2015
Year: 2015

Information Technology applications are growing significantly fast for the past decade. Many Business organizations with emphasize on IT applications are trying to gain competitive advantages. Empirical studies also demonstrate that IT increases competitive advantage when it acts with human resources. In this paper we analyzed and review how various IT applications can be utilized to to provide a company with strategic advantages over the global marketplace competitive forces.
Autoencoding the Retrieval Relevance of Medical Images
Venue: arXiv cs.CV 2015
Year: 2015

Content-based image retrieval (CBIR) of medical images is a crucial task that can contribute to a more reliable diagnosis if applied to big data. Recent advances in feature extraction and classification have enormously improved CBIR results for digital images. However, considering the increasing accessibility of big data in medical imaging, we are still in need of reducing both memory requirements and computational expenses of image retrieval systems. This work proposes to exclude the features of image blocks that exhibit a low encoding error when learned by a $n/p/n$ autoencoder ($p\!<\!n$). We examine the histogram of autoendcoding errors of image blocks for each image class to facilitate the decision which image regions, or roughly what percentage of an image perhaps, shall be declared relevant for the retrieval task. This leads to reduction of feature dimensionality and speeds up the retrieval process. To validate the proposed scheme, we employ local binary patterns (LBP) and support vector machines (SVM) which are both well-established approaches in CBIR research community. As well, we use IRMA dataset with 14,410 x-ray images as test data. The results show that the dimensionality of annotated feature vectors can be reduced by up to 50% resulting in speedups greater than 27% at expense of less than 1% decrease in the accuracy of retrieval when validating the precision and recall of the top 20 hits.
Learning Deep Neural Network Policies with Continuous Memory States
Venue: arXiv cs.LG 2015
Year: 2015

Policy learning for partially observed control tasks requires policies that can remember salient information from past observations. In this paper, we present a method for learning policies with internal memory for high-dimensional, continuous systems, such as robotic manipulators. Our approach consists of augmenting the state and action space of the system with continuous-valued memory states that the policy can read from and write to. Learning general-purpose policies with this type of memory representation directly is difficult, because the policy must automatically figure out the most salient information to memorize at each time step. We show that, by decomposing this policy search problem into a trajectory optimization phase and a supervised learning phase through a method called guided policy search, we can acquire policies with effective memorization and recall strategies. Intuitively, the trajectory optimization phase chooses the values of the memory states that will make it easier for the policy to produce the right action in future states, while the supervised learning phase encourages the policy to use memorization actions to produce those memory states. We evaluate our method on tasks involving continuous control in manipulation and navigation settings, and show that our method can learn complex policies that successfully complete a range of tasks that require memory.
Responses to remixing on a social media sharing website
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we describe the ways participants of the Scratch online community, primarily young people, engage in remixing of each others' shared animations, games, and interactive projects. In particular, we try to answer the following questions: How do users respond to remixing in a social media environment where remixing is explicitly permitted? What qualities of originators and their projects correspond to a higher likelihood of plagiarism accusations? Is there a connection between plagiarism complaints and similarities between a remix and the work it is based on? Our findings indicate that users have a very wide range of reactions to remixing and that as many users react positively as accuse remixers of plagiarism. We test several hypotheses that might explain the high number of plagiarism accusations related to original project complexity, cumulative remixing, originators' integration into remixing practice, and remixee-remixer project similarity, and find support for the first and last explanations.
Nonparametric Bayesian Modeling for Automated Database Schema Matching
Venue: arXiv cs.IR 2015
Year: 2015

The problem of merging databases arises in many government and commercial applications. Schema matching, a common first step, identifies equivalent fields between databases. We introduce a schema matching framework that builds nonparametric Bayesian models for each field and compares them by computing the probability that a single model could have generated both fields. Our experiments show that our method is more accurate and faster than the existing instance-based matching algorithms in part because of the use of nonparametric Bayesian models.
Pixel and Voxel Representations of Graphs
Venue: arXiv cs.DM 2015
Year: 2015

We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for $k$-outerplanar graphs with $n$ vertices, $Θ(kn)$ pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, $Θ(n^2)$ voxels are always sufficient and sometimes necessary for any $n$-vertex graph. We improve this bound to $Θ(n\cdot τ)$ for graphs of treewidth $τ$ and to $O((g+1)^2n\log^2n)$ for graphs of genus $g$. In particular, planar graphs admit representations with $O(n\log^2n)$ voxels.
A model building framework for Answer Set Programming with external computations
Venue: arXiv cs.AI 2015
Year: 2015

As software systems are getting increasingly connected, there is a need for equipping nonmonotonic logic programs with access to external sources that are possibly remote and may contain information in heterogeneous formats. To cater for this need, HEX programs were designed as a generalization of answer set programs with an API style interface that allows to access arbitrary external sources, providing great flexibility. Efficient evaluation of such programs however is challenging, and it requires to interleave external computation and model building; to decide when to switch between these tasks is difficult, and existing approaches have limited scalability in many real-world application scenarios. We present a new approach for the evaluation of logic programs with external source access, which is based on a configurable framework for dividing the non-ground program into possibly overlapping smaller parts called evaluation units. The latter will be processed by interleaving external evaluation and model building using an evaluation graph and a model graph, respectively, and by combining intermediate results. Experiments with our prototype implementation show a significant improvement compared to previous approaches. While designed for HEX-programs, the new evaluation approach may be deployed to related rule-based formalisms as well.
Revisiting Large Scale Distributed Machine Learning
Venue: arXiv cs.DC 2015
Year: 2015

Nowadays, with the widespread of smartphones and other portable gadgets equipped with a variety of sensors, data is ubiquitous available and the focus of machine learning has shifted from being able to infer from small training samples to dealing with large scale high-dimensional data. In domains such as personal healthcare applications, which motivates this survey, distributed machine learning is a promising line of research, both for scaling up learning algorithms, but mostly for dealing with data which is inherently produced at different locations. This report offers a thorough overview of and state-of-the-art algorithms for distributed machine learning, for both supervised and unsupervised learning, ranging from simple linear logistic regression to graphical models and clustering. We propose future directions for most categories, specific to the potential personal healthcare applications. With this in mind, the report focuses on how security and low communication overhead can be assured in the specific case of a strictly client-server architectural model. As particular directions we provides an exhaustive presentation of an empirical clustering algorithm, k-windows, and proposed an asynchronous distributed machine learning algorithm that would scale well and also would be computationally cheap and easy to implement.
Correspondence Factor Analysis of Big Data Sets: A Case Study of 30 Million Words; and Contrasting Analytics using Apache Solr and Correspondence Analysis in R
Venue: arXiv cs.CL 2015
Year: 2015

We consider a large number of text data sets. These are cooking recipes. Term distribution and other distributional properties of the data are investigated. Our aim is to look at various analytical approaches which allow for mining of information on both high and low detail scales. Metric space embedding is fundamental to our interest in the semantic properties of this data. We consider the projection of all data into analyses of aggregated versions of the data. We contrast that with projection of aggregated versions of the data into analyses of all the data. Analogously for the term set, we look at analysis of selected terms. We also look at inherent term associations such as between singular and plural. In addition to our use of Correspondence Analysis in R, for latent semantic space mapping, we also use Apache Solr. Setting up the Solr server and carrying out querying is described. A further novelty is that querying is supported in Solr based on the principal factor plane mapping of all the data. This uses a bounding box query, based on factor projections.
A generalised isodiametric problem
Venue: arXiv cs.CG 2015
Year: 2015

Fix positive integers $a$ and $b$ such that $a> b\geq 2$ and a positive real $δ>0$. Let $S$ be a planar set of diameter $δ$ having the following property: for every $a$ points in $S$, at least $b$ of them have pairwise distances that are all less than or equal to $2$. What is the maximum Lebesgue measure of $S$? In this paper we investigate this problem. We discuss the, devious, motivation that leads to its formulation and provide upper bounds on the Lebesgue measure of $S$. Our main result is based on a generalisation of a theorem that is due to Heinrich Jung. In certain instances we are able to find the extremal set but the general case seems elusive.
Millimeter Wave MIMO with Lens Antenna Array: A New Path Division Multiplexing Paradigm
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmWave) communication is a promising technology for 5G cellular systems. To compensate for the severe path loss in mmWave systems, large antenna arrays are generally used to achieve significant beamforming gains. However, due to the high hardware and power consumption cost associated with radio frequency (RF) chains, it is desirable to achieve the large-antenna gains, but with only limited number of RF chains for mmWave communications. To this end, we study in this paper a new lens antenna array enabled mmWave MIMO communication system. We first show that the array response of the proposed lens antenna array at the receiver/transmitter follows a "sinc" function, where the antenna with the peak response is determined by the angle of arrival (AoA)/departure (AoD) of the received/transmitted signal. By exploiting this unique property of lens antenna arrays along with the multi-path sparsity of mmWave channels, we propose a novel low-cost and capacity-achieving MIMO transmission scheme, termed \emph{orthogonal path division multiplexing (OPDM)}. For channels with insufficiently separated AoAs and/or AoDs, we also propose a simple \emph{path grouping} technique with group-based small-scale MIMO processing to mitigate the inter-path interference. Numerical results are provided to compare the performance of the proposed lens antenna arrays for mmWave MIMO system against that of conventional arrays, under different practical setups. It is shown that the proposed system achieves significant throughput gain as well as complexity and hardware cost reduction, both making it an appealing new paradigm for mmWave MIMO communications.
A New Execution Model for the logic of hereditary Harrop formulas
Venue: arXiv cs.LO 2015
Year: 2015

The class of first-order Hereditary Harrop formulas ($fohh$) is a well-established extension of first-order Horn clauses. Its operational semantics is based on intuitionistic provability. We propose another operational semantics for $fohh$ which is based on game semantics. This new semantics has several interesting aspects: in particular, it gives a logical status to the $read$ predicate in Prolog.
Demandance
Venue: arXiv cs.HC 2015
Year: 2015

A demandance is a psychological "pull" exerted by a stimulus. It is closely related to the theory of "affordance". I introduce the theory of demandance, offer some motivating examples, briefly explore its psychological basis, and examine some implications of the theory. I exemplify some of the positive and negative implications of demandances for design, with special attention to young children and the design of educational products and practices. I suggest that demandance offers an approach to one of the persistent mysteries of the theory of affordance, specifically: Given that there may be many affordances in any particular setting, how do we choose which to actually act upon?
MADNESS: A Multiresolution, Adaptive Numerical Environment for Scientific Simulation
Venue: arXiv cs.MS 2015
Year: 2015

MADNESS (multiresolution adaptive numerical environment for scientific simulation) is a high-level software environment for solving integral and differential equations in many dimensions that uses adaptive and fast harmonic analysis methods with guaranteed precision based on multiresolution analysis and separated representations. Underpinning the numerical capabilities is a powerful petascale parallel programming environment that aims to increase both programmer productivity and code scalability. This paper describes the features and capabilities of MADNESS and briefly discusses some current applications in chemistry and several areas of physics.
On the pathwidth of almost semicomplete digraphs
Venue: arXiv cs.DS 2015
Year: 2015

We call a digraph {\em $h$-semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $u \neq v$ such that there is no edge between $u$ and $v$ in either direction. This notion generalizes that of semicomplete digraphs which are $0$-semicomplete and tournaments which are semicomplete and have no anti-parallel pairs of edges. Our results in this paper are as follows. (1) We give an algorithm which, given an $h$-semicomplete digraph $G$ on $n$ vertices and a positive integer $k$, in $(h + 2k + 1)^{2k} n^{O(1)}$ time either constructs a path-decomposition of $G$ of width at most $k$ or concludes correctly that the pathwidth of $G$ is larger than $k$. (2) We show that there is a function $f(k, h)$ such that every $h$-semicomplete digraph of pathwidth at least $f(k, h)$ has a semicomplete subgraph of pathwidth at least $k$. One consequence of these results is that the problem of deciding if a fixed digraph $H$ is topologically contained in a given $h$-semicomplete digraph $G$ admits a polynomial-time algorithm for fixed $h$.
Metrics in the Space of High Order Networks
Venue: arXiv cs.SI 2015
Year: 2015

This paper presents methods to compare high order networks, defined as weighted complete hypergraphs collecting relationship functions between elements of tuples. They can be considered as generalizations of conventional networks where only relationship functions between pairs are defined. Important properties between relationships of tuples of different lengths are established, particularly when relationships encode dissimilarities or proximities between nodes. Two families of distances are then introduced in the space of high order networks. The distances measure differences between networks. We prove that they are valid metrics in the spaces of high order dissimilarity and proximity networks modulo permutation isomorphisms. Practical implications are explored by comparing the coauthorship networks of two popular signal processing researchers. The metrics succeed in identifying their respective collaboration patterns.
Archaeology in the Digital Age: From Paper to Databases
Venue: arXiv cs.DL 2015
Year: 2015

Research units in archaeology often manage large and precious archives containing various documents, including reports on fieldwork, scholarly studies and reference books. These archives are of course invaluable, recording decades of work, but are generally hard to consult and access. In this context, digitizing full text documents is not enough: information must be formalized, structured and easy to access thanks to friendly user interfaces.
SAR Imaging of Moving Target based on Knowledge-aided Two-dimensional Autofocus
Venue: arXiv cs.IT 2015
Year: 2015

Due to uncertainty on target's motion, the range cell migration (RCM) and azimuth phase error (APE) of moving targets can't be completely compensated in synthetic aperture radar (SAR) processing. Therefore, moving targets often appear two-dimensional (2-D) defocused in SAR images. In this paper, a 2-D autofocus method for refocusing defocused moving targets in SAR images is presented. The new method only requires a direct estimate of APE, while the residual 2-D phase error ( or RCM) is computed from the estimated APE by exploiting the analytical relationship between the 2-D phase error ( or RCM) and APE. Because the parameter estimation is performed in the reduced-dimension space by exploiting prior knowledge on phase error structure, the proposed approach offers clear advantages in both computational efficiency and estimation accuracy.
Double-Base Asymmetric AdaBoost
Venue: arXiv cs.CV 2015
Year: 2015

Based on the use of different exponential bases to define class-dependent error bounds, a new and highly efficient asymmetric boosting scheme, coined as AdaBoostDB (Double-Base), is proposed. Supported by a fully theoretical derivation procedure, unlike most of the other approaches in the literature, our algorithm preserves all the formal guarantees and properties of original (cost-insensitive) AdaBoost, similarly to the state-of-the-art Cost-Sensitive AdaBoost algorithm. However, the key advantage of AdaBoostDB is that our novel derivation scheme enables an extremely efficient conditional search procedure, dramatically improving and simplifying the training phase of the algorithm. Experiments, both over synthetic and real datasets, reveal that AdaBoostDB is able to save over 99% training time with regard to Cost-Sensitive AdaBoost, providing the same cost-sensitive results. This computational advantage of AdaBoostDB can make a difference in problems managing huge pools of weak classifiers in which boosting techniques are commonly used.
Optimal Non-coherent Data Detection for Massive SIMO Wireless Systems with General Constellations: A Polynomial Complexity Solution
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO systems can greatly increase spectral and energy efficiency over traditional MIMO systems by exploiting large antenna arrays. However, increasing the number of antennas at the base station (BS) makes the uplink non-coherent data detection very challenging in massive MIMO systems. In this paper we consider the joint maximum likelihood (ML) channel estimation and data detection problem for massive SIMO (single input multiple output) wireless systems, which is a special case of wireless systems with large antenna arrays. We propose exact ML non-coherent data detection algorithms for both constant-modulus and nonconstant-modulus constellations, with a low expected complexity. Despite the large number of unknown channel coefficients for massive SIMO systems, we show that the expected computational complexity of these algorithms is linear in the number of receive antennas and polynomial in channel coherence time. Simulation results show the performance gains (up to 5 dB improvement) of the optimal non-coherent data detection with a low computational complexity.
The Shadows of a Cycle Cannot All Be Paths
Venue: arXiv cs.CG 2015
Year: 2015

A "shadow" of a subset $S$ of Euclidean space is an orthogonal projection of $S$ into one of the coordinate hyperplanes. In this paper we show that it is not possible for all three shadows of a cycle (i.e., a simple closed curve) in $\mathbb R^3$ to be paths (i.e., simple open curves). We also show two contrasting results: the three shadows of a path in $\mathbb R^3$ can all be cycles (although not all convex) and, for every $d\geq 1$, there exists a $d$-sphere embedded in $\mathbb R^{d+2}$ whose $d+2$ shadows have no holes (i.e., they deformation-retract onto a point).