Dynamic self-organising map

We present in this paper a variation of the self-organising map algorithm where the original time-dependent (learning rate and neighbourhood) learning function is replaced by a time-invariant one. This allows for on-line and continuous learning on both static and dynamic data distributions. One of the property of the newly proposed algorithm is that it does not fit the magnification law and the achieved vector density is not directly proportional to the density of the distribution as found in most vector quantisation algorithms. From a biological point of view, this algorithm sheds light on cortical plasticity seen as a dynamic and tight coupling between the environment and the model.     

Dynamic interval-based labeling scheme for efficient XML query and update processing

XML data can be represented by a tree or graph structure and XML query processing requires the information of structural relationships among nodes. The basic structural relationships are parent-child and ancestor-descendant, and finding all occurrences of these basic structural relationships in an XML data is clearly a core operation in XML query processing. Several node labeling schemes have been suggested to support the determination of ancestor-descendant or parent-child structural relationships simply by comparing the labels of nodes. However, the previous node labeling schemes have some disadvantages, such as a large number of nodes that need to be relabeled in the case of an insertion of XML data, huge space requirements for node labels, and inefficient processing of structural joins. In this paper, we propose the nested tree structure that eliminates the disadvantages and takes advantage of the previous node labeling schemes. The nested tree structure makes it possible to use the dynamic interval-based labeling scheme, which supports XML data updates with almost no node relabeling as well as efficient structural join processing. Experimental results show that our approach is efficient in handling updates with the interval-based labeling scheme and also significantly improves the performance of the structural join processing compared with recent methods.     

Augmented relaxation labeling and dynamic relaxation labeling

Current implementations of relaxation labeling are homogeneous, where each pixel is in an identical relationship to a static neighbor set. These systems maintain the iterative probabilistic labeling but use a nonhomogeneous dynamic neighborhood to establish a local consistency. Neighborhoods are created at each iteration through the broadcasting and reception of label information according to semantically established broadcasting patterns for each label. Augmented relaxation labeling is a two stage process which contains a separate relaxation stage with a top-down direction capability for specific pixel label updating. Dynamic relaxation is a one step process where every pixel label is updated through the dynamic neighborhoods. Both labeling processes are demonstrated on simple line drawings.     

Improving the labeling accuracy by a new probabilistic relaxation labeling

The updating rule of probabilistic relaxation labeling (PRL) is analyzed. A new updating rule is derived by replacing a simplifying assumption used in the derivation of the conventional updating rule with a more relevant one. The PRL with the new updating rule does not show the labeling degradation phase which appears in the conventional PRL.     

Fast connected-component labeling

Labeling of connected components in a binary image is one of the most fundamental operations in pattern recognition: labeling is required whenever a computer needs to recognize objects (connected components) in a binary image. This paper presents a fast two-scan algorithm for labeling of connected components in binary images. We propose an efficient procedure for assigning provisional labels to object pixels and checking label equivalence. Our algorithm is very simple in principle, easy to implement, and suitable for hardware and parallel implementation. We show the correctness of our algorithm, analyze its complexity, and compare it with other labeling algorithms. Experimental results demonstrated that our algorithm is superior to conventional labeling algorithms.     

Adaptive relaxation labeling

Current implementation of probabilistic relaxation labeling (PRL) is based on stationary compatibility coefficients (SCC's). Such labeling frequently diverges from an achieved minimum labeling error. In this correspondence it is shown that by having nonstationary compatibility coefficients (NSCC's) the PRL stabilizes about the minimum error which is obtained during the early iterations. Also, a noniterative labeling algorithm which uses NSCC and has a performance similar to that of the modified PRL is suggested.     

Proof labeling schemes

This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification?” and more specifically, “how expensive is local verification compared to computation?” A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.     

Light speed labeling: efficient connected component labeling on RISC architectures

This article introduces two fast algorithms for connected component Labeling of binary images, a peculiar case of coloring. The first one, Selkow _DT is pixel-based and a Selkow’s algorithm combined with the decision tree optimization technique. The second one called light speed labeling is segment-based line-relative labeling and was especially thought for commodity RISC architectures. An extensive benchmark on both structured and unstructured images substantiates that these two algorithms, the way they were designed, run faster than Wu’s algorithm claimed to be the world fastest in 2007. Also they both show greater data independency hence runtime predictability.     

Semi-supervised labeling: a proposed methodology for labeling the twitter datasets

Twitter has nowadays become a trending microblogging and social media platform for news and discussions. Since the dramatic increase in its platform has additionally set off a dramatic increase in spam utilization in this platform. For Supervised machine learning, one always finds a need to have a labeled dataset of Twitter. It is desirable to design a semi-supervised labeling technique for labeling newly prepared recent datasets. To prepare the labeled dataset lot of human affords are required. This issue has motivated us to propose an efficient approach for preparing labeled datasets so that time can be saved and human errors can be avoided. Our proposed approach relies on readily available features in real-time for better performance and wider applicability. This work aims at collecting the most recent tweets of a user using Twitter streaming and prepare a recent dataset of Twitter. Finally, a semi-supervised machine learning algorithm based on the self-training technique was designed for labeling the tweets. Semi-supervised support vector machine and semi-supervised decision tree classifiers were used as base classifiers in the self-training technique. Further, the authors have applied K means clustering algorithm to the tweets based on the tweet content. The principled novel approach is an ensemble of semi-supervised and unsupervised learning wherein it was found that semi-supervised algorithms are more accurate in prediction than unsupervised ones. To effectively assign the labels to the tweets, authors have implemented the concept of voting in this novel approach and the label pre-directed by the majority voting classifier is the actual label assigned to the tweet dataset. Maximum accuracy of 99.0% has been reported in this paper using a majority voting classifier for spam labeling.

     

Particle-based labeling: Fast point-feature labeling without obscuring other visual features

In many information visualization techniques, labels are an essential part to communicate the visualized data. To preserve the expressiveness of the visual representation, a placed label should neither occlude other labels nor visual representatives (e.g., icons, lines) that communicate crucial information. Optimal, non-overlapping labeling is an NP-hard problem. Thus, only a few approaches achieve a fast non-overlapping labeling in highly interactive scenarios like information visualization. These approaches generally target the point-feature label placement (PFLP) problem, solving only label-label conflicts. This paper presents a new, fast, solid and flexible 2D labeling approach for the PFLP problem that additionally respects other visual elements and the visual extent of labeled features. The results (number of placed labels, processing time) of our particle-based method compare favorably to those of existing techniques. Although the esthetic quality of non-real-time approaches may not be achieved with our method, it complies with practical demands and thus supports the interactive exploration of information spaces. In contrast to the known adjacent techniques, the flexibility of our technique enables labeling of dense point clouds by the use of nonoccluding distant labels. Our approach is independent of the underlying visualization technique, which enables us to demonstrate the application of our labeling method within different information visualization scenarios.     

Cognitive map architecture

Among the challenges of building robots for everyday environments is the need to integrate diverse systems and subsystems. Here, we describe a step in this direction: the Cognitive Map robot architecture. It supports a flexible multicomponent system that can be dynamically reconfigured to handle different applications with minimal changes to the system. Runtime activation of traditional and hybrid robot architecture paradigms for any particular task is supported. Our method of isolating the communication interface within a single application programming interface (API) layer supports loose coupling between components, allowing easy integration of legacy code and expansion of existing systems. We classify the components into four main roles: perception, knowledge/state representation, decision-making, and expression. Interaction, Task Matrix and Multimodal Communication are modules built in this system for facilitating human?robot interaction with the humanoid robot ASIMO built by Honda Motor Co., Ltd.We describe the key ideas behind the architecture and illustrate how they are implemented in a memory card game application where people interact with ASIMO. Through our experience and comparison with alternative approaches, we show that the Cognitive Map architecture significantly facilitates implementation of human?robot interactive scenarios.     

Banded choropleth map

Because of the disability in visualizing statistical data with spatiotemporal information of choropleth map, we propose a novel method banded choropleth map (BCM). This technique makes use of space filling, splits sub-regions with equal width or area, and then fills partitions with different colors. It can utilize limited screen space more sufficiently than small multiples. It can also preserve context more clearly than animation. Based on the technique, we made a formal evaluation to find the efficiency of BCM in doing global task and local task under different factors.     

一种新的基于区域的动态XML编码方案

在区间编码和前缀编码的基础上,提出了一种区间编码的改进的编码方案RSD（region-string-dinary）,采用二进制编码策略,可顺序友好的插入位串;提出了新的位串插入算法,可生成有序位串,且不影响已经存在位串的顺序。描述了R S D中节点间结构关系的判定方法。该二进制编码方案和位串插入算法是有效进行查询处理和避免更新时重新编码的基础。实验表明R S D使得更新时完全可避免重新编码,显示出合理的查询处理性能。     

Parallel consistent labeling algorithms

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.⁽¹⁾ Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.⁽²⁾ In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, wheren is number of nodes, anda is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.This work was partially supported by NSF Grants MCS-8221750, DCR-8506393, and DMC-8502115.     

Learning with probabilistic labeling

A nonsupervised parametric learning model using a randomized labeling procedure is discussed. Our model is an extension of the Agrawala's model and is applicable even in the case where the probability of occurrence of each category is unknown. Furthermore, the method proposed here is computationally feasible to identify a finite mixture. The learning algorithm for multivariate normal distribution is presented in this paper.