OpenRaiser/Intern-Atlas huggingface dataset:
Approximate nearest neighbors search without false negatives for $l_2$ for $c>\sqrt{\log\log{n}}$
Venue: arXiv cs.CG 2017
Year: 2017

In this paper, we report progress on answering the open problem presented by Pagh~[14], who considered the nearest neighbor search without false negatives for the Hamming distance. We show new data structures for solving the $c$-approximate nearest neighbors problem without false negatives for Euclidean high dimensional space $\mathcal{R}^d$. These data structures work for any $c = ω(\sqrt{\log{\log{n}}})$, where $n$ is the number of points in the input set, with poly-logarithmic query time and polynomial preprocessing time. This improves over the known algorithms, which require $c$ to be $Ω(\sqrt{d})$. This improvement is obtained by applying a sequence of reductions, which are interesting on their own. First, we reduce the problem to $d$ instances of dimension logarithmic in $n$. Next, these instances are reduced to a number of $c$-approximate nearest neighbor search instances in $\big(\mathbb{R}^k\big)^L$ space equipped with metric $m(x,y) = \max_{1 \le i \le L}(\lVert x_i - y_i\rVert_2)$.
Performance Gains of Optimal Antenna Deployment for Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

We consider the uplink of a single-cell multi-user multiple-input multiple-output (MIMO) system with several single antenna transmitters/users and one base station with $N$ antennas in the $N\rightarrow\infty$ regime. The base station antennas are evenly distributed to $n$ admissable locations throughout the cell. First, we show that a reliable (per-user) rate of $O(\log n)$ is achievable through optimal locational optimization of base station antennas. We also prove that an $O(\log n)$ rate is the best possible. Therefore, in contrast to a centralized or circular deployment, where the achievable rate is at most a constant, the rate with a general deployment can grow logarithmically with $n$, resulting in a certain form of "macromultiplexing gain." Second, using tools from high-resolution quantization theory, we derive an accurate formula for the best achievable rate given any $n$ and any user density function. According to our formula, the dependence of the optimal rate on the user density function $f$ is curiously only through the differential entropy of $f$. In fact, the optimal rate decreases linearly with the differential entropy, and the worst-case scenario is a uniform user density. Numerical simulations confirm our analytical findings.
Practical Evaluation of the Lasp Programming Model at Large Scale - An Experience Report
Venue: arXiv cs.DC 2017
Year: 2017

Programming models for building large-scale distributed applications assist the developer in reasoning about consistency and distribution. However, many of the programming models for weak consistency, which promise the largest scalability gains, have little in the way of evaluation to demonstrate the promised scalability. We present an experience report on the implementation and large-scale evaluation of one of these models, Lasp, originally presented at PPDP `15, which provides a declarative, functional programming style for distributed applications. We demonstrate the scalability of Lasp's prototype runtime implementation up to 1024 nodes in the Amazon cloud computing environment. It achieves high scalability by uniquely combining hybrid gossip with a programming model based on convergent computation. We report on the engineering challenges of this implementation and its evaluation, specifically related to operating research prototypes in a production cloud environment.
SafePredict: A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness
Venue: arXiv cs.LG 2017
Year: 2017

SafePredict is a novel meta-algorithm that works with any base prediction algorithm for online data to guarantee an arbitrarily chosen correctness rate, $1-ε$, by allowing refusals. Allowing refusals means that the meta-algorithm may refuse to emit a prediction produced by the base algorithm on occasion so that the error rate on non-refused predictions does not exceed $ε$. The SafePredict error bound does not rely on any assumptions on the data distribution or the base predictor. When the base predictor happens not to exceed the target error rate $ε$, SafePredict refuses only a finite number of times. When the error rate of the base predictor changes through time SafePredict makes use of a weight-shifting heuristic that adapts to these changes without knowing when the changes occur yet still maintains the correctness guarantee. Empirical results show that (i) SafePredict compares favorably with state-of-the art confidence based refusal mechanisms which fail to offer robust error guarantees; and (ii) combining SafePredict with such refusal mechanisms can in many cases further reduce the number of refusals. Our software (currently in Python) is included in the supplementary material.
Constructing Words with High Distinct Square Densities
Venue: arXiv cs.FL 2017
Year: 2017

Fraenkel and Simpson showed that the number of distinct squares in a word of length n is bounded from above by 2n, since at most two distinct squares have their rightmost, or last, occurrence begin at each position. Improvements by Ilie to $2n-Θ(\log n)$ and by Deza et al. to 11n/6 rely on the study of combinatorics of FS-double-squares, when the maximum number of two last occurrences of squares begin. In this paper, we first study how to maximize runs of FS-double-squares in the prefix of a word. We show that for a given positive integer m, the minimum length of a word beginning with m FS-double-squares, whose lengths are equal, is 7m+3. We construct such a word and analyze its distinct-square-sequence as well as its distinct-square-density. We then generalize our construction. We also construct words with high distinct-square-densities that approach 5/6.
The Triple-Pair Construction for Weighted $ω$-Pushdown Automata
Venue: arXiv cs.FL 2017
Year: 2017

Let S be a complete star-omega semiring and Sigma be an alphabet. For a weighted omega-pushdown automaton P with stateset 1...n, n greater or equal to 1, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ((S<<Sigma*>>)^nxn, (S<<Sigma^omega>>)^n) such that the behavior ||P|| of P is a component of a solution of this system. In case the basic semiring is the Boolean semiring or the semiring of natural numbers (augmented with infinity), we show that there exists a mixed context-free grammar that generates ||P||. The construction of the mixed context-free grammar from P is a generalization of the well known triple construction and is called now triple-pair construction for omega-pushdown automata.
On h-Lexicalized Restarting Automata
Venue: arXiv cs.FL 2017
Year: 2017

Following some previous studies on restarting automata, we introduce a refined model - the h-lexicalized restarting automaton (h-RLWW). We argue that this model is useful for expressing lexicalized syntax in computational linguistics. We compare the input languages, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages, which are (implicitly) used by categorial grammars, the original tool for the description of lexicalized syntax. The basic and h-proper languages allow us to stress several nice properties of h-lexicalized restarting automata, and they are suitable for modeling the analysis by reduction and, subsequently, for the development of categories of a lexicalized syntax. Based on the fact that a two-way deterministic monotone restarting automaton can be transformed into an equivalent deterministic monotone RL-automaton in (Marcus) contextual form, we obtain a transformation from monotone RLWW-automata that recognize the class CFL of context-free languages as their input languages to deterministic monotone h-RLWW-automata that recognize CFL through their h-proper languages. Through this transformation we obtain automata with the complete correctness preserving property and an infinite hierarchy within CFL, based on the size of the read/write window. Additionally, we consider h-RLWW-automata that are allowed to perform multiple rewrite steps per cycle, and we establish another infinite hierarchy above CFL that is based on the number of rewrite steps that may be executed within a cycle. The corresponding separation results and their proofs illustrate the transparency of h-RLWW-automata that work with the (complete or cyclic) correctness preserving property
Strider-lsa: Massive RDF Stream Reasoning in the Cloud
Venue: arXiv cs.DB 2017
Year: 2017

Reasoning over semantically annotated data is an emerging trend in stream processing aiming to produce sound and complete answers to a set of continuous queries. It usually comes at the cost of finding a trade-off between data throughput and the cost of expressive inferences. Strider-lsa proposes such a trade-off and combines a scalable RDF stream processing engine with an efficient reasoning system. The main reasoning tasks are based on a query rewriting approach for SPARQL that benefits from an intelligent encoding of RDFS+ (RDFS + owl:sameAs) ontology elements. Strider-lsa runs in production at a major international water management company to detect anomalies from sensor streams. The system is evaluated along different dimensions and over multiple datasets to emphasize its performance.
Color and Gradient Features for Text Segmentation from Video Frames
Venue: arXiv cs.CV 2017
Year: 2017

Text segmentation in a video is drawing attention of researchers in the field of image processing, pattern recognition and document image analysis because it helps in annotating and labeling video events accurately. We propose a novel idea of generating an enhanced frame from the R, G, and B channels of an input frame by grouping high and low values using Min-Max clustering criteria. We also perform sliding window on enhanced frame to group high and low values from the neighboring pixel values to further enhance the frame. Subsequently, we use k-means with k=2 clustering algorithm to separate text and non-text regions. The fully connected components will be identified in the skeleton of the frame obtained by k-means clustering. Concept of connected component analysis based on gradient feature has been adapted for the purpose of symmetry verification. The components which satisfy symmetric verification are selected to be the representatives of text regions and they are permitted to grow to cover their respective region fully containing text. The method is tested on variety of video frames to evaluate the performance of the method in terms of recall, precision and f-measure. The results show that method is promising and encouraging.
Dynamic correlations at different time-scales with Empirical Mode Decomposition
Venue: arXiv cs.CE 2017
Year: 2017

The Empirical Mode Decomposition (EMD) provides a tool to characterize time series in terms of its implicit components oscillating at different time-scales. We apply this decomposition to intraday time series of the following three financial indices: the S\&P 500 (USA), the IPC (Mexico) and the VIX (volatility index USA), obtaining time-varying multidimensional cross-correlations at different time-scales. The correlations computed over a rolling window are compared across the three indices, across the components at different time-scales, at different lags and over time. We uncover a rich heterogeneity of interactions which depends on the time-scale and has important led-lag relations which can have practical use for portfolio management, risk estimation and investments.
A two-level approach to implicit surface modeling with compactly supported radial basis functions
Venue: arXiv cs.GR 2017
Year: 2017

We describe a two-level method for computing a function whose zero-level set is the surface reconstructed from given points scattered over the surface and associated with surface normal vectors. The function is defined as a linear combination of compactly supported radial basis functions (CSRBFs). The method preserves the simplicity and efficiency of implicit surface interpolation with CSRBFs and the reconstructed implicit surface owns the attributes, which are previously only associated with globally supported or globally regularized radial basis functions, such as exhibiting less extra zero-level sets, suitable for inside and outside tests. First, in the coarse scale approximation, we choose basis function centers on a grid that covers the enlarged bounding box of the given point set and compute their signed distances to the underlying surface using local quadratic approximations of the nearest surface points. Then a fitting to the residual errors on the surface points and additional off-surface points is performed with fine scale basis functions. The final function is the sum of the two intermediate functions and is a good approximation of the signed distance field to the surface in the bounding box. Examples of surface reconstruction and set operations between shapes are provided.
Bitwise Source Separation on Hashed Spectra: An Efficient Posterior Estimation Scheme Using Partial Rank Order Metrics
Venue: arXiv cs.SD 2017
Year: 2017

This paper proposes an efficient bitwise solution to the single-channel source separation task. Most dictionary-based source separation algorithms rely on iterative update rules during the run time, which becomes computationally costly especially when we employ an overcomplete dictionary and sparse encoding that tend to give better separation results. To avoid such cost we propose a bitwise scheme on hashed spectra that leads to an efficient posterior probability calculation. For each source, the algorithm uses a partial rank order metric to extract robust features that form a binarized dictionary of hashed spectra. Then, for a mixture spectrum, its hash code is compared with each source's hashed dictionary in one pass. This simple voting-based dictionary search allows a fast and iteration-free estimation of ratio masking at each bin of a signal spectrogram. We verify that the proposed BitWise Source Separation (BWSS) algorithm produces sensible source separation results for the single-channel speech denoising task, with 6-8 dB mean SDR. To our knowledge, this is the first dictionary based algorithm for this task that is completely iteration-free in both training and testing.
ElasticPlay: Interactive Video Summarization with Dynamic Time Budgets
Venue: arXiv cs.MM 2017
Year: 2017

Video consumption is being shifted from sit-and-watch to selective skimming. Existing video player interfaces, however, only provide indirect manipulation to support this emerging behavior. Video summarization alleviates this issue to some extent, shortening a video based on the desired length of a summary as an input variable. But an optimal length of a summarized video is often not available in advance. Moreover, the user cannot edit the summary once it is produced, limiting its practical applications. We argue that video summarization should be an interactive, mixed-initiative process in which users have control over the summarization procedure while algorithms help users achieve their goal via video understanding. In this paper, we introduce ElasticPlay, a mixed-initiative approach that combines an advanced video summarization technique with direct interface manipulation to help users control the video summarization process. Users can specify a time budget for the remaining content while watching a video; our system then immediately updates the playback plan using our proposed cut-and-forward algorithm, determining which parts to skip or to fast-forward. This interactive process allows users to fine-tune the summarization result with immediate feedback. We show that our system outperforms existing video summarization techniques on the TVSum50 dataset. We also report two lab studies (22 participants) and a Mechanical Turk deployment study (60 participants), and show that the participants responded favorably to ElasticPlay.
Elastic Local Breakout Strategy and Implementation for Delay-Sensitive Packets with Local Significance
Venue: arXiv cs.IT 2017
Year: 2017

Explosion of mobile traffic will bring a heavy burden to the core network, and rapid growth of mobile devices, as well as increasing demand for delay-sensitive services poses severe challenges to future wireless communication systems. In this regard, local breakout is a promising solution to save core network load and, more importantly, to reduce end-to-end (e2e) delay of packets with local significance. However, the capacity of local breakout link is limited, resulting in excessive delay when the traffic load through the local link is high. Therefore, the decision on whether the traffic flows should be transmitted through core network or by local breakout link has great practical significance. In this paper, we propose and implement a novel local breakout framework to deliver low e2e delay packets with local significance. A real-time local breakout rule based on the solution to a Markov decision process is given, showing that some packets with local significance should pass through core network rather than being delivered by local breakout link to meet the delay requirements. To test our proposed framework, a long-term-evolution (LTE) based test-bed with virtual base stations is implemented, by which we show the proposed framework is feasible and the e2e delay is significantly reduced.
Fault-Tolerant Dot-Product Engines
Venue: arXiv cs.IT 2017
Year: 2017

Coding schemes are presented that provide the ability to correct and detect computational errors while using dot-product engines for integer vector--matrix multiplication. Both the $L_1$-metric and the Hamming metric are considered.
Tomographic Reconstruction Methods for Decomposing Directional Components
Venue: arXiv cs.CE 2017
Year: 2017

Decomposition of tomographic reconstructions has many different practical application. We propose two new reconstruction methods that combines the task of tomographic reconstruction with object decomposition. We demonstrate these reconstruction methods in the context of decomposing directional objects into various directional components. Furthermore we propose a method for estimating the main direction in a directional object, directly from the measured computed tomography data. We demonstrate all the proposed methods on simulated and real samples to show their practical applicability. The numerical tests show that decomposition and reconstruction can combined to achieve a highly useful fibre-crack decomposition.
Bringing Fault-Tolerant GigaHertz-Computing to Space: A Multi-Stage Software-Side Fault-Tolerance Approach for Miniaturized Spacecraft
Venue: arXiv cs.DC 2017
Year: 2017

Modern embedded technology is a driving factor in satellite miniaturization, contributing to a massive boom in satellite launches and a rapidly evolving new space industry. Miniaturized satellites, however, suffer from low reliability, as traditional hardware-based fault-tolerance (FT) concepts are ineffective for on-board computers (OBCs) utilizing modern systems-on-a-chip (SoC). Therefore, larger satellites continue to rely on proven processors with large feature sizes. Software-based concepts have largely been ignored by the space industry as they were researched only in theory, and have not yet reached the level of maturity necessary for implementation. We present the first integral, real-world solution to enable fault-tolerant general-purpose computing with modern multiprocessor-SoCs (MPSoCs) for spaceflight, thereby enabling their use in future high-priority space missions. The presented multi-stage approach consists of three FT stages, combining coarse-grained thread-level distributed self-validation, FPGA reconfiguration, and mixed criticality to assure long-term FT and excellent scalability for both resource constrained and critical high-priority space missions. Early benchmark results indicate a drastic performance increase over state-of-the-art radiation-hard OBC designs and considerably lower software- and hardware development costs. This approach was developed for a 4-year European Space Agency (ESA) project, and we are implementing a tiled MPSoC prototype jointly with two industrial partners.
Delay Analysis for Wireless D2D Caching with Inter-cluster Cooperation
Venue: arXiv cs.IT 2017
Year: 2017

Proactive wireless caching and D2D communication have emerged as promising techniques for enhancing users' quality of service and network performance. In this paper, we propose a new architecture for D2D caching with inter-cluster cooperation. We study a cellular network in which users cache popular files and share them with other users either in their proximity via D2D communication or with remote users using cellular transmission. We characterize the network average delay per request from a queuing perspective. Specifically, we formulate the delay minimization problem and show that it is NP-hard. Furthermore, we prove that the delay minimization problem is equivalent to minimization of a non-increasing monotone super modular function subject to a partition matroid constraint. A computationally efficient greedy algorithm is proposed which is proven to be locally optimal within a factor 2 of the optimum. Simulation results show more than 45% delay reduction compared to a D2D caching system without inter-cluster cooperation.
3D Morphable Models as Spatial Transformer Networks
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we show how a 3D Morphable Model (i.e. a statistical model of the 3D shape of a class of objects such as faces) can be used to spatially transform input data as a module (a 3DMM-STN) within a convolutional neural network. This is an extension of the original spatial transformer network in that we are able to interpret and normalise 3D pose changes and self-occlusions. The trained localisation part of the network is independently useful since it learns to fit a 3D morphable model to a single image. We show that the localiser can be trained using only simple geometric loss functions on a relatively small dataset yet is able to perform robust normalisation on highly uncontrolled images including occlusion, self-occlusion and large pose changes.
Proportionate gradient updates with PercentDelta
Venue: arXiv cs.LG 2017
Year: 2017

Deep Neural Networks are generally trained using iterative gradient updates. Magnitudes of gradients are affected by many factors, including choice of activation functions and initialization. More importantly, gradient magnitudes can greatly differ across layers, with some layers receiving much smaller gradients than others. causing some layers to train slower than others and therefore slowing down the overall convergence. We analytically explain this disproportionality. Then we propose to explicitly train all layers at the same speed, by scaling the gradient w.r.t. every trainable tensor to be proportional to its current value. In particular, at every batch, we want to update all trainable tensors, such that the relative change of the L1-norm of the tensors is the same, across all layers of the network, throughout training time. Experiments on MNIST show that our method appropriately scales gradients, such that the relative change in trainable tensors is approximately equal across layers. In addition, measuring the test accuracy with training time, shows that our method trains faster than other methods, giving higher test accuracy given same budget of training steps.