A note on constructing binary heaps with periodic networks

We consider the problem of constructing binary heaps on constant degree networks performing compare-exchange operations only. The heap data structure, introduced by William and Williams [Comm. ACM 7 (6) (1964) 347-348], has many applications and, therefore, has been intensively studied in sequential and parallel context. In particular, Brodal and Pinotti [Theoret. Comput. Sci. 250 (2001) 235-245] have recently presented two families of comparator networks: the first of depth 4logN and the second of size O(NloglogN) for constructing binary heaps of size N. In this note, we give an new construction of such a network with the running time improved to 3logN. Moreover, the network has a novel property of being 3-periodic, that is, for each unit of time i the same sets of operations are performed in units i and i+3. Then we argue that our construction is optimal with respect to the length of the period, that is, we prove that there is no 2-periodic network that is able to build a binary heap in sublinear time. Finally, we show that our construction can be used to decrease also the depth of the networks with O(NloglogN) size.     

The bounds of min-max pair heap construction

In this paper, lower and upper bounds for min-max pair heap construction has been presented. It has been shown that the construction of a min-max pair heap with n elements requires at least 2.07n element comparisons. A new algorithm for creating min-max pair heap has been devised that lowers the upper bound to 2.43n.     

Optimal Content Location in Multicast Based Overlay Networks with Content Updates

The architecture of overlay networks should support high-performance and high-scalability at low costs. This becomes more crucial when communication, storage costs as well as service latencies grow with the exploding amounts of data exchanged and with the size and span of the overlay network. For that end, multicast methodologies can be used to deliver content from regional servers to end users, as well as for the timely and economical synchronization of content among the distributed servers. Another important architectural problem is the efficient allocation of objects to servers to minimize storage, delivery and update costs. In this work, we suggest a multicast based architecture and address the optimal allocation and replication of dynamic objects that are both consumed and updated. Our model network includes consumers which are served using multicast or unicast transmissions and media sources (that may be also consumers) which update the objects using multicast communication. General costs are associated with distribution (download) and update traffic as well as the storage of objects in the servers. Optimal object allocation algorithms for tree networks are presented with complexities of O(N) and O(N ²) in case of multicast and unicast distribution respectively. To our knowledge, the model of multicast distribution combined with multicast updates has not been analytically dealt before, despite its popularity in the industry.     

Two-tier relaxed heaps

We introduce a data structure which provides efficient heap operations with respect to the number of element comparisons performed. Let n denote the size of the heap being manipulated. Our data structure guarantees the worst-case cost of O(1) for finding the minimum, inserting an element, extracting an (unspecified) element, and replacing an element with a smaller element; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for deleting an element. We thereby improve the comparison complexity of heap operations known for run-relaxed heaps and other worst-case efficient heaps. Furthermore, our data structure supports melding of two heaps of size m and n at the worst-case cost of O(min {lg m, lg n}). A preliminary version of this paper [8] was presented at the 17th International Symposium on Algorithms and Computation held in Kolkata in December 2006. Partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools).     

An Optimal Algorithm for Selection in a Min-Heap

An O(k)-time algorithm is presented for selecting the kth smallest element in a binary min-heap of size nk. The approach uses recursively defined data structures that impose a hierarchical grouping on certain elements in the heap. The result establishes a further example of a partial order for which the kth smallest element can be determined in time proportional to the information theory lower bound. Two applications, to a resource allocation problem and to the enumeration of the k smallest spanning trees, are identified.     

Synchronization of Interconnected Multi‐valued Logical Networks

This paper studies the synchronization of interconnected k‐valued logical networks, as well as that of interconnected higher order k‐valued logical networks, based on their algebraic representations. For interconnected k‐valued logical networks, one necessary and sufficient criterion of synchronization is established via the definition of synchronization and another equivalent condition is given by combining synchronization with fixed points and cycles. Furthermore, with some special properties of semi‐tensor product, the third necessary and sufficient condition for synchronization of interconnected k‐valued logical networks is raised in terms of transition matrices. Then, the limit set method can be used to analyze the synchronization of interconnected higher order k‐valued logical networks. Finally, three examples, including the Boolean model for interconnected biochemical oscillators in the cell cycle, are presented to illustrate effectiveness of the results.     

A Bayesian Method for the Induction of Probabilistic Networks from Data

This paper presents a Bayesian method for constructing probabilistic networks from databases. In particular, we focus on constructing Bayesian belief networks. Potential applications include computer-assisted hypothesis testing, automated scientific discovery, and automated construction of probabilistic expert systems. We extend the basic method to handle missing data and hidden (latent) variables. We show how to perform probabilistic inference by averaging over the inferences of multiple belief networks. Results are presented of a preliminary evaluation of an algorithm for constructing a belief network from a database of cases. Finally, we relate the methods in this paper to previous work, and we discuss open problems.     

Improved sorting networks withO(logN) depth

The sorting network described by Ajtaiet al. was the first to achieve a depth ofO(logn). The networks introduced here are simplifications and improvements based strongly on their work. While the constants obtained for the depth bound still prevent the construction being of practical value, the structure of the presentation offers a convenient basis for further development.The author was supported by a Senior Fellowship from the Science and Engineering Research Council during the course of this work.     

Change Detection in Overhead Imagery Using Neural Networks

Identifying interesting changes from a sequence of overhead imagery—as opposed to clutter, lighting/seasonal changes, etc.—has been a problem for some time. Recent advances in data mining have greatly increased the size of datasets that can be attacked with pattern discovery methods. This paper presents a technique for using predictive modeling to identify unusual changes in images. Neural networks are trained to predict before and after pixel values for a sequence of images. These networks are then used to predict expected values for the same images used in training. Substantial differences between the expected and actual values represent an unusual change. Results are presented on both multispectral and panchromatic imagery.     

Design of multiband matching ladders without mutual coupling using parametric representation of Brune functions

In this study, a semianalytical method for the design of mutual coupling free multiband matching networks is introduced. A new parametric representation of Brune functions is used for the construction of multiband ladder network topologies without mutual induction. The method involves the use of Fujisawa's constraints for low pass ladders having finite transmission zeros, in a parametric representation of driving point impedance function resulting in mutual inductance free Brune sections. The developed parametric representation is incorporated with Real Frequency Techniques to design matching networks with a plurality of pass bands. Several illustrative design examples are presented to validate the method.     

Balancing energy efficiency and quality of aggregate data in sensor networks

In-network aggregation has been proposed as one method for reducing energy consumption in sensor networks. In this paper, we explore two ideas related to further reducing energy consumption in the context of in-network aggregation. The first is by influencing the construction of the routing trees for sensor networks with the goal of reducing the size of transmitted data. To this end, we propose a group-aware network configuration method that clusters along the same path sensor nodes that belong to the same group. The second idea involves imposing a hierarchy of output filters on the sensor network with the goal of both reducing the size of transmitted data and minimizing the number of transmitted messages. More specifically, we propose a framework to use temporal coherency tolerances in conjunction with in-network aggregation to save energy at the sensor nodes while maintaining specified quality of data. These tolerances are based on user preferences or can be dictated by the network in cases where the network cannot support the current tolerance level. Our framework, called TiNA, works on top of existing in-network aggregation schemes. We evaluate experimentally our proposed schemes in the context of existing in-network aggregation schemes. We present experimental results measuring energy consumption, response time, and quality of data for Group-By queries. Overall, our schemes provide significant energy savings with respect to communication and a negligible drop in quality of data.Received: 22 October 2003, Accepted: 16 April 2004, Published online: 12 November 2004Edited by: J. Gehrke and J. HellersteinThis work is supported in part by NSF award ANI-0123705. The first author is supported in part by the Andrew Mellon Predoctoral Fellowship. This paper expands on the material presented in two workshops [31,2].     

Analytical model based on green criteria for optical backbone network interconnection

Key terms such as Global warming, Green House Gas emissions, or Energy efficiency are currently on the scope of scientific research. Regarding telecommunications networks, wireless applications, routing protocols, etc. are being designed following this new “Green” trend. This work contributes to the evaluation of the environmental impact of networks from physical interconnection point of view. Networks deployment, usage, and disposal are analyzed as contributing elements to ICT's (Information and Communications Technology) CO₂ emissions. This paper presents an analytical model for evaluating and quantifying the CO₂ emissions of optical backbone networks during their lifetime. The main goal of this work is to present the model and illustrate how to evaluate the physical interconnection of backbones from an environmental perspective. This model can be applied as a new type of decision support criteria for backbone's interconnection, since minimization of CO₂ emissions is becoming an important factor. In addition, two case studies are presented to illustrate the use and application of this model, and the need for de facto and international standards to reduce CO₂ emissions through good network planning.     

Optimized k-shortest-paths algorithm for facility restoration

The problem of finding shortest paths arises in many contexts; testing restoration algorithms and developing design packages for large telecommunications networks are two cases where the simple task of finding sets of restoration paths can consume up to 95 per cent of the execution time of an application program. This paper presents experimental studies of several well-known shortest-paths algorithms adapted to the task of finding the k-successively-shortest link-disjoint replacement paths for restoration in a telecommunications network with n nodes. The implementations range in complexity from O(kn²) when based on Dijkstra's original method, through several improvements to an efficient implementation of O(kn[v+longn]) complexity, and finally to an O(kn) implementation for the special case of edge-sparse graphs with small integer edge weights. Here v is the maximum degree of a node in the network. Several alternatives were tested during the course of these studies, particularly with a view to minimizing the number of heap updates, These alternatives are possible because we are searching for several paths between a given pair of nodes, rather than just one path between one or more pairs of nodes. Two fairly straightforward changes yield a decrease in execution time, whereas a more complex heap management strategy consumes as much time in the added code as it releases from the main routine. Experimental results confirm the theoretical complexity of q k n log n) and demonstrate a speed-up of nearly an order of magnitude over the simpler O(kn²) implementation in the largest networks tested. The optimized implementation is recommended for planning and operational applications of k-shortest paths rerouting for telecommunications network restoration and restorable network design. If hop counts or small integer link weights can be used to measure distances, then the qkn) implementation is recommended, as typical telecommunications networks are edge-sparse.     

Self-stabilizing group communication in directed networks

This paper presents the first self-stabilizing group membership service, multicast service, and resource allocation service for directed networks. The first group communication algorithm is based on a token circulation over a virtual ring. The second algorithm is based on construction of distributed spanning trees. In addition, a technique is presented that emulates, in a self-stabilizing fashion, any undirected communication network over strongly connected directed networks, is presented. A resource allocation asynchronous algorithm for strongly connected directed networks is presented.Received: 23 July 2003, Published online: 29 June 2004Partially supported by NSF Award CCR-0098305, IBM faculty award, STRIMM consortium, and Israel ministry of defense.     

Training wavelet networks for nonlinear dynamic input–output modeling

In the framework of nonlinear process modeling, we propose training algorithms for feedback wavelet networks used as nonlinear dynamic models. An original initialization procedure is presented that takes the locality of the wavelet functions into account. Results obtained for the modeling of several processes are presented; a comparison with networks of neurons with sigmoidal functions is performed.     

Least possible time paths in stochastic, time-varying networks

In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. The first algorithm determines the least possible time path from each node for each departure time interval, the least possible travel time and a lower bound on the associated probability of the occurrence of this travel time. The second algorithm determines up to k least possible time paths, the associated travel times and the corresponding probabilities of occurrence of the travel times (or a lower bound on this probability). No such efficient algorithms for determining least time paths in stochastic, time-varying networks exist in the literature.     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

基于无线传感器网络的矿震监测系统设计

提出了将无线传感器网络应用到矿震监测系统,给出了系统的网络结构,分析了系统的优点,并对系统涉及的关键技术一时间同步、震源定位、无线网络协议以及异构网的组网等问题进行了讨论,给出了相应的解决方案。     

From local neural networks to granular neural networks: A study in information granulation

In this study, we are concerned with a construction of granular neural networks (GNNs)—architectures formed as a direct result reconciliation of results produced by a collection of local neural networks constructed on a basis of individual data sets. Being cognizant of the diversity of the results produced by the collection of networks, we arrive at the concept of granular neural network, producing results in the form of information granules (rather than plain numeric entities) that become reflective of the diversity of the results generated by the contributing networks. The design of a granular neural network exploits the concept of justifiable granularity. Introduced is a performance index quantifying the quality of information granules generated by the granular neural network. This study is illustrated with the aid of machine learning data sets. The experimental results provide a detailed insight into the developed granular neural networks.     

Generating probabilistic Boolean networks from a prescribed stationary distribution

Modeling gene regulation is an important problem in genomic research. Boolean networks (BN) and its generalization probabilistic Boolean networks (PBNs) have been proposed to model genetic regulatory interactions. BN is a deterministic model while PBN is a stochastic model. In a PBN, on one hand, its stationary distribution gives important information about the long-run behavior of the network. On the other hand, one may be interested in system synthesis which requires the construction of networks from the observed stationary distribution. This results in an inverse problem which is ill-posed and challenging. Because there may be many networks or no network having the given properties and the size of the inverse problem is huge. In this paper, we consider the problem of constructing PBNs from a given stationary distribution and a set of given Boolean Networks (BNs). We first formulate the inverse problem as a constrained least squares problem. We then propose a heuristic method based on Conjugate Gradient (CG) algorithm, an iterative method, to solve the resulting least squares problem. We also introduce an estimation method for the parameters of the PBNs. Numerical examples are then given to demonstrate the effectiveness of the proposed methods.