A space and time efficient algorithm for SimRank computation

SimRank has become an important similarity measure to rank web documents based on a graph model on hyperlinks. The existing approaches for conducting SimRank computation adopt an iteration paradigm. The most efficient deterministic technique yields O(n³)O\left(n^3\right) worst-case time per iteration with the space requirement O(n²)O\left(n^2\right), where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes O (min{ n ·m , n^r })O \left(\min \left\{ n \cdot m , n^r \right\}\right) time and O ( n + m )O \left( n + m \right) space, where m is the number of edges in a web-graph model and r ≤ log₂ 7. In addition, we extend the similarity transition matrix to prevent random surfers getting stuck, and devise a pruning technique to eliminate impractical similarities for each iteration. Moreover, we also develop a reordering technique combined with an over-relaxation method, not only speeding up the convergence rate of the existing techniques, but achieving I/O efficiency as well. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.     

EASEA: specification and execution of evolutionary algorithms on GPGPU

EASEA is a framework designed to help non-expert programmers to optimize their problems by evolutionary computation. It allows to generate code targeted for standard CPU architectures, GPGPU-equipped machines as well as distributed memory clusters. In this paper, EASEA is presented by its underlying algorithms and by some example problems. Achievable speedups are also shown onto different NVIDIA GPGPUs cards for different optimization algorithm families.     

Extension of the DEMATEL method in an uncertain linguistic environment

The decision making trial and evaluation laboratory (DEMATEL) method is a useful tool for analyzing correlations among factors using crisp values. However, the crisp values are inadequate to model real-life situations due to the fuzziness and uncertainty that are frequently involved in judgments of experts. The aim of this paper is to extend the DEMATEL method to an uncertain linguistic environment. In this paper, the correlation information among factors provided by experts is in the form of uncertain linguistic terms. A formula is first presented to transform correlation information from uncertain linguistic terms to trapezoidal fuzzy numbers. Then, we aggregate the transformed correlation information of each expert into group information using the operations of trapezoidal fuzzy numbers. The importance and classification of factors are determined via fuzzy matrix operations. Furthermore, a causal diagram is constructed to vividly show the different roles of factors. Finally, an example is used to illustrate the procedure of the proposed method.     

Mutual learning of multi-consciousness agents,including an ego for an autonomous vehicle

In this paper, we propose a multi-agent learning system for the control of an intelligent robot, based on a model of the human consciousnesses, including the ego. We pay attention to the intelligent learning processes of human beings. We try to give a robot a high learning ability by modeling the roles of the human consciousnesses, including the ego. In most ordinary methods, the instructions for learning are given from outside the system only. In the proposed method, the instructions are given not only from outside, but also from inside (from other agents in the system). Therefore, the robot can learn efficiently because it has more instructions than usual. The learning is also more flexible, since an agent learns by instructions from other agents while the learning agent and one of the instructing agents exchange roles according to changes in the environment. We experimentally verified that the proposed method is efficient by using an actual robot.     

Path planning for an autonomous mobile robot considering a region with a velocity constraint in a real environment

Recently, many research projects and competitions have attempted to find an autonomous mobile robot that can drive in the real world. In this article, we consider a path-planning method for an autonomous mobile robot that would be safe in a real environment. In such a case, it is very important for the robot to be able to identify its own position and orientation in real time. Therefore, we applied a localization method based on a particle filter. Moreover, in order to improve the safety of such autonomous locomotion, we improved the path-planning algorithm and the generation of the trajectory so that it can consider a region with a limited maximum velocity. In order to demonstrate the validity of the proposed method, we participated in the Real World Robot Challenge 2010. The experimental results are given.     

A note on double lacunary statistical $$\sigma$$-convergence of fuzzy numbers

Quite recently, Sava? (Appl Math Lett 21:134–141, 2008), defined the lacunary statistical analogue for double sequence \(X=\{X_{k,l}\}\) of fuzzy numbers as follows: a double sequence \(X=\{X_{k,l}\}\) is said to be lacunary P-statistically convergent to \(X_{0}\) provided that for each \(\epsilon >0\)

$ P-\lim_{r,s}\frac{1}{h_{r,s}}\left | \{(k,l)\in I_{r,s}: d(X_{k,l },X_0)\geq \epsilon\}\right|= 0. $

In this paper we introduce and study double lacunary \(\sigma\)-statistical convergence for sequence of fuzzy numbers and also we get some inclusion theorems.

     

A K-nearest neighbours method based on imprecise probabilities

K-nearest neighbours algorithms are among the most popular existing classification methods, due to their simplicity and good performances. Over the years, several extensions of the initial method have been proposed. In this paper, we propose a K-nearest neighbours approach that uses the theory of imprecise probabilities, and more specifically lower previsions. We show that the proposed approach has several assets: it can handle uncertain data in a very generic way, and decision rules developed within this theory allow us to deal with conflicting information between neighbours or with the absence of close neighbour to the instance to classify. We show that results of the basic k-NN and weighted k-NN methods can be retrieved by the proposed approach. We end with some experiments on the classical data sets.     

A digital library framework for heterogeneous music collections: from document acquisition to cross-modal interaction

In this paper, we present a digital library system for managing heterogeneous music collections. The heterogeneity refers to various document types and formats as well as to different modalities, e. g., CD-audio recordings, scanned sheet music, and lyrics. The system offers a full-fledged, widely automated document processing chain: digitization, indexing, annotation, access, and presentation. Our system is implemented as a generic and modular music repository based on a service-oriented software architecture. As a particular strength of our approach, the various documents representing aspects of a piece of music are jointly considered in all stages of the document processing chain. Our user interfaces allow for a multimodal and synchronized presentation of documents (WYSIWYH: what you see is what you hear), a score- or lyrics-based navigation in audio, as well as a cross- and multimodal retrieval. Hence, our music repository may be called a truly cross-modal library system. In our paper, we describe the system components, outline the techniques of the document processing chain, and illustrate the implemented functionalities for user interaction. We describe how the system is put into practice at the Bavarian State Library (BSB) Munich as a part of the German PROBADO Digital Library Initiative (PDLI).     

Missing data imputation for fuzzy rule-based classification systems

Fuzzy rule-based classification systems (FRBCSs) are known due to their ability to treat with low quality data and obtain good results in these scenarios. However, their application in problems with missing data are uncommon while in real-life data, information is frequently incomplete in data mining, caused by the presence of missing values in attributes. Several schemes have been studied to overcome the drawbacks produced by missing values in data mining tasks; one of the most well known is based on preprocessing, formerly known as imputation. In this work, we focus on FRBCSs considering 14 different approaches to missing attribute values treatment that are presented and analyzed. The analysis involves three different methods, in which we distinguish between Mamdani and TSK models. From the obtained results, the convenience of using imputation methods for FRBCSs with missing values is stated. The analysis suggests that each type behaves differently while the use of determined missing values imputation methods could improve the accuracy obtained for these methods. Thus, the use of particular imputation methods conditioned to the type of FRBCSs is required.