OpenRaiser/Intern-Atlas huggingface dataset:
Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array
Venue: arXiv cs.DS 2016
Year: 2016

The longest common prefix (LCP) array is a versatile auxiliary data structure in indexed string matching. It can be used to speed up searching using the suffix array (SA) and provides an implicit representation of the topology of an underlying suffix tree. The LCP array of a string of length $n$ can be represented as an array of length $n$ words, or, in the presence of the SA, as a bit vector of $2n$ bits plus asymptotically negligible support data structures. External memory construction algorithms for the LCP array have been proposed, but those proposed so far have a space requirement of $O(n)$ words (i.e. $O(n \log n)$ bits) in external memory. This space requirement is in some practical cases prohibitively expensive. We present an external memory algorithm for constructing the $2n$ bit version of the LCP array which uses $O(n \log σ)$ bits of additional space in external memory when given a (compressed) BWT with alphabet size $σ$ and a sampled inverse suffix array at sampling rate $O(\log n)$. This is often a significant space gain in practice where $σ$ is usually much smaller than $n$ or even constant. We also consider the case of computing succinct LCP arrays for circular strings.
Auto-Tuning Dedispersion for Many-Core Accelerators
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, we study the parallelization of the dedispersion algorithm on many-core accelerators, including GPUs from AMD and NVIDIA, and the Intel Xeon Phi. An important contribution is the computational analysis of the algorithm, from which we conclude that dedispersion is inherently memory-bound in any realistic scenario, in contrast to earlier reports. We also provide empirical proof that, even in unrealistic scenarios, hardware limitations keep the arithmetic intensity low, thus limiting performance. We exploit auto-tuning to adapt the algorithm, not only to different accelerators, but also to different observations, and even telescopes. Our experiments show how the algorithm is tuned automatically for different scenarios and how it exploits and highlights the underlying specificities of the hardware: in some observations, the tuner automatically optimizes device occupancy, while in others it optimizes memory bandwidth. We quantitatively analyze the problem space, and by comparing the results of optimal auto-tuned versions against the best performing fixed codes, we show the impact that auto-tuning has on performance, and conclude that it is statistically relevant.
A Theory of Local Matching: SIFT and Beyond
Venue: arXiv cs.CV 2016
Year: 2016

Why has SIFT been so successful? Why its extension, DSP-SIFT, can further improve SIFT? Is there a theory that can explain both? How can such theory benefit real applications? Can it suggest new algorithms with reduced computational complexity or new descriptors with better accuracy for matching? We construct a general theory of local descriptors for visual matching. Our theory relies on concepts in energy minimization and heat diffusion. We show that SIFT and DSP-SIFT approximate the solution the theory suggests. In particular, DSP-SIFT gives a better approximation to the theoretical solution; justifying why DSP-SIFT outperforms SIFT. Using the developed theory, we derive new descriptors that have fewer parameters and are potentially better in handling affine deformations.
Factors in Finetuning Deep Model for object detection
Venue: arXiv cs.CV 2016
Year: 2016

Finetuning from a pretrained deep model is found to yield state-of-the-art performance for many vision tasks. This paper investigates many factors that influence the performance in finetuning for object detection. There is a long-tailed distribution of sample numbers for classes in object detection. Our analysis and empirical results show that classes with more samples have higher impact on the feature learning. And it is better to make the sample number more uniform across classes. Generic object detection can be considered as multiple equally important tasks. Detection of each class is a task. These classes/tasks have their individuality in discriminative visual appearance representation. Taking this individuality into account, we cluster objects into visually similar class groups and learn deep representations for these groups separately. A hierarchical feature learning scheme is proposed. In this scheme, the knowledge from the group with large number of classes is transferred for learning features in its sub-groups. Finetuned on the GoogLeNet model, experimental results show 4.7% absolute mAP improvement of our approach on the ImageNet object detection dataset without increasing much computational cost at the testing stage.
Data-Driven Modeling, Control and Tools for Cyber-Physical Energy Systems
Venue: arXiv cs.SY 2016
Year: 2016

Demand response (DR) is becoming increasingly important as the volatility on the grid continues to increase. Current DR approaches are completely manual and rule-based or involve deriving first principles based models which are extremely cost and time prohibitive to build. We consider the problem of data-driven end-user DR for large buildings which involves predicting the demand response baseline, evaluating fixed rule based DR strategies and synthesizing DR control actions. We provide a model based control with regression trees algorithm (mbCRT), which allows us to perform closed-loop control for DR strategy synthesis for large commercial buildings. Our data-driven control synthesis algorithm outperforms rule-based DR by $17\%$ for a large DoE commercial reference building and leads to a curtailment of $380$kW and over $\$45,000$ in savings. Our methods have been integrated into an open source tool called DR-Advisor, which acts as a recommender system for the building's facilities manager and provides suitable control actions to meet the desired load curtailment while maintaining operations and maximizing the economic reward. DR-Advisor achieves $92.8\%$ to $98.9\%$ prediction accuracy for 8 buildings on Penn's campus. We compare DR-Advisor with other data driven methods and rank $2^{nd}$ on ASHRAE's benchmarking data-set for energy prediction.
Dynamic Intransitive Noninterference Revisited
Venue: arXiv cs.CR 2016
Year: 2016

The paper studies dynamic information flow security policies in an automaton-based model. Two semantic interpretations of such policies are developed, both of which generalize the notion of TA-security [van der Meyden ESORICS 2007] for static intransitive noninterference policies. One of the interpretations focuses on information flows permitted by policy edges, the other focuses on prohibitions implied by absence of policy edges. In general, the two interpretations differ, but necessary and sufficient conditions are identified for the two interpretations to be equivalent. Sound and complete proof techniques are developed for both interpretations. Two applications of the theory are presented. The first is a general result showing that access control mechanisms are able to enforce a dynamic information flow policy. The second is a simple capability system motivated by the Flume operating system.
A note on Edge Isoperimetric Numbers and Regular Graphs
Venue: arXiv cs.DM 2016
Year: 2016

This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
Global multi-layer network of human mobility
Venue: arXiv cs.SI 2016
Year: 2016

Recent availability of geo-localized data capturing individual human activity together with the statistical data on international migration opened up unprecedented opportunities for a study on global mobility. In this paper we consider it from the perspective of a multi-layer complex network, built using a combination of three datasets: Twitter, Flickr and official migration data. Those datasets provide different but equally important insights on the global mobility: while the first two highlight short-term visits of people from one country to another, the last one - migration - shows the long-term mobility perspective, when people relocate for good. And the main purpose of the paper is to emphasize importance of this multi-layer approach capturing both aspects of human mobility at the same time. So we start from a comparative study of the network layers, comparing short- and long- term mobility through the statistical properties of the corresponding networks, such as the parameters of their degree centrality distributions or parameters of the corresponding gravity model being fit to the network. We also focus on the differences in country ranking by their short- and long-term attractiveness, discussing the most noticeable outliers. Finally, we apply this multi-layered human mobility network to infer the structure of the global society through a community detection approach and demonstrate that consideration of mobility from a multi-layer perspective can reveal important global spatial patterns in a way more consistent with other available relevant sources of international connections, in comparison to the spatial structure inferred from each network layer taken separately.
On the Diagnostic of Road Pathway Visibility
Venue: arXiv cs.CV 2016
Year: 2016

Visibility distance on the road pathway plays a significant role in road safety and in particular, has a clear impact on the choice of speed limits. Visibility distance is thus of importance for road engineers and authorities. While visibility distance criteria are routinely taken into account in road design, only a few systems exist for estimating it on existing road networks. Most existing systems comprise a target vehicle followed at a constant distance by an observer vehicle, which only allows to check if a given, fixed visibility distance is available. We propose two new approaches that allow estimating the maximum available visibility distance, involving only one vehicle and based on different sensor technologies, namely binocular stereovision and 3D range sensing (LIDAR). The first approach is based on the processing of two views taken by digital cameras onboard the diagnostic vehicle. The main stages of the process are: road segmentation, edge registration between the two views, road profile 3D reconstruction and finally, maximal road visibility distance estimation. The second approach involves the use of a Terrestrial LIDAR Mobile Mapping System. The triangulated 3D model of the road and its surroundings provided by the system is used to simulate targets at different distances, which allows estimating the maximum geometric visibility distance along the pathway. These approaches were developed in the context of the SARI-VIZIR PREDIT project. Both approaches are described, evaluated and compared. Their pros and cons with respect to vehicle following systems are also discussed.
A New Approach for Testing Properties of Discrete Distributions
Venue: arXiv cs.DS 2016
Year: 2016

In this work, we give a novel general approach for distribution testing. We describe two techniques: our first technique gives sample-optimal testers, while our second technique gives matching sample lower bounds. As a consequence, we resolve the sample complexity of a wide variety of testing problems. Our upper bounds are obtained via a modular reduction-based approach. Our approach yields optimal testers for numerous problems by using a standard $\ell_2$-identity tester as a black-box. Using this recipe, we obtain simple estimators for a wide range of problems, encompassing most problems previously studied in the TCS literature, namely: (1) identity testing to a fixed distribution, (2) closeness testing between two unknown distributions (with equal/unequal sample sizes), (3) independence testing (in any number of dimensions), (4) closeness testing for collections of distributions, and (5) testing histograms. For all of these problems, our testers are sample-optimal, up to constant factors. With the exception of (1), ours are the {\em first sample-optimal testers for the corresponding problems.} Moreover, our estimators are significantly simpler to state and analyze compared to previous results. As an application of our reduction-based technique, we obtain the first {\em nearly instance-optimal} algorithm for testing equivalence between two {\em unknown} distributions. Moreover, our technique naturally generalizes to other metrics beyond the $\ell_1$-distance. Our lower bounds are obtained via a direct information-theoretic approach: Given a candidate hard instance, our proof proceeds by bounding the mutual information between appropriate random variables. While this is a classical method in information theory, prior to our work, it had not been used in distribution property testing.
B-spline Shape from Motion & Shading: An Automatic Free-form Surface Modeling for Face Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

Recently, many methods have been proposed for face reconstruction from multiple images, most of which involve fundamental principles of Shape from Shading and Structure from motion. However, a majority of the methods just generate discrete surface model of face. In this paper, B-spline Shape from Motion and Shading (BsSfMS) is proposed to reconstruct continuous B-spline surface for multi-view face images, according to an assumption that shading and motion information in the images contain 1st- and 0th-order derivative of B-spline face respectively. Face surface is expressed as a B-spline surface that can be reconstructed by optimizing B-spline control points. Therefore, normals and 3D feature points computed from shading and motion of images respectively are used as the 1st- and 0th- order derivative information, to be jointly applied in optimizing the B-spline face. Additionally, an IMLS (iterative multi-least-square) algorithm is proposed to handle the difficult control point optimization. Furthermore, synthetic samples and LFW dataset are introduced and conducted to verify the proposed approach, and the experimental results demonstrate the effectiveness with different poses, illuminations, expressions etc., even with wild images.
Exponent Function for Source Coding with Side Information at the Decoder at Rates below the Rate Distortion Function
Venue: arXiv cs.IT 2016
Year: 2016

We consider the rate distortion problem with side information at the decoder posed and investigated by Wyner and Ziv. The rate distortion function indicating the trade-off between the rate on the data compression and the quality of data obtained at the decoder was determined by Wyner and Ziv. In this paper, we study the error probability of decoding at rates below the rate distortion function. We evaluate the probability of decoding such that the estimation of source outputs by the decoder has a distortion not exceeding a prescribed distortion level. We prove that when the rate of the data compression is below the rate distortion function this probability goes to zero exponentially and derive an explicit lower bound of this exponent function. On the Wyner-Ziv source coding problem the strong converse coding theorem has not been established yet. We prove this as a simple corollary of our result.
Diversifying Software Architecture for Sustainability: A Value-based Perspective
Venue: arXiv cs.SE 2016
Year: 2016

Although the concept of software diversity has been thoroughly adopted by software architects for many years, yet the advent of using diversity to achieve sustainability is overlooked. We argue that option thinking is an effective decision making tool to evaluate the trade-offs between architectural strategies and their long-term values under uncertainty. Our method extends cost-benefit analysis method CBAM. Unlike CBAM, our focus is on valuing the options which diversification can embed in the architecture and their corresponding value using real options pricing theory. The intuitive assumption is that the value of these options can provide the architect with insights on the long-term performance of these decisions in relation to some scenarios of interest and use them as the basis for reasoning about sustainability. The method aims to answer the following: (1) Is diversification of architectural decisions beneficial and when they can help in sustaining the software, (2) When, where and to what extent. The proposed model is illustrated and evaluated using a case study from the literature referred to as GridStix.
Applying a Differential Evolutionary Algorithm to a Constraint-based System to support Separation of OTDR Superimposed Signal after Passive Optical Network Splitters
Venue: arXiv cs.CE 2016
Year: 2016

The FTTH (Fiber To The Home) market currently needs new network maintenance technologies that can, economically and effectively, cope with massive fiber plants. However, operating these networks requires adequate means for an effective monitoring cost. Especially for troubleshooting faults that are associated with the possibility of remote identification of fiber breaks, which may exist in the network. Optical Time Domain Reflectometry (OTDR) techniques are widely used in point-to-point optical network topologies. Nevertheless, it has major limitations in tree-structured PONs (Passive Optical Networks), where all different branches backscatter the light in just one conventional OTDR trace with combined signals arriving on the OLT (Optical Line Terminal) side. Furthermore, passive power splitters used in FTTH networks input large attenuation, impoverishing the reflected signal. This makes the identification of the very branch affected by the problem practically impossible, when considering conventional analyses. The use of constraint-based techniques have been applied in a large amount of applications for Engineering Design, where the duties imposed for graphics and equations constraints result in valued features to CAD/CAE software capabilities. Currently, it provides a faster decision making capacity for engineers. This work applies the constraint based approach along with a Differential Evolutionary Algorithm to separate the superimposed OTDR signals, after the splitters of a FTTH Passive Optical Networks. This research introduces a new set of algorithms performing a coupling to an Optical Network (ON) CAD Design with its correspondent OTDR measurement signal, considering its geographical distribution branches of different lengths after the splitter. Results of this work are presented in a FTTN (Fiber To The Node) prototype arrangement, using a 1:8 passive power splitter.
Software Engineers' Attitudes Towards Organizational Change - an Industrial Case Study
Venue: arXiv cs.SE 2016
Year: 2016

In order to cope with a complex and changing environment, industries seek to find new and more efficient ways to conduct their business. According to previous research, many of these change efforts fail to achieve their intended aims. Researchers have therefore sought to identify factors that increase the likelihood of success and found that employees' attitude towards change is one of the most critical. The ability to manage change is especially important in software engineering organizations, where rapid changes in influential technologies and constantly evolving methodologies create a turbulent environment. Nevertheless, to the best of our knowledge, no studies exist that explore attitude towards change in a software engineering organization. In this case study, we have used industry data to examine if the knowledge about the intended change outcome, the understanding of the need for change, and the feelings of participation affect software engineers' openness to change and readiness for change respectively, two commonly used attitude constructs. The result of two separate multiple regression analysis showed that openness to change is predicted by all three concepts, while readiness for change is predicted by need for change and participation. In addition, our research also provides a hierarchy with respect to the three predictive constructs' degree of impact. Ultimately, our result can help managers in software engineering organizations to increase the likelihood of successfully implementing change initiatives that result in a changed organizational behavior. However, the first-order models we propose are to be recognized as early approximations that captures the most significant effects and should therefore, in future research, be extended to include additional software engineering unique factors.
Manifold-Kernels Comparison in MKPLS for Visual Speech Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Speech recognition is a challenging problem. Due to the acoustic limitations, using visual information is essential for improving the recognition accuracy in real-life unconstraint situations. One common approach is to model the visual recognition as nonlinear optimization problem. Measuring the distances between visual units is essential for solving this problem. Embedding the visual units on a manifold and using manifold kernels is one way to measure these distances. This work is intended to evaluate the performance of several manifold kernels for solving the problem of visual speech recognition. We show the theory behind each kernel. We apply manifold kernel partial least squares framework to OuluVs and AvLetters databases, and show empirical comparison between all kernels. This framework provides convenient way to explore different kernels.
A Review on Recent Active Vibration Control Techniques
Venue: arXiv cs.SY 2016
Year: 2016

Active vibration control has been introduced and used as one of the effective approaches to suppress unwanted vibrations in different systems. Effective performance of each vibration control method is contingent to accurate design and proper dynamics selection of the control unit. These methods have been extensively studied in various studies in recent years. Each of these new methods are designed by a specific dynamics for a specific system. Here in this paper, we aim to introduce some of these recent approaches in a brief discussion, and familiarize the readers with these techniques. Engineers who wish to design proper vibration controllers in different scales, from micro- to macro applications, will certainly design a more successful vibration controller if they know better about similar techniques, and they can implement the novelties that other scholars have utilized.