OpenRaiser/Intern-Atlas huggingface dataset:
Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency
Venue: arXiv cs.CR 2017
Year: 2017

Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become mandatory in the design of new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost's scheme is constructed with a relatively inefficient public key cryptographic primitive, and has a poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost's scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost's scheme. The experiment results show that both our schemes are highly efficient, and FASTIO achieves a much better scalability due to its optimized I/O.
Efficient Dynamic Searchable Encryption with Forward Privacy
Venue: arXiv cs.CR 2017
Year: 2017

Searchable symmetric encryption (SSE) enables a client to perform searches over its outsourced encrypted files while preserving privacy of the files and queries. Dynamic schemes, where files can be added or removed, leak more information than static schemes. For dynamic schemes, forward privacy requires that a newly added file cannot be linked to previous searches. We present a new dynamic SSE scheme that achieves forward privacy by replacing the keys revealed to the server on each search. Our scheme is efficient and parallelizable and outperforms the best previous schemes providing forward privacy, and achieves competitive performance with dynamic schemes without forward privacy. We provide a full security proof in the random oracle model. In our experiments on the Wikipedia archive of about four million pages, the server takes one second to perform a search with 100,000 results.
Physics-based Motion Planning: Evaluation Criteria and Benchmarking
Venue: arXiv cs.RO 2017
Year: 2017

Motion planning has evolved from coping with simply geometric problems to physics-based ones that incorporate the kinodynamic and the physical constraints imposed by the robot and the physical world. Therefore, the criteria for evaluating physics-based motion planners goes beyond the computational complexity (e.g. in terms of planning time) usually used as a measure for evaluating geometrical planners, in order to consider also the quality of the solution in terms of dynamical parameters. This study proposes an evaluation criteria and analyzes the performance of several kinodynamic planners, which are at the core of physics-based motion planning, using different scenarios with fixed and manipulatable objects. RRT, EST, KPIECE and SyCLoP are used for the benchmarking. The results show that KPIECE computes the time-optimal solution with heighest success rate, whereas, SyCLoP compute the most power-optimal solution among the planners used.
Implementation of the algorithm for testing an automaton for synchronization in linear expected time
Venue: arXiv cs.FL 2017
Year: 2017

Berlinkov has suggested an algorithm that, given a deterministic finite automaton $\mathcal{A}$, verifies whether or not $\mathcal{A}$ is synchronizing in linear (of the number of states and letters) expected time. We present a modification of Berlinkov's algorithm which we have implemented and tested. Our experiments show that the implementation outperforms the standard quadratic algorithm even for automata of modest size and allow us to give a statistically accurate approximation of the ratio of non-synchronizing automata amongst all automata with a given number of states.
The Crowdfunding Game
Venue: arXiv cs.GT 2017
Year: 2017

The recent success of crowdfunding for supporting new and innovative products has been overwhelming with over 34 Billion Dollars raised in 2015. In many crowdfunding platforms, firms set a campaign threshold and contributions are collected only if this threshold is reached. During the campaign, consumers are uncertain as to the ex-post value of the product, the business model viability, and the seller's reliability. Consumer who commit to a contribution therefore gambles. This gamble is effected by the campaign's threshold. Contributions to campaigns with higher thresholds are collected only if a greater number of agents find the offering acceptable. Therefore, high threshold serves as a social insurance and thus in high-threshold campaigns, potential contributors feel more at ease with contributing. We introduce the crowdfunding game and explore the contributor's dilemma in the context of experience goods. We discuss equilibrium existence and related social welfare, information aggregation and revenue implications.
Straggler Mitigation by Delayed Relaunch of Tasks
Venue: arXiv cs.PF 2017
Year: 2017

Redundancy for straggler mitigation, originally in data download and more recently in distributed computing context, has been shown to be effective both in theory and practice. Analysis of systems with redundancy has drawn significant attention and numerous papers have studied pain and gain of redundancy under various service models and assumptions on the straggler characteristics. We here present a cost (pain) vs. latency (gain) analysis of using simple replication or erasure coding for straggler mitigation in executing jobs with many tasks. We quantify the effect of the tail of task execution times and discuss tail heaviness as a decisive parameter for the cost and latency of using redundancy. Specifically, we find that coded redundancy achieves better cost vs. latency tradeoff than simple replication and can yield reduction in both cost and latency under less heavy tailed execution times. We show that delaying redundancy is not effective in reducing cost and that delayed relaunch of stragglers can yield significant reduction in cost and latency. We validate these observations by comparing with the simulations that use empirical distributions extracted from Google cluster data.
Physics-based Motion Planning with Temporal Logic Specifications
Venue: arXiv cs.RO 2017
Year: 2017

One of the main foci of robotics is nowadays centered in providing a great degree of autonomy to robots. A fundamental step in this direction is to give them the ability to plan in discrete and continuous spaces to find the required motions to complete a complex task. In this line, some recent approaches describe tasks with Linear Temporal Logic (LTL) and reason on discrete actions to guide sampling-based motion planning, with the aim of finding dynamically-feasible motions that satisfy the temporal-logic task specifications. The present paper proposes an LTL planning approach enhanced with the use of ontologies to describe and reason about the task, on the one hand, and that includes physics-based motion planning to allow the purposeful manipulation of objects, on the other hand. The proposal has been implemented and is illustrated with didactic examples with a mobile robot in simple scenarios where some of the goals are occupied with objects that must be removed in order to fulfill the task.
Extracting Insights from the Topology of the JavaScript Package Ecosystem
Venue: arXiv cs.SE 2017
Year: 2017

Software ecosystems have had a tremendous impact on computing and society, capturing the attention of businesses, researchers, and policy makers alike. Massive ecosystems like the JavaScript node package manager (npm) is evidence of how packages are readily available for use by software projects. Due to its high-dimension and complex properties, software ecosystem analysis has been limited. In this paper, we leverage topological methods in visualize the high-dimensional datasets from a software ecosystem. Topological Data Analysis (TDA) is an emerging technique to analyze high-dimensional datasets, which enables us to study the shape of data. We generate the npm software ecosystem topology to uncover insights and extract patterns of existing libraries by studying its localities. Our real-world example reveals many interesting insights and patterns that describes the shape of a software ecosystem.
Visual Reasoning with Natural Language
Venue: arXiv cs.CL 2017
Year: 2017

Natural language provides a widely accessible and expressive interface for robotic agents. To understand language in complex environments, agents must reason about the full range of language inputs and their correspondence to the world. Such reasoning over language and vision is an open problem that is receiving increasing attention. While existing data sets focus on visual diversity, they do not display the full range of natural language expressions, such as counting, set reasoning, and comparisons. We propose a simple task for natural language visual reasoning, where images are paired with descriptive statements. The task is to predict if a statement is true for the given scene. This abstract describes our existing synthetic images corpus and our current work on collecting real vision data.
Building a Structured Query Engine
Venue: arXiv cs.IR 2017
Year: 2017

Finding patterns in data and being able to retrieve information from those patterns is an important task in Information retrieval. Complex search requirements which are not fulfilled by simple string matching and require exploring certain patterns in data demand a better query engine that can support searching via structured queries. In this article, we built a structured query engine which supports searching data through structured queries on the lines of ElasticSearch. We will show how we achieved real time indexing and retrieving of data through a RESTful API and how complex queries can be created and processed using efficient data structures we created for storing the data in structured way. Finally, we will conclude with an example of movie recommendation system built on top of this query engine.
Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits
Venue: arXiv cs.DC 2017
Year: 2017

Patrolling consists of scheduling perpetual movements of a collection of mobile robots, so that each point of the environment is regularly revisited by any robot in the collection. In previous research, it was assumed that all points of the environment needed to be revisited with the same minimal frequency. In this paper we study efficient patrolling protocols for points located on a path, where each point may have a different constraint on frequency of visits. The problem of visiting such divergent points was recently posed by Gasieniec et al. in [13], where the authors study protocols using a single robot patrolling a set of $n$ points located in nodes of a complete graph and in Euclidean spaces. The focus in this paper is on patrolling with two robots. We adopt a scenario in which all points to be patrolled are located on a line. We provide several approximation algorithms concluding with the best currently known $\sqrt 3$-approximation.
Margin Sample Mining Loss: A Deep Learning Based Method for Person Re-identification
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification (ReID) is an important task in computer vision. Recently, deep learning with a metric learning loss has become a common framework for ReID. In this paper, we also propose a new metric learning loss with hard sample mining called margin smaple mining loss (MSML) which can achieve better accuracy compared with other metric learning losses, such as triplet loss. In experi- ments, our proposed methods outperforms most of the state-of-the-art algorithms on Market1501, MARS, CUHK03 and CUHK-SYSU.
Design and Performance Analysis of Dual and Multi-hop Diffusive Molecular Communication Systems
Venue: arXiv cs.IT 2017
Year: 2017

This work presents a comprehensive performance analysis of diffusion based direct, dual-hop, and multi-hop molecular communication systems with Brownian motion and drift in the presence of various distortions such as inter-symbol interference (ISI), multi-source interference (MSI), and counting errors. Optimal decision rules are derived employing the likelihood ratio tests (LRTs) for symbol detection at each of the cooperative as well as the destination nanomachines. Further, closed-form expressions are also derived for the probabilities of detection, false alarm at the individual cooperative, destination nanomachines, as well as the overall end-to-end probability of error for source-destination communication. The results also characterize the impact of detection performance of the intermediate cooperative nanomachine(s) on the end-to-end performance of dual/multi hop diffusive molecular communication systems. In addition, capacity expressions are also derived for direct, dual-hop, and multi-hop molecular communication scenarios. Simulation results are presented to corroborate the theoretical results derived and also, to yield insights into system performance.
Adaptive Smoothing in fMRI Data Processing Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Functional Magnetic Resonance Imaging (fMRI) relies on multi-step data processing pipelines to accurately determine brain activity; among them, the crucial step of spatial smoothing. These pipelines are commonly suboptimal, given the local optimisation strategy they use, treating each step in isolation. With the advent of new tools for deep learning, recent work has proposed to turn these pipelines into end-to-end learning networks. This change of paradigm offers new avenues to improvement as it allows for a global optimisation. The current work aims at benefitting from this paradigm shift by defining a smoothing step as a layer in these networks able to adaptively modulate the degree of smoothing required by each brain volume to better accomplish a given data analysis task. The viability is evaluated on real fMRI data where subjects did alternate between left and right finger tapping tasks.
Motif Iteration Model for Network Representation
Venue: arXiv cs.SI 2017
Year: 2017

Social media mining has become one of the most popular research areas in Big Data with the explosion of social networking information from Facebook, Twitter, LinkedIn, Weibo and so on. Understanding and representing the structure of a social network is a key in social media mining. In this paper, we propose the Motif Iteration Model (MIM) to represent the structure of a social network. As the name suggested, the new model is based on iteration of basic network motifs. In order to better show the properties of the model, a heuristic and greedy algorithm called Vertex Reordering and Arranging (VRA) is proposed by studying the adjacency matrix of the three-vertex undirected network motifs. The algorithm is for mapping from the adjacency matrix of a network to a binary image, it shows a new perspective of network structure visualization. In summary, this model provides a useful approach towards building link between images and networks and offers a new way of representing the structure of a social network.
Low Complexity Modem Structure for OFDM-based Orthogonal Time Frequency Space Modulation
Venue: arXiv cs.IT 2017
Year: 2017

Orthogonal time frequency space (OTFS) modulation is a two-dimensional signaling technique that has recently emerged in the literature to tackle the time-varying (TV) wireless channels. OTFS deploys the Doppler-delay plane to multiplex the transmit data where the time variations of the TV channel are integrated over time and hence the equivalent channel relating the input and output of the system boils down to a time-invariant one. This signaling technique can be implemented on the top of a given multicarrier waveform with the addition of precoding and post-processing units to the modulator and demodulator. In this paper, we present discrete-time formulation of an OFDM-based OTFS system. We argue against deployment of window functions at the OTFS transmitter in realistic scenarios and thus limit any sort of windowing to the receiver side. We study the channel impact in discrete-time providing deeper insights into OTFS systems. Moreover, our derivations lead to simplified modulator and demodulator structures that are far simpler than those in the literature.
Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots
Venue: arXiv cs.DS 2017
Year: 2017

A graph environment must be explored by a collection of mobile robots. Some of the robots, a priori unknown, may turn out to be unreliable. The graph is weighted and each node is assigned a deadline. The exploration is successful if each node of the graph is visited before its deadline by a reliable robot. The edge weight corresponds to the time needed by a robot to traverse the edge. Given the number of robots which may crash, is it possible to design an algorithm, which will always guarantee the exploration, independently of the choice of the subset of unreliable robots by the adversary? We find the optimal time, during which the graph may be explored. Our approach permits to find the maximal number of robots, which may turn out to be unreliable, and the graph is still guaranteed to be explored. We concentrate on line graphs and rings, for which we give positive results. We start with the case of the collections involving only reliable robots. We give algorithms finding optimal times needed for exploration when the robots are assigned to fixed initial positions as well as when such starting positions may be determined by the algorithm. We extend our consideration to the case when some number of robots may be unreliable. Our most surprising result is that solving the line exploration problem with robots at given positions, which may involve crash-faulty ones, is NP-hard. The same problem has polynomial solutions for a ring and for the case when the initial robots' positions on the line are arbitrary. The exploration problem is shown to be NP-hard for star graphs, even when the team consists of only two reliable robots.
Minimal Dependency Translation: a Framework for Computer-Assisted Translation for Under-Resourced Languages
Venue: arXiv cs.CL 2017
Year: 2017

This paper introduces Minimal Dependency Translation (MDT), an ongoing project to develop a rule-based framework for the creation of rudimentary bilingual lexicon-grammars for machine translation and computer-assisted translation into and out of under-resourced languages as well as initial steps towards an implementation of MDT for English-to-Amharic translation. The basic units in MDT, called groups, are headed multi-item sequences. In addition to wordforms, groups may contain lexemes, syntactic-semantic categories, and grammatical features. Each group is associated with one or more translations, each of which is a group in a target language. During translation, constraint satisfaction is used to select a set of source-language groups for the input sentence and to sequence the words in the associated target-language groups.
Large-Scale Location-Aware Services in Access: Hierarchical Building/Floor Classification and Location Estimation using Wi-Fi Fingerprinting Based on Deep Neural Networks
Venue: arXiv cs.NI 2017
Year: 2017

One of key technologies for future large-scale location-aware services in access is a scalable indoor localization technique. In this paper, we report preliminary results from our investigation on the use of deep neural networks (DNNs) for hierarchical building/floor classification and floor-level location estimation based on Wi-Fi fingerprinting, which we carried out as part of a feasibility study project on Xi'an Jiaotong-Liverpool University (XJTLU) Campus Information and Visitor Service System. To take into account the hierarchical nature of the building/floor classification problem, we propose a new DNN architecture based on a stacked autoencoder for the reduction of feature space dimension and a feed-forward classifier for multi-label classification with argmax functions to convert multi-label classification results into multi-class classification ones. We also describe the demonstration of a prototype DNN-based indoor localization system for floor-level location estimation using real received signal strength (RSS) data collected at one of the buildings on the XJTLU campus. The preliminary results for both building/floor classification and floor-level location estimation clearly show the strengths of DNN-based approaches, which can provide near state-of-the-art performance with less parameter tuning and higher scalability.
Joint Person Re-identification and Camera Network Topology Inference in Multiple Cameras
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification is the task of recognizing or identifying a person across multiple views in multi-camera networks. Although there has been much progress in person re-identification, person re-identification in large-scale multi-camera networks still remains a challenging task because of the large spatio-temporal uncertainty and high complexity due to a large number of cameras and people. To handle these difficulties, additional information such as camera network topology should be provided, which is also difficult to automatically estimate, unfortunately. In this study, we propose a unified framework which jointly solves both person re-identification and camera network topology inference problems with minimal prior knowledge about the environments. The proposed framework takes general multi-camera network environments into account and can be applied to online person re-identification in large-scale multi-camera networks. In addition, to effectively show the superiority of the proposed framework, we provide a new person re-identification dataset with full annotations, named SLP, captured in the multi-camera network consisting of nine non-overlapping cameras. Experimental results using our person re-identification and public datasets show that the proposed methods are promising for both person re-identification and camera topology inference tasks.
An Iterative and Toolchain-Based Approach to Automate Scanning and Mapping Computer Networks
Venue: arXiv cs.CR 2017
Year: 2017

As today's organizational computer networks are ever evolving and becoming more and more complex, finding potential vulnerabilities and conducting security audits has become a crucial element in securing these networks. The first step in auditing a network is reconnaissance by mapping it to get a comprehensive overview over its structure. The growing complexity, however, makes this task increasingly effortful, even more as mapping (instead of plain scanning), presently, still involves a lot of manual work. Therefore, the concept proposed in this paper automates the scanning and mapping of unknown and non-cooperative computer networks in order to find security weaknesses or verify access controls. It further helps to conduct audits by allowing comparing documented with actual networks and finding unauthorized network devices, as well as evaluating access control methods by conducting delta scans. It uses a novel approach of augmenting data from iteratively chained existing scanning tools with context, using genuine analytics modules to allow assessing a network's topology instead of just generating a list of scanned devices. It further contains a visualization model that provides a clear, lucid topology map and a special graph for comparative analysis. The goal is to provide maximum insight with a minimum of a priori knowledge.