OpenRaiser/Intern-Atlas huggingface dataset:
The I/O complexity of Strassen's matrix multiplication with recomputation
Venue: arXiv cs.DS 2016
Year: 2016

A tight $Ω((n/\sqrt{M})^{\log_2 7}M)$ lower bound is derived on the \io complexity of Strassen's algorithm to multiply two $n \times n$ matrices, in a two-level storage hierarchy with $M$ words of fast memory. A proof technique is introduced, which exploits the Grigoriev's flow of the matrix multiplication function as well as some combinatorial properties of the Strassen computational directed acyclic graph (CDAG). Applications to parallel computation are also developed. The result generalizes a similar bound previously obtained under the constraint of no-recomputation, that is, that intermediate results cannot be computed more than once. For this restricted case, another lower bound technique is presented, which leads to a simpler analysis of the \io complexity of Strassen's algorithm and can be readily extended to other "Strassen-like" algorithms.
An analysis of visitors' behavior in the Louvre Museum: A study using Bluetooth data
Venue: arXiv cs.CY 2016
Year: 2016

Museums often suffer from so-called "hyper-congestion", wherein the number of visitors exceeds the capacity of the physical space of the museum. This can potentially deteriorate the quality of visitor's experience disturbed by other visitors' behaviors and presences. Although this situation can be mitigated by managing visitors' flow between spaces, a detailed analysis of the visitor's movement is required to fully realize and apply a proper solution to the problem. This paper analyzes the visitor's sequential movements, the spatial layout, and the relationship between them in large-scale art museums - Louvre Museum - using anonymized data collected through noninvasive Bluetooth sensors. This enables us to unveil some features of visitor's behavior and spatial impact that shed some light on the mechanism of the museum overcrowding. The analysis reveals that the visiting style of short and long stay visitors are not as significantly different as one could expect. Both types of visitors tend to visit a similar number of key locations in the museum while the longer stay type visitors just tend to do so more extensively. In addition, we reveal that some ways of exploring the museum appear frequently for both types of visitors, although long stay type visitors might be expected to diversify much more given the greater time spent in the museum. We suggest that these similarities/dissimilarities make for an uneven distribution of the quantity of visitors in the museum space. The findings increase the understanding of the unknown behaviors of visitors, which is key to improve the museum's environment and visiting experience.
Block structure vs scope extrusion: between innocence and omniscience
Venue: arXiv cs.PL 2016
Year: 2016

We study the semantic meaning of block structure using game semantics. To that end, we introduce the notion of block-innocent strategies and characterise call-by-value computation with block-allocated storage through soundness, finite definability and universality results. This puts us in a good position to conduct a comparative study of purely functional computation, computation with block storage as well as that with dynamic memory allocation. For example, we can show that dynamic variable allocation can be replaced with block-allocated variables exactly when the term involved (open or closed) is of base type and that block-allocated storage can be replaced with purely functional computation when types of order two are involved. To illustrate the restrictive nature of block structure further, we prove a decidability result for a finitary fragment of call-by-value Idealized Algol for which it is known that allowing for dynamic memory allocation leads to undecidability.
Full Duplex Emulation via Spatial Separation of Half Duplex Nodes in a Planar Cellular Network
Venue: arXiv cs.IT 2016
Year: 2016

A Full Duplex Base Station (FD-BS) can be used to serve simultaneously two Half-Duplex (HD) Mobile Stations (MSs), one working in the uplink and one in the downlink, respectively. The same functionality can be realized by having two interconnected and spatially separated Half Duplex Base Stations (HD-BSs), which is a scheme termed \emph{CoMPflex} (CoMP for In-Band Wireless Full Duplex). A FD-BS can be seen as a special case of CoMPflex with separation distance zero. In this paper we study the performance of CoMPflex in a two-dimensional cellular scenario using stochastic geometry and compare it to the one achieved by FD-BSs. By deriving the Cumulative Distribution Functions, we show that CoMPflex brings BSs closer to the MSs they are serving, while increasing the distance between a MS and interfering MSs. Furthermore, the results show that CoMPflex brings benefits over FD-BS in terms of communication reliability. Following the trend of wireless network densification, CoMPflex can be regarded as a method with a great potential to effectively use the dense HD deployments.
A Random Finite Set Approach for Dynamic Occupancy Grid Maps with Real-Time Application
Venue: arXiv cs.RO 2016
Year: 2016

Grid mapping is a well established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot's environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter (BBF). A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.
Group decision makers making process - an analytic hierarchy approach
Venue: arXiv cs.MA 2016
Year: 2016

The paper deals with a step-wise analytic hierarchy process (AHP) applied by a group of decision makers wherein nobody has a dominant position and it is unlikely to come to terms with respect to either the weights of different objectives or expected utilities of different alternatives. One of the AHP outcomes, that is the consistency index is computed for each decision maker, for all other decision makers but that one, and for the whole group. Doing so, the group is able to assess to which extent each decision maker alters the group consistency index and a better consistency index could be achieved if the assessment procedure is being resumed by the most influential decision maker in terms of consistency. The main contribution of the new approach is the algorithm presented in as a flow chart where the condition to stop the process might be either a threshold value for the consistency index, or a given number of iterations for the group or decision maker, depending on the degree to which the targeted goal has been decomposed into conflictual objectives.
2.4GHZ Class AB power Amplifier For Healthcare Application
Venue: arXiv cs.OH 2016
Year: 2016

The objective of this research was to design a 2.4 GHz class AB Power Amplifier, with 0.18 um SMIC CMOS technology by using Cadence software, for health care applications. The ultimate goal for such application is to minimize the trade-offs between performance and cost, and between performance and low power consumption design. The performance of the power amplifier meets the specification requirements of the desired.
The Controlled Natural Language of Randall Munroe's Thing Explainer
Venue: arXiv cs.CL 2016
Year: 2016

It is rare that texts or entire books written in a Controlled Natural Language (CNL) become very popular, but exactly this has happened with a book that has been published last year. Randall Munroe's Thing Explainer uses only the 1'000 most often used words of the English language together with drawn pictures to explain complicated things such as nuclear reactors, jet engines, the solar system, and dishwashers. This restricted language is a very interesting new case for the CNL community. I describe here its place in the context of existing approaches on Controlled Natural Languages, and I provide a first analysis from a scientific perspective, covering the word production rules and word distributions.
Fuzzy Clustering Based Segmentation Of Vertebrae in T1-Weighted Spinal MR Images
Venue: arXiv cs.CV 2016
Year: 2016

Image segmentation in the medical domain is a challenging field owing to poor resolution and limited contrast. The predominantly used conventional segmentation techniques and the thresholding methods suffer from limitations because of heavy dependence on user interactions. Uncertainties prevalent in an image cannot be captured by these techniques. The performance further deteriorates when the images are corrupted by noise, outliers and other artifacts. The objective of this paper is to develop an effective robust fuzzy C- means clustering for segmenting vertebral body from magnetic resonance image owing to its unsupervised form of learning. The motivation for this work is detection of spine geometry and proper localisation and labelling will enhance the diagnostic output of a physician. The method is compared with Otsu thresholding and K-means clustering to illustrate the robustness.The reference standard for validation was the annotated images from the radiologist, and the Dice coefficient and Hausdorff distance measures were used to evaluate the segmentation.
Orientation Driven Bag of Appearances for Person Re-identification
Venue: arXiv cs.CV 2016
Year: 2016

Person re-identification (re-id) consists of associating individual across camera network, which is valuable for intelligent video surveillance and has drawn wide attention. Although person re-identification research is making progress, it still faces some challenges such as varying poses, illumination and viewpoints. For feature representation in re-identification, existing works usually use low-level descriptors which do not take full advantage of body structure information, resulting in low representation ability. %discrimination. To solve this problem, this paper proposes the mid-level body-structure based feature representation (BSFR) which introduces body structure pyramid for codebook learning and feature pooling in the vertical direction of human body. Besides, varying viewpoints in the horizontal direction of human body usually causes the data missing problem, $i.e.$, the appearances obtained in different orientations of the identical person could vary significantly. To address this problem, the orientation driven bag of appearances (ODBoA) is proposed to utilize person orientation information extracted by orientation estimation technic. To properly evaluate the proposed approach, we introduce a new re-identification dataset (Market-1203) based on the Market-1501 dataset and propose a new re-identification dataset (PKU-Reid). Both datasets contain multiple images captured in different body orientations for each person. Experimental results on three public datasets and two proposed datasets demonstrate the superiority of the proposed approach, indicating the effectiveness of body structure and orientation information for improving re-identification performance.
GLEU Without Tuning
Venue: arXiv cs.CL 2016
Year: 2016

The GLEU metric was proposed for evaluating grammatical error corrections using n-gram overlap with a set of reference sentences, as opposed to precision/recall of specific annotated errors (Napoles et al., 2015). This paper describes improvements made to the GLEU metric that address problems that arise when using an increasing number of reference sets. Unlike the originally presented metric, the modified metric does not require tuning. We recommend that this version be used instead of the original version.
Fundamental Limits of Spectrum Sharing Full-Duplex Multicell Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the degrees of freedom of full-duplex multicell networks that share the spectrum among multiple cells in a non-orthogonal setting. In the considered network, we assume that {\em full-duplex} base stations with multiple transmit and receive antennas communicate with multiple single-antenna mobile users. By spectrum sharing among multiple cells and (simultaneously) enabling full-duplex radio, the network can utilize the spectrum more flexibly, but, at the same time, the network is subject to multiple sources of interference compared to a network with separately dedicated bands for distinct cells and uplink--downlink traffic. Consequently, to take advantage of the additional freedom in utilizing the spectrum, interference management is a crucial ingredient. In this work, we propose a novel strategy based on interference alignment which takes into account inter-cell interference and intra-cell interference caused by spectrum sharing and full-duplex to establish a general achievability result on the sum degrees of freedom of the considered network. Paired with an upper bound on the sum degrees of freedom, which is tight under certain conditions, we demonstrate how spectrum sharing and full-duplex can significantly improve the throughput over conventional cellular networks, especially for a network with large number of users and/or cells.
Efficient Reversible Data Hiding Algorithms Based on Dual Prediction
Venue: arXiv cs.MM 2016
Year: 2016

In this paper, a new reversible data hiding (RDH) algorithm that is based on the concept of shifting of prediction error histograms is proposed. The algorithm extends the efficient modification of prediction errors (MPE) algorithm by incorporating two predictors and using one prediction error value for data embedding. The motivation behind using two predictors is driven by the fact that predictors have different prediction accuracy which is directly related to the embedding capacity and quality of the stego image. The key feature of the proposed algorithm lies in using two predictors without the need to communicate additional overhead with the stego image. Basically, the identification of the predictor that is used during embedding is done through a set of rules. The proposed algorithm is further extended to use two and three bins in the prediction errors histogram in order to increase the embedding capacity. Performance evaluation of the proposed algorithm and its extensions showed the advantage of using two predictors in boosting the embedding capacity while providing competitive quality for the stego image.
On the Emergence of Shortest Paths by Reinforced Random Walks
Venue: arXiv cs.NE 2016
Year: 2016

The co-evolution between network structure and functional performance is a fundamental and challenging problem whose complexity emerges from the intrinsic interdependent nature of structure and function. Within this context, we investigate the interplay between the efficiency of network navigation (i.e., path lengths) and network structure (i.e., edge weights). We propose a simple and tractable model based on iterative biased random walks where edge weights increase over time as function of the traversed path length. Under mild assumptions, we prove that biased random walks will eventually only traverse shortest paths in their journey towards the destination. We further characterize the transient regime proving that the probability to traverse non-shortest paths decays according to a power-law. We also highlight various properties in this dynamic, such as the trade-off between exploration and convergence, and preservation of initial network plasticity. We believe the proposed model and results can be of interest to various domains where biased random walks and decentralized navigation have been applied.
Global network cooperation catalysed by a small prosocial migrant clique
Venue: arXiv cs.MA 2016
Year: 2016

Much research has been carried out to understand the emergence of cooperation in simulated social networks of competing individuals. Such research typically implements a population as a single connected network. Here we adopt a more realistic premise; namely that populations consist of multiple networks, whose members migrate from one to another. Specifically, we isolate the key elements of the scenario where a minority of members from a cooperative network migrate to a network populated by defectors. Using the public goods game to model group-wise cooperation, we find that under certain circumstances, the concerted actions of a trivial number of such migrants will catalyse widespread behavioural change throughout an entire population. Such results support a wider argument: that the general presence of some form of disruption contributes to the emergence of cooperation in social networks, and consequently that simpler models may encode a determinism that precludes the emergence of cooperation.
Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Venue: arXiv cs.DS 2016
Year: 2016

We present a data structure for *spherical range reporting* on a point set $S$, i.e., reporting all points in $S$ that lie within radius $r$ of a given query point $q$. Our solution builds upon the Locality-Sensitive Hashing (LSH) framework of Indyk and Motwani, which represents the asymptotically best solutions to near neighbor problems in high dimensions. While traditional LSH data structures have several parameters whose optimal values depend on the distance distribution from $q$ to the points of $S$, our data structure is parameter-free, except for the space usage, which is configurable by the user. Nevertheless, its expected query time basically matches that of an LSH data structure whose parameters have been *optimally chosen for the data and query* in question under the given space constraints. In particular, our data structure provides a smooth trade-off between hard queries (typically addressed by standard LSH) and easy queries such as those where the number of points to report is a constant fraction of $S$, or where almost all points in $S$ are far away from the query point. In contrast, known data structures fix LSH parameters based on certain parameters of the input alone. The algorithm has expected query time bounded by $O(t (n/t)^ρ)$, where $t$ is the number of points to report and $ρ\in (0,1)$ depends on the data distribution and the strength of the LSH family used. We further present a parameter-free way of using multi-probing, for LSH families that support it, and show that for many such families this approach allows us to get expected query time close to $O(n^ρ+t)$, which is the best we can hope to achieve using LSH. The previously best running time in high dimensions was $Ω(t n^ρ)$. For many data distributions where the intrinsic dimensionality of the point set close to $q$ is low, we can give improved upper bounds on the expected query time.
A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
Venue: arXiv cs.DS 2016
Year: 2016

We present a framework for similarity search based on Locality-Sensitive Filtering (LSF), generalizing the Indyk-Motwani (STOC 1998) Locality-Sensitive Hashing (LSH) framework to support space-time tradeoffs. Given a family of filters, defined as a distribution over pairs of subsets of space with certain locality-sensitivity properties, we can solve the approximate near neighbor problem in $d$-dimensional space for an $n$-point data set with query time $dn^{ρ_q+o(1)}$, update time $dn^{ρ_u+o(1)}$, and space usage $dn + n^{1 + ρ_u + o(1)}$. The space-time tradeoff is tied to the tradeoff between query time and update time, controlled by the exponents $ρ_q, ρ_u$ that are determined by the filter family. Locality-sensitive filtering was introduced by Becker et al. (SODA 2016) together with a framework yielding a single, balanced, tradeoff between query time and space, further relying on the assumption of an efficient oracle for the filter evaluation algorithm. We extend the LSF framework to support space-time tradeoffs and through a combination of existing techniques we remove the oracle assumption. Building on a filter family for the unit sphere by Laarhoven (arXiv 2015) we use a kernel embedding technique by Rahimi & Recht (NIPS 2007) to show a solution to the $(r,cr)$-near neighbor problem in $\ell_s^d$-space for $0 < s \leq 2$ with query and update exponents $ρ_q=\frac{c^s(1+λ)^2}{(c^s+λ)^2}$ and $ρ_u=\frac{c^s(1-λ)^2}{(c^s+λ)^2}$ where $λ\in[-1,1]$ is a tradeoff parameter. This result improves upon the space-time tradeoff of Kapralov (PODS 2015) and is shown to be optimal in the case of a balanced tradeoff. Finally, we show a lower bound for the space-time tradeoff on the unit sphere that matches Laarhoven's and our own upper bound in the case of random data.
Adaptive Combination of l0 LMS Adaptive Filters for Sparse System Identification in Fluctuating Noise Power
Venue: arXiv cs.IT 2016
Year: 2016

Recently, the l0-least mean square (l0-LMS) algorithm has been proposed to identify sparse linear systems by employing a sparsity-promoting continuous function as an approximation of l0 pseudonorm penalty. However, the performance of this algorithm is sensitive to the appropriate choice of the some parameter responsible for the zero-attracting intensity. The optimum choice for this parameter depends on the signal-to-noise ratio (SNR) prevailing in the system. Thus, it becomes difficult to fix a suitable value for this parameter, particularly in a situation where SNR fluctuates over time. In this work, we propose several adaptive combinations of differently parameterized l0-LMS to get an overall satisfactory performance independent of the SNR, and discuss some issues relevant to these combination structures. We also demonstrate an efficient partial update scheme which not only reduces the number of computations per iteration, but also achieves some interesting performance gain compared with the full update case. Then, we propose a new recursive least squares (RLS)-type rule to update the combining parameter more efficiently. Finally, we extend the combination of two filters to a combination of M number adaptive filters, which manifests further improvement for M > 2.
Flag-Based Big-Step Semantics
Venue: arXiv cs.PL 2016
Year: 2016

Structural operational semantic specifications come in different styles: small-step and big-step. A problem with the big-step style is that specifying divergence and abrupt termination gives rise to annoying duplication. We present a novel approach to representing divergence and abrupt termination in big-step semantics using status flags. This avoids the duplication problem, and uses fewer rules and premises for representing divergence than previous approaches in the literature.