Sketches are compact bit-string representations of points, often employed for speeding up searches through the effects of dimensionality reduction and data compression. In this paper, we propose a novel sketch enumeration method and demonstrate its ability to realize fast filtering for approximate nearest neighbor search in metric spaces. Whereas the Hamming distance between the query’s sketch and sketches of points to be searched has been used for sketch prioritization traditionally, recent research has introduced asymmetric distances, enabling higher recall rates with fewer candidates. Additionally, sketch enumeration methods that speed up the filtering such that high-priority solution candidates are selected based on the priority of the sketch to the given query without the need for direct sketch comparisons have been proposed. Our primary goal in this paper is to further accelerate sketch enumeration through parallel processing. While Hamming distance-based enumeration can be parallelized relatively easily, achieving high recall rates requires a large number of candidates, and speeding up the filtering alone is insufficient for overall similarity search acceleration. Therefore, we introduce the conjunctive enumeration method, which concatenates two Hamming distance-based enumerations to approximate asymmetric distance-based enumeration. Then, we validate the effectiveness of the proposed method through experiments using large-scale public datasets. Our approach offers a significant acceleration effect, thereby enhancing the efficiency of similarity search operations.

In this paper, we investigate a subcaterpillar isomorphism that is a problem, for a rooted labeled caterpillar P and a rooted labeled tree T , of determining whether or not there exists a subtree in T which is isomorphic to P .Then, we design two algorithms to solve the subcaterpillar isomorphism for a caterpillar P and a tree T in (i) O(p + tDhσ) time and O(Dh) space and in (ii) O(p + tDσ) time and O(D(h + H)) space, respectively.Here, p is the number of vertices in P , t is the number of vertices in T , h is the height of P , H is the height of T , σ is the number of alphabets for labels and D is the degree of T .Furthermore, we give experimental results of the two algorithms for artificial data and real data.

Annealing by Increasing Resampling (AIR) is a stochastic hill-climbing optimization by resampling with increasing size for evaluating an objective function. In this paper, we introduce a unified view of the conventional Simulated Annealing (SA) and AIR. In this view, we generalize both SA and AIR to a stochastic hill-climbing for objective functions with stochastic fluctuations, i.e., logit and probit, respectively. Since the logit function is approximated by the probit function, we show that AIR is regarded as an approximation of SA. The experimental results on sparse pivot selection and annealing-based clustering also support that AIR is an approximation of SA. Moreover, when an objective function requires a large number of samples, AIR is much faster than SA without sacrificing the quality of the results.

In this paper, first we formulate the problem of a bipartite edge correlation clustering which finds an edge biclique partition with the minimum disagreement from a bipartite graph, by extending the bipartite correlation clustering which finds a biclique partition. Then, we design a simple randomized algorithm for bipartite edge correlation clustering, based on the randomized algorithm of bipartite correlation clustering. Finally, we give experimental results to evaluate the algorithms from both artificial data and real data.

A rooted labeled caterpillar (caterpillar, for short) is a rooted labeled tree transformed to a rooted path (called a backbone) after removing all the leaves in it and we can compute the edit distance between caterpillars in quartic time. In this paper, we introduce two vertical distances and two horizontal distances for caterpillars. The former are based on a string edit distance between the string representations of the backbones and the latter on a multiset edit distance between the multisets of labels occurring in all the leaves. Then, we show that these distances give both lower bound and upper bound of the edit distance and we can compute the vertical distances in quadratic time and the horizontal distances in linear time under the unit cost function.

A rooted labeled caterpillar is a rooted labeled tree transformed to a path after removing all the leaves in it.In this paper, we design the algorithm to compute the edit distance between rooted labeled caterpillars in O(λ 2 h 2 ) time, where λ and h are the maximum number of leaves and the maximum height in two caterpillars, respectively.

In this paper, we formulate an anchored alignment distance between rooted labeled unordered trees as the minimum cost of the anchored alignment whose anchoring is constructed from the minimum cost isolated-subtree mapping by adding the pairs of non-mapped leaves, and design the algorithm to compute it.Since this algorithm runs in exponential time with respect to the number of leaves in theoretical, we give experimental results for randomly generated trees and for N-glycan data with small degree as real data to evaluate the anchored alignment distance by comparing with the isolated-subtree distance and the alignment distance.

In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmental mapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as the minimum costs of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance.

This article proposes an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that σ/2 ≤ τ ≤ (h + 1)σ + h, where τ is the tree edit distance between trees, and σ is the string edit distance between their binary tree codes and h is the minimum height of the trees.