38014133
On Achieving the Shortest-Path Routing in 2-D Meshes
In this paper, we present a fully distributed process to collect and distribute the minimal connected component (MCC) fault information so that the shortest-path between the source and the destination can always be found in the corresponding information-based routing via routing decisions at each intermediate node. Considering the communication cost in the above information distribution, a more practical implementation is provided with only a low number of nodes along the boundary lines involved in the information propagation. The experimental results show the substantial improvement of our approach in terms of the success rate in finding the shortest-path and the average path length.
2254959
Local-Safety-Information-Based Broadcasting in Hypercube Multicomputers with Node and Link Faults
This paper presents a method to cope with fault-tolerant broadcasting in hypercube multicomputers with both node and link faults. The local safety concept is extended to faulty hypercubes with both node and link faults. The local-safety-based algorithm is used in a fully unsafe hypercube, where there is no safe node. A fully unsafe hypercube can be split into a set of maximal safe subcubes. We show that if these maximal safe subcubes meet certain requirements given in the paper, broadcasting can still be carried out successfully and in some case optimal broadcast is still possible. The method is extended to fault-tolerant routing and multicasting when the system contains both node and link faults.
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
7582647
On self-similarity and hamiltonicity of dual-cubes
The dual-cube is a newly proposed topology for interconnection networks, which uses low dimensional hypercubes as building blocks. The primary advantages of the dual-cube over the hypercube are that, with the same node degree n, the dual-cube contains 2/sup n-1/ times more nodes than the hypercube and, with the same amount of nodes, the dual-cube has approximately 50% less links than the hypercube. This paper was focused on the investigations of the structural self-similarity and the Hamiltonian property of the dual-cube. It was shown that a dual-cube can be recursively constructed from lower dimensional dual-cubes and, conversely, a dual-cube can be recursively decomposed into lower dimensional dual-cubes. It was also proved that all dual-cubes are Hamiltonian. There exist multiple Hamiltonian cycles on a dual-cube, among which, [(n-1)/2] cycles are edge-disjoint. It was illustrated that rings and linear arrays can be effectively emulated on dual-cubes. Some strategies for track sharing in efficient VLSI layout design were also discussed.
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.
27746153
Broadcasting in Faulty Cube-Connected-Cycles with Minimum Recovery Time
We propose a broadcasting algorithm for a faulty Cube-Connected-Cycles multiprocessor. The broadcasting algorithm delivers a message to all the nodes non-redundantly using a binomial tree. The traffic generated because of the recovery is guaranteed to be minimum.
2785443
An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree
In this paper, we prove that any edge-coloring critical graph G with maximum degree @D>=([email protected])/2, where @e= =8 and |V(G)|>[email protected]@d-4-(@D+6)/(@d-6), where @d is the minimum degree of G. It generalizes a result of Sanders and Zhao.
2718321
Face recognition with one training image per person
At present there are many methods that could deal well with frontal view face recognition. However, most of them cannot work well when there is only one training image per person. In this paper, an extension of the eigenface technique, i.e. projection-combined principal component analysis, (PC)2A, is proposed. (PC)2A combines the original face image with its horizontal and vertical projections and then performs principal component analysis on the enriched version of the image. It requires less computational cost than the standard eigenface technique and experimental results show that on a gray-level frontal view face database where each person has only one training image, (PC)2A achieves 3-5% higher accuracy than the standard eigenface technique through using 10-15% fewer eigenfaces.
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.
7567561
Genetic Algorithm based Selective Neural Network Ensemble
Neural network ensemble is a learning paradigm where several neural networks are jointly used to solve a problem. In this paper, the relationship between the generalization ability of the neural network ensemble and the correlation of the individual neural networks is analyzed, which reveals that ensembling a selective subset of individual networks is superior to ensembling all the individual networks in some cases. Therefore an approach named GASEN is proposed, which trains several individual neural networks and then employs genetic algorithm to select an optimum subset of individual networks to constitute an ensemble. Experimental results show that, comparing with a popular ensemble approach, i.e. averaging all, and a theoretically optimum selective ensemble approach, i.e. enumerating, GASEN has preferable performance in generating ensembles with strong generalization ability in relatively small computational cost.
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.