OpenRaiser/Intern-Atlas huggingface dataset:
Fluid Flow Complexity in Fracture Networks: Analysis with Graph Theory and LBM
Venue: arXiv cs.CE 2012
Year: 2012

Through this research, embedded synthetic fracture networks in rock masses are studied. To analysis the fluid flow complexity in fracture networks with respect to the variation of connectivity patterns, two different approaches are employed, namely, the Lattice Boltzmann method and graph theory. The Lattice Boltzmann method is used to show the sensitivity of the permeability and fluid velocity distribution to synthetic fracture networks' connectivity patterns. Furthermore, the fracture networks are mapped into the graphs, and the characteristics of these graphs are compared to the main spatial fracture networks. Among different characteristics of networks, we distinguish the modularity of networks and sub-graphs distributions. We map the flow regimes into the proper regions of the network's modularity space. Also, for each type of fluid regime, corresponding motifs shapes are scaled. Implemented power law distributions of fracture length in spatial fracture networks yielded the same node's degree distribution in transformed networks. Two general spatial networks are considered: random networks and networks with "hubness" properties mimicking a spatial damage zone (both with power law distribution of fracture length). In the first case, the fractures are embedded in uniformly distributed fracture sets; the second case covers spatial fracture zones. We prove numerically that the abnormal change (transition) in permeability is controlled by the hub growth rate. Also, comparing LBM results with the characteristic mean length of transformed networks' links shows a reverse relationship between the aforementioned parameters. In addition, the abnormalities in advection through nodes are presented.
Coevolution of Network Structure and Content
Venue: arXiv cs.SI 2012
Year: 2012

As individuals communicate, their exchanges form a dynamic network. We demonstrate, using time series analysis of communication in three online settings, that network structure alone can be highly revealing of the diversity and novelty of the information being communicated. Our approach uses both standard and novel network metrics to characterize how unexpected a network configuration is, and to capture a network's ability to conduct information. We find that networks with a higher conductance in link structure exhibit higher information entropy, while unexpected network configurations can be tied to information novelty. We use a simulation model to explain the observed correspondence between the evolution of a network's structure and the information it carries.
Scheduling partially ordered jobs faster than 2^n
Venue: arXiv cs.DS 2012
Year: 2012

In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.
Hierarchical Object Parsing from Structured Noisy Point Clouds
Venue: arXiv cs.CV 2012
Year: 2012

Object parsing and segmentation from point clouds are challenging tasks because the relevant data is available only as thin structures along object boundaries or other features, and is corrupted by large amounts of noise. To handle this kind of data, flexible shape models are desired that can accurately follow the object boundaries. Popular models such as Active Shape and Active Appearance models lack the necessary flexibility for this task, while recent approaches such as the Recursive Compositional Models make model simplifications in order to obtain computational guarantees. This paper investigates a hierarchical Bayesian model of shape and appearance in a generative setting. The input data is explained by an object parsing layer, which is a deformation of a hidden PCA shape model with Gaussian prior. The paper also introduces a novel efficient inference algorithm that uses informed data-driven proposals to initialize local searches for the hidden variables. Applied to the problem of object parsing from structured point clouds such as edge detection images, the proposed approach obtains state of the art parsing errors on two standard datasets without using any intensity information.
Performance Bounds and Associated Design Principles for Multi-Cellular Wireless OFDMA Systems (with Detailed Proofs)
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the downlink of large-scale multi-cellular OFDMA-based networks and study performance bounds of the system as a function of the number of users $K$, the number of base-stations $B$, and the number of resource-blocks $N$. Here, a resource block is a collection of subcarriers such that all such collections, that are disjoint have associated independently fading channels. We derive novel upper and lower bounds on the sum-utility for a general spatial geometry of base stations, a truncated path loss model, and a variety of fading models (Rayleigh, Nakagami-$m$, Weibull, and LogNormal). We also establish the associated scaling laws and show that, in the special case of fixed number of resource blocks, a grid-based network of base stations, and Rayleigh-fading channels, the sum information capacity of the system scales as $Θ(B \log\log K/B)$ for extended networks, and as $O(B \log\log K)$ and $Ω(\log \log K)$ for dense networks. Interpreting these results, we develop some design principles for the service providers along with some guidelines for the regulators in order to achieve provisioning of various QoS guarantees for the end users and, at the same time, maximize revenue for the service providers.
Spatial Interactions of Peers and Performance of File Sharing Systems
Venue: arXiv cs.NI 2012
Year: 2012

We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model allows one to cope with key features of P2P networking like degree or locality constraints or the fact that distant peers often have a smaller rate than nearby peers. We show that the spatial point process describing peers in their steady state then exhibits an interesting repulsion phenomenon. We analyze two asymptotic regimes of the peer-to-peer network: the fluid regime and the hard--core regime. We get closed form expressions for the mean (and in some cases the law) of the peer latency and the download rate obtained by a peer as well as for the spatial density of peers in the steady state of each regime, as well as an accurate approximation that holds for all regimes. The analytical results are based on a mix of mathematical analysis and dimensional analysis and have important design implications. The first of them is the existence of a setting where the equilibrium mean latency is a decreasing function of the load, a phenomenon that we call super-scalability.
Numerical extraction of a macroscopic pde and a lifting operator from a lattice Boltzmann model
Venue: arXiv cs.CE 2012
Year: 2012

Lifting operators play an important role in starting a lattice Boltzmann model from a given initial density. The density, a macroscopic variable, needs to be mapped to the distribution functions, mesoscopic variables, of the lattice Boltzmann model. Several methods proposed as lifting operators have been tested and discussed in the literature. The most famous methods are an analytically found lifting operator, like the Chapman-Enskog expansion, and a numerical method, like the Constrained Runs algorithm, to arrive at an implicit expression for the unknown distribution functions with the help of the density. This paper proposes a lifting operator that alleviates several drawbacks of these existing methods. In particular, we focus on the computational expense and the analytical work that needs to be done. The proposed lifting operator, a numerical Chapman-Enskog expansion, obtains the coefficients of the Chapman-Enskog expansion numerically. Another important feature of the use of lifting operators is found in hybrid models. There the lattice Boltzmann model is spatially coupled with a model based on a more macroscopic description, for example an advection-diffusion-reaction equation. In one part of the domain, the lattice Boltzmann model is used, while in another part, the more macroscopic model. Such a hybrid coupling results in missing data at the interfaces between the different models. A lifting operator is then an important tool since the lattice Boltzmann model is typically described by more variables than a model based on a macroscopic partial differential equation.
Distributed Power Control and Coding-Modulation Adaptation in Wireless Networks using Annealed Gibbs Sampling
Venue: arXiv cs.NI 2012
Year: 2012

In wireless networks, the transmission rate of a link is determined by received signal strength, interference from simultaneous transmissions, and available coding-modulation schemes. Rate allocation is a key problem in wireless network design, but a very challenging problem because: (i) wireless interference is global, i.e., a transmission interferes all other simultaneous transmissions, and (ii) the rate-power relation is non-convex and non-continuous, where the discontinuity is due to limited number of coding-modulation choices in practical systems. In this paper, we propose a distributed power control and coding-modulation adaptation algorithm using annealed Gibbs sampling, which achieves throughput optimality in an arbitrary network topology. We consider a realistic Signal-to-Interference-and-Noise-Ratio (SINR) based interference model, and assume continuous power space and finite rate options (coding-modulation choices). Our algorithm first decomposes network-wide interference to local interference by properly choosing a "neighborhood" for each transmitter and bounding the interference from non-neighbor nodes. The power update policy is then carefully designed to emulate a Gibbs sampler over a Markov chain with a continuous state space. We further exploit the technique of simulated annealing to speed up the convergence of the algorithm to the optimal power and coding-modulation configuration. Finally, simulation results demonstrate the superior performance of the proposed algorithm.
A unified formulation of Gaussian vs. sparse stochastic processes - Part II: Discrete-domain theory
Venue: arXiv cs.IT 2012
Year: 2012

This paper is devoted to the characterization of an extended family of CARMA (continuous-time autoregressive moving average) processes that are solutions of stochastic differential equations driven by white Levy innovations. These are completely specified by: (1) a set of poles and zeros that fixes their correlation structure, and (2) a canonical infinitely-divisible probability distribution that controls their degree of sparsity (with the Gaussian model corresponding to the least sparse scenario). The generalized CARMA processes are either stationary or non-stationary, depending on the location of the poles in the complex plane. The most basic non-stationary representatives (with a single pole at the origin) are the Levy processes, which are the non-Gaussian counterparts of Brownian motion. We focus on the general analog-to-discrete conversion problem and introduce a novel spline-based formalism that greatly simplifies the derivation of the correlation properties and joint probability distributions of the discrete versions of these processes. We also rely on the concept of generalized increment process, which suppresses all long range dependencies, to specify an equivalent discrete-domain innovation model. A crucial ingredient is the existence of a minimally-supported function associated with the whitening operator L; this B-spline, which is fundamental to our formulation, appears in most of our formulas, both at the level of the correlation and the characteristic function. We make use of these discrete-domain results to numerically generate illustrative examples of sparse signals that are consistent with the continuous-domain model.
Estimating 3D Human Shapes from Measurements
Venue: arXiv cs.CV 2012
Year: 2012

The recent advances in 3-D imaging technologies give rise to databases of human shapes, from which statistical shape models can be built. These statistical models represent prior knowledge of the human shape and enable us to solve shape reconstruction problems from partial information. Generating human shape from traditional anthropometric measurements is such a problem, since these 1-D measurements encode 3-D shape information. Combined with a statistical shape model, these easy-to-obtain measurements can be leveraged to create 3D human shapes. However, existing methods limit the creation of the shapes to the space spanned by the database and thus require a large amount of training data. In this paper, we introduce a technique that extrapolates the statistically inferred shape to fit the measurement data using nonlinear optimization. This method ensures that the generated shape is both human-like and satisfies the measurement conditions. We demonstrate the effectiveness of the method and compare it to existing approaches through extensive experiments, using both synthetic data and real human measurements.
The path inference filter: model-based low-latency map matching of probe vehicle data
Venue: arXiv cs.AI 2012
Year: 2012

We consider the problem of reconstructing vehicle trajectories from sparse sequences of GPS points, for which the sampling interval is between 10 seconds and 2 minutes. We introduce a new class of algorithms, called altogether path inference filter (PIF), that maps GPS data in real time, for a variety of trade-offs and scenarios, and with a high throughput. Numerous prior approaches in map-matching can be shown to be special cases of the path inference filter presented in this article. We present an efficient procedure for automatically training the filter on new data, with or without ground truth observations. The framework is evaluated on a large San Francisco taxi dataset and is shown to improve upon the current state of the art. This filter also provides insights about driving patterns of drivers. The path inference filter has been deployed at an industrial scale inside the Mobile Millennium traffic information system, and is used to map fleets of data in San Francisco, Sacramento, Stockholm and Porto.
Optimal Backpressure Scheduling in Wireless Networks using Mutual Information Accumulation
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we develop scheduling policies that maximize the stability region of a wireless network under the assumption that mutual information accumulation is implemented at the physical layer. When the link quality between nodes is not sufficiently high that a packet can be decoded within a single slot, the system can accumulate information across multiple slots, eventually decoding the packet. The result is an expanded stability region. The accumulation process over weak links is temporally coupled and therefore does not satisfy the independent and identically distributed (i.i.d) assumption that underlies many previous analysis in this area. Therefore the problem setting also poses new analytic challenges. We propose two dynamic scheduling algorithms to cope with the non-i.i.d nature of the decoding. The first performs scheduling every $T$ slots, and approaches the boundary of the stability region as $T$ gets large, but at the cost of increased average delay. The second introduces virtual queues for each link and constructs a virtual system wherein two virtual nodes are introduced for each link. The constructed virtual system is shown to have the same stability region as the original system. Through controlling the virtual queues in the constructed system, we avoid the non-i.i.d analysis difficulty and attain the full stability region. We derive performance bounds for both algorithms and compare them through simulation results.
Diameter Perfect Lee Codes
Venue: arXiv cs.IT 2012
Year: 2012

Lee codes have been intensively studied for more than 40 years. Interest in these codes has been triggered by the Golomb-Welch conjecture on the existence of the perfect error-correcting Lee codes. In this paper we deal with the existence and enumeration of diameter perfect Lee codes. As main results we determine all $q$ for which there exists a linear diameter-4 perfect Lee code of word length $n$ over $Z_{q},$ and prove that for each $n\geq 3$ there are uncountable many diameter-4 perfect Lee codes of word length $n$ over $Z.$ This is in a strict contrast with perfect error-correcting Lee codes of word length $n$ over $Z\,$\ as there is a unique such code for $n=3,$ and its is conjectured that this is always the case when $2n+1$ is a prime. We produce diameter perfect Lee codes by an algebraic construction that is based on a group homomorphism. This will allow us to design an efficient algorithm for their decoding. We hope that this construction will turn out to be useful far beyond the scope of this paper.
Compressive Sensing of Analog Signals Using Discrete Prolate Spheroidal Sequences
Venue: arXiv cs.IT 2012
Year: 2012

Compressive sensing (CS) has recently emerged as a framework for efficiently capturing signals that are sparse or compressible in an appropriate basis. While often motivated as an alternative to Nyquist-rate sampling, there remains a gap between the discrete, finite-dimensional CS framework and the problem of acquiring a continuous-time signal. In this paper, we attempt to bridge this gap by exploiting the Discrete Prolate Spheroidal Sequences (DPSS's), a collection of functions that trace back to the seminal work by Slepian, Landau, and Pollack on the effects of time-limiting and bandlimiting operations. DPSS's form a highly efficient basis for sampled bandlimited functions; by modulating and merging DPSS bases, we obtain a dictionary that offers high-quality sparse approximations for most sampled multiband signals. This multiband modulated DPSS dictionary can be readily incorporated into the CS framework. We provide theoretical guarantees and practical insight into the use of this dictionary for recovery of sampled multiband signals from compressive measurements.
Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
Venue: arXiv cs.DC 2012
Year: 2012

Generalized sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. Here we show that SpGEMM also yields efficient algorithms for general sparse-matrix indexing in distributed memory, provided that the underlying SpGEMM implementation is sufficiently flexible and scalable. We demonstrate that our parallel SpGEMM methods, which use two-dimensional block data distributions with serial hypersparse kernels, are indeed highly flexible, scalable, and memory-efficient in the general case. This algorithm is the first to yield increasing speedup on an unbounded number of processors; our experiments show scaling up to thousands of processors in a variety of test scenarios.
Dynamic Deferral of Workload for Capacity Provisioning in Data Centers
Venue: arXiv cs.NI 2012
Year: 2012

Recent increase in energy prices has led researchers to find better ways for capacity provisioning in data centers to reduce energy wastage due to the variation in workload. This paper explores the opportunity for cost saving utilizing the flexibility from the Service Level Agreements (SLAs) and proposes a novel approach for capacity provisioning under bounded latency requirements of the workload. We investigate how many servers to be kept active and how much workload to be delayed for energy saving while meeting every deadline. We present an offline LP formulation for capacity provisioning by dynamic deferral and give two online algorithms to determine the capacity of the data center and the assignment of workload to servers dynamically. We prove the feasibility of the online algorithms and show that their worst case performance are bounded by a constant factor with respect to the offline formulation. We validate our algorithms on a MapReduce workload by provisioning capacity on a Hadoop cluster and show that the algorithms actually perform much better in practice compared to the naive `follow the workload' provisioning, resulting in 20-40% cost-savings.
A Faster Grammar-Based Self-Index
Venue: arXiv cs.DS 2012
Year: 2012

To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on grammars. In this paper we show how, given a straight-line program with $r$ rules for a string (S [1..n]) whose LZ77 parse consists of $z$ phrases, we can store a self-index for $S$ in $\Oh{r + z \log \log n}$ space such that, given a pattern (P [1..m]), we can list the $\occ$ occurrences of $P$ in $S$ in $\Oh{m^2 + \occ \log \log n}$ time. If the straight-line program is balanced and we accept a small probability of building a faulty index, then we can reduce the $\Oh{m^2}$ term to $\Oh{m \log m}$. All previous self-indexes are larger or slower in the worst case.
One-bit compressed sensing by linear programming
Venue: arXiv cs.IT 2012
Year: 2012

We give the first computationally tractable and almost optimal solution to the problem of one-bit compressed sensing, showing how to accurately recover an s-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linear measurements of x. The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors x. Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.
Enhance accuracy in Software cost and schedule estimation by using "Uncertainty Analysis and Assessment" in the system modeling process
Venue: arXiv cs.SE 2012
Year: 2012

Accurate software cost and schedule estimation are essential for software project success. Often it referred to as the "black art" because of its complexity and uncertainty, software estimation is not as difficult or puzzling as people think. In fact, generating accurate estimates is straightforward-once you understand the intensity of uncertainty and framework for the modeling process. The mystery to successful software estimation-distilling academic information and real-world experience into a practical guide for working software professionals. Instead of arcane treatises and rigid modeling techniques, this will guide highlights a proven set of procedures, understandable formulas, and heuristics that individuals and development teams can apply to their projects to help achieve estimation proficiency with choose appropriate development approaches In the early stage of software life cycle project manager are inefficient to estimate the effort, schedule, cost estimation and its development approach .This in turn, confuses the manager to bid effectively on software project and choose incorrect development approach. That will directly effect on productivity cycle and increase level of uncertainty. This becomes a strong cause of project failure. So to avoid such problem if we know level and sources of uncertainty in model design, It will directive the developer to design accurate software cost and schedule estimation, which are essential for software project success. However once the required efforts have estimated, little is done to recalibrate and reduce the uncertainty of the initial estimates.