OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Discretization of Analog Filters via Sampled-Data H-infinity Control Theory
Venue: arXiv cs.SY 2013
Year: 2013

In this article, we propose optimal discretization of analog filters (or controllers) based on the theory of sampled-data H-infinity control. We formulate the discretization problem as minimization of the H-infinity norm of the error system between a (delayed) target analog filter and a digital system including an ideal sampler, a zero-order hold, and a digital filter. The problem is reduced to discrete-time H-infinity optimization via the fast sample/hold approximation method. We also extend the proposed method to multirate systems. Feedback controller discretization by the proposed method is discussed with respect to stability. Numerical examples show the effectiveness of the proposed method.
Local Type Checking for Linked Data Consumers
Venue: arXiv cs.PL 2013
Year: 2013

The Web of Linked Data is the cumulation of over a decade of work by the Web standards community in their effort to make data more Web-like. We provide an introduction to the Web of Linked Data from the perspective of a Web developer that would like to build an application using Linked Data. We identify a weakness in the development stack as being a lack of domain specific scripting languages for designing background processes that consume Linked Data. To address this weakness, we design a scripting language with a simple but appropriate type system. In our proposed architecture some data is consumed from sources outside of the control of the system and some data is held locally. Stronger type assumptions can be made about the local data than external data, hence our type system mixes static and dynamic typing. Throughout, we relate our work to the W3C recommendations that drive Linked Data, so our syntax is accessible to Web developers.
Proving Properties of Rich Internet Applications
Venue: arXiv cs.NI 2013
Year: 2013

We introduce application layer specifications, which allow us to reason about the state and transactions of rich Internet applications. We define variants of the state/event based logic UCTL* along with two example applications to demonstrate this approach, and then look at a distributed, rich Internet application, proving properties about the information it stores and disseminates. Our approach enables us to justify proofs about abstract properties that are preserved in the face of concurrent, networked inputs by proofs about concrete properties in an Internet setting. We conclude that our approach makes it possible to reason about the programs and protocols that comprise the Internet's application layer with reliability and generality.
Expansion Trees with Cut
Venue: arXiv cs.LO 2013
Year: 2013

Herbrand's theorem is one of the most fundamental insights in logic. From the syntactic point of view it suggests a compact representation of proofs in classical first- and higher-order logic by recording the information which instances have been chosen for which quantifiers, known in the literature as expansion trees. Such a representation is inherently analytic and hence corresponds to a cut-free sequent calculus proof. Recently several extensions of such proof representations to proofs with cut have been proposed. These extensions are based on graphical formalisms similar to proof nets and are limited to prenex formulas. In this paper we present a new approach that directly extends expansion trees by cuts and covers also non-prenex formulas. We describe a cut-elimination procedure for our expansion trees with cut that is based on the natural reduction steps. We prove that it is weakly normalizing using methods from the epsilon-calculus.
Parameterized Complexity of k-Chinese Postman Problem
Venue: arXiv cs.DS 2013
Year: 2013

We consider the following problem called the $k$-Chinese Postman Problem ($k$-CPP): given a connected edge-weighted graph $G$ and integers $p$ and $k$, decide whether there are at least $k$ closed walks such that every edge of $G$ is contained in at least one of them and the total weight of the edges in the walks is at most $p$? The problem $k$-CPP is NP-complete, and van Bevern et al. (to appear) and Sorge (2013) asked whether the $k$-CPP is fixed-parameter tractable when parameterized by $k$. We prove that the $k$-CPP is indeed fixed-parameter tractable. In fact, we prove a stronger result: the problem admits a kernel with $O(k^2\log k)$ vertices. We prove that the directed version of $k$-CPP is NP-complete and ask whether the directed version is fixed-parameter tractable when parameterized by $k$.
A Comparison of Named Entity Recognition Tools Applied to Biographical Texts
Venue: arXiv cs.IR 2013
Year: 2013

Named entity recognition (NER) is a popular domain of natural language processing. For this reason, many tools exist to perform this task. Amongst other points, they differ in the processing method they rely upon, the entity types they can detect, the nature of the text they can handle, and their input/output formats. This makes it difficult for a user to select an appropriate NER tool for a specific situation. In this article, we try to answer this question in the context of biographic texts. For this matter, we first constitute a new corpus by annotating Wikipedia articles. We then select publicly available, well known and free for research NER tools for comparison: Stanford NER, Illinois NET, OpenCalais NER WS and Alias-i LingPipe. We apply them to our corpus, assess their performances and compare them. When considering overall performances, a clear hierarchy emerges: Stanford has the best results, followed by LingPipe, Illionois and OpenCalais. However, a more detailed evaluation performed relatively to entity types and article categories highlights the fact their performances are diversely influenced by those factors. This complementarity opens an interesting perspective regarding the combination of these individual tools in order to improve performance.
A Survey on Security and Privacy Protocols for Cognitive Wireless Sensor Networks
Venue: arXiv cs.CR 2013
Year: 2013

Wireless sensor networks have emerged as an important and new area in wireless and mobile computing research because of their numerous potential applications that range from indoor deployment scenarios in home and office to outdoor deployment in adversary's territory in tactical battleground. Since in many WSN applications, lives and livelihoods may depend on the timeliness and correctness of sensor data obtained from dispersed sensor nodes, these networks must be secured to prevent any possible attacks that may be launched on them. Security is, therefore, an important issue in WSNs. However, this issue becomes even more critical in cognitive wireless sensor networks, a type of WSN in which the sensor nodes have the capabilities of changing their transmission and reception parameters according to the radio environment under which they operate in order to achieve reliable and efficient communication and optimum utilization of the network resources. This survey paper presents a comprehensive discussion on various security issues in CWSNs by identifying numerous security threats in these networks and defense mechanisms to counter these vulnerabilities. Various types of attacks on CWSNs are categorized under different classes based on their natures and tragets, and corresponding to each attack class, appropriate security mechanisms are presented. The paper also identifies some open problems in this emerging area of wireless networking.
As-You-Go Deployment of a Wireless Network with On-Line Measurements and Backtracking
Venue: arXiv cs.NI 2013
Year: 2013

We are motivated by the need, in some applications, for impromptu or as-you-go deployment of wireless sensor networks. A person walks along a line, making link quality measurements with the previous relay at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed on the line with a sink at the start of the line. In this paper, we extend our earlier work on the problem (see [1]) to incorporate two new aspects: (i) inclusion of path outage in the deployment objective, and (ii) permitting the deployment agent to make measurements over several consecutive steps before selecting a placement location among them (which we call backtracking). We consider a light traffic regime, and formulate the problem as a Markov decision process. Placement algorithms are obtained for two cases: (i) the distance to the source is geometrically distributed with known mean, and (ii) the average cost per step case. We motivate the per-step cost function in terms of several known forwarding protocols for sleep-wake cycling wireless sensor networks. We obtain the structures of the optimal policies for the various formulations, and provide some sensitivity results about the policies and the optimal values. We then provide a numerical study of the algorithms, thus providing insights into the advantage of backtracking, and a comparison with simple heuristic placement policies.
Accuracy of simple, initials-based methods for author name disambiguation
Venue: arXiv cs.DL 2013
Year: 2013

There are a number of solutions that perform unsupervised name disambiguation based on the similarity of bibliographic records or common co-authorship patterns. Whether the use of these advanced methods, which are often difficult to implement, is warranted depends on whether the accuracy of the most basic disambiguation methods, which only use the author's last name and initials, is sufficient for a particular purpose. We derive realistic estimates for the accuracy of simple, initials-based methods using simulated bibliographic datasets in which the true identities of authors are known. Based on the simulations in five diverse disciplines we find that the first initial method already correctly identifies 97% of authors. An alternative simple method, which takes all initials into account, is typically two times less accurate, except in certain datasets that can be identified by applying a simple criterion. Finally, we introduce a new name-based method that combines the features of first initial and all initials methods by implicitly taking into account the last name frequency and the size of the dataset. This hybrid method reduces the fraction of incorrectly identified authors by 10-30% over the first initial method.
SketchPadN-D: WYDIWYG Sculpting and Editing in High-Dimensional Space
Venue: arXiv cs.HC 2013
Year: 2013

High-dimensional data visualization has been attracting much attention. To fully test related software and algorithms, researchers require a diverse pool of data with known and desired features. Test data do not always provide this, or only partially. Here we propose the paradigm WYDIWYGS (What You Draw Is What You Get). Its embodiment, Sketch Pad ND, is a tool that allows users to generate high-dimensional data in the same interface they also use for visualization. This provides for an immersive and direct data generation activity, and furthermore it also enables users to interactively edit and clean existing high-dimensional data from possible artifacts. Sketch Pad ND offers two visualization paradigms, one based on parallel coordinates and the other based on a relatively new framework using an N-D polygon to navigate in high-dimensional space. The first interface allows users to draw arbitrary profiles of probability density functions along each dimension axis and sketch shapes for data density and connections between adjacent dimensions. The second interface embraces the idea of sculpting. Users can carve data at arbitrary orientations and refine them wherever necessary. This guarantees the data generated is truly high-dimensional. We demonstrate our tool's usefulness in real data visualization scenarios.
Cost Minimization in Multiple IaaS Clouds: A Double Auction Approach
Venue: arXiv cs.NI 2013
Year: 2013

IaaS clouds invest substantial capital in operating their data centers. Reducing the cost of resource provisioning, is their forever pursuing goal. Computing resource trading among multiple IaaS clouds provide a potential for IaaS clouds to utilize cheaper resources to fulfill their jobs, by exploiting the diversities of different clouds' workloads and operational costs. In this paper, we focus on studying the IaaS clouds' cost reduction through computing resource trading among multiple IaaS clouds. We formulate the global cost minimization problem among multiple IaaS clouds under cooperative scenario where each individual cloud's workload and cost information is known. Taking into consideration jobs with disparate lengths, a non-preemptive approximation algorithm for leftover job migration and new job scheduling is designed. Given to the selfishness of individual clouds, we further design a randomized double auction mechanism to elicit clouds' truthful bidding for buying or selling virtual machines. We evaluate our algorithms using trace-driven simulations.
A Spline-based Volumetric Data Modeling Framework and Its Applications
Venue: arXiv cs.GR 2013
Year: 2013

In this dissertation, we concentrate on the challenging research issue of developing a spline-based modeling framework, which converts the conventional data (e.g., surface meshes) to tensor-product trivariate splines. This methodology can represent both boundary/volumetric geometry and real volumetric physical attributes in a compact and continuous fashion. The regular tensor-product structure enables our new developed methods to be embedded into the industry standard seamlessly. These properties make our techniques highly preferable in many physically-based applications including mechanical analysis, shape deformation and editing, virtual surgery training, etc.
On Interference Networks over Finite Fields
Venue: arXiv cs.IT 2013
Year: 2013

We present a framework to study linear deterministic interference networks over finite fields. Unlike the popular linear deterministic models introduced to study Gaussian networks, we consider networks where the channel coefficients are general scalars over some extension field $\FF_{p^m}$ (scalar $m$-th extension-field models), $m \times m$ diagonal matrices over $\FF_p$ ($m$-symbol extension ground-field models), and $m \times m$ general non-singular matrices (MIMO ground field models). We use the companion matrix representation of the extension field to convert $m$-th extension scalar models into MIMO ground-field models where the channel matrices have special algebraic structure. For such models, we consider the $2 \times 2 \times 2$ topology (two-hops two-flow) and the 3-user interference network topology. We derive achievability results and feasibility conditions for certain schemes based on the Precoding-Based Network Alignment (PBNA) approach, where intermediate nodes use random linear network coding (i.e., propagate random linear combinations of their incoming messages) and non-trivial precoding/decoding is performed only at the network edges, at the sources and destinations. Furthermore, we apply this approach to the scalar $2\times 2\times 2$ complex Gaussian IC with fixed channel coefficients, and show two competitive schemes outperforming other known approaches at any SNR, where we combine finite-field linear precoding/decoding with lattice coding and the Compute and Forward approach at the signal level. As a side result, we also show significant advantages of vector linear network coding both in terms of feasibility probability (with random coding coefficients) and in terms of coding latency, with respect to standard scalar linear network coding, in PBNA schemes.
Handling Parallelism in a Concurrency Model
Venue: arXiv cs.SE 2013
Year: 2013

Programming models for concurrency are optimized for dealing with nondeterminism, for example to handle asynchronously arriving events. To shield the developer from data race errors effectively, such models may prevent shared access to data altogether. However, this restriction also makes them unsuitable for applications that require data parallelism. We present a library-based approach for permitting parallel access to arrays while preserving the safety guarantees of the original model. When applied to SCOOP, an object-oriented concurrency model, the approach exhibits a negligible performance overhead compared to ordinary threaded implementations of two parallel benchmark programs.
Incentives and Efficiency in Uncertain Collaborative Environments
Venue: arXiv cs.GT 2013
Year: 2013

We consider collaborative systems where users make contributions across multiple available projects and are rewarded for their contributions in individual projects according to a local sharing of the value produced. This serves as a model of online social computing systems such as online Q&A forums and of credit sharing in scientific co-authorship settings. We show that the maximum feasible produced value can be well approximated by simple local sharing rules where users are approximately rewarded in proportion to their marginal contributions and that this holds even under incomplete information about the player's abilities and effort constraints. For natural instances we show almost 95% optimality at equilibrium. When players incur a cost for their effort, we identify a threshold phenomenon: the efficiency is a constant fraction of the optimal when the cost is strictly convex and decreases with the number of players if the cost is linear.
Sign Stable Projections, Sign Cauchy Projections and Chi-Square Kernels
Venue: arXiv cs.LG 2013
Year: 2013

The method of stable random projections is popular for efficiently computing the Lp distances in high dimension (where 0<p<=2), using small space. Because it adopts nonadaptive linear projections, this method is naturally suitable when the data are collected in a dynamic streaming fashion (i.e., turnstile data streams). In this paper, we propose to use only the signs of the projected data and analyze the probability of collision (i.e., when the two signs differ). We derive a bound of the collision probability which is exact when p=2 and becomes less sharp when p moves away from 2. Interestingly, when p=1 (i.e., Cauchy random projections), we show that the probability of collision can be accurately approximated as functions of the chi-square similarity. For example, when the (un-normalized) data are binary, the maximum approximation error of the collision probability is smaller than 0.0192. In text and vision applications, the chi-square similarity is a popular measure for nonnegative data when the features are generated from histograms. Our experiments confirm that the proposed method is promising for large-scale learning applications.
Coevolutionary networks of reinforcement-learning agents
Venue: arXiv cs.MA 2013
Year: 2013

This paper presents a model of network formation in repeated games where the players adapt their strategies and network ties simultaneously using a simple reinforcement-learning scheme. It is demonstrated that the coevolutionary dynamics of such systems can be described via coupled replicator equations. We provide a comprehensive analysis for three-player two-action games, which is the minimum system size with nontrivial structural dynamics. In particular, we characterize the Nash equilibria (NE) in such games and examine the local stability of the rest points corresponding to those equilibria. We also study general n-player networks via both simulations and analytical methods and find that in the absence of exploration, the stable equilibria consist of star motifs as the main building blocks of the network. Furthermore, in all stable equilibria the agents play pure strategies, even when the game allows mixed NE. Finally, we study the impact of exploration on learning outcomes, and observe that there is a critical exploration rate above which the symmetric and uniformly connected network topology becomes stable.
Coolhunting for the World's Thought Leaders
Venue: arXiv cs.SI 2013
Year: 2013

Which thinkers are we guided by? A novel "Thought Leader Map" shows the select group of people with real influence who are setting the trends in the market for ideas. The influencers in philosophy, sociology, economics, and the "hard sciences" have been identified by a Delphi process, asking 50 thought leaders to name their peers. The importance of the influencers is calculated by constructing a co-occurrence network in the Blogosphere. Our main insight is that the era of the great authorities seems to be over. Major thought leaders are rare - the picture is composed of many specialists.
Increasing Knowledge Worker Efficiency through a "Virtual Mirror" of the Social Network
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we introduce a case study describing the combination of manual survey-based and e-mail-based social network analysis. The goal of the project was to increase collaboration efficiency in a team of consultants of a major high tech manufacturer. By analyzing the social network of a team of 42 consultants and comparing it with their utilization as the dependent variable, their efficiency in working together was improved in various way by bridging structure holes and eliminating bottlenecks, reducing stress for overburdened individuals, connecting isolated individuals and identifying the best network structures for high utilization and increased job satisfaction.
Role and Discipline Relationships in a Transdisciplinary Biomedical Team: Structuration, Values Override and Context Scaffolding
Venue: arXiv cs.CY 2013
Year: 2013

Though accepted that "team science" is needed to tackle and conquer the health problems that are plaguing our society significant empirical evidence of team mechanisms and functional dynamics is still lacking in abundance. Through grounded methods the relationship between scientific disciplines and team roles was observed in a United States National Institutes of Health-funded (NIH) research consortium. Interviews and the Organizational Culture Assessment Instrument (OCAI) were employed.. Findings show strong role and discipline idiosyncrasies that when viewed separately provide different insights into team functioning and change receptivity. When considered simultaneously, value-latent characteristics emerged showing self-perceived contributions to the team. This micro/meso analysis suggests that individual participation in team level interactions can inform the structuration of roles and disciplines in an attempt to tackle macro level problems.
Benchmarking Soundtrack Recommendation Systems with SRBench
Venue: arXiv cs.IR 2013
Year: 2013

In this work, a benchmark to evaluate the retrieval performance of soundtrack recommendation systems is proposed. Such systems aim at finding songs that are played as background music for a given set of images. The proposed benchmark is based on preference judgments, where relevance is considered a continuous ordinal variable and judgments are collected for pairs of songs with respect to a query (i.e., set of images). To capture a wide variety of songs and images, we use a large space of possible music genres, different emotions expressed through music, and various query-image themes. The benchmark consists of two types of relevance assessments: (i) judgments obtained from a user study, that serve as a "gold standard" for (ii) relevance judgments gathered through Amazon's Mechanical Turk. We report on an analysis of relevance judgments based on different levels of user agreement and investigate the performance of two state-of-the-art soundtrack recommendation systems using the proposed benchmark.