OpenRaiser/Intern-Atlas huggingface dataset:
Multi-View Video Packet Scheduling
Venue: arXiv cs.MM 2013
Year: 2013

In multiview applications, multiple cameras acquire the same scene from different viewpoints and generally produce correlated video streams. This results in large amounts of highly redundant data. In order to save resources, it is critical to handle properly this correlation during encoding and transmission of the multiview data. In this work, we propose a correlation-aware packet scheduling algorithm for multi-camera networks, where information from all cameras are transmitted over a bottleneck channel to clients that reconstruct the multiview images. The scheduling algorithm relies on a new rate-distortion model that captures the importance of each view in the scene reconstruction. We propose a problem formulation for the optimization of the packet scheduling policies, which adapt to variations in the scene content. Then, we design a low complexity scheduling algorithm based on a trellis search that selects the subset of candidate packets to be transmitted towards effective multiview reconstruction at clients. Extensive simulation results confirm the gain of our scheduling algorithm when inter-source correlation information is used in the scheduler, compared to scheduling policies with no information about the correlation or non-adaptive scheduling policies. We finally show that increasing the optimization horizon in the packet scheduling algorithm improves the transmission performance, especially in scenarios where the level of correlation rapidly varies with time.
Role Mining with Probabilistic Models
Venue: arXiv cs.CR 2013
Year: 2013

Role mining tackles the problem of finding a role-based access control (RBAC) configuration, given an access-control matrix assigning users to access permissions as input. Most role mining approaches work by constructing a large set of candidate roles and use a greedy selection strategy to iteratively pick a small subset such that the differences between the resulting RBAC configuration and the access control matrix are minimized. In this paper, we advocate an alternative approach that recasts role mining as an inference problem rather than a lossy compression problem. Instead of using combinatorial algorithms to minimize the number of roles needed to represent the access-control matrix, we derive probabilistic models to learn the RBAC configuration that most likely underlies the given matrix. Our models are generative in that they reflect the way that permissions are assigned to users in a given RBAC configuration. We additionally model how user-permission assignments that conflict with an RBAC configuration emerge and we investigate the influence of constraints on role hierarchies and on the number of assignments. In experiments with access-control matrices from real-world enterprises, we compare our proposed models with other role mining methods. Our results show that our probabilistic models infer roles that generalize well to new system users for a wide variety of data, while other models' generalization abilities depend on the dataset given.
On the Complexity of Joint Subcarrier and Power Allocation for Multi-User OFDMA Systems
Venue: arXiv cs.IT 2013
Year: 2013

Consider a multi-user Orthogonal Frequency Division Multiple Access (OFDMA) system where multiple users share multiple discrete subcarriers, but at most one user is allowed to transmit power on each subcarrier. To adapt fast traffic and channel fluctuations and improve the spectrum efficiency, the system should have the ability to dynamically allocate subcarriers and power resources to users. Assuming perfect channel knowledge, two formulations for the joint subcarrier and power allocation problem are considered in this paper: the first is to minimize the total transmission power subject to quality of service constraints and the OFDMA constraint, and the second is to maximize some system utility function (including the sum-rate utility, the proportional fairness utility, the harmonic mean utility, and the min-rate utility) subject to the total transmission power constraint per user and the OFDMA constraint. In spite of the existence of various heuristics approaches, little is known about the computational complexity status of the above problem. This paper aims to fill this theoretical gap, i.e., characterizing the complexity of the joint subcarrier and power allocation problem for the multi-user OFDMA system. It is shown in this paper that both formulations of the joint subcarrier and power allocation problem are strongly NP-hard. The proof is based on a polynomial time transformation from the so-called 3-dimensional matching problem. Several subclasses of the problem which can be solved to global optimality or $ε$-global optimality in polynomial time are also identified. These complexity results suggest that there are not polynomial time algorithms which are able to solve the general joint subcarrier and power allocation problem to global optimality (unless P$=$NP), and determining an approximately optimal subcarrier and power allocation strategy is more realistic in practice.
Adapting Voting Techniques for Online Forum Thread Retrieval
Venue: arXiv cs.IR 2013
Year: 2013

Online forums or message boards are rich knowledge-based communities. In these communities, thread retrieval is an essential tool facilitating information access. However, the issue on thread search is how to combine evidence from text units(messages) to estimate thread relevance. In this paper, we first rank a list of messages, then we score threads by aggregating their ranked messages' scores. To aggregate the message scores, we adopt several voting techniques that have been applied in ranking aggregates tasks such as blog distillation and expert finding. The experimental result shows that many voting techniques should be preferred over a baseline that treats a thread as a concatenation of its message texts.
Data complexity measured by principal graphs
Venue: arXiv cs.LG 2013
Year: 2013

How to measure the complexity of a finite set of vectors embedded in a multidimensional space? This is a non-trivial question which can be approached in many different ways. Here we suggest a set of data complexity measures using universal approximators, principal cubic complexes. Principal cubic complexes generalise the notion of principal manifolds for datasets with non-trivial topologies. The type of the principal cubic complex is determined by its dimension and a grammar of elementary graph transformations. The simplest grammar produces principal trees. We introduce three natural types of data complexity: 1) geometric (deviation of the data's approximator from some "idealized" configuration, such as deviation from harmonicity); 2) structural (how many elements of a principal graph are needed to approximate the data), and 3) construction complexity (how many applications of elementary graph transformations are needed to construct the principal object starting from the simplest one). We compute these measures for several simulated and real-life data distributions and show them in the "accuracy-complexity" plots, helping to optimize the accuracy/complexity ratio. We discuss various issues connected with measuring data complexity. Software for computing data complexity measures from principal cubic complexes is provided as well.
Blinking Molecule Tracking
Venue: arXiv cs.CV 2013
Year: 2013

We discuss a method for tracking individual molecules which globally optimizes the likelihood of the connections between molecule positions fast and with high reliability even for high spot densities and blinking molecules. Our method works with cost functions which can be freely chosen to combine costs for distances between spots in space and time and which can account for the reliability of positioning a molecule. To this end, we describe a top-down polyhedral approach to the problem of tracking many individual molecules. This immediately yields an effective implementation using standard linear programming solvers. Our method can be applied to 2D and 3D tracking.
Local Thresholding in General Network Graphs
Venue: arXiv cs.DC 2013
Year: 2013

Local thresholding algorithms were first presented more than a decade ago and have since been applied to a variety of data mining tasks in peer-to-peer systems, wireless sensor networks, and in grid systems. One critical assumption made by those algorithms has always been cycle-free routing. The existence of even one cycle may lead all peers to the wrong outcome. Outside the lab, unfortunately, cycle freedom is not easy to achieve. This work is the first to lift the requirement of cycle freedom by presenting a local thresholding algorithm suitable for general network graphs. The algorithm relies on a new repositioning of the problem in weighted vector arithmetics, on a new stopping rule, whose proof does not require that the network be cycle free, and on new methods for balance correction when the stopping rule fails. The new stopping and update rules permit calculation of the very same functions that were calculable using previous algorithms, which do assume cycle freedom. The algorithm is implemented on a standard peer-to-peer simulator and is validated for networks of up to 80,000 peers, organized in three different topologies, which are representative of the topology of major current distributed systems: the Internet, structured peer-to-peer systems, and wireless sensor networks.
Real and Complex Monotone Communication Games
Venue: arXiv cs.GT 2013
Year: 2013

Noncooperative game-theoretic tools have been increasingly used to study many important resource allocation problems in communications, networking, smart grids, and portfolio optimization. In this paper, we consider a general class of convex Nash Equilibrium Problems (NEPs), where each player aims to solve an arbitrary smooth convex optimization problem. Differently from most of current works, we do not assume any specific structure for the players' problems, and we allow the optimization variables of the players to be matrices in the complex domain. Our main contribution is the design of a novel class of distributed (asynchronous) best-response- algorithms suitable for solving the proposed NEPs, even in the presence of multiple solutions. The new methods, whose convergence analysis is based on Variational Inequality (VI) techniques, can select, among all the equilibria of a game, those that optimize a given performance criterion, at the cost of limited signaling among the players. This is a major departure from existing best-response algorithms, whose convergence conditions imply the uniqueness of the NE. Some of our results hinge on the use of VI problems directly in the complex domain; the study of these new kind of VIs also represents a noteworthy innovative contribution. We then apply the developed methods to solve some new generalizations of SISO and MIMO games in cognitive radios and femtocell systems, showing a considerable performance improvement over classical pure noncooperative schemes.
Partition Parameters for Girth Maximum (m, r) BTUs
Venue: arXiv cs.DM 2013
Year: 2013

This paper describes the calculation of the optimal partition parameters such that the girth maximum (m, r) Balanced Tanner Unit lies in family of BTUs specified by them using a series of proved results and thus creates a framework for specifying a search problem for finding the girth maximum (m, r) BTU. Several open questions for girth maximum (m, r) BTU have been raised.
Three-Element Min-Sol and Conservative Min-Cost-Hom
Venue: arXiv cs.CC 2013
Year: 2013

Thapper and Zivny [STOC'13] recently classified the complexity of VCSP for all finite-valued constraint languages. However, the complexity of VCSPs for constraint languages that are not finite-valued remains poorly understood. In this paper we study the complexity of two such VCSPs, namely Min-Cost-Hom and Min-Sol. We obtain a full classification for the complexity of Min-Sol on domains that contain at most three elements and for the complexity of conservative Min-Cost-Hom on arbitrary finite domains. Our results answer a question raised by Takhanov [STACS'10, COCOON'10].
Generating Property-Directed Potential Invariants By Backward Analysis
Venue: arXiv cs.LO 2013
Year: 2013

This paper addresses the issue of lemma generation in a k-induction-based formal analysis of transition systems, in the linear real/integer arithmetic fragment. A backward analysis, powered by quantifier elimination, is used to output preimages of the negation of the proof objective, viewed as unauthorized states, or gray states. Two heuristics are proposed to take advantage of this source of information. First, a thorough exploration of the possible partitionings of the gray state space discovers new relations between state variables, representing potential invariants. Second, an inexact exploration regroups and over-approximates disjoint areas of the gray state space, also to discover new relations between state variables. k-induction is used to isolate the invariants and check if they strengthen the proof objective. These heuristics can be used on the first preimage of the backward exploration, and each time a new one is output, refining the information on the gray states. In our context of critical avionics embedded systems, we show that our approach is able to outperform other academic or commercial tools on examples of interest in our application field. The method is introduced and motivated through two main examples, one of which was provided by Rockwell Collins, in a collaborative formal verification framework.
Property-based Code Slicing for Efficient Verification of OSEK/VDX Operating Systems
Venue: arXiv cs.SE 2013
Year: 2013

Testing is a de-facto verification technique in industry, but insufficient for identifying subtle issues due to its optimistic incompleteness. On the other hand, model checking is a powerful technique that supports comprehensiveness, and is thus suitable for the verification of safety-critical systems. However, it generally requires more knowledge and cost more than testing. This work attempts to take advantage of both techniques to achieve integrated and efficient verification of OSEK/VDX-based automotive operating systems. We propose property-based environment generation and model extraction techniques using static code analysis, which can be applied to both model checking and testing. The technique is automated and applied to an OSEK/VDX-based automotive operating system, Trampoline. Comparative experiments using random testing and model checking for the verification of assertions in the Trampoline kernel code show how our environment generation and abstraction approach can be utilized for efficient fault-detection.
MIMS: Towards a Message Interface based Memory System
Venue: arXiv cs.AR 2013
Year: 2013

Memory system is often the main bottleneck in chipmultiprocessor (CMP) systems in terms of latency, bandwidth and efficiency, and recently additionally facing capacity and power problems in an era of big data. A lot of research works have been done to address part of these problems, such as photonics technology for bandwidth, 3D stacking for capacity, and NVM for power as well as many micro-architecture level innovations. Many of them need a modification of current memory architecture, since the decades-old synchronous memory architecture (SDRAM) has become an obstacle to adopt those advances. However, to the best of our knowledge, none of them is able to provide a universal memory interface that is scalable enough to cover all these problems. In this paper, we argue that a message-based interface should be adopted to replace the traditional bus-based interface in memory system. A novel message interface based memory system (MIMS) is proposed. The key innovation of MIMS is that processor and memory system communicate through a universal and flexible message interface. Each message packet could contain multiple memory requests or commands along with various semantic information. The memory system is more intelligent and active by equipping with a local buffer scheduler, which is responsible to process packet, schedule memory requests, and execute specific commands with the help of semantic information. The experimental results by simulator show that, with accurate granularity message, the MIMS would improve performance by 53.21%, while reducing energy delay product (EDP) by 55.90%, the effective bandwidth utilization is improving by 62.42%. Furthermore, combining multiple requests in a packet would reduce link overhead and provide opportunity for address compression.
How to Understand LMMSE Transceiver Design for MIMO Systems From Quadratic Matrix Programming
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a unified linear minimum mean-square-error (LMMSE) transceiver design framework is investigated, which is suitable for a wide range of wireless systems. The unified design is based on an elegant and powerful mathematical programming technology termed as quadratic matrix programming (QMP). Based on QMP it can be observed that for different wireless systems, there are certain common characteristics which can be exploited to design LMMSE transceivers e.g., the quadratic forms. It is also discovered that evolving from a point-to-point MIMO system to various advanced wireless systems such as multi-cell coordinated systems, multi-user MIMO systems, MIMO cognitive radio systems, amplify-and-forward MIMO relaying systems and so on, the quadratic nature is always kept and the LMMSE transceiver designs can always be carried out via iteratively solving a number of QMP problems. A comprehensive framework on how to solve QMP problems is also given. The work presented in this paper is likely to be the first shoot for the transceiver design for the future ever-changing wireless systems.
Joint Iterative Power Allocation and Linear Interference Suppression Algorithms in Cooperative DS-CDMA Networks
Venue: arXiv cs.IT 2013
Year: 2013

This work presents joint iterative power allocation and interference suppression algorithms for spread spectrum networks which employ multiple hops and the amplify-and-forward cooperation strategy for both the uplink and the downlink. We propose a joint constrained optimization framework that considers the allocation of power levels across the relays subject to individual and global power constraints and the design of linear receivers for interference suppression. We derive constrained linear minimum mean-squared error (MMSE) expressions for the parameter vectors that determine the optimal power levels across the relays and the linear receivers. In order to solve the proposed optimization problems, we develop cost-effective algorithms for adaptive joint power allocation, and estimation of the parameters of the receiver and the channels. An analysis of the optimization problem is carried out and shows that the problem can have its convexity enforced by an appropriate choice of the power constraint parameter, which allows the algorithms to avoid problems with local minima. A study of the complexity and the requirements for feedback channels of the proposed algorithms is also included for completeness. Simulation results show that the proposed algorithms obtain significant gains in performance and capacity over existing non-cooperative and cooperative schemes.
2D Lyndon Words and Applications
Venue: arXiv cs.DS 2013
Year: 2013

A Lyndon word is a primitive string which is lexicographically smallest among cyclic permutations of its characters. Lyndon words are used for constructing bases in free Lie algebras, constructing de Bruijn sequences, finding the lexicographically smallest or largest substring in a string, and succinct suffix-prefix matching of highly periodic strings. In this paper, we extend the concept of the Lyndon word to two dimensions. We introduce the 2D Lyndon word and use it to capture 2D horizontal periodicity of a matrix in which each row is highly periodic, and to efficiently solve 2D horizontal suffix-prefix matching among a set of patterns. This yields a succinct and efficient algorithm for 2D dictionary matching. We present several algorithms that compute the 2D Lyndon word that represents a matrix. The final algorithm achieves linear time complexity even when the least common multiple of the periods of the rows is exponential in the matrix width.
A Semi-automated Statistical Algorithm for Object Separation
Venue: arXiv cs.CV 2013
Year: 2013

We explicate a semi-automated statistical algorithm for object identification and segregation in both gray scale and color images. The algorithm makes optimal use of the observation that definite objects in an image are typically represented by pixel values having narrow Gaussian distributions about characteristic mean values. Furthermore, for visually distinct objects, the corresponding Gaussian distributions have negligible overlap with each other and hence the Mahalanobis distance between these distributions are large. These statistical facts enable one to sub-divide images into multiple thresholds of variable sizes, each segregating similar objects. The procedure incorporates the sensitivity of human eye to the gray pixel values into the variable threshold size, while mapping the Gaussian distributions into localized δ-functions, for object separation. The effectiveness of this recursive statistical algorithm is demonstrated using a wide variety of images.
Capturing Sensor Data from Mobile Phones using Global Sensor Network Middleware
Venue: arXiv cs.NI 2013
Year: 2013

Mobile phones play increasingly bigger role in our everyday lives. Today, most smart phones comprise a wide variety of sensors which can sense the physical environment. The Internet of Things vision encompasses participatory sensing which is enabled using mobile phones based sensing and reasoning. In this research, we propose and demonstrate our DAM4GSN architecture to capture sensor data using sensors built into the mobile phones. Specifically, we combine an open source sensor data stream processing engine called 'Global Sensor Network (GSN)' with the Android platform to capture sensor data. To achieve this goal, we proposed and developed a prototype application that can be installed on Android devices as well as a AndroidWrapper as a GSN middleware component. The process and the difficulty of manually connecting sensor devices to sensor data processing middleware systems are examined. We evaluated the performance of the system based on power consumption of the mobile client.
A Novel Design Specification Distance(DSD) Based K-Mean Clustering Performace Evluation on Engineering Materials Database
Venue: arXiv cs.LG 2013
Year: 2013

Organizing data into semantically more meaningful is one of the fundamental modes of understanding and learning. Cluster analysis is a formal study of methods for understanding and algorithm for learning. K-mean clustering algorithm is one of the most fundamental and simple clustering algorithms. When there is no prior knowledge about the distribution of data sets, K-mean is the first choice for clustering with an initial number of clusters. In this paper a novel distance metric called Design Specification (DS) distance measure function is integrated with K-mean clustering algorithm to improve cluster accuracy. The K-means algorithm with proposed distance measure maximizes the cluster accuracy to 99.98% at P = 1.525, which is determined through the iterative procedure. The performance of Design Specification (DS) distance measure function with K - mean algorithm is compared with the performances of other standard distance functions such as Euclidian, squared Euclidean, City Block, and Chebshew similarity measures deployed with K-mean algorithm.The proposed method is evaluated on the engineering materials database. The experiments on cluster analysis and the outlier profiling show that these is an excellent improvement in the performance of the proposed method.