Previously, we proposed a probabilistic data generation model represented by an unobservable tree and a sequential updating method to calculate a posterior distribution over a set of trees. The set is called a meta-tree. In this paper, we propose a more efficient batch updating method.

A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.

Given two feasible solutions A and B, a reconfiguration problem asks whether there exists a reconfiguration sequence (A0=A, A1,...,Aℓ=B) such that (i) A0,...,Aℓ are feasible solutions and (ii) we can obtain Ai from Ai-1 under the prescribed rule (the reconfiguration rule) for each i ∈ {1,...,ℓ}. In this paper, we address the reconfiguration problem for induced trees, where an induced tree is a connected and acyclic induced subgraph of an input graph. We consider the following two rules as the prescribed rules: Token Jumping: removing u from an induced tree and adding v to the tree, and Token Sliding: removing u from an induced tree and adding v adjacent to u to the tree, where u and v are vertices of an input graph. As the main results, we show that (I) the reconfiguration problemis PSPACE-complete even if the input graph is of bounded maximum degree, (II) the reconfiguration problem is W[1]-hard when parameterized by both the size of induced trees and the length of the reconfiguration sequence, and (III) there exists an FPT algorithm when the problem is parameterized by both the size of induced trees and the maximum degree of an input graph under Token Jumping and Token Sliding.

Many concurrency control protocols for B-trees use latch-coupling because its execution is efficient on a single machine. Some studies have indicated that latch-coupling may involve a performance bottleneck when using multicore processors in a shared-everything environment, but no studies have considered the possible performance bottleneck caused by sending messages between processing elements (PEs) in shared-nothing environments. We propose two new concurrency control protocols, “LCFB” and “LCFB-link”, which require no latch-coupling in optimistic processes. The LCFB-link also innovates B-link approach within each PE to reduce the cost of modifications in the PE, as a solution to the difficulty of consistency management for the side pointers in a parallel B-tree. The B-link algorithm is well known as a protocol without latch-coupling, but B-link has the difficulty of guaranteeing the consistency of the side pointers in a parallel B-tree. Experimental results in various environments indicated that the system throughput of the proposed protocols was always superior to those of the conventional protocols, particularly in large-scale configurations, and using LCFB-link was effective for higher update ratios. In addition, to mitigate access skew, data should migrate between PEs. We have demonstrated that our protocols always improve the system throughput and are effective as concurrency controls for data migration.

Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.

We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσn letters are packed in a single machine word on the standard word RAM model, and let f(k,n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1,n] in O(klog n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in $O(rac{m}{alpha} f(k,n))$ worst-case time and in $O(rac{m}{alpha} + f(k,n))$ expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.

In the obnoxious facility game with a set of agents in a space, we wish to design a mechanism, a decision-making procedure that determines a location of an undesirable facility based on locations reported by the agents, where we do not know whether the location reported by an agent is where exactly the agent exists in the space. For a location of the facility, the benefit of each agent is defined to be the distance from the location of the facility to where the agent exists. Given a mechanism, all agents are informed of how the mechanism utilizes locations reported by the agents to determine a location of the facility before they report their locations. Some agent may try to manipulate the decision of the facility location by strategically misreporting her location. As a fair decision-making, mechanisms should be designed so that no particular group of agents can get a larger benefit by misreporting their locations. A mechanism is called group strategy-proof if no subset of agents can form a group such that every member of the group can increase her benefit by misreporting her location jointly with the rest of the group. For a given mechanism, a point in the space is called a candidate if it can be output as the location of the facility by the mechanism for some set of locations reported by agents. In this paper, we consider the case where a given space is a tree metric, and characterize the group strategy-proof mechanisms in terms of distribution of all candidates in the tree metric. We prove that there exists a group strategy-proof mechanism in the tree metric if and only if the tree has a point to which every candidate has the same distance.

Two spanning trees T1,T2 of a graph G = (V,E) are independent if they are rooted at the same vertex, say r, and for each vertex v ∈ V, the path from r to v in T1 and the path from r to v in T2 have no common vertices and no common edges except for r and v. In general, spanning trees T1,T2,…,Tk of a graph G = (V,E) are independent if they are pairwise independent. A graph G = (V,E) is called a 2-chordal ring and denoted by CR(N,d1,d2), if V = {0,1,…,N-1} and E = {(u,v)|[v-u]N = 1 or [v-u]N = d1 or [v-u]N = d2, 2 ≤ d1 < d2 ≤ N/2}. CR(N,d1,N/2) is 5-connected if N ≥ 8 is even and d1 ≠ N/2-1. We give an algorithm to construct 5 independent spanning trees of CR(N,d1,N/2),N ≥ 8 is even and 2 ≤ d1 ≤ ⌈N/4⌉.

Given a graph G, a set of spanning trees of G are completely independent if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. In this paper, we prove that for graphs of order n, with n ≥ 6, if the minimum degree is at least n-2, then there are at least ⌊n/3⌋ completely independent spanning trees.

Suppose one of the edges is attacked in a graph G, where some number of guards are placed on some of its vertices. If a guard is placed on one of the end-vertices of the attacked edge, she can defend such an attack to protect G by passing over the edge. For each of such attacks, every guard is allowed either to move to a neighboring vertex, or to stay at where she is. The eternal vertex cover number τ∞(G) is the minimum number of guards sufficient to protect G from any length of any sequence of edge attacks. This paper derives the eternal vertex cover number τ∞(G) of such graphs constructed by replacing each edge of a tree by an arbitrary elementary bipartite graph (or by an arbitrary clique), in terms of easily computable graph invariants only, thereby showing that τ∞(G) can be computed in polynomial time for such graphs G.

Let T1,T2,...,Tk be spanning trees in a graph G. If, for any two vertices u,v of G, the paths joining u and v on the k trees are mutually vertex-disjoint, then T1,T2,...,Tk are called completely independent spanning trees (CISTs for short) of G. The construction of CISTs can be applied in fault-tolerant broadcasting and secure message distribution on interconnection networks. Hasunuma (2001) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Unfortunately, this conjecture was disproved by Péterfalvi recently. In this note, we give a necessary condition for k-connected k-regular graphs with ⌊k/2⌋ CISTs. Based on this condition, we provide more counterexamples for Hasunuma's conjecture. By contrast, we show that there are two CISTs in 4-regular chordal rings CR(N,d) with N=k(d-1)+j under the condition that k ≥ 4 is even and 0 ≤ j ≤ 4. In particular, the diameter of each constructed CIST is derived.

Coupled with the discrete wavelet transform, SPIHT (set partitioning in hierarchical trees) is a highly efficient image compression technique that allows for progressive transmission. One problem, however, is that its decoding can be extremely sensitive to bit errors in the code sequence. In this paper, we address the issue of transmitting SPIHT-encoded images via noisy channels, wherein errors are inevitable. The communication scenario assumed in this paper is that the transmitter cannot get any acknowledgement from the receiver. In our scheme, the original SPIHT code sequence is first segmented into packets. Each packet is classified as either a CP (critical packet) or an RP (refinement packet). For error control, cyclic redundancy check (CRC) is incorporated into each packet. By checking the CRC check sum, the receiver is able to tell whether a packet is correctly received or not. In this way, the noisy channel can be effectively modeled as an erasure channel. For unequal error protection (UEP), each of those packets are repeatedly transmitted for a few times, as determined by a process called diversity allocation (DA). Two DA algorithms are proposed. The first algorithm produces a nearly optimal decoded image (as measured in the expected signal-to-noise ratio). However, its computation cost is extremely high. The second algorithm works in a progressive fashion and is naturally compatible with progressive transmission. Its computation complexity is extremely low. Nonetheless, its decoded image is nearly as good. Experimental results show that the proposed scheme significantly improves the decoded images. They also show that making distinction between CP and RP results in wiser diversity allocation to packets and thus produces higher quality in the decoded images.

A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where .

In this study, a novel forest method based on specific random trees (SRT) was proposed for a multiclass classification problem. The proposed SRT was built on one specific class, which decides whether a sample belongs to a certain class. The forest can make a final decision on classification by ensembling all the specific trees. Compared with the original random forest, our method has higher strength, but lower correlation and upper error bound. The experimental results based on 10 different public datasets demonstrated the efficiency of the proposed method.

This paper proposes a high-precision, high-speed keypoint matching method using two-stage randomized trees (RTs). The keypoint classification uses conventional RTs for high-precision, real-time keypoint matching. However, the wide variety of view transformations for templates expressed by RTs make it diffidult to achieve high-precision classification for all transformations with a single RTs. To solve this problem, the proposed method classifies the template view transformations in the first stage and then, in the second stage, classifies the keypoints using the RTs that corresponds to each of the view transformations classified in the first stage. Testing demonstrated that the proposed method is 88.5% more precise than SIFT, and 63.5% more precise than using conventional RTs for images in which the viewpoint of the object is rotated by 70 degrees. We have also shown that the proposed method supports real-time keypoint matching at 12 fps.

This paper proposes likelihood smoothing techniques to improve decision tree-based acoustic models, where decision trees are used as replacements for Gaussian mixture models to compute the observation likelihoods for a given HMM state in a speech recognition system. Decision trees have a number of advantageous properties, such as not imposing restrictions on the number or types of features, and automatically performing feature selection. This paper describes basic configurations of decision tree-based acoustic models and proposes two methods to improve the robustness of the basic model: DT mixture models and soft decisions for continuous features. Experimental results for the Aurora 2 speech database show that a system using decision trees offers state-of-the-art performance, even without taking advantage of its full potential and soft decisions improve the performance of DT-based acoustic models with 16.8% relative error rate reduction over hard decisions.

Scene-context plays an important role in scene analysis and object recognition. Among various sources of scene-context, we focus on scene-context scale, which means the effective scale of local context to classify an image pixel in a scene. This paper presents random forests based image categorization using the scene-context scale. The proposed method uses random forests, which are ensembles of randomized decision trees. Since the random forests are extremely fast in both training and testing, it is possible to perform classification, clustering and regression in real time. We train multi-scale texton forests which efficiently provide both a hierarchical clustering into semantic textons and local classification in various scale levels. The scene-context scale can be estimated by the entropy of the leaf node in the multi-scale texton forests. For image categorization, we combine the classified category distributions in each scale and the estimated scene-context scale. We evaluate on the MSRC21 segmentation dataset and find that the use of the scene-context scale improves image categorization performance. Our results have outperformed the state-of-the-art in image categorization accuracy.

In this paper, we introduce a concise representation, called right-distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formed sequences suggested by Zaks [Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63-82]. Using a coding tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without computing all the entries of the coefficient table.

We propose a moving picture coding by lapped transform and an edge adaptive deblocking filter to reduce the blocking distortion. We apply subband coding (SBC) with lapped transform (LT) and zero pruning set partitioning in hierarchical trees (zpSPIHT) to encode the difference picture. Effective coding using zpSPIHT was achieved by quantizing and pruning the quantized zeros. The blocking distortion caused by block motion compensated prediction is reduced by an edge adaptive deblocking filter. Since the original edges can be detected precisely at the reference picture, an edge adaptive deblocking filter on the predicted picture is very effective. Experimental results show that blocking distortion has been visually reduced at very low bit rate coding and better PSNRs of about 1.0 dB was achieved.

Set-partitioning in hierarchical trees (SPIHT) is one of the well-known image compression schemes. SPIHT offers an agreeable compression ratio and produces an embedded bit-stream for progressive transmission. However, the major disadvantage of SPIHT is its large memory requirement. In this paper, we propose a memory efficient SPIHT image coder and its parallel implantation. The memory requirement is reduced without sacrificing image quality. All bit-planes are concurrently encoded in order to speed up the entire coding flow. The result shows that the proposed algorithm is roughly 6 times faster than the original SPIHT. For a 512512 image, the memory requirement is reduced from 5.83 Mb to 491 Kb. The proposed algorithm is also realized on FPGA. With pipeline design, the circuit can run at 110 MHz, which can encode a 512512 image in 1.438 ms. Thus, the circuit achieves very high throughput, 182 MPixels/sec, and can be applied to high performance image compression applications.