OpenRaiser/Intern-Atlas huggingface dataset:
Tuning the Diversity of Open-Ended Responses from the Crowd
Venue: arXiv cs.HC 2014
Year: 2014

Crowdsourcing can solve problems that current fully automated systems cannot. Its effectiveness depends on the reliability, accuracy, and speed of the crowd workers that drive it. These objectives are frequently at odds with one another. For instance, how much time should workers be given to discover and propose new solutions versus deliberate over those currently proposed? How do we determine if discovering a new answer is appropriate at all? And how do we manage workers who lack the expertise or attention needed to provide useful input to a given task? We present a mechanism that uses distinct payoffs for three possible worker actions---propose,vote, or abstain---to provide workers with the necessary incentives to guarantee an effective (or even optimal) balance between searching for new answers, assessing those currently available, and, when they have insufficient expertise or insight for the task at hand, abstaining. We provide a novel game theoretic analysis for this mechanism and test it experimentally on an image---labeling problem and show that it allows a system to reliably control the balance betweendiscovering new answers and converging to existing ones.
SFA Referee Allocation Scheme
Venue: arXiv cs.OH 2014
Year: 2014

For many sports, the allocation of officials to matches is performed manually and is a very time consuming procedure. For the Scottish Football Association (SFA), the allocation of referees and other officials to matches is governed by a number of rules specifying the expertise required from the different types of official at each level, e.g. Scottish Premiership League referee must be a grade 1 with high experience. The allocation requires an SFA secretary to expend several hours to find suitable officials, contact them and assign them. Most of the time, the secretary is a volunteer who performs the allocation as a hobby and it would be useful to reduce his costs and time. The project aims to reduce the burden on SFA, and potentially other secretaries, by developing a program to assign SFA officials. A suitable algorithm must be devised to search through the set of data about matches and officials and find a potential allocation. The program then updates the database with the new data, and provides a web interface for both secretaries and officials. A prototype system using the new greedy algorithm has been implemented and evaluated with SFA secretaries. A final usable referee allocation system has been designed that uses the greedy algorithm, and is extended after evaluation of the prototype. The final allocation system based provides both a command line and a web interface and has also been evaluated by SFA secretaries. In their letters of recommendation in Appendix F the SFA secretaries indicate that the final allocation system it will be used again in the future.
Generation bidding game with flexible demand
Venue: arXiv cs.GT 2014
Year: 2014

For a simple model of price-responsive demand, we consider a deregulated electricity marketplace wherein the grid (ISO, retailer-distributor) accepts bids per-unit supply from generators (simplified herein neither to consider start-up/ramp-up expenses nor day-ahead or shorter-term load following) which are then averaged (by supply allocations via an economic dispatch) to a common "clearing" price borne by customers (irrespective of variations in transmission/distribution or generation prices), i.e., the ISO does not compensate generators based on their marginal costs. Rather, the ISO provides sufficient information for generators to sensibly adjust their bids. Notwithstanding our idealizations, the dispatch dynamics are complex. For a simple benchmark power system, we find a price-symmetric Nash equilibrium through numerical experiments.
BSP Sorting: An experimental Study
Venue: arXiv cs.DC 2014
Year: 2014

The Bulk-Synchronous Parallel model of computation has been used for the architecture independent design and analysis of parallel algorithms whose performance is expressed not only in terms of problem size n but also in terms of parallel machine properties. In this paper the performance of implementations of deterministic and randomized BSP sorting algorithms is examined. The deterministic algorithm uses deterministic regular oversampling and parallel sample sorting and is augmented to handle duplicate keys transparently with optimal asymptotic efficiency. The randomized algorithm is sample-sort based and uses oversampling and the ideas introduced with the deterministic algorithm. The resulting randomized design, however, works differently from traditional parallel sample-sort based algorithms and is also augmented to transparently handle duplicate keys with optimal asymptotic efficiency thus eliminating the need to tag all input keys and to double communication/computation time. Both algorithms are shown to balance the work-load evenly among the processors and the use and precise tuning of oversampling that the BSP analysis allows combined with the transparent duplicate-key handling insures regular and balanced communication.
A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle
Venue: arXiv cs.LG 2014
Year: 2014

Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut. In this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes. We show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm. A publicly available C++ implementation is provided at http://pub.ist.ac.at/~vnk/papers/SVM.html .
Mathematical Knowledge Representation: Semantic Models and Formalisms
Venue: arXiv cs.AI 2014
Year: 2014

The paper provides a survey of semantic methods for solution of fundamental tasks in mathematical knowledge management. Ontological models and formalisms are discussed. We propose an ontology of mathematical knowledge, covering a wide range of fields of mathematics. We demonstrate applications of this representation in mathematical formula search, and learning.
Towards a General Framework for Searching on a Line and Searching on $m$ Rays
Venue: arXiv cs.DS 2014
Year: 2014

Consider the following classical search problem: given a target point $p\in \Re$, starting at the origin, find $p$ with minimum cost, where cost is defined as the distance travelled. Let $D$ be the distance of $p$ from the origin. When no lower bound on $D$ is given, no competitive search strategy exists. Demaine, Fekete and Gal (Online searching with turn cost, Theor. Comput. Sci., 361(2-3):342-355, 2006) considered the situation where no lower bound on $D$ is given but a fixed \emph{turn cost} $t>0$ is charged every time the searcher changes direction. When the total cost is expressed as $c D+ϕ$, where $c$ and $ϕ$ are positive constants, they showed that if $c$ is set to $9$, then the optimal search strategy has a cost of $9D+2t$. Although their strategy is optimal for $c=9$, we prove that the minimum cost in their framework is $5D+t+2\sqrt{2D(2D+t)} < 9D+2t$. Note that the minimum cost requires knowledge of $D$. However, given $D$, the optimal strategy has a smaller cost of $3D+t$. Therefore, this problem cannot be solved optimally and exactly when no lower bound on $D$ is given. To resolve this issue, we introduce a general framework where the cost of moving distance $x$ away from the origin is $α_1 x+β_1$ and the cost of moving distance $y$ towards the origin is $α_2 y+β_2$ for constants $α_1,α_2,β_1,β_2$. Given a lower bound $λ$ on $D$, we provide a provably optimal competitive search strategy when $α_1,α_2,β_1,β_2 \geq 0$ and $α_1+α_2 > 0$. Finally, we address the problem of searching for a target lying on one of $m$ rays extending from the origin where the cost is measured as the total distance travelled plus $t \geq 0$ times the number of turns. We provide a search strategy and compute its cost. We prove our strategy is optimal for small values of $t$ and conjecture it is always optimal.
Universal Source Polarization and an Application to a Multi-User Problem
Venue: arXiv cs.IT 2014
Year: 2014

We propose a scheme that universally achieves the smallest possible compression rate for a class of sources with side information, and develop an application of this result for a joint source channel coding problem over a broadcast channel.
Integer programming methods for special college admissions problems
Venue: arXiv cs.GT 2014
Year: 2014

We develop Integer Programming (IP) solutions for some special college admission problems arising from the Hungarian higher education admission scheme. We focus on four special features, namely the solution concept of stable score-limits, the presence of lower and common quotas, and paired applications. We note that each of the latter three special feature makes the college admissions problem NP-hard to solve. Currently, a heuristic based on the Gale-Shapley algorithm is being used in the application. The IP methods that we propose are not only interesting theoretically, but may also serve as an alternative solution concept for this practical application, and also for other ones.
Mobile recommender systems: An overview of technologies and challenges
Venue: arXiv cs.IR 2014
Year: 2014

The use of mobile devices in combination with the rapid growth of the internet has generated an information overload problem. Recommender systems is a necessity to decide which of the data are relevant to the user. However in mobile devices there are different factors who are crucial to information retrieval, such as the location, the screen size and the processor speed. This paper gives an overview of the technologies related to mobile recommender systems and a more detailed description of the challenged faced.
Rethinking the Role of Interference in Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

This article re-examines the fundamental notion of interference in wireless networks by contrasting traditional approaches to new concepts that handle interference in a creative way. Specifically, we discuss the fundamental limits of the interference channel and present the interference alignment technique and its extension of signal alignment techniques. Contrary to this traditional view, which treats interference as a detrimental phenomenon, we introduce three concepts that handle interference as a useful resource. The first concept exploits interference at the modulation level and leads to simple multiuser downlink precoding that provides significant energy savings. The second concept uses radio frequency radiation for energy harvesting and handles interference as a source of green energy. The last concept refers to a secrecy environment and uses interference as an efficient means to jam potential eavesdroppers. These three techniques bring a new vision about interference in wireless networks and motivate a plethora of potential new applications and services.
An effective single-hop distributed hash table with high lookup performance and low traffic overhead
Venue: arXiv cs.DC 2014
Year: 2014

Distributed Hash Tables (DHTs) have been used in several applications, but most DHTs have opted to solve lookups with multiple hops, to minimize bandwidth costs while sacrificing lookup latency. This paper presents D1HT, an original DHT which has a peer-to-peer and self-organizing architecture and maximizes lookup performance with reasonable maintenance traffic, and a Quarantine mechanism to reduce overheads caused by volatile peers. We implemented both D1HT and a prominent single-hop DHT, and we performed an extensive and highly representative DHT experimental comparison, followed by complementary analytical studies. In comparison with current single-hop DHTs, our results showed that D1HT consistently had the lowest bandwidth requirements, with typical reductions of up to one order of magnitude, and that D1HT could be used even in popular Internet applications with millions of users. In addition, we ran the first latency experiments comparing DHTs to directory servers, which revealed that D1HT can achieve latencies equivalent to or better than a directory server, and confirmed its greater scalability properties. Overall, our extensive set of results allowed us to conclude that D1HT can provide a very effective solution for a broad range of environments, from large-scale corporate datacenters to widely deployed Internet applications.
Improving the Effectiveness of Content Popularity Prediction Methods using Time Series Trends
Venue: arXiv cs.SI 2014
Year: 2014

We here present a simple and effective model to predict the popularity of web content. Our solution, which is the winner of two of the three tasks of the ECML/PKDD 2014 Predictive Analytics Challenge, aims at predicting user engagement metrics, such as number of visits and social network engagement, that a web page will achieve 48 hours after its upload, using only information available in the first hour after upload. Our model is based on two steps. We first use time series clustering techniques to extract common temporal trends of content popularity. Next, we use linear regression models, exploiting as predictors both content features (e.g., numbers of visits and mentions on online social networks) and metrics that capture the distance between the popularity time series to the trends extracted in the first step. We discuss why this model is effective and show its gains over state of the art alternatives.
Virtual Evidence: A Constructive Semantics for Classical Logics
Venue: arXiv cs.LO 2014
Year: 2014

This article presents a computational semantics for classical logic using constructive type theory. Such semantics seems impossible because classical logic allows the Law of Excluded Middle (LEM), not accepted in constructive logic since it does not have computational meaning. However, the apparently oracular powers expressed in the LEM, that for any proposition P either it or its negation, not P, is true can also be explained in terms of constructive evidence that does not refer to "oracles for truth." Types with virtual evidence and the constructive impossibility of negative evidence provide sufficient semantic grounds for classical truth and have a simple computational meaning. This idea is formalized using refinement types, a concept of constructive type theory used since 1984 and explained here. A new axiom creating virtual evidence fully retains the constructive meaning of the logical operators in classical contexts. Key Words: classical logic, constructive logic, intuitionistic logic, propositions-as-types, constructive type theory, refinement types, double negation translation, computational content, virtual evidence
A Mobile Food Recommendation System Based on The Traffic Light Diet
Venue: arXiv cs.CY 2014
Year: 2014

Innovative, real-time solutions are needed to address the mismatch between the demand for and supply of critical information to inform and motivate diet and health-related behavior change. Research suggests that interventions using mobile health technologies hold great promise for influencing knowledge, attitudes, and behaviors related to energy balance. The objective of this paper is to present insights related to the development and testing of a mobile food recommendation system targeting fast food restaurants. The system is designed to provide consumers with information about energy density of food options combined with tips for healthier choices when dining out, accessible through a mobile phone.
Using Architecture to Reason about Information Security
Venue: arXiv cs.CR 2014
Year: 2014

We demonstrate, by a number of examples, that information-flow security properties can be proved from abstract architectural descriptions, that describe only the causal structure of a system and local properties of trusted components. We specify these architectural descriptions of systems by generalizing intransitive noninterference policies to admit the ability to filter information passed between communicating domains. A notion of refinement of such system architectures is developed that supports top-down development of architectural specifications and proofs by abstraction of information security properties. We also show that, in a concrete setting where the causal structure is enforced by access control, a static check of the access control setting plus local verification of the trusted components is sufficient to prove that a generalized intransitive noninterference policy is satisfied.
On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs
Venue: arXiv cs.CG 2014
Year: 2014

An $st$-path in a drawing of a graph is self-approaching if during the traversal of the corresponding curve from $s$ to any point $t'$ on the curve the distance to $t'$ is non-increasing. A path has increasing chords if it is self-approaching in both directions. A drawing is self-approaching (increasing-chord) if any pair of vertices is connected by a self-approaching (increasing-chord) path. We study self-approaching and increasing-chord drawings of triangulations and 3-connected planar graphs. We show that in the Euclidean plane, triangulations admit increasing-chord drawings, and for planar 3-trees we can ensure planarity. We prove that strongly monotone (and thus increasing-chord) drawings of trees and binary cactuses require exponential resolution in the worst case, answering an open question by Kindermann et al. [GD'14]. Moreover, we provide a binary cactus that does not admit a self-approaching drawing. Finally, we show that 3-connected planar graphs admit increasing-chord drawings in the hyperbolic plane and characterize the trees that admit such drawings.
Supporting acceptance testing in distributed software projects with integrated feedback systems: Experiences and requirements
Venue: arXiv cs.SE 2014
Year: 2014

During acceptance testing customers assess whether a system meets their expectations and often identify issues that should be improved. These findings have to be communicated to the developers a task we observed to be error prone, especially in distributed teams. Here, it is normally not possible to have developer representatives from every site attend the test. Developers who were not present might misunderstand insufficiently documented findings. This hinders fixing the issues and endangers customer satisfaction. Integrated feedback systems promise to mitigate this problem. They allow to easily capture findings and their context. Correctly applied, this technique could improve feedback, while reducing customer effort. This paper collects our experiences from comparing acceptance testing with and without feedback systems in a distributed project. Our results indicate that this technique can improve acceptance testing if certain requirements are met. We identify key requirements feedback systems should meet to support acceptance testing.
Autonomous Driving - 5 Years after the Urban Challenge: The Anticipatory Vehicle as a Cyber-Physical System
Venue: arXiv cs.RO 2014
Year: 2014

In November 2007 the international competition DARPA Urban Challenge took place on the former George Airforce Base in Victorville, California to significantly promote the research and development on autonomously driving vehicles for urban environments. In the final race only eleven out of initially 89 competitors participated and "Boss" from Carnegie Mellon University succeeded. This paper summarizes results of the research carried out by all finalists within the last five years after the competition and provides an outlook where further investigation especially for software engineering is now necessary to achieve the goal of driving safely and reliably through urban environments with an anticipatory vehicle for the mass-market.
SSELab: A Plug-In-Based Framework for Web-Based Project Portals
Venue: arXiv cs.SE 2014
Year: 2014

Tools are an essential part of every software engineering project. But the number of tools that are used in all phases of the software development life-cycle and their complexity is growing continually. Consequently, the setup and maintenance of current tool chains and development environments requires much effort and consumes a lot of time. One approach to counter this, is to employ web-based systems for development tasks, because centralized systems simplify the administration and the deployment of new features. But desktop IDEs play an important role in software development projects today, and will not be replaced entirely by web-based environments in the near future. Therefore, supporting a mixture of hosted tools and tools integrated into desktop IDEs is a sensible approach. In this paper, we present the SSELab, a framework for web- based project portals that attempts to migrate more software development tools from desktop to server environments, but still allows their integration into modern desktop IDEs. It supports the deployment of tools as hosted services using plug-in systems on the server-side. Additionally, it provides access to these tools by a set of clients that can be used in different contexts, either from the command line, from within IDEs such as Eclipse, or from web pages. In the paper, we discuss the architecture and the extensibility of the SSELab framework. Furthermore, we share our experiences with creating an instance of the framework and integrating various tools for our own software development projects.
A Coloring Algorithm for Disambiguating Graph and Map Drawings
Venue: arXiv cs.DM 2014
Year: 2014

Drawings of non-planar graphs always result in edge crossings. When there are many edges crossing at small angles, it is often difficult to follow these edges, because of the multiple visual paths resulted from the crossings that slow down eye movements. In this paper we propose an algorithm that disambiguates the edges with automatic selection of distinctive colors. Our proposed algorithm computes a near optimal color assignment of a dual collision graph, using a novel branch-and-bound procedure applied to a space decomposition of the color gamut. We give examples demonstrating the effectiveness of this approach in clarifying drawings of real world graphs and maps.
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
Venue: arXiv cs.CG 2014
Year: 2014

Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a polynomial-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-hard, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.