OpenRaiser/Intern-Atlas huggingface dataset:
A Synergistic Approach for Recovering Occlusion-Free Textured 3D Maps of Urban Facades from Heterogeneous Cartographic Data
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we present a practical approach for generating an occlusion-free textured 3D map of urban facades by the synergistic use of terrestrial images, 3D point clouds and area-based information. Particularly in dense urban environments, the high presence of urban objects in front of the facades causes significant difficulties for several stages in computational building modeling. Major challenges lie on the one hand in extracting complete 3D facade quadrilateral delimitations and on the other hand in generating occlusion-free facade textures. For these reasons, we describe a straightforward approach for completing and recovering facade geometry and textures by exploiting the data complementarity of terrestrial multi-source imagery and area-based information.
Detecting wheels
Venue: arXiv cs.DM 2013
Year: 2013

A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph $G$ and whose question is "does $G$ contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems.
Coloring perfect graphs with no balanced skew-partitions
Venue: arXiv cs.DM 2013
Year: 2013

We present an $O(n^5)$ algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present $O(n^7)$ time algorithm that colors them.
Localizability of Wireless Sensor Networks: Beyond Wheel Extension
Venue: arXiv cs.DC 2013
Year: 2013

A network is called localizable if the positions of all the nodes of the network can be computed uniquely. If a network is localizable and embedded in plane with generic configuration, the positions of the nodes may be computed uniquely in finite time. Therefore, identifying localizable networks is an important function. If the complete information about the network is available at a single place, localizability can be tested in polynomial time. In a distributed environment, networks with trilateration orderings (popular in real applications) and wheel extensions (a specific class of localizable networks) embedded in plane can be identified by existing techniques. We propose a distributed technique which efficiently identifies a larger class of localizable networks. This class covers both trilateration and wheel extensions. In reality, exact distance is almost impossible or costly. The proposed algorithm based only on connectivity information. It requires no distance information.
Integer-Forcing Source Coding
Venue: arXiv cs.IT 2013
Year: 2013

Integer-Forcing (IF) is a new framework, based on compute-and-forward, for decoding multiple integer linear combinations from the output of a Gaussian multiple-input multiple-output channel. This work applies the IF approach to arrive at a new low-complexity scheme, IF source coding, for distributed lossy compression of correlated Gaussian sources under a minimum mean squared error distortion measure. All encoders use the same nested lattice codebook. Each encoder quantizes its observation using the fine lattice as a quantizer and reduces the result modulo the coarse lattice, which plays the role of binning. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. In general, the linear combinations have smaller average powers than the original signals. This allows to increase the density of the coarse lattice, which in turn translates to smaller compression rates. We also propose and analyze a one-shot version of IF source coding, that is simple enough to potentially lead to a new design principle for analog-to-digital converters that can exploit spatial correlations between the sampled signals.
Cross-Correlation of Photovoltaic Output Fluctuation in Power System Operation for Large-Scale Photovoltaic Integration
Venue: arXiv cs.SY 2013
Year: 2013

We analyzed the cross-correlation of Photovoltaic (PV) output fluctuation for the actual PV output time series data in both the Tokyo area and the whole of Japan using the principal component analysis with the random matrix theory. Based on the obtained cross-correlation coefficients, the forecast error for PV output was estimated with/without considering the cross-correlations. Then operation schedule of thermal plants is calculated to integrate PV output using our unit commitment model with the estimated forecast error. The cost for grid integration of PV system was also estimated. Finally, validity of the concept of "local production for local consumption of renewable energy" and alternative policy implications were also discussed.
Benchmarking Summarizability Processing in XML Warehouses with Complex Hierarchies
Venue: arXiv cs.DB 2013
Year: 2013

Business Intelligence plays an important role in decision making. Based on data warehouses and Online Analytical Processing, a business intelligence tool can be used to analyze complex data. Still, summarizability issues in data warehouses cause ineffective analyses that may become critical problems to businesses. To settle this issue, many researchers have studied and proposed various solutions, both in relational and XML data warehouses. However, they find difficulty in evaluating the performance of their proposals since the available benchmarks lack complex hierarchies. In order to contribute to summarizability analysis, this paper proposes an extension to the XML warehouse benchmark (XWeB) with complex hierarchies. The benchmark enables us to generate XML data warehouses with scalable complex hierarchies as well as summarizability processing. We experimentally demonstrated that complex hierarchies can definitely be included into a benchmark dataset, and that our benchmark is able to compare two alternative approaches dealing with summarizability issues.
Discriminative Parameter Estimation for Random Walks Segmentation
Venue: arXiv cs.CV 2013
Year: 2013

The Random Walks (RW) algorithm is one of the most e - cient and easy-to-use probabilistic segmentation methods. By combining contrast terms with prior terms, it provides accurate segmentations of medical images in a fully automated manner. However, one of the main drawbacks of using the RW algorithm is that its parameters have to be hand-tuned. we propose a novel discriminative learning framework that estimates the parameters using a training dataset. The main challenge we face is that the training samples are not fully supervised. Speci cally, they provide a hard segmentation of the images, instead of a proba- bilistic segmentation. We overcome this challenge by treating the opti- mal probabilistic segmentation that is compatible with the given hard segmentation as a latent variable. This allows us to employ the latent support vector machine formulation for parameter estimation. We show that our approach signi cantly outperforms the baseline methods on a challenging dataset consisting of real clinical 3D MRI volumes of skeletal muscles.
A Hypergraph-Partitioned Vertex Programming Approach for Large-scale Consensus Optimization
Venue: arXiv cs.AI 2013
Year: 2013

In modern data science problems, techniques for extracting value from big data require performing large-scale optimization over heterogenous, irregularly structured data. Much of this data is best represented as multi-relational graphs, making vertex programming abstractions such as those of Pregel and GraphLab ideal fits for modern large-scale data analysis. In this paper, we describe a vertex-programming implementation of a popular consensus optimization technique known as the alternating direction of multipliers (ADMM). ADMM consensus optimization allows elegant solution of complex objectives such as inference in rich probabilistic models. We also introduce a novel hypergraph partitioning technique that improves over state-of-the-art partitioning techniques for vertex programming and significantly reduces the communication cost by reducing the number of replicated nodes up to an order of magnitude. We implemented our algorithm in GraphLab and measure scaling performance on a variety of realistic bipartite graph distributions and a large synthetic voter-opinion analysis application. In our experiments, we are able to achieve a 50% improvement in runtime over the current state-of-the-art GraphLab partitioning scheme.
Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms
Venue: arXiv cs.DS 2013
Year: 2013

We consider several combinatorial optimization problems which combine the classic shop scheduling problems, namely open shop scheduling or job shop scheduling, and the shortest path problem. The objective of the obtained problem is to select a subset of jobs that forms a feasible solution of the shortest path problem, and to execute the selected jobs on the open (or job) shop machines to minimize the makespan. We show that these problems are NP-hard even if the number of machines is two, and cannot be approximated within a factor less than 2 if the number of machines is an input unless P=NP. We present several approximation algorithms for these combination problems.
Information filtering via hybridization of similarity preferential diffusion processes
Venue: arXiv cs.IR 2013
Year: 2013

The recommender system is one of the most promising ways to address the information overload problem in online systems. Based on the personal historical record, the recommender system can find interesting and relevant objects for the user within a huge information space. Many physical processes such as the mass diffusion and heat conduction have been applied to design the recommendation algorithms. The hybridization of these two algorithms has been shown to provide both accurate and diverse recommendation results. In this paper, we proposed two similarity preferential diffusion processes. Extensive experimental analyses on two benchmark data sets demonstrate that both recommendation and accuracy and diversity are improved duet to the similarity preference in the diffusion. The hybridization of the similarity preferential diffusion processes is shown to significantly outperform the state-of-art recommendation algorithm. Finally, our analysis on network sparsity show that there is significant difference between dense and sparse system, indicating that all the former conclusions on recommendation in the literature should be reexamined in sparse system.
People Are the Answer to Security: Establishing a Sustainable Information Security Awareness Training (ISAT) Program in Organization
Venue: arXiv cs.CY 2013
Year: 2013

Educating the users on the essential of information security is very vital and important to the mission of establishing a sustainable information security in any organization and institute. At the University Technology Malaysia (UTM), we have recognized the fact that, it is about time information security should no longer be a lacking factor in productivity, both information security and productivity must work together in closed proximity. We have recently implemented a broad campus information security awareness program to educate faculty member, staff, students and non-academic staff on this essential topic of information security. The program consists of training based on web, personal or individual training with a specific monthly topic, campus campaigns, guest speakers and direct presentations to specialized groups. The goal and the objective are to educate the users on the challenges that are specific to information security and to create total awareness that will change the perceptions of people thinking and ultimately their reactions when it comes to information security. In this paper, we explain how we created and implemented our information security awareness training (ISAT) program and discuss the impediment we encountered along the process. We explore different methods of deliveries such as target audiences, and probably the contents as we believe might be vital to a successful information security program. Finally, we discuss the importance and the flexibility of establishing a sustainable information security training program that could be adopted to meet current and future needs and demands while still relevant to our current users.
Optimizing the MapReduce Framework on Intel Xeon Phi Coprocessor
Venue: arXiv cs.DC 2013
Year: 2013

With the ease-of-programming, flexibility and yet efficiency, MapReduce has become one of the most popular frameworks for building big-data applications. MapReduce was originally designed for distributed-computing, and has been extended to various architectures, e,g, multi-core CPUs, GPUs and FPGAs. In this work, we focus on optimizing the MapReduce framework on Xeon Phi, which is the latest product released by Intel based on the Many Integrated Core Architecture. To the best of our knowledge, this is the first work to optimize the MapReduce framework on the Xeon Phi. In our work, we utilize advanced features of the Xeon Phi to achieve high performance. In order to take advantage of the SIMD vector processing units, we propose a vectorization friendly technique for the map phase to assist the auto-vectorization as well as develop SIMD hash computation algorithms. Furthermore, we utilize MIMD hyper-threading to pipeline the map and reduce to improve the resource utilization. We also eliminate multiple local arrays but use low cost atomic operations on the global array for some applications, which can improve the thread scalability and data locality due to the coherent L2 caches. Finally, for a given application, our framework can either automatically detect suitable techniques to apply or provide guideline for users at compilation time. We conduct comprehensive experiments to benchmark the Xeon Phi and compare our optimized MapReduce framework with a state-of-the-art multi-core based MapReduce framework (Phoenix++). By evaluating six real-world applications, the experimental results show that our optimized framework is 1.2X to 38X faster than Phoenix++ for various applications on the Xeon Phi.
A Verifiable and Correct-by-Construction Controller for Robot Functional Levels
Venue: arXiv cs.RO 2013
Year: 2013

Autonomous robots are complex systems that require the interaction and cooperation between numerous heterogeneous software components. In recent times, robots are being increasingly used for complex and safety-critical tasks, such as exploring Mars and assisting/replacing humans. Consequently, robots are becoming critical systems that must meet safety properties, in particular, logical, temporal and real-time constraints. To this end, we present an evolution of the LAAS architecture for autonomous systems, in particular its GenoM tool. This evolution relies on the BIP component-based design framework, which has been successfully used in other domains such as embedded systems. We show how we integrate BIP into our existing methodology for developing the lowest (functional) level of robots. Particularly, we discuss the componentization of the functional level, the synthesis of an execution controller for it, and how we verify whether the resulting functional level conforms to properties such as deadlock-freedom. We also show through experimentation that the verification is feasible and usable for complex, real world robotic systems, and that the BIP-based functional levels resulting from our new methodology are, despite an overhead during execution, still practical on real world robotic platforms. Our approach has been fully implemented in the LAAS architecture, and the implementation has been used in several experiments on a real robot.
Threefold Post Correspondence System
Venue: arXiv cs.CC 2013
Year: 2013

We introduce the concept of a threefold Post correspondence system (3PCS for short) and we consider it as an instance of the threefold Post correspondence problem. With each 3PCS, we associate three Post correspondence systems, i.e., three instances of the Post correspondence problem. We conjecture that for each 3PCS, the question of the threefold Post correspondence problem or for some associated Post correspondence system the question of the Post correspondence problem is decidable.
Strip Planarity Testing of Embedded Planar Graphs
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph $G(V,E)$ and a function $γ:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is monotone in the $y$-direction and, for any $u,v\in V$ with $γ(u)<γ(v)$, it holds $y(u)<y(v)$. The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if $G$ has a fixed planar embedding.
On the Robustness of Temporal Properties for Stochastic Models
Venue: arXiv cs.LO 2013
Year: 2013

Stochastic models such as Continuous-Time Markov Chains (CTMC) and Stochastic Hybrid Automata (SHA) are powerful formalisms to model and to reason about the dynamics of biological systems, due to their ability to capture the stochasticity inherent in biological processes. A classical question in formal modelling with clear relevance to biological modelling is the model checking problem. i.e. calculate the probability that a behaviour, expressed for instance in terms of a certain temporal logic formula, may occur in a given stochastic process. However, one may not only be interested in the notion of satisfiability, but also in the capacity of a system to mantain a particular emergent behaviour unaffected by the perturbations, caused e.g. from extrinsic noise, or by possible small changes in the model parameters. To address this issue, researchers from the verification community have recently proposed several notions of robustness for temporal logic providing suitable definitions of distance between a trajectory of a (deterministic) dynamical system and the boundaries of the set of trajectories satisfying the property of interest. The contributions of this paper are twofold. First, we extend the notion of robustness to stochastic systems, showing that this naturally leads to a distribution of robustness scores. By discussing two examples, we show how to approximate the distribution of the robustness score and its key indicators: the average robustness and the conditional average robustness. Secondly, we show how to combine these indicators with the satisfaction probability to address the system design problem, where the goal is to optimize some control parameters of a stochastic model in order to best maximize robustness of the desired specifications.
A hybrid mammalian cell cycle model
Venue: arXiv cs.CE 2013
Year: 2013

Hybrid modeling provides an effective solution to cope with multiple time scales dynamics in systems biology. Among the applications of this method, one of the most important is the cell cycle regulation. The machinery of the cell cycle, leading to cell division and proliferation, combines slow growth, spatio-temporal re-organisation of the cell, and rapid changes of regulatory proteins concentrations induced by post-translational modifications. The advancement through the cell cycle comprises a well defined sequence of stages, separated by checkpoint transitions. The combination of continuous and discrete changes justifies hybrid modelling approaches to cell cycle dynamics. We present a piecewise-smooth version of a mammalian cell cycle model, obtained by hybridization from a smooth biochemical model. The approximate hybridization scheme, leading to simplified reaction rates and binary event location functions, is based on learning from a training set of trajectories of the smooth model. We discuss several learning strategies for the parameters of the hybrid model.
Producing a Set of Models for the Iron Homeostasis Network
Venue: arXiv cs.CE 2013
Year: 2013

This paper presents a method for modeling biological systems which combines formal techniques on intervals, numerical simulations and satisfaction of Signal Temporal Logic (STL) formulas. The main modeling challenge addressed by this approach is the large uncertainty in the values of the parameters due to the experimental difficulties of getting accurate biological data. This method considers intervals for each parameter and a formal description of the expected behavior of the model. In a first step, it produces reduced intervals of possible parameter values. Then by performing a systematic search in these intervals, it defines sets of parameter values used in the next step. This procedure aims at finding a sub-space where the model robustly behaves as expected. We apply this method to the modeling of the cellular iron homeostasis network in erythroid progenitors. The produced model describes explicitly the regulation mechanism which acts at the translational level.
A Hybrid Model of a Genetic Regulatory Network in Mammalian Sclera
Venue: arXiv cs.SY 2013
Year: 2013

Myopia in human and animals is caused by the axial elongation of the eye and is closely linked to the thinning of the sclera which supports the eye tissue. This thinning has been correlated with the overproduction of matrix metalloproteinase (MMP-2), an enzyme that degrades the collagen structure of the sclera. In this short paper, we propose a descriptive model of a regulatory network with hysteresis, which seems necessary for creating oscillatory behavior in the hybrid model between MMP-2, MT1-MMP and TIMP-2. Numerical results provide insight on the type of equilibria present in the system.
Shortest Paths in Microseconds
Venue: arXiv cs.DC 2013
Year: 2013

Computing shortest paths is a fundamental primitive for several social network applications including socially-sensitive ranking, location-aware search, social auctions and social network privacy. Since these applications compute paths in response to a user query, the goal is to minimize latency while maintaining feasible memory requirements. We present ASAP, a system that achieves this goal by exploiting the structure of social networks. ASAP preprocesses a given network to compute and store a partial shortest path tree (PSPT) for each node. The PSPTs have the property that for any two nodes, each edge along the shortest path is with high probability contained in the PSPT of at least one of the nodes. We show that the structure of social networks enable the PSPT of each node to be an extremely small fraction of the entire network; hence, PSPTs can be stored efficiently and each shortest path can be computed extremely quickly. For a real network with 5 million nodes and 69 million edges, ASAP computes a shortest path for most node pairs in less than 49 microseconds per pair. ASAP, unlike any previous technique, also computes hundreds of paths (along with corresponding distances) between any node pair in less than 100 microseconds. Finally, ASAP admits efficient implementation on distributed programming frameworks like MapReduce.
From Branching to Linear Time, Coalgebraically
Venue: arXiv cs.LO 2013
Year: 2013

We consider state-based systems modelled as coalgebras whose type incorporates branching, and show that by suitably adapting the definition of coalgebraic bisimulation, one obtains a general and uniform account of the linear-time behaviour of a state in such a coalgebra. By moving away from a boolean universe of truth values, our approach can measure the extent to which a state in a system with branching is able to exhibit a particular linear-time behaviour. This instantiates to measuring the probability of a specific behaviour occurring in a probabilistic system, or measuring the minimal cost of exhibiting a specific behaviour in the case of weighted computations.