In this article we present a novel packet scheduling algorithm LBFS-DRR, which combines features from the Last-Come First-Served scheduling discipline and the Deficit Round Robin (DRR) algorithm. In comparison with DR...
详细信息
ISBN:
(纸本)9781424412297;1424412293
In this article we present a novel packet scheduling algorithm LBFS-DRR, which combines features from the Last-Come First-Served scheduling discipline and the Deficit Round Robin (DRR) algorithm. In comparison with DRR it provides lower average packet delay, while preserving the advantageous feature like O(l) complexity, fairness, bandwidth guarantee. The lower mean delay is realized by giving service in a round first to flows transmitting bellow their (weighted) fair share. The algorithm exploits the high variability in the typical user traffic pattern resulting in lower mean file transfer delay.
This paper presents a novel approach to parts-based object recognition in the presence of occlusion. We focus on the problem of determining the pose of a 3-D object from a single 2-D image when convex parts of the obj...
详细信息
This paper presents a novel approach to parts-based object recognition in the presence of occlusion. We focus on the problem of determining the pose of a 3-D object from a single 2-D image when convex parts of the object have been matched to corresponding regions in the image. We consider three types of occlusions: self-occlusion, occlusions whose locus is identified in the image, and completely arbitrary occlusions. We derive efficient algorithms for the first two cases, and characterize their performance. For the last case, we prove that the problem of finding valid poses is computationally hard, but provide an efficient, approximate algorithm. This work generalizes our previous work on region-based object recognition, which focused on the case of planar models.
In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable c...
详细信息
ISBN:
(纸本)0262201526
In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for Ada- Boost's output. By considering AdaBoost as a dynamical system, we are able to prove Ratsch and Warmuth's conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a 'nonoptimal' weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arcgv.
We present a distributed algorithm for rerouting to accommodate unlimited movement of mobile hosts in a mobile-mobile connection. The algorithm is source initiated-that is the source base station is responsible for th...
详细信息
We present a distributed algorithm for rerouting to accommodate unlimited movement of mobile hosts in a mobile-mobile connection. The algorithm is source initiated-that is the source base station is responsible for the rerouting. The algorithm ensures that the establishment of non-optimal and incorrect paths is avoided and that no packets in the session are lost as there is always a path between the base stations in charge of the source and the destination. The design of this distributed algorithm ensures that the processing at the mobile hosts is kept to a minimum. In addition, the proposed framework for rerouting in mobile-mobile communications is independent of the type of rerouting scheme.
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the val...
详细信息
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the value of the function on instances drawn according to some distribution, and possibly may query the function on instances of its choice. First, they establish some connections between property testing and problems in learning theory. Next, they focus on testing graph properties, and devise algorithms to test whether a graph has properties such as being k-colorable or having a /spl rho/-clique (clique of density /spl rho/ w.r.t. the vertex set). The graph property testing algorithms are probabilistic and make assertions which are correct with high probability utilizing only poly(1//spl epsiv/) edge-queries into the graph, where /spl epsiv/ is the distance parameter. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph which correspond to the property being tested, if it holds for the input graph.
This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we p...
This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we propagate normal form demand at compile time as well as run time, and detect parallelism automatically using strictness analysis. The EQUALS implementation indicates the effectiveness of NF-demand propagation in identifying significant parallelism and in achieving good sequential as well as parallel performance. Another important difference between EQUALS and previous implementations is the use of reference counting for memory management, instead of mark-and-sweep or copying garbage collection. Implementation results show that reference counting leads to very good scalability and low memory requirements, and offers sequential performance comparable to generational garbage collectors. We compare the performance of EQUALS with that of other parallel implementations (the 〈v, G〉-machine and GAML) as well as with the performance of SML/NJ, a sequential implementation of a strict language.
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-Ε) = Ω(n0.546), for any Ε > 0. Moreover, there...
详细信息
ISBN:
(纸本)9781581136746
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-Ε) = Ω(n0.546), for any Ε > 0. Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.
A dynamic environment, such as a production process, a communication network, highway traffic, etc., may contain a huge amount of information, changing with time, which is a valuable resource for understanding the gen...
详细信息
暂无评论