970236
Pseudo likelihood estimation in network tomography
Network monitoring and diagnosis are key to improving network performance. The difficulties of performance monitoring lie in today's fast growing Internet, accompanied by increasingly heterogeneous and unregulated structures. Moreover, these tasks become even harder since one cannot rely on the collaboration of individual routers and servers to directly measure network traffic. Even though the aggregatory nature of possible network measurements gives rise to inverse problems, existing methods for solving inverse problems are usually computationally intractable or statistically inefficient. In this paper, a pseudo likelihood approach is proposed to solve a group of network tomography problems. The basic idea of pseudo likelihood is to form simple subproblems and construct a product of marginal likelihood of subproblems by the ignoring their dependences. As a result, it keeps a good balance between the computational complexity and the statistical efficiency of the parameter estimation. Some statistical properties of the pseudo likelihood estimator, such as consistency and asymptotic normality, are established. A pseudo expectation-maximization (EM) algorithm is developed to maximize the pseudo log-likelihood function. Two examples with simulated or real data are used to illustrate the pseudo likelihood proposal: (1) internal link delay distribution inference through multicast end-to-end measurements; (2) origin-destination matrix estimation through link traffic counts.
1767373
Wavelet thresholding via MDL for natural images
We study the application of Rissanen's (1989) principle of minimum description length (MDL) to the problem of wavelet denoising and compression for natural images. After making a connection between thresholding and model selection, we derive an MDL criterion based on a Laplacian model for noiseless wavelet coefficients. We find that this approach leads to an adaptive thresholding rule. While achieving mean-squared-error performance comparable with other popular thresholding schemes, the MDL procedure tends to keep far fewer coefficients. From this property, we demonstrate that our method is an excellent tool for simultaneous denoising and compression. We make this claim precise by analyzing MDL thresholding in two optimality frameworks; one in which we measure rate and distortion based on quantized coefficients and one in which we do not quantize, but instead record rate simply as the number of nonzero coefficients.
39243731
A rate of convergence result for a universal D-semifaithful code
The problem of optimal rate universal coding is considered in the context of rate-distortion theory. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to approach its lower bound, the rate-distortion function, at a rate O(n/sup -1/log n), and this is conjectured to be optimal based on a result of A.J. Pilc (1968). Issues of constructiveness and universality are addressed. >
15189341
Wavelet thresholding for multiple noisy image copies
This correspondence addresses the recovery of an image from its multiple noisy copies. The standard method is to compute the weighted average of these copies. Since the wavelet thresholding technique has been shown to effectively denoise a single noisy copy, we consider in this paper combining the two operations of averaging and thresholding. Because thresholding is a nonlinear technique, averaging then thresholding or thresholding then averaging produce different estimators. By modeling the signal wavelet coefficients as Laplacian distributed and the noise as Gaussian, our investigation finds the optimal ordering to depend on the number of available copies and on the signal-to-noise ratio. We then propose thresholds that are nearly optimal under the assumed model for each ordering. With the optimal and near-optimal thresholds, the two methods yield similar performance, and both show considerable improvement over merely averaging.
1825087
The Minimum Description Length Principle in Coding and Modeling
We review the principles of minimum description length and stochastic complexity as used in data compression and statistical modeling. Stochastic complexity is formulated as the solution to optimum universal coding problems extending Shannon's basic source coding theorem. The normalized maximized likelihood, mixture, and predictive codings are each shown to achieve the stochastic complexity to within asymptotically vanishing terms. We assess the performance of the minimum description length criterion both from the vantage point of quality of data compression and accuracy of statistical inference. Context tree modeling, density estimation, and model selection in Gaussian linear regression serve as examples.
12479973
Adaptive wavelet thresholding for image denoising and compression
The first part of this paper proposes an adaptive, data-driven threshold for image denoising via wavelet soft-thresholding. The threshold is derived in a Bayesian framework, and the prior used on the wavelet coefficients is the generalized Gaussian distribution (GGD) widely used in image processing applications. The proposed threshold is simple and closed-form, and it is adaptive to each subband because it depends on data-driven estimates of the parameters. Experimental results show that the proposed method, called BayesShrink, is typically within 5% of the MSE of the best soft-thresholding benchmark with the image assumed known. It also outperforms SureShrink (Donoho and Johnstone 1994, 1995; Donoho 1995) most of the time. The second part of the paper attempts to further validate claims that lossy compression can be used for denoising. The BayesShrink threshold can aid in the parameter selection of a coder designed with the intention of denoising, and thus achieving simultaneous denoising and compression. Specifically, the zero-zone in the quantization step of compression is analogous to the threshold value in the thresholding function. The remaining coder design parameters are chosen based on a criterion derived from Rissanen's minimum description length (MDL) principle. Experiments show that this compression method does indeed remove noise significantly, especially for large noise power. However, it introduces quantization noise and should be used only if bitrate were an additional concern to denoising.
788765
Intelligent online BGP-4 analyzer
Border Gateway Protocol 4 (BGP-4) is one of the widely used routing protocols. This paper presents the design and implementation of an intelligent BGP-4 analyzer working online. Serving in the study and test of BGP-4, the analyzer can capture all the BGP-4 traffic and further exploit "state synchronization" algorithm to analyze the behavior of the BGP-4 state machine by observing the interaction between BGP-4 peers. As to the routing information manipulation, the analyzer can also verify its correctness and efficiency through internal process simulation and statistical computation. And the interested sessions and routes are traced and analyzed. This analyzer possesses many other beneficial features and plays an important role both in the study and test of BGP-4 and the network management.
1757616
A scalable overlay video mixing service model
Figure 1. Information disparity over time and between streams
15548673
Adaptive Query Processing in Point-Transformation Schemes
Point-transformation schemes transform multidimensional points to one-dimensional values so that conventional access methods can be used to index multidimensional points, enabling convenient integration of multidimensional query facilities into complex transactional database management systems. However, in high-dimensional data spaces, the computational complexity of the required query transformation is prohibitive. This paper proposes a near-optimal solution based on our novel ideas of adaptive Z-ordering. The experimental results show that the proposed approach significantly improves the query performance of point-transformation schemes. The idea can easily be generalized to accommodate any hierarchical space-filling curve, not just the Z-curve.
1444182
Detecting deception in reputation management
We previously developed a social mechanism for distributed reputation management, in which an agent combines testimonies from several witnesses to determine its ratings of another agent. However, that approach does not fully protect against spurious ratings generated by malicious agents. This paper focuses on the problem of deception in testimony propagation and aggregation. We introduce some models of deception and study how to efficiently detect deceptive agents following those models. Our approach involves a novel application of the well-known weighted majority technique to belief function and their aggregation. We describe simulation experiments to study the number of apparently accurate witnesses found in different settings, the number of witnesses on prediction accuracy, and the evolution of trust networks.
1764942
SpiderNet: an integrated peer-to-peer service composition framework
Service composition is highly desirable in peer-to-peer (P2P) systems where application services are naturally dispersed on distributed peers. However, it is challenging to provide high quality and failure resilient service composition in P2P systems due to the decentralization requirement and dynamic peer arrivals/departures. We present an integrated P2P service composition framework called SpiderNet to address the challenges. At service setup phase, SpiderNet performs a novel bounded composition probing protocol to provide scalable quality-aware and resource-efficient sendee composition in a fully distributed fashion. Moreover, SpiderNet supports directed acyclic graph composition topologies and explores exchangeable composition orders for enhanced service quality. During service runtime, SpiderNet provides proactive failure recovery to overcome dynamic changes (e.g., peer departures) in P2P systems. The proactive failure recovery scheme maintains a small number of dynamically selected backup compositions to achieve quick failure recovery for soft realtime streaming applications. We have implemented a prototype of SpiderNet and conducted extensive experiments using both large-scale simulations and wide-area network testbed. Experimental results show the feasibility and efficiency of the SpiderNet service composition solution for P2P systems.