16257632
XYZ: a scalable, partially centralized lookup service for large-scale peer-to-peer systems
Peer-to-peer (P2P) systems are characterized by direct access between peer computers, rather than through a centralized server. File sharing is the dominant P2P application on the Internet, allowing users to easily contribute, search and obtain content. P2P systems can be categorized by the degrees of centralization. For fully centralized systems, the lookup service will not be available when the central directory server is down. For purely decentralized and unstructured systems, since there is no information about which nodes are likely to have the relevant files, searching essentially amounts to random search. This makes the lookup service unscalable and unpredictable. The objective of this paper is to design a partially centralized, scalable and self-organizing lookup service (XYZ) for wide area P2P systems. A clustering method is used to create the system backbone by connecting the cluster heads together and a color clustering method is adopted to create color overlays and minimize the searching space. Simulations and analysis are also provided. Extensions are proposed to achieve better performance
18143775
An extended link reversal protocol in dynamic networks
We consider the problem of maintaining routing paths between nodes in a dynamic network. Gafni and Bertsekas proposed a link reversal approach called the BG method that maintains a directed acyclic graph (DAG) with a given destination as the sink node. By virtue of built-in redundancy, an updating algorithm to establish a new DAG is activated infrequently and it happens only when the last outgoing link of a host in the DAG is destroyed due to the movement of nodes. In this paper, we propose another updating approach that tries to minimize the total number of reversed links and to maintain routing information without using much extra overhead. The approach maintains a reversed breadth-first tree. Nodes in the network are either marked (inside the tree) or unmarked (outside the tree). When it is too costly to maintain a minimum path for a marked node, the branch rooted at the node is trimmed and the approach then gracefully switches to the BG method. Several extensions are also discussed. A simulation study is conducted to compare the performance of the proposed approach with the existing one.
11143071
Cluster-based intelligent searching in unstructured peer-to-peer networks
Existing cluster-based searching schemes in unstructured peer-to-peer (P2P) networks employ flooding/random forwarding on connected dominating sets (CDS) of networks. There exists no upper bound on the size of CDS of a network. Both flooding and CDS hinder query efficiency. Random forwarding worsens the recall ratio. In this paper, we propose a cluster-based searching scheme that intelligently forward queries on the maximum independent sets (MIS) of networks. Our approach partitions the entire network into disjoint clusters with one clusterhead (CH) per cluster. CHs form a MIS and are connected through gateway nodes. Each node fakes one role, a CH, a gateway, or an ordinary node. A CH looks up the data for the entire cluster using data summaries of cluster members, which are represented by bloom filters. Between clusters, CHs intelligently forward queries via gateways to the best neighbor CHs that are most likely to return query results. The experimental results demonstrate that our scheme greatly improves the query efficiency without degrading the quality of the query results, compared to existing approaches.
5896177
Fault-tolerant routing in meshes/tori using planarly constructed fault blocks
A few faulty nodes can make an n-dimensional mesh or torus network unsafe for fault-tolerant routing methods based on the block fault model, where the whole system (n-dimensional space) forms a fault block. A new concept, called extended local safety information in meshes or tori, is proposed to guide fault-tolerant routing, and classifies fault-free nodes inside 2-dimensional planes. Many nodes globally marked as unsafe become locally enabled inside 2-dimensional planes. A fault-tolerant routing algorithm based on extended local safety information is proposed for k-ary n-dimensional meshes/tori. Our method does not need to disable any fault-free nodes, unlike many previous methods, and this enhances the computational power of the system and improves performance of the routing algorithm greatly. All fault blocks are constructed inside 2-dimensional planes rather than in the whole system. Extensive simulation results are presented and compared with the previous methods.
7867681
Mobility management and its applications in efficient broadcasting in mobile ad hoc networks
We study an efficient broadcast scheme in mobile ad hoc networks (MANETs). The objective is to determine a small set of forward nodes to ensure full coverage. We first study several methods to select a small forward node set assuming that the neighborhood information can be updated in a timely manner. Then we consider a general case, where each node updates its neighborhood information based asynchronously on a predefined frequency and node move even during the broadcast process. The virtual network constructed from local views of nodes may not be connected, its links may not exist in the physical network, and the global view constructed from collection of local views may not be consistent. In this paper, we first give a sufficient condition for connectivity at the physical network to ensure the connectivity at the virtual network. We then propose a solution using two transmission ranges to address the link availability issue. The neighborhood information as well as the forward node set are determined based on a short transmission range while the broadcast process is done on a long transmission range. The difference between these two ranges is based on the update frequency and the speed of node movement. Finally, we propose a mechanism called aggregated local view to ensure consistency of the global view. By these, we extend Wu and Dai's coverage condition for broadcasting in a network with mobile nodes. The simulation study is conducted to evaluate the coverage of the proposed scheme.
17371165
QoS Routing in Hypercube Multicomputers
In this paper, we present a coding method to capture QoS information in hypercube multicomputers. The coding method is based on a localized algorithm where each node interacts with its neighbors to gather QoS information. Specifically, each node maintains a QoS vector where the k-th element represents the guaranteed QoS performance to a destination that is k hops away. The localized algorithm exhibits desirable properties of self-stabilizing, self-optimizing, and self-healing. Simulation results show that this coding method provides a good approximation of the minimum QoS value to a k-hop destination and, at the same time, uses a relatively small number of packets to propagate a change in link state (QoS value) compared with the classical distributed Bellman-Ford method.
1886465
Learning a Rare Event Detection Cascade by Direct Feature Selection
Face detection is a canonical example of a rare event detection problem, in which target patterns occur with much lower frequency than non-targets. Out of millions of face-sized windows in an input image, for example, only a few will typically contain a face. Viola and Jones recently proposed a cascade architecture for face detection which successfully addresses the rare event nature of the task. A central part of their method is a feature selection algorithm based on AdaBoost. We present a novel cascade learning algorithm based on forward feature selection which is two orders of magnitude faster than the Viola-Jones approach and yields classifiers of equivalent quality. This faster method could be used for more demanding classification tasks, such as on-line learning.
18802972
A diagnostic fault simulator for fast diagnosis of bridge faults
A new diagnostic fault simulator is described that diagnoses both feedback and non-feedback bridge faults while using information from fault simulation of single stuck-at faults. A realistic fault model is used which considers the existence of the Byzantine Generals Problem. The approach has been demonstrated for two-line bridge faults on several large combinational benchmark circuits and has achieved over 98% accuracy for non-feedback bridge faults and over 80% accuracy for feedback bridge faults with good diagnostic resolution.
6832021
Multiresolution Image Registration Based on Kullback-Leibler Distance
This paper extends our prior work on multi-modal image registration based on the a priori knowledge of the joint intensity dis- tribution that we expect to obtain, and Kullback-Leibler distance. This expected joint distribution can be estimated from pre-aligned training images. Experimental results show that, as compared with the Mutual Information and Approximate Maximum Likelihood based registration methods, the new method has longer capture range at different image resolutions, which can lead to a more robust image registration method. Moreover, with a simple interpolation algorithm based on non-grid point random sampling, the proposed method can avoid interpolation artifacts at the low resolution registration. Finally, it is experimentally demon- strated that our method is applicable to a variety of imaging modalities.
15943479
Efficient face candidates selector for face detection
Abstract In this paper an efficient face candidates selector is proposed for face detection tasks in still gray level images. The proposed method acts as a selective attentional mechanism. Eye-analogue segments at a given scale are discovered by finding regions which are roughly as large as real eyes and are darker than their neighborhoods. Then a pair of eye-analogue segments are hypothesized to be eyes in a face and combined into a face candidate if their placement is consistent with the anthropological characteristic of human eyes. The proposed method is robust in that it can deal with illumination changes and moderate rotations. A subset of the FERET data set and the BioID face database are used to evaluate the proposed method. The proposed face candidates selector is successful in 98.75% and 98.6% cases, respectively.
412675
Linear Asymmetric Classifier for cascade detectors
The detection of faces in images is fundamentally a rare event detection problem. Cascade classifiers provide an efficient computational solution, by leveraging the asymmetry in the distribution of faces vs. non-faces. Training a cascade classifier in turn requires a solution for the following subproblems: Design a classifier for each node in the cascade with very high detection rate but only moderate false positive rate. While there are a few strategies in the literature for indirectly addressing this asymmetric node learning goal, none of them are based on a satisfactory theoretical framework. We present a mathematical characterization of the node-learning problem and describe an effective closed form approximation to the optimal solution, which we call the Linear Asymmetric Classifier (LAC). We first use AdaBoost or AsymBoost to select features, and use LAC to learn a linear discriminant function to achieve the node learning goal. Experimental results on face detection show that LAC can improve the detection performance in comparison to standard methods. We also show that Fisher Discriminant Analysis on the features selected by AdaBoost yields better performance than AdaBoost itself.