Self-organizing maps whose topologies can be learned with adaptive binary search trees using conditional rotations

Numerous variants of Self-Organizing Maps (SOMs) have been proposed in the literature, including those which also possess an underlying structure, and in some cases, this structure itself can be defined by the user. Although the concepts of growing the SOM and updating it have been studied, the whole issue of using a self-organizing Adaptive Data Structure (ADS) to further enhance the properties of the underlying SOM, has been unexplored. In an earlier work, we impose an arbitrary, user-defined, tree-like topology onto the codebooks, which consequently enforced a neighborhood phenomenon and the so-called tree-based Bubble of Activity (BoA). In this paper, we consider how the underlying tree itself can be rendered dynamic and adaptively transformed. To do this, we present methods by which a SOM with an underlying Binary Search Tree (BST) structure can be adaptively re-structured using Conditional Rotations (CONROT). These rotations on the nodes of the tree are local, can be done in constant time, and performed so as to decrease the Weighted Path Length (WPL) of the entire tree. In doing this, we introduce the pioneering concept referred to as Neural Promotion, where neurons gain prominence in the Neural Network (NN) as their significance increases. We are not aware of any research which deals with the issue of Neural Promotion. The advantage of such a scheme is that the user need not be aware of any of the topological peculiarities of the stochastic data distribution. Rather, the algorithm, referred to as the TTOSOM with Conditional Rotations (TTOCONROT), converges in such a manner that the neurons are ultimately placed in the input space so as to represent its stochastic distribution, and additionally, the neighborhood properties of the neurons suit the best BST that represents the data. These properties have been confirmed by our experimental results on a variety of data sets. We submit that all these concepts are both novel and of a pioneering sort.     

Representing Trees of Higher Degree

This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled {1,...,k}, each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child, and subtree size. For cardinal trees the structure also supports finding the child labelled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers {1, ..., n}, giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.     

Rank and select revisited and extended

The deep connection between the Burrows–Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes.     

Efficient Learning in Adaptive Processing of Data Structures

Many researchers have explored the use of neural network models for the adaptive processing of data structures. The learning formulation for one of the models is known as the Backpropagation Through Structure (BPTS) algorithm. The main limitations of the BPTS algorithm are attributed to the problems of slow convergence speed and long-term dependency. In this Letter, a novel heuristic algorithm is proposed. The idea of this algorithm is to optimize the free parameters of the node representation in data structure by using a hybrid type of learning algorithm. Encouraging results achieved demonstrate that this proposed algorithm outperforms the BPTS algorithm.     

Using structured steiner trees for hierarchical global routing

The Steiner problem in a hierarchical graph model, the structured graph, is defined. The problem finds applications to hierarchical global routing. Properties of minimum-cost Steiner trees in structured graphs are investigated. A “top-down” approximate solution to the Steiner problem in structured graphs, called a top-down Steiner tree, is defined, and an algorithm is given to compute such solution. The top-down Steiner tree provides also an approximate solution to the Steiner problem in graphs admitting a structured representation. The properties of such solution are discussed and some experimental results on the quality of the approximation are presented. A reduction in time complexity is demonstrated with respect to both exact and heuristic algorithms applied to such graphs.     

Adaptive searching and replication of images in mobile hierarchical peer-to-peer networks

Due to the limitation of resources in mobile handheld devices and bandwidth constraints in wireless networks, it is important to efficiently manage image content and traffic to improve network throughput and response time. The efficient distribution of images in wireless networks is based on many parameters like the quality of service requirement, available bandwidth, restricted memory and diverse user profiles. We consider digital images as data objects accessed in a hierarchical mobile ad-hoc peer-to-peer network, referred as M-P2P. Our objective is to optimize the number of replicas of images in such a network architecture based on the resource limitations of the requesting peers equipped with miniature mobile devices as well as of wireless constraints in mobile ad-hoc networks (MANET). While replicating images, fragments of different resolution and their residues are used to optimize the traffic in the network and to decrease the search turnaround time. We call this replication algorithm as Ada-Rep. Performance evaluation is done by simulating Ada-Rep, base replication and uniform replication methods to evaluate parameters such as response time, failure rate, memory usage, traffic etc. Our results prove the efficiency and better performance of Ada-Rep.     

Static Optimality and Dynamic Search-Optimality in Lists and Trees

Abstract. Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made in [BB] that if computational decision-making costs are not considered, then these ``weighted experts' techniques from Machine Learning allow one to achieve a 1+ε ratio against the best static object in hindsight for a wide range of data structure problems. In this paper we give two results. First, we show that for the case of lists , we can achieve a 1+ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously. Second, for trees, we show a (computationally in efficient) algorithm that achieves what we call ``dynamic search optimality': dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.     

Finding extreme points in three dimensions and solving the post-office problem in the plane

This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ? in h, determine a point of P that is hit first when h is rotated around ?. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.     

飞行数据改进中值滤波和自适应小波降噪

研究飞行数据预处理时提高数据质量问题.针对飞行数据易受噪声干扰,提出了改进中值滤波和自适应小波阈值降噪的降噪算法.首先以改进的中值滤波算法对飞行数据进行处理以剔除野值;然后对剔除野值后的飞行数据进行小波分解,根据各层小波系数的噪声自相关函数确定最佳小波分解层数;最后设计了新的自适应阈值函数,对小波系数进行处理并重构,得到降噪数据.采用仿真数据和飞行数据进行实验,结果表明,改进方法取得了良好的降噪效果,改善了数据质量,证明算法有效性.