OpenRaiser/Intern-Atlas huggingface dataset:
Relative distance features for gait recognition with Kinect
Venue: arXiv cs.CV 2016
Year: 2016

Gait and static body measurement are important biometric technologies for passive human recognition. Many previous works argue that recognition performance based completely on the gait feature is limited. The reason for this limited performance remains unclear. This study focuses on human recognition with gait feature obtained by Kinect and shows that gait feature can effectively distinguish from different human beings through a novel representation -- relative distance-based gait features. Experimental results show that the recognition accuracy with relative distance features reaches up to 85%, which is comparable with that of anthropometric features. The combination of relative distance features and anthropometric features can provide an accuracy of more than 95%. Results indicate that the relative distance feature is quite effective and worthy of further study in more general scenarios (e.g., without Kinect).
Partitions of planar point sets into polygons
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we characterize planar point sets that can be partitioned into disjoint polygons of arbitrarily specified sizes. We provide an algorithm to construct such a partition, if it exists, in polynomial time. We show that this problem is equivalent to finding a specified $2$-factor in the visibility graph of the point set. The characterization for the case where all cycles have length $3$ also translates to finding a $K_3$-factor of the visibility graph of the point set. We show that the generalized problem of finding a $K_k$-factor of the visibility graph of a given point set for $k \geq 5$ is NP-hard.
Low-Rank Matrices on Graphs: Generalized Recovery & Applications
Venue: arXiv cs.CV 2016
Year: 2016

Many real world datasets subsume a linear or non-linear low-rank structure in a very low-dimensional space. Unfortunately, one often has very little or no information about the geometry of the space, resulting in a highly under-determined recovery problem. Under certain circumstances, state-of-the-art algorithms provide an exact recovery for linear low-rank structures but at the expense of highly inscalable algorithms which use nuclear norm. However, the case of non-linear structures remains unresolved. We revisit the problem of low-rank recovery from a totally different perspective, involving graphs which encode pairwise similarity between the data samples and features. Surprisingly, our analysis confirms that it is possible to recover many approximate linear and non-linear low-rank structures with recovery guarantees with a set of highly scalable and efficient algorithms. We call such data matrices as \textit{Low-Rank matrices on graphs} and show that many real world datasets satisfy this assumption approximately due to underlying stationarity. Our detailed theoretical and experimental analysis unveils the power of the simple, yet very novel recovery framework \textit{Fast Robust PCA on Graphs}
On the Precision to Sort Line-Quadric Intersections
Venue: arXiv cs.CG 2016
Year: 2016

To support exactly tracking a neutron moving along a given line segment through a CAD model with quadric surfaces, this paper considers the arithmetic precision required to compute the order of intersection points of two quadrics along the line segment. When the orders of all but one pair of intersections are known, we show that a resultant can resolve the order of the remaining pair using only half the precision that may be required to eliminate radicals by repeated squaring. We compare the time and accuracy of our technique with converting to extended precision to calculate roots.
Energy-Recycling Full-Duplex Radios for Next-Generation Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this work, a novel energy-recycling single-antenna full-duplex (FD) radio is designed, in which a new 3-port element including a power divider and an energy harvester is added between the circulator and the receiver (RX) chain. The presence of this new element brings advantages over the state of the art in terms of both spectral efficiency and energy consumption. In particular, it provides the means of performing both an arbitrary attenuation of the incoming signal, which in turn increases the effectiveness of the state-of-the-art self-interference cancellation strategies subsequently adopted in the RX chain, and the recycling of a non-negligible portion of the energy leaked through the non-ideal circulator. The performance of this architecture is analyzed in a practically relevant 4-node scenario in which 2 nodes operate in FD and 2 nodes in half-duplex (HD). Analytical approximations are derived for both the achievable rates of the transmissions performed by the FD and HD radios and the energy recycled by the FD radios. The accuracy of these derivations is confirmed by numerical simulations. Quantitatively, achievable rate gains up to 40% over the state-of-the-art alternatives, in the considered scenario, are highlighted. Furthermore, up to 50% of the leaked energy at the circulator, i.e., 5% of the energy of the transmitted signal, can be recycled.
Simultaneous Wireless Information and Power Transfer Under Different CSI Acquisition Schemes
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we consider a multiple-input single-output system in which an access point (AP) performs a simultaneous wireless information and power transfer (SWIPT) to serve a user terminal (UT) that is not equipped with external power supply. In order to assess the efficacy of the SWIPT, we target a practically relevant scenario characterized by imperfect channel state information (CSI) at the transmitter, the presence of penalties associated to the CSI acquisition procedures, and non-zero power consumption for the operations performed by the UT, such as CSI estimation, uplink signaling and data decoding. We analyze three different cases for the CSI knowledge at the AP: no CSI, and imperfect CSI in case of time-division duplexing and frequency-division duplexing communications. Closed-form representations of the ergodic downlink rate and both the energy shortage and data outage probability are derived for the three cases. Additionally, analytic expressions for the ergodically optimal duration of power transfer and channel estimation/feedback phases are provided. Our numerical findings verify the correctness of our derivations, and also show the importance and benefits of CSI knowledge at the AP in SWIPT systems, albeit imperfect and acquired at the expense of the time available for the information transfer.
Distributed Parallel D8 Up-Slope Area Calculation in Digital Elevation Models
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents a parallel algorithm for calculating the eight-directional (D8) up-slope contributing area in digital elevation models (DEMs). In contrast with previous algorithms, which have potentially unbounded inter-node communications, the algorithm presented here realizes strict bounds on the number of inter-node communications. Those bounds in turn allow D8 attributes to be processed for arbitrarily large DEMs on hardware ranging from average desktops to supercomputers. The algorithm can use the OpenMP and MPI parallel computing models, either in combination or separately. It partitions the DEM between slave nodes, calculates an internal up-slope area by replacing information from other slaves with variables representing unknown quantities, passes the results on to a master node which combines all the slaves' data, and passes information back to each slave, which then computes its final result. In this way each slave's DEM partition is treated as a simple unit in the DEM as a whole and only two communications take place per node.
A comparison of semi-deterministic and stochastic search techniques
Venue: arXiv cs.NE 2016
Year: 2016

This paper presents an investigation of two search techniques, tabu search (TS) and simulated annealing (SA), to assess their relative merits when applied to engineering design optimisation. Design optimisation problems are generally characterised as having multi-modal search spaces and discontinuities making global optimisation techniques beneficial. Both techniques claim to be capable of locating globally optimum solutions on a range of problems but this capability is derived from different underlying philosophies. While tabu search uses a semi-deterministic approach to escape local optima, simulated annealing uses a complete stochastic approach. The performance of each technique is investigated using a structural optimisation problem. These performances are then compared to each other as and to a steepest descent (SD) method.
Privacy-Related Consequences of Turkish Citizen Database Leak
Venue: arXiv cs.CR 2016
Year: 2016

Personal data is collected and stored more than ever by the governments and companies in the digital age. Even though the data is only released after anonymization, deanonymization is possible by joining different datasets. This puts the privacy of individuals in jeopardy. Furthermore, data leaks can unveil personal identifiers of individuals when security is breached. Processing the leaked dataset can provide even more information than what is visible to naked eye. In this work, we report the results of our analyses on the recent "Turkish citizen database leak", which revealed the national identifier numbers of close to fifty million voters, along with personal information such as date of birth, birth place, and full address. We show that with automated processing of the data, one can uniquely identify (i) mother's maiden name of individuals and (ii) landline numbers, for a significant portion of people. This is a serious privacy and security threat because (i) identity theft risk is now higher, and (ii) scammers are able to access more information about individuals. The only and utmost goal of this work is to point out to the security risks and suggest stricter measures to related companies and agencies to protect the security and privacy of individuals.
SONATA: Service Programming and Orchestration for Virtualized Software Networks
Venue: arXiv cs.SE 2016
Year: 2016

In conventional large-scale networks, creation and management of network services are costly and complex tasks that often consume a lot of resources, including time and manpower. Network softwarization and network function virtualization have been introduced to tackle these problems. They replace the hardware-based network service components and network control mechanisms with software components running on general-purpose hardware, aiming at decreasing costs and complexity of implementing new services, maintaining the implemented services, and managing available resources in service provisioning platforms and underlying infrastructures. To experience the full potential of these approaches, innovative development support tools and service provisioning environments are needed. To answer these needs, we introduce the SONATA architecture, a service programming, orchestration, and management framework. We present a development toolchain for virtualized network services, fully integrated with a service platform and orchestration system. We motivate the modular and flexible architecture of our system and discuss its main components and features, such as function- and service-specific managers that allow fine- grained service management, slicing support to facilitate multi-tenancy, recursiveness for improved scalability, and full-featured DevOps support.
Domain Theory: An Introduction
Venue: arXiv cs.PL 2016
Year: 2016

This monograph is an ongoing revision of "Lectures On A Mathematical Theory of Computation" by Dana Scott. Scott's monograph uses a formulation of domains called neighborhood systems in which finite elements are selected subsets of a master set of objects called "tokens". Since tokens have little intuitive significance, Scott has discarded neighborhood systems in favor of an equivalent formulation of domains called information systems. Unfortunately, he has not rewritten his monograph to reflect this change. We have rewritten Scott's monograph in terms of finitary bases instead of information systems. A finitary basis is an information system that is closed under least upper bounds on finite consistent subsets. This convention ensures that every finite answer is represented by a single basis object instead of a set of objects.
Hierarchical Piecewise-Constant Super-regions
Venue: arXiv cs.CV 2016
Year: 2016

Recent applications in computer vision have come to heavily rely on superpixel over-segmentation as a pre-processing step for higher level vision tasks, such as object recognition, image labelling or image segmentation. Here we present a new superpixel algorithm called Hierarchical Piecewise-Constant Super-regions (HPCS), which not only obtains superpixels comparable to the state-of-the-art, but can also be applied hierarchically to form what we call n-th order super-regions. In essence, a Markov Random Field (MRF)-based anisotropic denoising formulation over the quantized feature space is adopted to form piecewise-constant image regions, which are then combined with a graph-based split & merge post-processing step to form superpixels. The graph and quantized feature based formulation of the problem allows us to generalize it hierarchically to preserve boundary adherence with fewer superpixels. Experimental results show that, despite the simplicity of our framework, it is able to provide high quality superpixels, and to hierarchically apply them to form layers of over-segmentation, each with a decreasing number of superpixels, while maintaining the same desired properties (such as adherence to strong image edges). The algorithm is also memory efficient and has a low computational cost.
Geometric Near-neighbor Access Tree (GNAT) revisited
Venue: arXiv cs.DS 2016
Year: 2016

Geometric Near-neighbor Access Tree (GNAT) is a metric space indexing method based on hierarchical hyperplane partitioning of the space. While GNAT is very efficient in proximity searching, it has a bad reputation of being a memory hog. We show that this is partially based on too coarse analysis, and that the memory requirements can be lowered while at the same time improving the search efficiency. We also show how to make GNAT memory adaptive in a smooth way, and that the hyperplane partitioning can be replaced with ball partitioning, which can further improve the search performance. We conclude with experimental results showing the new methods can give significant performance boost.
Minimizing The Expected Distortion Using Multi-layer Coding Approach In Two-Hop Networks
Venue: arXiv cs.IT 2016
Year: 2016

This work concerns minimizing the achievable distortion of a Gaussian source over a two-hop block fading channel under mean square-error criterion. It is assumed that there is not a direct link between transmission ends and the communication is carried out through the use of a relay, employing the Decode and Forward (DF) strategy. Moreover, for both of transmitter-to-relay and relay-to-destination links the channel statistics are merely available at the corresponding receivers, while the channel gains are not available at the affiliated transmitters. It is assumed that a Gaussian source is hierarchically encoded through the use of successive refinement source coding approach and sent to the relay using a multi-layer channel code. Similarly, the relay transmits the retrieved information to the destination through the use of a multi-layer code. Accordingly, in a Rayleigh block fading environment, the optimal power allocation across code layers is derived. Numerical results demonstrate that the achievable distortion of the proposed multi-layer approach outperforms that of single-layer code. Moreover, the resulting distortion of DF strategy is better than Amplify and Forward~(AF) strategy for channel mismatch factors greater than one, while the resulting distortion has a marginal degradation for channel mismatch factors lower than one.
Ancilla-free Reversible Logic Synthesis via Sorting
Venue: arXiv cs.ET 2016
Year: 2016

Reversible logic synthesis is emerging as a major research component for post-CMOS computing devices, in particular Quantum computing. In this work, we link the reversible logic synthesis problem to sorting algorithms. Based on our analysis, an alternative derivation of the worst-case complexity of generated reversible circuits is provided. Furthermore, a novel column-wise reversible logic synthesis method, termed RevCol, is designed with inspiration from radix sort. Extending the principles of RevCol, we present a hybrid reversible logic synthesis framework. The theoretical and experimental results are presented. The results are extensively benchmarked with state-of-the-art ancilla-free reversible logic synthesis methods.
What is the effect of synergy in international collaboration on regional economies?
Venue: arXiv cs.CY 2016
Year: 2016

We analyze the effects of relative increments of mutual information among the geographical, technological, and organizational distributions of firms on the relative augmentation of regional summary turnover in terms of synergies. How do increases in synergy in international cooperation affect regional turnover? The methodological contribution of this study is that we translate the synergy (abstractly measured in bits of information) into more familiar economic terms, such as turnover for the special case of domestic-foreign collaborations. The analysis is based on Norwegian data, as Norway is a small country with an open and export-oriented economy. Data for Norway is publicly available in great detail.
Hierarchical Clustering in Face Similarity Score Space
Venue: arXiv cs.CV 2016
Year: 2016

Similarity scores in face recognition represent the proximity between pairs of images as computed by a matching algorithm. Given a large set of images and the proximities between all pairs, a similarity score space is defined. Cluster analysis was applied to the similarity score space to develop various taxonomies. Given the number of subjects in the dataset, we used hierarchical methods to aggregate images of the same subject. We also explored the hierarchy above and below the subject level, including clusters that reflect gender and ethnicity. Evidence supports the existence of clustering by race, gender, subject, and illumination condition.
A Hierarchical Latent Variable Encoder-Decoder Model for Generating Dialogues
Venue: arXiv cs.CL 2016
Year: 2016

Sequential data often possesses a hierarchical structure with complex dependencies between subsequences, such as found between the utterances in a dialogue. In an effort to model this kind of generative process, we propose a neural network-based generative architecture, with latent stochastic variables that span a variable number of time steps. We apply the proposed model to the task of dialogue response generation and compare it with recent neural network architectures. We evaluate the model performance through automatic evaluation metrics and by carrying out a human evaluation. The experiments demonstrate that our model improves upon recently proposed models and that the latent variables facilitate the generation of long outputs and maintain the context.
Consensus+Innovations Distributed Kalman Filter with Optimized Gains
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we address the distributed filtering and prediction of time-varying random fields represented by linear time-invariant (LTI) dynamical systems. The field is observed by a sparsely connected network of agents/sensors collaborating among themselves. We develop a Kalman filter type consensus+innovations distributed linear estimator of the dynamic field termed as Consensus+Innovations Kalman Filter. We analyze the convergence properties of this distributed estimator. We prove that the mean-squared error of the estimator asymptotically converges if the degree of instability of the field dynamics is within a pre-specified threshold defined as tracking capacity of the estimator. The tracking capacity is a function of the local observation models and the agent communication network. We design the optimal consensus and innovation gain matrices yielding distributed estimates with minimized mean-squared error. Through numerical evaluations, we show that, the distributed estimator with optimal gains converges faster and with approximately 3dB better mean-squared error performance than previous distributed estimators.
Finding Needles in the Haystack: Harnessing Syslogs for Data Center Management
Venue: arXiv cs.NI 2016
Year: 2016

Network device syslogs are ubiquitous and abundant in modern data centers with most large data centers producing millions of messages per day. Yet, the operational information reflected in syslogs and their implications on diagnosis or management tasks are poorly understood. Prevalent approaches to understanding syslogs focus on simple correlation and abnormality detection and are often limited to detection providing little insight towards diagnosis and resolution. Towards improving data center operations, we propose and implement Log-Prophet, a system that applies a toolbox of statistical techniques and domain-specific models to mine detailed diagnoses. Log-Prophet infers causal relationships between syslog lines and constructs succinct but valuable problem graphs, summarizing root causes and their locality, including cascading problems. We validate Log-Prophet using problem tickets and through operator interviews. To demonstrate the strength of Log-Prophet, we perform an initial longitudinal study of a large online service provider's data center. Our study demonstrates that Log-Prophet significantly reduces the number of alerts while highlighting interesting operational issues.
Fine-Grained Classification of Pedestrians in Video: Benchmark and State of the Art
Venue: arXiv cs.CV 2016
Year: 2016

A video dataset that is designed to study fine-grained categorisation of pedestrians is introduced. Pedestrians were recorded "in-the-wild" from a moving vehicle. Annotations include bounding boxes, tracks, 14 keypoints with occlusion information and the fine-grained categories of age (5 classes), sex (2 classes), weight (3 classes) and clothing style (4 classes). There are a total of 27,454 bounding box and pose labels across 4222 tracks. This dataset is designed to train and test algorithms for fine-grained categorisation of people, it is also useful for benchmarking tracking, detection and pose estimation of pedestrians. State-of-the-art algorithms for fine-grained classification and pose estimation were tested using the dataset and the results are reported as a useful performance baseline.
Fully Convolutional Networks for Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional networks are powerful visual models that yield hierarchies of features. We show that convolutional networks by themselves, trained end-to-end, pixels-to-pixels, improve on the previous best result in semantic segmentation. Our key insight is to build "fully convolutional" networks that take input of arbitrary size and produce correspondingly-sized output with efficient inference and learning. We define and detail the space of fully convolutional networks, explain their application to spatially dense prediction tasks, and draw connections to prior models. We adapt contemporary classification networks (AlexNet, the VGG net, and GoogLeNet) into fully convolutional networks and transfer their learned representations by fine-tuning to the segmentation task. We then define a skip architecture that combines semantic information from a deep, coarse layer with appearance information from a shallow, fine layer to produce accurate and detailed segmentations. Our fully convolutional network achieves improved segmentation of PASCAL VOC (30% relative improvement to 67.2% mean IU on 2012), NYUDv2, SIFT Flow, and PASCAL-Context, while inference takes one tenth of a second for a typical image.