OpenRaiser/Intern-Atlas huggingface dataset:
Access Time Tradeoffs in Archive Compression
Venue: arXiv cs.IT 2016
Year: 2016

Web archives, query and proxy logs, and so on, can all be very large and highly repetitive; and are accessed only sporadically and partially, rather than continually and holistically. This type of data is ideal for compression-based archiving, provided that random-access to small fragments of the original data can be achieved without needing to decompress everything. The recent RLZ (relative Lempel Ziv) compression approach uses a semi-static model extracted from the text to be compressed, together with a greedy factorization of the whole text encoded using static integer codes. Here we demonstrate more precisely than before the scenarios in which RLZ excels. We contrast RLZ with alternatives based on block-based adaptive methods, including approaches that "prime" the encoding for each block, and measure a range of implementation options using both hard-disk (HDD) and solid-state disk (SSD) drives. For HDD, the dominant factor affecting access speed is the compression rate achieved, even when this involves larger dictionaries and larger blocks. When the data is on SSD the same effects are present, but not as markedly, and more complex trade-offs apply.
Full-Duplex Cloud-RAN with Uplink/Downlink Remote Radio Head Association
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a cloud radio access network (C-RAN) where spatially distributed remote radio heads (RRHs) communicate with a full-duplex user. In order to reflect a realistic scenario, the uplink (UL) and downlink (DL) RRHs are assumed to be equipped with multiple antennas and distributed according to a Poisson point process. We consider all participate and nearest RRH association schemes with distributed beamforming in the form of maximum ratio combining/maximal ratio transmission (MRC/MRT) and zero-forcing/MRT(ZF/MRT) processing. We derive analytical expressions useful to compare the average sum rate among association schemes as a function of the number of RRHs antennas and density of the UL and DL RRHs. Numerical results show that significant performance improvements can be achieved by using the full-duplex mode as compared to the half-duplex mode, while the choice of the beamforming design as well as the RRH association scheme plays a critical role in determining the full-duplex gains.
QoS-Aware Joint Mode Selection and Channel Assignment for D2D Communications
Venue: arXiv cs.IT 2016
Year: 2016

Underlaying device-to-device (D2D) communications to a cellular network is considered as a key technique to improve spectral efficiency in 5G networks. For such D2D systems, mode selection and resource allocation have been widely utilized for managing interference. However, previous works allowed at most one D2D link to access the same channel, while mode selection and resource allocation are typically separately designed. In this paper, we jointly optimize the mode selection and channel assignment in a cellular network with underlaying D2D communications, where multiple D2D links may share the same channel. Meanwhile, the QoS requirements for both cellular and D2D links are guaranteed, in terms of Signal-to-Interference-plus-Noise Ratio (SINR). We first propose an optimal dynamic programming (DP) algorithm, which provides a much lower computation complexity compared to exhaustive search and serves as the performance bench mark. A bipartite graph based greedy algorithm is then proposed to achieve a polynomial time complexity. Simulation results will demonstrate the advantage of allowing each channel to be accessed by multiple D2D links in dense D2D networks, as well as, the effectiveness of the proposed algorithms.
A hierarchy of local decision
Venue: arXiv cs.DC 2016
Year: 2016

We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with $O(\log n)$-bit certificates in $n$-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires $Ω(\log^2 n)$-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires $Ω(n^2)$ bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with $O(\log n)$-bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs.
FALDOI: A new minimization strategy for large displacement variational optical flow
Venue: arXiv cs.CV 2016
Year: 2016

We propose a large displacement optical flow method that introduces a new strategy to compute a good local minimum of any optical flow energy functional. The method requires a given set of discrete matches, which can be extremely sparse, and an energy functional which locally guides the interpolation from those matches. In particular, the matches are used to guide a structured coordinate-descent of the energy functional around these keypoints. It results in a two-step minimization method at the finest scale which is very robust to the inevitable outliers of the sparse matcher and able to capture large displacements of small objects. Its benefits over other variational methods that also rely on a set of sparse matches are its robustness against very few matches, high levels of noise and outliers. We validate our proposal using several optical flow variational models. The results consistently outperform the coarse-to-fine approaches and achieve good qualitative and quantitative performance on the standard optical flow benchmarks.
Modeling the Infectiousness of Twitter Hashtags
Venue: arXiv cs.SI 2016
Year: 2016

This study applies dynamical and statistical modeling techniques to quantify the proliferation and popularity of trending hashtags on Twitter. Using time-series data reflecting actual tweets in New York City and San Francisco, we present estimates for the dynamics (i.e., rates of infection and recovery) of several hundred trending hashtags using an epidemic modeling framework coupled with Bayesian Markov Chain Monte Carlo (MCMC) methods. This methodological strategy is an extension of techniques traditionally used to model the spread of infectious disease. We demonstrate that in some models, hashtags can be grouped by infectiousness, possibly providing a method for quantifying the trendiness of a topic.
Asymptotic Analysis of Random Lattices in High Dimensions
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents the asymptotic analysis of random lattices in high dimensions to clarify the distance properties of the considered lattices. These properties not only indicate the asymptotic value for the distance between any pair of lattice points in high-dimension random lattices, but also describe the convergence behavior of how the asymptotic value approaches the exact distance. The asymptotic analysis further prompts new insights into the asymptotic behavior of sphere-decoding complexity and the pairwise error probability (PEP) with maximum-likelihood (ML) detector for a large number of antennas.
Phase-only signal reconstruction by MagnitudeCut
Venue: arXiv cs.NA 2016
Year: 2016

In this paper, we present a new algorithm, called MagnitudeCut, for recovering a signal from the phase of its Fourier transform. We casted our recovering problem into a new convex optimization problem, and then solved it by the block coordinate descent algorithm and the interior point algorithm, in which the iteration process consists of matrix vector product and inner product. We used the new method for reconstruction of a set of signal/image. The simulation results reveal that the proposed MagnitudeCut method can reconstruct the original signal with fewer sampling number of the phase information than that of the Greedy algorithm and iterative method under the same reconstruction error. Moreover, our algorithm can also reconstruct the symmetric image from its Fourier phase.
Quantifying the vanishing gradient and long distance dependency problem in recursive neural networks and recursive LSTMs
Venue: arXiv cs.AI 2016
Year: 2016

Recursive neural networks (RNN) and their recently proposed extension recursive long short term memory networks (RLSTM) are models that compute representations for sentences, by recursively combining word embeddings according to an externally provided parse tree. Both models thus, unlike recurrent networks, explicitly make use of the hierarchical structure of a sentence. In this paper, we demonstrate that RNNs nevertheless suffer from the vanishing gradient and long distance dependency problem, and that RLSTMs greatly improve over RNN's on these problems. We present an artificial learning task that allows us to quantify the severity of these problems for both models. We further show that a ratio of gradients (at the root node and a focal leaf node) is highly indicative of the success of backpropagation at optimizing the relevant weights low in the tree. This paper thus provides an explanation for existing, superior results of RLSTMs on tasks such as sentiment analysis, and suggests that the benefits of including hierarchical structure and of including LSTM-style gating are complementary.
Keypoint Density-based Region Proposal for Fine-Grained Object Detection and Classification using Regions with Convolutional Neural Network Features
Venue: arXiv cs.CV 2016
Year: 2016

Although recent advances in regional Convolutional Neural Networks (CNNs) enable them to outperform conventional techniques on standard object detection and classification tasks, their response time is still slow for real-time performance. To address this issue, we propose a method for region proposal as an alternative to selective search, which is used in current state-of-the art object detection algorithms. We evaluate our Keypoint Density-based Region Proposal (KDRP) approach and show that it speeds up detection and classification on fine-grained tasks by 100% versus the existing selective search region proposal technique without compromising classification accuracy. KDRP makes the application of CNNs to real-time detection and classification feasible.
US-Cut: Interactive Algorithm for rapid Detection and Segmentation of Liver Tumors in Ultrasound Acquisitions
Venue: arXiv cs.CV 2016
Year: 2016

Ultrasound (US) is the most commonly used liver imaging modality worldwide. It plays an important role in follow-up of cancer patients with liver metastases. We present an interactive segmentation approach for liver tumors in US acquisitions. Due to the low image quality and the low contrast between the tumors and the surrounding tissue in US images, the segmentation is very challenging. Thus, the clinical practice still relies on manual measurement and outlining of the tumors in the US images. We target this problem by applying an interactive segmentation algorithm to the US data, allowing the user to get real-time feedback of the segmentation results. The algorithm has been developed and tested hand-in-hand by physicians and computer scientists to make sure a future practical usage in a clinical setting is feasible. To cover typical acquisitions from the clinical routine, the approach has been evaluated with dozens of datasets where the tumors are hyperechoic (brighter), hypoechoic (darker) or isoechoic (similar) in comparison to the surrounding liver tissue. Due to the interactive real-time behavior of the approach, it was possible even in difficult cases to find satisfying segmentations of the tumors within seconds and without parameter settings, and the average tumor deviation was only 1.4mm compared with manual measurements. However, the long term goal is to ease the volumetric acquisition of liver tumors in order to evaluate for treatment response. Additional aim is the registration of intraoperative US images via the interactive segmentations to the patient's pre-interventional CT acquisitions.
Hierarchical Role-Based Access Control with Homomorphic Encryption for Database as a Service
Venue: arXiv cs.CR 2016
Year: 2016

Database as a service provides services for accessing and managing customers data which provides ease of access, and the cost is less for these services. There is a possibility that the DBaaS service provider may not be trusted, and data may be stored on untrusted server. The access control mechanism can restrict users from unauthorized access, but in cloud environment access control policies are more flexible. However, an attacker can gather sensitive information for a malicious purpose by abusing the privileges as another user and so database security is compromised. The other problems associated with the DBaaS are to manage role hierarchy and secure session management for query transaction in the database. In this paper, a role-based access control for the multitenant database with role hierarchy is proposed. The query is granted with least access privileges, and a session key is used for session management. The proposed work protects data from privilege escalation and SQL injection. It uses the partial homomorphic encryption (Paillier Encryption) for the encrypting the sensitive data. If a query is to perform any operation on sensitive data, then extra permissions are required for accessing sensitive data. Data confidentiality and integrity are achieved using the role-based access control with partial homomorphic encryption.
Generalized Analysis of Convergence of Absolute Trust in Peer to Peer Networks
Venue: arXiv cs.NI 2016
Year: 2016

Open and anonymous nature of peer to peer networks provides an opportunity to malicious peers to behave unpredictably in the network. This leads the lack of trust among the peers. To control the behavior of peers in the network, reputation system can be used. In a reputation system, aggregation of trust is a primary issue. Algorithm for aggregation of trust should be designed such that, it can converge to a certain finite value. Absolute Trust is one of the algorithm, which is used for the aggregation of trust in peer to peer networks. In this letter, we present the generalized analysis of convergence of the Absolute Trust algorithm.
Porting Code Across Simple Mobile Robots
Venue: arXiv cs.RO 2016
Year: 2016

The StarL programming framework aims to simplify development of distributed robotic applications by providing easy-to-use language constructs for communication and control. It has been used to develop applications such as formation control, distributed tracking, and collaborative search. In this paper, we present a complete redesign of the StarL language and its runtime system which enables us to achieve portability of robot programs across platforms. Thus, the same application program, say, for distributed tracking, can now be compiled and deployed on multiple, heterogeneous robotic platforms. Towards portability, this we first define the semantics of StarL programs in a way that is largely platform independent, except for a few key platform-dependent parameters that capture the worst-case execution and sensing delays and resolution of sensors. Next, we present a design of the StarL runtime system, including a robot controller, that meets the above semantics. The controller consists of a platform-independent path planner implemented using RRTs and a platform-dependent way-point tracker that is implemented using the control commands available for the platform. We demonstrate portability of StarL applications using simulation results for two different robotic platforms, and several applications.
Are you Charlie or Ahmed? Cultural pluralism in Charlie Hebdo response on Twitter
Venue: arXiv cs.CY 2016
Year: 2016

We study the response to the Charlie Hebdo shootings of January 7, 2015 on Twitter across the globe. We ask whether the stances on the issue of freedom of speech can be modeled using established sociological theories, including Huntington's culturalist Clash of Civilizations, and those taking into consideration social context, including Density and Interdependence theories. We find support for Huntington's culturalist explanation, in that the established traditions and norms of one's "civilization" predetermine some of one's opinion. However, at an individual level, we also find social context to play a significant role, with non-Arabs living in Arab countries using #JeSuisAhmed ("I am Ahmed") five times more often when they are embedded in a mixed Arab/non-Arab (mention) network. Among Arabs living in the West, we find a great variety of responses, not altogether associated with the size of their expatriate community, suggesting other variables to be at play.
Model-Based Testing, Using Belief-Desire-Intentions Agents, of Control Code for Robots in Collaborative Human-Robot Interactions
Venue: arXiv cs.RO 2016
Year: 2016

The software of robotic assistants needs to be verified, to ensure its safety and functional correctness. Testing in simulation allows a high degree of realism in the verification. However, generating tests that cover both interesting foreseen and unforeseen scenarios in human-robot interaction (HRI) tasks, while executing most of the code, remains a challenge. We propose the use of belief-desire-intention (BDI) agents in the test environment, to increase the level of realism and human-like stimulation of simulated robots. Artificial intelligence, such as agent theory, can be exploited for more intelligent test generation. An automated testbench was implemented for a simulation in Robot Operating System (ROS) and Gazebo, of a cooperative table assembly task between a humanoid robot and a person. Requirements were verified for this task, and some unexpected design issues were discovered, leading to possible code improvements. Our results highlight the practicality of BDI agents to automatically generate valid and human-like tests to get high code coverage, compared to hand-written directed tests, pseudorandom generation, and other variants of model-based test generation. Also, BDI agents allow the coverage of combined behaviours of the HRI system with more ease than writing temporal logic properties for model checking.
Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
Venue: arXiv cs.LO 2016
Year: 2016

Designing query languages for graph structured data is an active field of research, where expressiveness and efficient algorithms for query evaluation are conflicting goals. To better handle dynamically changing data, recent work has been done on designing query languages that can compare values stored in the graph database, without hard coding the values in the query. The main idea is to allow variables in the query and bind the variables to values when evaluating the query. For query languages that bind variables only once, query evaluation is usually NP-complete. There are query languages that allow binding inside the scope of Kleene star operators, which can themselves be in the scope of bindings and so on. Uncontrolled nesting of binding and iteration within one another results in query evaluation being PSPACE-complete. We define a way to syntactically control the nesting depth of iterated bindings, and study how this affects expressiveness and efficiency of query evaluation. The result is an infinite, syntactically defined hierarchy of expressions. We prove that the corresponding language hierarchy is strict. Given an expression in the hierarchy, we prove that it is undecidable to check if there is a language equivalent expression at lower levels. We prove that evaluating a query based on an expression at level i can be done in $Σ_i$ in the polynomial time hierarchy. Satisfiability of quantified Boolean formulas can be reduced to query evaluation; we study the relationship between alternations in Boolean quantifiers and the depth of nesting of iterated bindings.
Unsupervised Watertight Mesh Generation for Physics Simulation Applications Using Growing Neural Gas on Noisy Free-Form Object Models
Venue: arXiv cs.RO 2016
Year: 2016

We present a framework to generate watertight mesh representations in an unsupervised manner from noisy point clouds of complex, heterogeneous objects with free-form surfaces. The resulting meshes are ready to use in applications like kinematics and dynamics simulation where watertightness and fast processing are the main quality criteria. This works with no necessity of user interaction, mainly by utilizing a modified Growing Neural Gas technique for surface reconstruction combined with several post-processing steps. In contrast to existing methods, the proposed framework is able to cope with input point clouds generated by consumer-grade RGBD sensors and works even if the input data features large holes, e.g. a missing bottom which was not covered by the sensor. Additionally, we explain a method to unsupervisedly optimize the parameters of our framework in order to improve generalization quality and, at the same time, keep the resulting meshes as coherent as possible to the original object regarding visual and geometric properties.
A Security Analysis and Revised Security Extension for the Precision Time Protocol
Venue: arXiv cs.CR 2016
Year: 2016

The Precision Time Protocol (PTP) aims to provide highly accurate and synchronised clocks. Its defining standard, IEEE 1588, has a security section ("Annex K") which relies on symmetric-key secrecy. In this paper we present a detailed threat analysis of the PTP standard, in which we highlight the security properties that should be addressed by any security extension. During this analysis we identify a sequence of new attacks and non-cryptographic network-based defenses that mitigate them. We then suggest to replace Annex K's symmetric cryptography by an efficient elliptic-curve Public-Key signatures. We implemented all our attacks to demonstrate their effectiveness, and also implemented and evaluated both the network and cryptographic defenses. Our results show that the proposed schemes are extremely practical, and much more secure than previous suggestions.
LevelMerge: Collaborative Game Level Editing by Merging Labeled Graphs
Venue: arXiv cs.GR 2016
Year: 2016

Game level editing is the process of constructing a full game level starting from 3D asset libraries, e.g. 3d models, textures, shaders, scripts. In level editing, designers define the look and behavior of the whole level by placing objects, assigning materials and lighting parameters, setting animations and physics properties and customizing the objects AI and behavior by editing scripts. The heterogeneity of the task usually translates to a workflow where a team of people, experts on separate aspects, cooperate to edit the game level, often working on the same objects (e.g.: a programmer working on the AI of a character, while an artist works on its 3D model or its materials). Today this collaboration is established by using version control systems designed for text documents, such as Git, to manage different versions and share them amongst users. The merge algorithms used in these systems though does not perform well in our case since it does not respect the relations between game objects necessary to maintain the semantic of the game level behavior and look. This is a known problem and commercial systems for game level merging exists, e.g. PlasticSCM, but these are only slightly more robust than text-based ones. This causes designers to often merge scenes manually, essentially reapplying others edits in the game level editor.