OpenRaiser/Intern-Atlas huggingface dataset:
A Geographic Multi-Copy Routing Scheme for DTNs With Heterogeneous Mobility
Venue: arXiv cs.DC 2016
Year: 2016

Previous geographic routing schemes in Delay/Disruption Tolerant Networks (DTNs) only consider the homogeneous scenario where nodal mobility is identical. Motivated by this gap, we turn to design a DTN based geographic routing scheme in heterogeneous scenario. Systematically, our target is achieved via two steps: 1) We first propose "The-Best-Geographic-Relay (TBGR)" routing scheme to relay messages via a limited number of copies, under the homogeneous scenario. We further overcome the local maximum problem of TBGR given a sparse network density, different from those efforts in dense networks like clustered Wireless Sensor Networks (WSNs). 2) We next extend TBGR for heterogeneous scenario, and propose "The-Best-Heterogeneity-Geographic-Relay (TBHGR)" routing scheme considering individual nodal visiting preference (referred to non-identical nodal mobility). Extensive results under a realistic heterogeneous scenario show the advantage of TBHGR over literature works in terms of reliable message delivery, while with low routing overhead.
Transit directions at global scale
Venue: arXiv cs.OH 2016
Year: 2016

A novel approach to integrated ground and air public transport journey planning, operating at continent scale. Flexible date search, prerequisite for long distance trips given their typical low and irregular service frequencies, is core functionality. The algorithm is especially suited for irregular and poorly structured networks. Almost all of the described functionality is implemented in a working prototype. Using ground transport only, the system is on par with Google Transit on random country-wide trips in the US.
Arbitrarily Varying Wiretap Channels with Type Constrained States
Venue: arXiv cs.IT 2016
Year: 2016

An arbitrarily varying wiretap channel (AVWTC) with a type constraint on the allowed state sequences is considered, and a single-letter characterization of its correlated-random (CR) assisted semantic-security (SS) capacity is derived. The allowed state sequences are the ones in a typical set around a single constraining type. SS is established by showing that the mutual information between the message and the eavesdropper's observations is negligible even when maximized over all message distributions, choices of state sequences and realizations of the CR-code. Both the achievability and the converse proofs of the type constrained coding theorem rely on stronger claims than actually required. The direct part establishes a novel single-letter lower bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained by any convex and closed set of state probability mass functions. This bound achieves the best known single-letter secrecy rates for a corresponding compound wiretap channel over the same constraint set. In contrast to other single-letter results in the AVWTC literature, this work does not assume the existence of a best channel to the eavesdropper. Instead, SS follows by leveraging the heterogeneous version of the stronger soft-covering lemma and a CR-code reduction argument. Optimality is a consequence of an max-inf upper bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained to any collection of type-classes. When adjusted to the aforementioned compound WTC, the upper bound simplifies to a max-min structure, thus strengthening the previously best known single-letter upper bound by Liang et al. that has a min-max form. The proof of the upper bound uses a novel distribution coupling argument.
Dual-tree $k$-means with bounded iteration runtime
Venue: arXiv cs.DS 2016
Year: 2016

k-means is a widely used clustering algorithm, but for $k$ clusters and a dataset size of $N$, each iteration of Lloyd's algorithm costs $O(kN)$ time. Although there are existing techniques to accelerate single Lloyd iterations, none of these are tailored to the case of large $k$, which is increasingly common as dataset sizes grow. We propose a dual-tree algorithm that gives the exact same results as standard $k$-means; when using cover trees, we use adaptive analysis techniques to, under some assumptions, bound the single-iteration runtime of the algorithm as $O(N + k log k)$. To our knowledge these are the first sub-$O(kN)$ bounds for exact Lloyd iterations. We then show that this theoretically favorable algorithm performs competitively in practice, especially for large $N$ and $k$ in low dimensions. Further, the algorithm is tree-independent, so any type of tree may be used.
Optimal Current Waveforms for Switched-Reluctance Motors
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we address the problem of finding current waveforms for a switched reluctance motor that minimize a user-defined combination of torque ripple and RMS current. The motor model we use is fairly general, and includes magnetic saturation, voltage and current limits, and highly coupled magnetics (and therefore, unconventional geometries and winding patterns). We solve this problem by approximating it as a mixed-integer convex program, which we solve globally using branch and bound. We demonstrate our approach on an experimentally verified model of a fully pitched switched reluctance motor, for which we find the globally optimal waveforms, even for high rotor speeds.
Trust from the past: Bayesian Personalized Ranking based Link Prediction in Knowledge Graphs
Venue: arXiv cs.LG 2016
Year: 2016

Link prediction, or predicting the likelihood of a link in a knowledge graph based on its existing state is a key research task. It differs from a traditional link prediction task in that the links in a knowledge graph are categorized into different predicates and the link prediction performance of different predicates in a knowledge graph generally varies widely. In this work, we propose a latent feature embedding based link prediction model which considers the prediction task for each predicate disjointly. To learn the model parameters it utilizes a Bayesian personalized ranking based optimization technique. Experimental results on large-scale knowledge bases such as YAGO2 show that our link prediction approach achieves substantially higher performance than several state-of-art approaches. We also show that for a given predicate the topological properties of the knowledge graph induced by the given predicate edges are key indicators of the link prediction performance of that predicate in the knowledge graph.
A Theorem Prover for Quantum Hoare Logic and Its Applications
Venue: arXiv cs.LO 2016
Year: 2016

Quantum Hoare Logic (QHL) was introduced in Ying's work to specify and reason about quantum programs. In this paper, we implement a theorem prover for QHL based on Isabelle/HOL. By applying the theorem prover, verifying a quantum program against a specification is transformed equivalently into an order relation between matrices. Due to the limitation of Isabelle/HOL, the calculation of the order relation is solved by calling an outside oracle written in Python. To the best of our knowledge, this is the first theorem prover for quantum programs. To demonstrate its power, the correctness of two well-known quantum algorithms, i.e., Grover Quantum Search and Quantum Phase Estimation (the key step in Shor's quantum algorithm of factoring in polynomial time) are proved using the theorem prover. These are the first mechanized proofs for both of them.
PKI Safety Net (PKISN): Addressing the Too-Big-to-Be-Revoked Problem of the TLS Ecosystem
Venue: arXiv cs.CR 2016
Year: 2016

In a public-key infrastructure (PKI), clients must have an efficient and secure way to determine whether a certificate was revoked (by an entity considered as legitimate to do so), while preserving user privacy. A few certification authorities (CAs) are currently responsible for the issuance of the large majority of TLS certificates. These certificates are considered valid only if the certificate of the issuing CA is also valid. The certificates of these important CAs are effectively too big to be revoked, as revoking them would result in massive collateral damage. To solve this problem, we redesign the current revocation system with a novel approach that we call PKI Safety Net (PKISN), which uses publicly accessible logs to store certificates (in the spirit of Certificate Transparency) and revocations. The proposed system extends existing mechanisms, which enables simple deployment. Moreover, we present a complete implementation and evaluation of our scheme.
Stereo Matching by Joint Energy Minimization
Venue: arXiv cs.CV 2016
Year: 2016

In [18], Mozerov et al. propose to perform stereo matching as a two-step energy minimization problem. For the first step they solve a fully connected MRF model. And in the next step the marginal output is employed as the unary cost for a locally connected MRF model. In this paper we intend to combine the two steps of energy minimization in order to improve stereo matching results. We observe that the fully connected MRF leads to smoother disparity maps, while the locally connected MRF achieves superior results in fine-structured regions. Thus we propose to jointly solve the fully connected and locally connected models, taking both their advantages into account. The joint model is solved by mean field approximations. While remaining efficient, our joint model outperforms the two-step energy minimization approach in both time and estimation error on the Middlebury stereo benchmark v3.
A stabilized finite element formulation for liquid shells and its application to lipid bilayers
Venue: arXiv cs.CE 2016
Year: 2016

This paper presents a new finite element (FE) formulation for liquid shells that is based on an explicit, 3D surface discretization using $C^1$-continuous finite elements constructed from NURBS interpolation. Both displacement-based and mixed FE formulations are proposed. The latter is needed for area-incompressible material behavior, where penalty-type regularizations can lead to misleading results. In order to obtain quasi-static solutions, several numerical stabilization schemes are proposed based on either stiffness, viscosity or projection. Several numerical examples are considered in order to illustrate the accuracy and the capabilities of the proposed formulation, and to compare the different stabilization schemes. The presented formulation is capable of simulating non-trivial surface shapes associated with tube formation and protein-induced budding of lipid bilayers. In the latter case, the presented formulation yields non-axisymmetric solutions, which have not been observed in previous simulations. It is shown that those non-axisymmetric shapes are preferred over axisymmetric ones.
On an application of multidimensional arrays
Venue: arXiv cs.DS 2016
Year: 2016

This article discusses some difficulties in the implementation of combinatorial algorithms associated with the choice of all elements with certain properties among the elements of a set with great cardinality.The problem has been resolved by using multidimensional arrays. Illustration of the method is a solution of the problem of obtaining one representative from each equivalence class with respect to the described in the article equivalence relation in the set of all $m\sim n$ binary matrices. This equivalence relation has an application in the mathematical modeling in the textile industry.
A Model-Driven Engineering Approach for ROS using Ontological Semantics
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents a novel ontology-driven software engineering approach for the development of industrial robotics control software. It introduces the ReApp architecture that synthesizes model-driven engineering with semantic technologies to facilitate the development and reuse of ROS-based components and applications. In ReApp, we show how different ontological classification systems for hardware, software, and capabilities help developers in discovering suitable software components for their tasks and in applying them correctly. The proposed model-driven tooling enables developers to work at higher abstraction levels and fosters automatic code generation. It is underpinned by ontologies to minimize discontinuities in the development workflow, with an integrated development environment presenting a seamless interface to the user. First results show the viability and synergy of the selected approach when searching for or developing software with reuse in mind.
Keyboard Surface Interaction: Making the keyboard into a pointing device
Venue: arXiv cs.HC 2016
Year: 2016

Pointing devices that reside on the keyboard can reduce the overall time needed to perform mixed pointing and typing tasks, since the hand of the user does not have to reach for the pointing device. However, previous implementations of this kind of device have a higher movement time compared to the mouse and trackpad due to large error rate, low speed and spatial resolution. In this paper we introduce Keyboard Surface Interaction (KSI), an interaction approach that turns the surface of a keyboard into an interaction surface and allows users to rest their hands on the keyboard at all times to minimize fatigue. We developed a proof-of-concept implementation, Fingers, which we optimized over a series of studies. Finally, we evaluated Fingers against the mouse and trackpad in a user study with 25 participants on a Fitts law test style, mixed typing and pointing task. Results showed that for users with more exposure to KSI, our KSI device had better performance (reduced movement and homing time) and reduced discomfort compared to the trackpad. When compared to the mouse, KSI had reduced homing time and reduced discomfort, but increased movement time. This interaction approach is not only a new way to capitalize on the space on top of the keyboard, but also a call to innovate and think beyond the touchscreen, touchpad, and mouse as our main pointing devices. The results of our studies serve as a specification for future KSI devices.
Microdatabases for the Industrial Internet
Venue: arXiv cs.DB 2016
Year: 2016

The Industrial Internet market is targeted to grow by trillions of US dollars by the year 2030, driven by adoption, deployment and integration of billions of intelligent devices and their associated data. This digital expansion faces a number of significant challenges, including reliable data management, security and privacy. Realizing the benefits from this evolution is made more difficult because a typical industrial plant includes multiple vendors and legacy technology stacks. Aggregating all the raw data to a single data center before performing analysis increases response times, raising performance concerns in traditional markets and requiring a compromise between data duplication and data access performance. Similar to the way microservices can integrate disparate information technologies without imposing monolithic cross-cutting architecture impacts, we propose microdatabases to manage the data heterogeneity of the Industrial Internet while allowing records to be captured and secured close to the industrial processes, but also be made available near the applications that can benefit from the data. A microdatabase is an abstraction of a data store that standardizes and protects the interactions between distributed data sources, providers and consumers. It integrates an information model with discoverable object types that can be browsed interactively and programmatically, and supports repository instances that evolve with their own lifecycles. The microdatabase abstraction is independent of technology choice and was designed based on solicitation and review of industry stakeholder concerns.
It's about time: Online Macrotask Sequencing in Expert Crowdsourcing
Venue: arXiv cs.SI 2016
Year: 2016

We introduce the problem of Task Assignment and Sequencing (TAS), which adds the timeline perspective to expert crowdsourcing optimization. Expert crowdsourcing involves macrotasks, like document writing, product design, or web development, which take more time than typical binary microtasks, require expert skills, assume varying degrees of knowledge over a topic, and require crowd workers to build on each other's contributions. Current works usually assume offline optimization models, which consider worker and task arrivals known and do not take into account the element of time. Realistically however, time is critical: tasks have deadlines, expert workers are available only at specific time slots, and worker/task arrivals are not known a-priori. Our work is the first to address the problem of optimal task sequencing for online, heterogeneous, time-constrained macrotasks. We propose tas-online, an online algorithm that aims to complete as many tasks as possible within budget, required quality and a given timeline, without future input information regarding job release dates or worker availabilities. Results, comparing tas-online to four typical benchmarks, show that it achieves more completed jobs, lower flow times and higher job quality. This work has practical implications for improving the Quality of Service of current crowdsourcing platforms, allowing them to offer cost, quality and time improvements for expert tasks.
Modification of Question Writing Style Influences Content Popularity in a Social Q&A System
Venue: arXiv cs.IR 2016
Year: 2016

TurboTax AnswerXchange is a social Q&A system supporting users working on federal and state tax returns. Using 2015 data, we demonstrate that content popularity (or number of views per AnswerXchange question) can be predicted with reasonable accuracy based on attributes of the question alone. We also employ probabilistic topic analysis and uplift modeling to identify question features with the highest impact on popularity. We demonstrate that content popularity is driven by behavioral attributes of AnswerXchange users and depends on complex interactions between search ranking algorithms, psycholinguistic factors and question writing style. Our findings provide a rationale for employing popularity predictions to guide the users into formulating better questions and editing the existing ones. For example, starting question title with a question word or adding details to the question increase number of views per question. Similar approach can be applied to promoting AnswerXchange content indexed by Google to drive organic traffic to TurboTax.
Training Recurrent Neural Networks by Diffusion
Venue: arXiv cs.LG 2016
Year: 2016

This work presents a new algorithm for training recurrent neural networks (although ideas are applicable to feedforward networks as well). The algorithm is derived from a theory in nonconvex optimization related to the diffusion equation. The contributions made in this work are two fold. First, we show how some seemingly disconnected mechanisms used in deep learning such as smart initialization, annealed learning rate, layerwise pretraining, and noise injection (as done in dropout and SGD) arise naturally and automatically from this framework, without manually crafting them into the algorithms. Second, we present some preliminary results on comparing the proposed method against SGD. It turns out that the new algorithm can achieve similar level of generalization accuracy of SGD in much fewer number of epochs.
Complexity Analysis of 2-Heterogeneous Minimum Spanning Forest Problem
Venue: arXiv cs.CC 2016
Year: 2016

For complexity of the heterogeneous minimum spanning forest problem has not been determined, we reduce 3-SAT which is NP-complete to 2-heterogeneous minimum spanning forest problem to prove this problem is NP-hard and spread result to general problem, which determines complexity of this problem. It provides a theoretical basis for the future designing of approximation algorithms for the problem.
Whats in a Country Name - Twitter Hashtag Analysis of #singapore
Venue: arXiv cs.SI 2016
Year: 2016

Twitter as a micro-blogging platform rose to instant fame mainly due to its minimalist features that allow seamless communication between users. As the conversations grew thick and faster, a placeholder feature called as Hashtags became important as it captured the themes behind the tweets. Prior studies have investigated the conversation dynamics, inter-play with other media platforms and communication patterns between users for specific event-based hashtags such as the #Occupy movement. Commonplace hashtags which are used on a daily basis have been largely ignored due to their seemingly innocuous presence in tweets and also due to the lack of connection with real-world events. However, it can be postulated that utility of these hashtags is the main reason behind their continued usage. This study is aimed at understanding the rationale behind the usage of a particular type of commonplace hashtags - location hashtags such as country and city name hashtags. Tweets with the hashtag #singapore were extracted for one week duration. Manual and automatic tweet classification was performed along with social network analysis, to identify the underlying themes. Seven themes were identified. Findings indicate that the hashtag is prominent in tweets about local events, local news, users current location and landmark related information sharing. Users who share content from social media sites such as Instagram make use of the hashtag in a more prominent way when compared to users who post textual content. News agencies, commercial bodies and celebrities make use of the hashtag more than common individuals. Overall, the results show the non-conversational nature of the hashtag. The findings are to be validated with other country names and cross-validated with hashtag data from other social media platforms.
$\mathbf{D^3}$: Deep Dual-Domain Based Fast Restoration of JPEG-Compressed Images
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we design a Deep Dual-Domain ($\mathbf{D^3}$) based fast restoration model to remove artifacts of JPEG compressed images. It leverages the large learning capacity of deep networks, as well as the problem-specific expertise that was hardly incorporated in the past design of deep architectures. For the latter, we take into consideration both the prior knowledge of the JPEG compression scheme, and the successful practice of the sparsity-based dual-domain approach. We further design the One-Step Sparse Inference (1-SI) module, as an efficient and light-weighted feed-forward approximation of sparse coding. Extensive experiments verify the superiority of the proposed $D^3$ model over several state-of-the-art methods. Specifically, our best model is capable of outperforming the latest deep model for around 1 dB in PSNR, and is 30 times faster.
Brain-Inspired Deep Networks for Image Aesthetics Assessment
Venue: arXiv cs.CV 2016
Year: 2016

Image aesthetics assessment has been challenging due to its subjective nature. Inspired by the scientific advances in the human visual perception and neuroaesthetics, we design Brain-Inspired Deep Networks (BDN) for this task. BDN first learns attributes through the parallel supervised pathways, on a variety of selected feature dimensions. A high-level synthesis network is trained to associate and transform those attributes into the overall aesthetics rating. We then extend BDN to predicting the distribution of human ratings, since aesthetics ratings are often subjective. Another highlight is our first-of-its-kind study of label-preserving transformations in the context of aesthetics assessment, which leads to an effective data augmentation approach. Experimental results on the AVA dataset show that our biological inspired and task-specific BDN model gains significantly performance improvement, compared to other state-of-the-art models with the same or higher parameter capacity.