Search

One of the most popular recommender system techniques is collaborative filtering (CF). Nowadays, many researchers apply a neural network with CF, but few focus on the neighbors' concept of CF. This work needs to consider two major issues: the similarity levels between the neighbors and the target user and the user's rating pattern conversion. Because different neighbors have a different influence on the target user and different users usually have a different rating pattern, the ratings directly utilized by the neighbor's preference pattern may be incorrect for the target user. Under two main issues, we try to accomplish three main ideas of CF's prediction: the similarity between users' levels, the neighbor's rating, and the rating conversion. Thus, we propose three main modules, the rating conversion module, the similarity module, and the prediction module, to solve the two issues mentioned above. The rating conversion module projects the neighbor's rating into the target user's aspect. The similarity module uses the users' attentions to compute similarity levels between users. Finally, these similarity levels and the converted ratings are integrated to perform the prediction. The proposed method is compared with the current CF with friends and latent factor model using two types of datasets: real-world and synthetic datasets. We evaluate N neighbors and all neighbors on real-world datasets to prove the number of neighbor is important. Moreover, the performance of the rating conversion module is also evaluated. The proposed method simulates the full rating datasets and the partial rating dataset to compare the effectiveness of using different types of distribution and dataset size. The experimental results demonstrate that the proposed method effectively outperformed the baselines using ranking evaluation and prediction accuracy on real-world and synthetic datasets. Besides, The effectiveness of using different the number of neighbors depends on the quality of neighbors., Competing Interests: The authors have declared that no competing interests exist.

Background: Measuring similarities between tree structured data is important for analysis of RNA secondary structures, phylogenetic trees, glycan structures, and vascular trees. The edit distance is one of the most widely used measures for comparison of tree structured data. However, it is known that computation of the edit distance for rooted unordered trees is NP-hard. Furthermore, there is almost no available software tool that can compute the exact edit distance for unordered trees., Results: In this paper, we present a practical method for computing the edit distance between rooted unordered trees. In this method, the edit distance problem for unordered trees is transformed into the maximum clique problem and then efficient solvers for the maximum clique problem are applied. We applied the proposed method to similar structure search for glycan structures. The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees. It also suggests that the proposed method has the accuracy comparative to those by the edit distance for ordered trees and by an existing method for glycan search., Conclusions: The proposed method is simple but useful for computation of the edit distance between unordered trees. The object code is available upon request.

Abstract: This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in time and space, where the parameter is the maximum bound of the edit distance and is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant. [ABSTRACT FROM AUTHOR]

The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "target tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpeläinen and Mannila from 1995 that runs in O (d 2 2 d m n) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O (d 2 d m n 2) time, improving the exponential factor from 2 2 d to 2 d by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem. • We present an O ⁎ (2 d) -time algorithm for the unordered tree inclusion problem. • This is the first improvement since the O ⁎ (4 d) -time algorithm from 1995 by Kilpeläinen and Mannila. • Even faster algorithms are given for some versions of the problem with restrictions on the node labels and tree heights. • A special case of the problem where only the leaves have distinct labels is proved to be NP-hard. [ABSTRACT FROM AUTHOR]