OpenRaiser/Intern-Atlas huggingface dataset:
Worst-Case Optimal Algorithms for Parallel Query Processing
Venue: arXiv cs.DB 2016
Year: 2016

In this paper, we study the communication complexity for the problem of computing a conjunctive query on a large database in a parallel setting with $p$ servers. In contrast to previous work, where upper and lower bounds on the communication were specified for particular structures of data (either data without skew, or data with specific types of skew), in this work we focus on worst-case analysis of the communication cost. The goal is to find worst-case optimal parallel algorithms, similar to the work of [18] for sequential algorithms. We first show that for a single round we can obtain an optimal worst-case algorithm. The optimal load for a conjunctive query $q$ when all relations have size equal to $M$ is $O(M/p^{1/ψ^*})$, where $ψ^*$ is a new query-related quantity called the edge quasi-packing number, which is different from both the edge packing number and edge cover number of the query hypergraph. For multiple rounds, we present algorithms that are optimal for several classes of queries. Finally, we show a surprising connection to the external memory model, which allows us to translate parallel algorithms to external memory algorithms. This technique allows us to recover (within a polylogarithmic factor) several recent results on the I/O complexity for computing join queries, and also obtain optimal algorithms for other classes of queries.
A CNN Based Scene Chinese Text Recognition Algorithm With Synthetic Data Engine
Venue: arXiv cs.CV 2016
Year: 2016

Scene text recognition plays an important role in many computer vision applications. The small size of available public available scene text datasets is the main challenge when training a text recognition CNN model. In this paper, we propose a CNN based Chinese text recognition algorithm. To enlarge the dataset for training the CNN model, we design a synthetic data engine for Chinese scene character generation, which generates representative character images according to the fonts use frequency of Chinese texts. As the Chinese text is more complex, the English text recognition CNN architecture is modified for Chinese text. To ensure the small size nature character dataset and the large size artificial character dataset are comparable in training, the CNN model are trained progressively. The proposed Chinese text recognition algorithm is evaluated with two Chinese text datasets. The algorithm achieves better recognize accuracy compared to the baseline methods.
Improved Transients in Multiple Frequencies Estimation via Dynamic Regressor Extension and Mixing
Venue: arXiv cs.SY 2016
Year: 2016

A problem of performance enhancement for multiple frequencies estimation is studied. First, we consider a basic gradient-based estimation approach with global exponential convergence. Next, we apply dynamic regressor extension and mixing technique to improve transient performance of the basic approach and ensure non-strict monotonicity of estimation errors. Simulation results illustrate benefits of the proposed solution.
Trajectory Aligned Features For First Person Action Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Egocentric videos are characterised by their ability to have the first person view. With the popularity of Google Glass and GoPro, use of egocentric videos is on the rise. Recognizing action of the wearer from egocentric videos is an important problem. Unstructured movement of the camera due to natural head motion of the wearer causes sharp changes in the visual field of the egocentric camera causing many standard third person action recognition techniques to perform poorly on such videos. Objects present in the scene and hand gestures of the wearer are the most important cues for first person action recognition but are difficult to segment and recognize in an egocentric video. We propose a novel representation of the first person actions derived from feature trajectories. The features are simple to compute using standard point tracking and does not assume segmentation of hand/objects or recognizing object or hand pose unlike in many previous approaches. We train a bag of words classifier with the proposed features and report a performance improvement of more than 11% on publicly available datasets. Although not designed for the particular case, we show that our technique can also recognize wearer's actions when hands or objects are not visible.
On Stochastic Belief Revision and Update and their Combination
Venue: arXiv cs.AI 2016
Year: 2016

I propose a framework for an agent to change its probabilistic beliefs when a new piece of propositional information $α$ is observed. Traditionally, belief change occurs by either a revision process or by an update process, depending on whether the agent is informed with $α$ in a static world or, respectively, whether $α$ is a 'signal' from the environment due to an event occurring. Boutilier suggested a unified model of qualitative belief change, which "combines aspects of revision and update, providing a more realistic characterization of belief change." In this paper, I propose a unified model of quantitative belief change, where an agent's beliefs are represented as a probability distribution over possible worlds. As does Boutilier, I take a dynamical systems perspective. The proposed approach is evaluated against several rationality postulated, and some properties of the approach are worked out.
Cryptompress: A Symmetric Cryptography algorithm to deny Bruteforce Attack
Venue: arXiv cs.CR 2016
Year: 2016

Cryptompress, a new 128-bit (initial) private-key cryptography algorithm is proposed. It uses a block size of at least 30 bits and increments prior key size to additional 32 bits on each unsuccessful attempt of any means, including bruteforcing, further changing a specific portion of the cyphertext using the reformed Feistel network. Encryption process results from a proposed compression sequence developed using lookup table and shift operations followed by key generation. Eventually, four matrixes named add-sub matrix, reduced matrix, sequence matrix and term matrix are obtained which ultimately forms a cyphertext.
SensIs - Underwater acoustic network for ice-monitoring
Venue: arXiv cs.NI 2016
Year: 2016

Routing for low latency underwater acoustic network-communication is investigated. The application is monitoring of ice-threats to offshore operations in the Arctic - to provide warnings that enable operators to react to such threats. The scenario produces relatively high traffic load, and the network should favour low delay and adequate reliability rather than energy usage minimization. The ICRP (Information-Carrying based Routing Protocol), originally proposed by Wei Liang et al. in 2007, is chosen as basis. ICRP obtains unicast routing paths by sending data payload as broadcast packets when no route information is available. Thus, data can be delivered without the cost of reactive signalling latency. In this paper we explore the capabilities of a slightly enhanced/adapted ICRP, tailored to the ice monitoring application. By simulations and experiments at sea it is demonstrated that the protocol performs well and can manage the applications high traffic load - this provided that the point-to-point links provide sufficient bit rates and capacity headroom.
Decidability of the Membership Problem for $2\times 2$ integer matrices
Venue: arXiv cs.DM 2016
Year: 2016

The main result of this paper is the decidability of the membership problem for $2\times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2\times 2$ integer matrices $M_1,\dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by $\{M_1,\dots,M_n\}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $\mathrm{GL}(2,\mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
Predicting the evolution of complex networks via local information
Venue: arXiv cs.SI 2016
Year: 2016

Almost all real-world networks are subject to constant evolution, and plenty of evolving networks have been investigated to uncover the underlying mechanisms for a deeper understanding of the organization and development of them. Compared with the rapid expansion of the empirical studies about evolution mechanisms exploration, the future links prediction methods corresponding to the evolution mechanisms are deficient. Real-world information always contain hints of what would happen next, which is also the case in the observed evolving networks. In this paper, we firstly propose a structured-dependent index to strengthen the robustness of link prediction methods. Then we treat the observed links and their timestamps in evolving networks as known information. We envision evolving networks as dynamic systems and model the evolutionary dynamics of nodes similarity. Based on the iterative updating of nodes' network position, the potential trend of evolving networks is uncovered, which improves the accuracy of future links prediction. Experiments on various real-world networks show that the proposed index performs better than baseline methods and the spatial-temporal position drift model performs well in real-world evolving networks.
Efficient Summing over Sliding Windows
Venue: arXiv cs.DS 2016
Year: 2016

This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of Ω(1/ε + log W) memory bits for Wε-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/ε + log W) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0,1,...,R}, is addressed. The paper shows that approximating the sum within an additive error of RWε can also be done using Θ(1/ε + log W) bits for ε=Ω(1/W). For ε=o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B=Θ(Wlog(1/Wε)) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time.
Refinement Types for TypeScript
Venue: arXiv cs.PL 2016
Year: 2016

We present Refined TypeScript (RSC), a lightweight refinement type system for TypeScript, that enables static verification of higher-order, imperative programs. We develop a formal core of RSC that delineates the interaction between refinement types and mutability. Next, we extend the core to account for the imperative and dynamic features of TypeScript. Finally, we evaluate RSC on a set of real world benchmarks, including parts of the Octane benchmarks, D3, Transducers, and the TypeScript compiler.
Word embeddings and recurrent neural networks based on Long-Short Term Memory nodes in supervised biomedical word sense disambiguation
Venue: arXiv cs.CL 2016
Year: 2016

Word sense disambiguation helps identifying the proper sense of ambiguous words in text. With large terminologies such as the UMLS Metathesaurus ambiguities appear and highly effective disambiguation methods are required. Supervised learning algorithm methods are used as one of the approaches to perform disambiguation. Features extracted from the context of an ambiguous word are used to identify the proper sense of such a word. The type of features have an impact on machine learning methods, thus affect disambiguation performance. In this work, we have evaluated several types of features derived from the context of the ambiguous word and we have explored as well more global features derived from MEDLINE using word embeddings. Results show that word embeddings improve the performance of more traditional features and allow as well using recurrent neural network classifiers based on Long-Short Term Memory (LSTM) nodes. The combination of unigrams and word embeddings with an SVM sets a new state of the art performance with a macro accuracy of 95.97 in the MSH WSD data set.
Fusing Audio, Textual and Visual Features for Sentiment Analysis of News Videos
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a novel approach to perform sentiment analysis of news videos, based on the fusion of audio, textual and visual clues extracted from their contents. The proposed approach aims at contributing to the semiodiscoursive study regarding the construction of the ethos (identity) of this media universe, which has become a central part of the modern-day lives of millions of people. To achieve this goal, we apply state-of-the-art computational methods for (1) automatic emotion recognition from facial expressions, (2) extraction of modulations in the participants' speeches and (3) sentiment analysis from the closed caption associated to the videos of interest. More specifically, we compute features, such as, visual intensities of recognized emotions, field sizes of participants, voicing probability, sound loudness, speech fundamental frequencies and the sentiment scores (polarities) from text sentences in the closed caption. Experimental results with a dataset containing 520 annotated news videos from three Brazilian and one American popular TV newscasts show that our approach achieves an accuracy of up to 84% in the sentiments (tension levels) classification task, thus demonstrating its high potential to be used by media analysts in several applications, especially, in the journalistic domain.
Sub-Nyquist Cyclostationary Detection for Cognitive Radio
Venue: arXiv cs.IT 2016
Year: 2016

Cognitive Radio requires efficient and reliable spectrum sensing of wideband signals. In order to cope with the sampling rate bottleneck, new sampling methods have been proposed that sample below the Nyquist rate. However, such techniques decrease the signal to noise ratio (SNR), deteriorating the performance of subsequent energy detection. Cyclostationary detection, which exploits the periodic property of communication signal statistics, absent in stationary noise, is a natural candidate for this setting. In this work, we consider cyclic spectrum recovery from sub-Nyquist samples, in order to achieve both efficiency and robustness to noise. To that end, we propose a structured compressed sensing algorithm, that extends orthogonal matching pursuit to account for the structure imposed by cyclostationarity. Next, we derive a lower bound on the sampling rate required for perfect cyclic spectrum recovery in the presence of stationary noise and show that it can be reconstructed from samples obtained below Nyquist, without any sparsity constraints on the signal. In particular, in non sparse settings, the cyclic spectrum can be recovered at $4/5$ of the Nyquist rate. If the signal of interest is sparse, then the sampling rate may be further reduced to $8/5$ of the Landau rate. Once the cyclic spectrum is recovered, we estimate the number of transmissions that compose the input signal, along with their carrier frequencies and bandwidths. Simulations show that cyclostationary detection outperforms energy detection in low SNRs in the sub-Nyquist regime. This was already known in the Nyquist regime, but is even more pronounced at sub-Nyquist sampling rates.
Energy Efficiency Optimization of 5G Radio Frequency Chain Systems
Venue: arXiv cs.NI 2016
Year: 2016

With the massive multi-input multi-output (MIMO) antennas technology adopted for the fifth generation (5G) wireless communication systems, a large number of radio frequency (RF) chains have to be employed for RF circuits. However, a large number of RF chains not only increase the cost of RF circuits but also consume additional energy in 5G wireless communication systems. In this paper we investigate energy and cost efficiency optimization solutions for 5G wireless communication systems with a large number of antennas and RF chains. An energy efficiency optimization problem is formulated for 5G wireless communication systems using massive MIMO antennas and millimeter wave technology. Considering the nonconcave feature of the objective function, a suboptimal iterative algorithm, i.e., the energy efficient hybrid precoding (EEHP) algorithm is developed for maximizing the energy efficiency of 5G wireless communication systems. To reduce the cost of RF circuits, the energy efficient hybrid precoding with the minimum number of RF chains (EEHP-MRFC) algorithm is also proposed. Moreover, the critical number of antennas searching (CNAS) and user equipment number optimization (UENO) algorithms are further developed to optimize the energy efficiency of 5G wireless communication systems by the number of transmit antennas and UEs. Compared with the maximum energy efficiency of conventional zero-forcing (ZF) precoding algorithm, numerical results indicate that the maximum energy efficiency of the proposed EEHP and EEHP-MRFC algorithms are improved by 220% and 171%, respectively.
Predicting Social Status via Social Networks: A Case Study on University, Occupation, and Region
Venue: arXiv cs.SI 2016
Year: 2016

Social status refers to the relative position within the society. It is an important notion in sociology and related research. The problem of measuring social status has been studied for many years. Various indicators are proposed to assess social status of individuals, including educational attainment, occupation, and income/wealth. However, these indicators are sometimes difficult to collect or measure. We investigate social networks for alternative measures of social status. Online activities expose certain traits of users in the real world. We are interested in how these activities are related to social status, and how social status can be predicted with social network data. To the best of our knowledge, this is the first study on connecting online activities with social status in reality. In particular, we focus on the network structure of microblogs in this study. A user following another implies some kind of status. We cast the predicted social status of users to the "status" of real-world entities, e.g., universities, occupations, and regions, so that we can compare and validate predicted results with facts in the real world. We propose an efficient algorithm for this task and evaluate it on a dataset consisting of 3.4 million users from Sina Weibo. The result shows that it is possible to predict social status with reasonable accuracy using social network data. We also point out challenges and limitations of this approach, e.g., inconsistence between online popularity and real-world status for certain users. Our findings provide insights on analyzing online social status and future designs of ranking schemes for social networks.
Gone in Six Characters: Short URLs Considered Harmful for Cloud Services
Venue: arXiv cs.CR 2016
Year: 2016

Modern cloud services are designed to encourage and support collaboration. To help users share links to online documents, maps, etc., several services, including cloud storage providers such as Microsoft OneDrive and mapping services such as Google Maps, directly integrate URL shorteners that convert long, unwieldy URLs into short URLs, consisting of a domain such as 1drv.ms or goo.gl and a short token. In this paper, we demonstrate that the space of 5- and 6-character tokens included in short URLs is so small that it can be scanned using brute-force search. Therefore, all online resources that were intended to be shared with a few trusted friends or collaborators are effectively public and can be accessed by anyone. This leads to serious security and privacy vulnerabilities. In the case of cloud storage, we focus on Microsoft OneDrive. We show how to use short-URL enumeration to discover and read shared content stored in the OneDrive cloud, including even files for which the user did not generate a short URL. 7% of the OneDrive accounts exposed in this fashion allow anyone to write into them. Since cloud-stored files are automatically copied into users' personal computers and devices, this is a vector for large-scale, automated malware injection. In the case of online maps, we show how short-URL enumeration reveals the directions that users shared with each other. For many individual users, this enables inference of their residential addresses, true identities, and extremely sensitive locations they visited that, if publicly revealed, would violate medical and financial privacy.
Cooperative Interference Mitigation Algorithm in Heterogeneous Networks
Venue: arXiv cs.NI 2016
Year: 2016

Heterogeneous hetworks (HetNets) have been introduced as an emerging technology in order to meet the increasing demand for mobile data. HetNets are a combination of multi-layer networks such as macrocells and small cells. In such networks, users may suffer significant cross-layer interference. To manage this interference, the 3rd Generation Partnership Project (3GPP) has introduced enhanced Inter-Cell Interference Coordination (eICIC) techniques. Almost Blank SubFrame (ABSF) is one of the time-domain techniques used in eICIC solutions. We propose a dynamically optimal Signal-to-Interference-and-Noise Ratio (SINR)-based ABSF framework to ensure macro user performance while maintaining small user performance. We also study cooperative mechanisms to help small cells collaborate efficiently in order to reduce mutual interference. Simulations show that our proposed scheme achieves good performance and outperforms the existing ABSF frameworks.
Trends toward real-time network data steganography
Venue: arXiv cs.MM 2016
Year: 2016

Network steganography has been a well-known covert data channeling method for over three decades. The basic set of techniques and implementation tools have not changed significantly since their introduction in the early 1980's. In this paper, we review the predominant methods of classical network steganography, describing the detailed operations and resultant challenges involved in embedding data in the network transport domain. We also consider the various cyber threat vectors of network steganography and point out the major differences between classical network steganography and the widely known end-point multimedia embedding techniques, which focus exclusively on static data modification for data hiding. We then challenge the security community by introducing an entirely new network dat hiding methodology, which we refer to as real-time network data steganography. Finally we provide the groundwork for this fundamental change of covert network data embedding by forming a basic framework for real-time network data operations that will open the path for even further advances in computer network security.
Categorical semiotics
Venue: arXiv cs.LO 2016
Year: 2016

The integration of knowledge extracted from different models described by domain experts or from models generated by machine learning algorithms is strongly conditioned by the lack of an appropriated framework to specify and integrate structures, learning processes, data transformations and data models or data rules. In this work we extended algebraic specification methods to be used in this type of framework. This methodology uses graphic structures similar to Ehresmann's sketches interpreted on a fuzzy set universe. This approach takes advantages of the sketches ability to integrate data deterministic and nondeterministic structures. Selecting this strategy we also try to take advantage on how the graphic languages, used in Category theory in general and used for sketch definition in particular, are suited to reasoning about problems, to structural description and to task specification and task decomposition.