OpenRaiser/Intern-Atlas huggingface dataset:
Refining Vision Videos
Venue: arXiv cs.SE 2019
Year: 2019

[Context and motivation] Complex software-based systems involve several stakeholders, their activities and interactions with the system. Vision videos are used during the early phases of a project to complement textual representations. They visualize previously abstract visions of the product and its use. By creating, elaborating, and discussing vision videos, stakeholders and developers gain an improved shared understanding of how those abstract visions could translate into concrete scenarios and requirements to which individuals can relate. [Question/problem] In this paper, we investigate two aspects of refining vision videos: (1) Refining the vision by providing alternative answers to previously open issues about the system to be built. (2) A refined understanding of the camera perspective in vision videos. The impact of using a subjective (or "ego") perspective is compared to the usual third-person perspective. [Methodology] We use shopping in rural areas as a real-world application domain for refining vision videos. Both aspects of refining vision videos were investigated in an experiment with 20 participants. [Contribution] Subjects made a significant number of additional contributions when they had received not only video or text but also both - even with very short text and short video clips. Subjective video elements were rated as positive. However, there was no significant preference for either subjective or non-subjective videos in general.
Weakly-Private Information Retrieval
Venue: arXiv cs.IT 2019
Year: 2019

Private information retrieval (PIR) protocols make it possible to retrieve a file from a database without disclosing any information about the identity of the file being retrieved. These protocols have been rigorously explored from an information-theoretic perspective in recent years. While existing protocols strictly impose that no information is leaked on the file's identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the requirement of perfect privacy. In case the user is willing to leak some information on the identity of the retrieved file, we study how the PIR rate, as well as the upload cost and access complexity, can be improved. For the particular case of replicated servers, we propose two weakly-private information retrieval schemes based on two recent PIR protocols and a family of schemes based on partitioning. Lastly, we compare the performance of the proposed schemes.
A New Algorithm for Two-Stage Group Testing
Venue: arXiv cs.IT 2019
Year: 2019

Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed $s$ and $t\to\infty$. For the case $s=2$ this algorithm achieves information-theoretic lower bound $2\log_2t(1+o(1))$ on the number of tests in the worst case. Also, the problem of finding $m$ out of $s$ defectives is considered.
Using Quantization to Deploy Heterogeneous Nodes in Two-Tier Wireless Sensor Networks
Venue: arXiv cs.IT 2019
Year: 2019

We study a heterogeneous two-tier wireless sensor network in which N heterogeneous access points (APs) collect sensing data from densely distributed sensors and then forward the data to M heterogeneous fusion centers (FCs). This heterogeneous node deployment problem is modeled as a quantization problem with distortion defined as the total power consumption of the network. The necessary conditions of the optimal AP and FC node deployment are explored in this paper. We provide a variation of Voronoi Diagram as the optimal cell partition for this network, and show that each AP should be placed between its connected FC and the geometric center of its cell partition. In addition, we propose a heterogeneous two-tier Lloyd algorithm to optimize the node deployment. Simulation results show that our proposed algorithm outperforms the existing clustering methods like Minimum Energy Routing, Agglomerative Clustering, and Divisive Clustering, on average.
A construction of UD $k$-ary multi-user codes from $(2^m(k-1)+1)$-ary codes for MAAC
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we proposed a construction of a UD $k$-ary $T$-user coding scheme for MAAC. We first give a construction of $k$-ary $T^{f+g}$-user UD code from a $k$-ary $T^{f}$-user UD code and a $k^{\pm}$-ary $T^{g}$-user difference set with its two component sets $\mathcal{D}^{+}$ and $\mathcal{D}^{-}$ {\em a priori}. Based on the $k^{\pm}$-ary $T^{g}$-user difference set constructed from a $(2k-1)$-ary UD code, we recursively construct a UD $k$-ary $T$-user codes with code length of $2^m$ from initial multi-user codes of $k$-ary, $2(k-1)+1$-ary, \dots, $(2^m(k-1)+1)$-ary. Introducing multi-user codes with higer-ary makes the total rate of generated code $\mathcal{A}$ higher than that of conventional code.
Pattern Generation Strategies for Improving Recognition of Handwritten Mathematical Expressions
Venue: arXiv cs.CV 2019
Year: 2019

Recognition of Handwritten Mathematical Expressions (HMEs) is a challenging problem because of the ambiguity and complexity of two-dimensional handwriting. Moreover, the lack of large training data is a serious issue, especially for academic recognition systems. In this paper, we propose pattern generation strategies that generate shape and structural variations to improve the performance of recognition systems based on a small training set. For data generation, we employ the public databases: CROHME 2014 and 2016 of online HMEs. The first strategy employs local and global distortions to generate shape variations. The second strategy decomposes an online HME into sub-online HMEs to get more structural variations. The hybrid strategy combines both these strategies to maximize shape and structural variations. The generated online HMEs are converted to images for offline HME recognition. We tested our strategies in an end-to-end recognition system constructed from a recent deep learning model: Convolutional Neural Network and attention-based encoder-decoder. The results of experiments on the CROHME 2014 and 2016 databases demonstrate the superiority and effectiveness of our strategies: our hybrid strategy achieved classification rates of 48.78% and 45.60%, respectively, on these databases. These results are competitive compared to others reported in recent literature. Our generated datasets are openly available for research community and constitute a useful resource for the HME recognition research in future.
AccUDNN: A GPU Memory Efficient Accelerator for Training Ultra-deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Typically, Ultra-deep neural network(UDNN) tends to yield high-quality model, but its training process is usually resource intensive and time-consuming. Modern GPU's scarce DRAM capacity is the primary bottleneck that hinders the trainability and the training efficiency of UDNN. In this paper, we present "AccUDNN", an accelerator that aims to make the utmost use of finite GPU memory resources to speed up the training process of UDNN. AccUDNN mainly includes two modules: memory optimizer and hyperparameter tuner. Memory optimizer develops a performance-model guided dynamic swap out/in strategy, by offloading appropriate data to host memory, GPU memory footprint can be significantly slashed to overcome the restriction of trainability of UDNN. After applying the memory optimization strategy, hyperparameter tuner is designed to explore the efficiency-optimal minibatch size and the matched learning rate. Evaluations demonstrate that AccUDNN cuts down the GPU memory requirement of ResNet-152 from more than 24GB to 8GB. In turn, given 12GB GPU memory budget, the efficiency-optimal minibatch size can reach 4.2x larger than original Caffe. Benefiting from better utilization of single GPU's computing resources and fewer parameter synchronization of large minibatch size, 7.7x speed-up is achieved by 8 GPUs' cluster without any communication optimization and no accuracy losses.
Semantic Image Networks for Human Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose the use of a semantic image, an improved representation for video analysis, principally in combination with Inception networks. The semantic image is obtained by applying localized sparse segmentation using global clustering (LSSGC) prior to the approximate rank pooling which summarizes the motion characteristics in single or multiple images. It incorporates the background information by overlaying a static background from the window onto the subsequent segmented frames. The idea is to improve the action-motion dynamics by focusing on the region which is important for action recognition and encoding the temporal variances using the frame ranking method. We also propose the sequential combination of Inception-ResNetv2 and long-short-term memory network (LSTM) to leverage the temporal variances for improved recognition performance. Extensive analysis has been carried out on UCF101 and HMDB51 datasets which are widely used in action recognition studies. We show that (i) the semantic image generates better activations and converges faster than its original variant, (ii) using segmentation prior to approximate rank pooling yields better recognition performance, (iii) The use of LSTM leverages the temporal variance information from approximate rank pooling to model the action behavior better than the base network, (iv) the proposed representations can be adaptive as they can be used with existing methods such as temporal segment networks to improve the recognition performance, and (v) our proposed four-stream network architecture comprising of semantic images and semantic optical flows achieves state-of-the-art performance, 95.9% and 73.5% recognition accuracy on UCF101 and HMDB51, respectively.
Reed-Solomon Codes over Fields of Characteristic Zero
Venue: arXiv cs.IT 2019
Year: 2019

We study Reed--Solomon codes over arbitrary fields, inspired by several recent papers dealing with Gabidulin codes over fields of characteristic zero. Over the field of rational numbers, we derive bounds on the coefficient growth during encoding and the bit complexity of decoding, which is polynomial in the code length and in the bit width of error and codeword values. The results can be generalized to arbitrary number fields.
A First-Order Logic for Reasoning about Knowledge and Probability
Venue: arXiv cs.LO 2019
Year: 2019

We present a first-order probabilistic epistemic logic, which allows combining operators of knowledge and probability within a group of possibly infinitely many agents. The proposed framework is the first order extension of the logic of Fagin and Halpern from (J.ACM 41:340-367,1994). We define its syntax and semantics, and prove the strong completeness property of the corresponding axiomatic system.
Construction and Decoding of Product Codes with Non-Systematic Polar Codes
Venue: arXiv cs.IT 2019
Year: 2019

Product codes are widespread in optical communications, thanks to their high throughput and good error-correction performance. Systematic polar codes have been recently considered as component codes for product codes. In this paper, we present a novel construction for product polar codes based on non-systematic polar codes. We prove that the resulting product code is actually a polar code, having a frozen set that is dependent on the frozen sets of the component polar codes. We propose a low-complexity decoding algorithm exploiting the dual nature of the constructed code. Performance analysis and simulations show high decoding speed, that allows to construct long codes while maintaining low decoding latency. The resulting high throughput and good error-correction performance are appealing for optical communication systems and other systems where high throughput and low latency are required.
Optimal Task Scheduling Benefits From a Duplicate-Free State-Space
Venue: arXiv cs.DC 2019
Year: 2019

The NP-hard problem of task scheduling with communication delays (P|prec,c_{ij}|C_{\mathrm{max}}) is often tackled using approximate methods, but guarantees on the quality of these heuristic solutions are hard to come by. Optimal schedules are therefore invaluable for properly evaluating these heuristics, as well as being very useful for applications in time critical systems. Optimal solving using branch-and-bound algorithms like A* has been shown to be promising in the past, with a state-space model we refer to as exhaustive list scheduling (ELS). The obvious weakness of this model is that it leads to the production of large numbers of duplicate states during a search, requiring special techniques to mitigate this which cost additional time and memory. In this paper we define a new state-space model (AO) in which we divide the problem into two distinct sub-problems: first we decide the allocations of all tasks to processors, and then we order the tasks on their allocated processors in order to produce a complete schedule. This two-phase state-space model offers no potential for the production of duplicates. We also describe how the pruning techniques and optimisations developed for the ELS model were adapted or made obsolete by the AO model. An experimental evaluation shows that the use of this new state-space model leads to a significant increase in the number of task graphs able to be scheduled within a feasible time-frame, particularly for task graphs with a high communication-to-computation ratio. Finally, some advanced lower bound heuristics are proposed for the AO model, and evaluation demonstrates that significant gains can be achieved from the consideration of necessary idle time.
Challenges of Multi-Factor Authentication for Securing Advanced IoT (A-IoT) Applications
Venue: arXiv cs.NI 2019
Year: 2019

The unprecedented proliferation of smart devices together with novel communication, computing, and control technologies have paved the way for the Advanced Internet of Things~(A-IoT). This development involves new categories of capable devices, such as high-end wearables, smart vehicles, and consumer drones aiming to enable efficient and collaborative utilization within the Smart City paradigm. While massive deployments of these objects may enrich people's lives, unauthorized access to the said equipment is potentially dangerous. Hence, highly-secure human authentication mechanisms have to be designed. At the same time, human beings desire comfortable interaction with their owned devices on a daily basis, thus demanding the authentication procedures to be seamless and user-friendly, mindful of the contemporary urban dynamics. In response to these unique challenges, this work advocates for the adoption of multi-factor authentication for A-IoT, such that multiple heterogeneous methods - both well-established and emerging - are combined intelligently to grant or deny access reliably. We thus discuss the pros and cons of various solutions as well as introduce tools to combine the authentication factors, with an emphasis on challenging Smart City environments. We finally outline the open questions to shape future research efforts in this emerging field.
On Performance Evaluation of Random Access Enhancements for 5G uRLLC
Venue: arXiv cs.NI 2019
Year: 2019

One of the key challenges in realizing ultra-reliable low-latency communications (uRLLC) for factories-of-the-future (FoF) applications is to enhance the cellular random access channel (RACH) procedure. The state-of-the-art LTE RACH procedure does not fulfil the latency requirements for envisioned FoF applications. Moreover, it becomes challenging due to congestion and overloading from massive machine type communication (mMTC) devices leading to collisions especially in a densely populated factory scenarios. The main objective of this paper is to conduct a comprehensive performance evaluation of different random access (RA) enhancements for uRLLC over 5G wireless networks. Our performance evaluation is based on a realistic system-level simulator. The core enhancements considered in this work include early data transmission (EDT), reserved preambles and the use of flexible physical (PHY) layer numerology. We also propose three new RA enhancements for uRLLC. Performance evaluation demonstrates that the proposed RA enhancements can fulfil the 3GPP control plane target of less than 10 ms latency with 99.99% reliability in factory environments.
Predictive Indexing
Venue: arXiv cs.DB 2019
Year: 2019

There has been considerable research on automated index tuning in database management systems (DBMSs). But the majority of these solutions tune the index configuration by retrospectively making computationally expensive physical design changes all at once. Such changes degrade the DBMS's performance during the process, and have reduced utility during subsequent query processing due to the delay between a workload shift and the associated change. A better approach is to generate small changes that tune the physical design over time, forecast the utility of these changes, and apply them ahead of time to maximize their impact. This paper presents predictive indexing that continuously improves a database's physical design using lightweight physical design changes. It uses a machine learning model to forecast the utility of these changes, and continuously refines the index configuration of the database to handle evolving workloads. We introduce a lightweight hybrid scan operator with which a DBMS can make use of partially-built indexes for query processing. Our evaluation shows that predictive indexing improves the throughput of a DBMS by 3.5--5.2x compared to other state-of-the-art indexing approaches. We demonstrate that predictive indexing works seamlessly with other lightweight automated physical design tuning methods.
A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation
Venue: arXiv cs.DS 2019
Year: 2019

An NP-hard graph problem may be intractable for general graphs but it could be efficiently solvable using dynamic programming for graphs with bounded width (or depth or some other structural parameter). Dynamic programming is a well-known approach used for finding exact solutions for NP-hard graph problems based on tree decompositions. It has been shown that there exist algorithms using linear time in the number of vertices and single exponential time in the width (depth or other parameters) of a given tree decomposition for many connectivity problems. Employing dynamic programming on a tree decomposition usually uses exponential space. In 2010, Lokshtanov and Nederlof introduced an elegant framework to avoid exponential space by algebraization. Later, Fürer and Yu modified the framework in a way that even works when the underlying set is dynamic, thus applying it to tree decompositions. In this work, we design space-efficient algorithms to solve the Hamiltonian Cycle and the Traveling Salesman problems, using polynomial space while the time complexity is only slightly increased. This might be inevitable since we are reducing the space usage from an exponential amount (in dynamic programming solution) to polynomial. We give an algorithm to solve Hamiltonian cycle in time $\mathcal{O}((4w)^d\, nM(n\log{n}))$ using $\mathcal{O}(dn\log{n})$ space, where $M(r)$ is the time complexity to multiply two integers, each of which being represented by at most $r$ bits. Then, we solve the more general Traveling Salesman problem in time $\mathcal{O}((4w)^d poly(n))$ using space $\mathcal{O}(\mathcal{W}dn\log{n})$, where $w$ and $d$ are the width and the depth of the given tree decomposition and $\mathcal{W}$ is the sum of weights. Furthermore, this algorithm counts the number of Hamiltonian Cycles.
Reduced Complexity Index Codes and Improved Upperbound on Broadcast Rate for Neighboring Interference Problems
Venue: arXiv cs.IT 2019
Year: 2019

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has $K$ messages and $K$ receivers, the $k$th receiver $R_{k}$ wanting the $k$th message $x_{k}$ and having the interference with $D$ messages after and $U$ messages before its desired message. Maleki, Cadambe and Jafar studied SUICP(SNI) because of its importance in topological interference management problems. Maleki \textit{et. al.} derived the lowerbound on the broadcast rate of this setting to be $D+1$. In our earlier work, for SUICP(SNI) with arbitrary $K,D$ and $U$, we defined set $\mathbf{S}$ of 2-tuples and for every $(a,b) \in \mathbf{S}$, we constructed $b$-dimensional vector linear index code with rate $D+1+\frac{a}{b}$ by using an encoding matrix of dimension $Kb \times (b(D+1)+a)$. In this paper, we use the symmetric structure of the SUICP(SNI) to reduce the size of encoding matrix by partitioning the message symbols. The rate achieved in this paper is same as that of the existing constructions of vector linear index codes. More specifically, we construct $b$-dimensional vector linear index codes for SUICP(SNI) by partitioning the $Kb$ messages into $b(U+1)+c$ sets for some non-negative integer $c$. We use an encoding matrix of size $\frac{Kb}{b(U+1)+c} \times \frac{b(D+1)+a}{b(U+1)+c}$ to encode each partition separately. The advantage of this method is that the receivers need to store atmost $\frac{b(D+1)+a}{b(U+1)+c}$ number of broadcast symbols (index code symbols) to decode a given wanted message symbol. We also give a construction of scalar linear index codes for SUICP(SNI) with arbitrary $K,D$ and $U$. We give an improved upperbound on the braodcast rate of SUICP(SNI).
An Adversarial Approach to High-Quality, Sentiment-Controlled Neural Dialogue Generation
Venue: arXiv cs.CL 2019
Year: 2019

In this work, we propose a method for neural dialogue response generation that allows not only generating semantically reasonable responses according to the dialogue history, but also explicitly controlling the sentiment of the response via sentiment labels. Our proposed model is based on the paradigm of conditional adversarial learning; the training of a sentiment-controlled dialogue generator is assisted by an adversarial discriminator which assesses the fluency and feasibility of the response generating from the dialogue history and a given sentiment label. Because of the flexibility of our framework, the generator could be a standard sequence-to-sequence (SEQ2SEQ) model or a more complicated one such as a conditional variational autoencoder-based SEQ2SEQ model. Experimental results using automatic and human evaluation both demonstrate that our proposed framework is able to generate both semantically reasonable and sentiment-controlled dialogue responses.
Linear Index Coding With Multiple Senders and Extension to a Cellular Network
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, linear index codes with multiple senders are studied, where every receiver receives encoded messages from all senders. A new fitting matrix for the multiple senders is proposed and it is proved that the minimum rank of the proposed fitting matrices is the optimal codelength of linear index codes for the multiple senders. In addition, a new type of a side information graph related with the optimal codelength is proposed and whether given side information is critical or not is studied. Furthermore, linear index codes for the cellular network scenario are studied, where each receiver can receive a subset of sub-codewords. Since some receivers cannot receive the entire codeword in the cellular network scenario, the encoding method based on the fitting matrix has to be modified. In the cellular network scenario, we propose another fitting matrix and prove that an optimal generator matrix can be found based on these fitting matrices. In addition, some properties on the optimal codelength of linear index codes for the cellular network case are studied.