Entity matching is an issue of interest in information integration and data cleaning. Since the representations of the same entity vary, it is often impossible to fully automate the entity matching and require human inputs. However, to guarantee high-quality entity matching, how to integrate human resources into the entity matching while minimizing the cost of human resources? In this paper, we propose BUBBLE, a novel human-in-the-loop entity matching framework hybridizing Bayesian inference and crowdsourcing. To guarantee entity matching quality, Bayesian inference is conducted to determine whether the matching requires crowdsourcing. We show that we can define Bayesian error rate for this problem. For optimization, we use metric learning to select the candidate matching pairs by nearest-neighbor search in the learned embedding space, and we construct a k-nearest neighbor graph to avoid the redundant matching. We applied BUBBLE to a bibliographic data matching problem on the National Diet Library. The experimental results show that BUBBLE can assign tasks to humans with higher quality results compared to those of the same number of task assignments to humans. The result also shows that our optimization scheme is effective without sacrificing the quality.

Packet classification is used to determine the behavior of packets incoming to network devices. Since it is achieved using linear search on a classification rule list, a large number of rules leads to longer communication latency. To decrease this latency, the problem is generalized as optimal rule ordering (ORO), which aims to identify the order of rules that minimizes the classification latency caused by packet classification while preserving the classification policy. Since ORO is known to be NP-complete, various heuristics for ORO have been proposed. Sub-graph merging (SGM) is the state-of-the-art heuristic algorithm for ORO. However, the SGM algorithm does not terminate in most cases because of inappropriate updates of the array that stores the number of reachable rules. Moreover, since SGM uses the adjacent matrix to maintain the preceding relation on the rules, a considerable amount of time is consumed when the preceding relation is complex. In this paper, we propose a correction for SGM that can terminate for any instance. The proposed algorithm decreases reordering time by about 99\% compared to SGM. Furthermore, we propose a reordering algorithm that selects sub-graphs more comprehensively than SGM. Doing so decreases the latency in comparison with SGM. We show the efficiency of the algorithms through experiments.

Physical therapist (PT) emphasizes their haptic feedback during diagnosing patient symptoms. However, there is no standardized method to quantitatively assess PT's haptic sensation. In this paper, we report the difference of the haptic sensation between experts and novices using the end-feel training robot. The training robot is driven by the combination of the motor torque (controllable force) and the spring force (uncontrollable force). We employ three kinds of force protocol which imitates human end-feel reaction force. In the subjective experiment, the PTs are presented the reaction forces from the training robot and answered the most similar end-feel. We divide the PTs into two groups based on the similarity score using K-means++. The PTs are clearly classified into the high score group and the low score group. Depending on to the questionnaire, the PTs in the high score group worked long years and treated motor system disease patients mainly. This result indicates that our scoring method utilizing the training robot can evaluate the PT's haptic sensation quantitatively.

One of the problems in crowdsourcing is the development of appropriate instructions for workers. To improve task instructions, we must find typical mistake patterns. However, manually identifying these patterns is a cumbersome task. This study shows that a relatively simple approach classifying workers in terms of their understanding of task instructions is promising for addressing this issue. The verification results by domain experts suggest that the output is useful for improving task instructions.

The quest for ever faster pick-and-place robots has led to ingenious parallel robots with reduced mobility, e.g., capable of producing motions proper of SCARA systems: three independent translations and one rotation about an axis of fixed direction. These robots are also known as Schönflies-motion generators (SMG). Some parallel versions are commercially available, as are serial-parallel designs. The former are provided with four limbs, the latter with three, the fourth degree of freedom being appended in series with a Delta robot. Parallel robots are more attractive than their hybrid counterparts, but the presence of four legs poses serious challenges to their designers, as limb-interference limits the rotatability of the moving plate. A solution to this problem includes a gear train for rotation-range amplification, but this increases the inertial load on the motors and complicates the design - too many parts - and the control - because of inherent gear backlash and Coulomb friction. Recently, a SMG system was proposed that is supplied with two limbs, arrayed in an isostatic structure, which provides high rotatability of its gripper. This robot is driven by one C (cylindrical)-joint at each limb. As this joint allows for two degrees of freedom, it calls for two motors, that might as well be fixed to the base, which poses interesting design challenges. Reported in this paper is a design solution for the drive of a C joint, which is termed the C (cylindrical)-drive, based on a cylindrical differential mechanism of the RHHR type, with R standing for revolute, H for helical (or screw) joint. The design, kinematics and dynamics of the drive are discussed, along with a realization, and preliminary tests.

In this paper, parallel link mechanisms for multi drive linear motors (MDLMs) are proposed. The multi drive is a control method for linear motors in which a number of moving parts are individually driven on one stator part. Various configurations of parallel link mechanisms which were constructed for MDLMs are proposed. These mechanisms offer a wide range of motion in addition to the existing characteristics that parallel mechanisms provide, namely, rigid mechanisms, high precision, and high speed. Moreover, they are suitable for force control because of their low friction direct drive actuators. In this paper, the kinematic and dynamic characteristics of 2-DOF (xy) and 3-DOF (xy¿) planar parallel link mechanisms are investigated. A singularity analysis and internal force control method for a 3-DOF with 4 redundant moving parts is derived. The condition of dynamic decoupling and the constant inertia design of a 2-DOF with 2 moving parts and a 3-DOF with 4 moving parts are derived. The effectiveness of these analyses is then confirmed by numerical simulation. Based on this analysis, a prototype of the 3-DOF with 4 moving parts is designed and developed.

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.

A network partition, which makes it impossible for some pairs of processes to communicate with each other, is one of the most serious network failures. Although the notion of k-coterie is introduced to design a k-mutual exclusion algorithm that is robust against network failures, the number of processes allowed to simultaneously access the critical section may fatally decrease once network partition occurs. We discuss how to construct a k-coterie such that the k-mutual exclusion algorithm adopting it is robust against a network 2-partition. To this end, we introduce the notion of complemental k-coterie, and show that complemental k-coteries meet our requirements. We then give methods for constructing complemental k-coteries, and show a necessary and sufficient condition for a k-coterie to be complemental.

The coterie join operation proposed by M.L. Neilsen and M. Mizuno (1994) produces, from a k-coterie and a coterie, a new k-coterie. For the coterie join operation, this paper first shows 1) a necessary and sufficient condition to produce a nondominated k-coterie (more accurately, a nondominated k-semicoterie satisfying nonintersection property) and 2) a sufficient condition to produce a k-coterie with higher availability. By recursively applying the coterie join operation in such a way that the above conditions hold, we define nondominated k-coteries, called tree structured k-coteries, the availabilities of which are thus expected to be very high. This paper then proposes a new k-mutual exclusion algorithm that effectively uses a tree structured k-coterie, by extending Agrawal and El Abbadi's tree algorithm. The number of messages necessary for k processes obeying the algorithm to simultaneously enter the critical section is approximately bounded by k log(n/k) in the best case, where n is the number of processes in the system.

We model a distributed system by a graph G=(V, E), where V represents the set of processes and E the set of bidirectional communication links between two processes. G may not be complete. A popular (distributed) mutual exclusion algorithm on G uses a coterie C(/spl sube/2/sup V/), which is a nonempty set of nonempty subsets of V (called quorums) such that, for any two quorums P, Q/spl isin/C, 1) P/spl cup/Q/spl ne/0 and 2) P/spl nsub/Q hold. The availability is the probability that the algorithm tolerates process and/or link failures, given the probabilities that a process and a link, respectively, are operational. The availability depends on the coterie used in the algorithm. This paper proposes a method to improve the availability by transforming a given coterie.

Let C and D be two distinct coteries under the vertex set V of a graph G=(V,E) that models a distributed system. Coterie C is said to G-dominate D (with respect to G) if the following condition holds: For any connected subgraph H of G that contains a quorum in D (as a subset of its vertex set), there exists a connected subgraph H' of H that contains a quorum in C. A coterie C on a graph G is said to be G-nondominated (G-ND) (with respect to G) if no coterie D(/spl ne/C) on G G-dominates C. Intuitively, a G-ND coterie consists of irreducible quorums. This paper characterizes G-ND coteries in graph theoretical terms, and presents a procedure for deciding whether or not a given coterie C is G-ND with respect to a given graph G, based on this characterization. We then improve the time complexity of the decision procedure, provided that the given coterie C is nondominated in the sense of Garcia-Molina and Barbara (1985). Finally, we characterize the class of graphs G on which the majority coterie is G-ND.

Robust implementations of impedance control against modelling errors and disturbances are proposed. Deviation between desired impedance and actual impedance in Cartesian space is defined and modelled as impedance error. Two type robust controllers are designed based on either a high gain feedback eliminating the impedance error or a compensator of the impedance error estimated by disturbance observer. The effectiveness of the proposed controllers is confirmed by numerical simulation and realized on a 2 degree-of-freedom planer direct drive manipulator. estimated by the disturbance observer. Proposed controllers deal with Cartesian space impedance error directly and compensate for this using the usual feedback control, less computational power is needed compared with that based on joint space or the complex control techniques. The effectiveness of the proposed controllers is confirmed by numerical simulation and realized on a 2 degree-of-freedom planer direct drive manipulator.

The random logic portion of an MOS LSI chip intended mainly for a calculator is constructed of an array of MOS complex gates, each composed of an MOS ratioless circuit with a multiphase clocking system, and occupies ordinarily a considerable part of chip area. In this paper a layout system for this portion of an LSI chip is described, which is constructed on the basis of heuristics for a set of interrelated optimization problems. Implementation results of the layout system are also shown to reveal that the random logic portion can be realized in such an areas as comparable to one done by manual layout.

The random logic portion of an MOS LSI chip intended mainly for a calculator is constructed of an array of MOS complex gates, each composed of an MOS ratioless circuit with a multi-phase clocking system, and occupies ordinarily a considerable part of chip area. In this paper, a layout system for this portion of an LSI is described, which is constructed on the basis of a set of optimization heuristics. Experimental results of the layout system are also shown so as to reveal that the random logic portion can be realized in much the same area as can be done by manual layout.