Search

Abstract: In school, at least in the US, we were taught to multiply by hand according to a standard algorithm. Most people find that algorithm difficult to use, and many children fail to learn it. We propose a new way to make sense of this difficulty: to treat explicit computation as perceptually supported physical and mental action. Based on recent work in neuroscience, we trace the flow of arithmetic information to emphasize demands on visual working memory and attention. We predict that algorithms that make moderate demands on memory and attention will work better than others that make stronger demands. We suggest that the judicious use of spatial schemas can reduce such cognitive demands. Experimental evidence from children in an inner-city school supports this claim. Our work suggests new ways to think about instruction. The goal should be to minimize demands that present obstacles and maximize instead what human eyes, bodies, and brains do well. [Copyright &y& Elsevier]

Abstract: In this paper, we kernelize conventional clustering algorithms from a novel point of view. Based on the fully mathematical proof, we first demonstrate that kernel KMeans (KKMeans) is equivalent to kernel principal component analysis (KPCA) prior to the conventional KMeans algorithm. By using KPCA as a preprocessing step, we also generalize Gaussian mixture model (GMM) to its kernel version, the kernel GMM (KGMM). Consequently, conventional clustering algorithms can be easily kernelized in the linear feature space instead of a nonlinear one. To evaluate the newly established KKMeans and KGMM algorithms, we utilized them to the problem of semantic object extraction (segmentation) of color images. Based on a series of experiments carried out on a set of color images, we indicate that both KKMeans and KGMM can offer more elaborate output than the conventional KMeans and GMM, respectively. [Copyright &y& Elsevier]

Abstract: This paper presents a novel algorithm for computing graph edit distance (GED) in image categorization. This algorithm is purely structural, i.e., it needs only connectivity structure of the graph and does not draw on node or edge attributes. There are two major contributions: (1) Introducing edge direction histogram (EDH) to characterize shape features of images. It is shown that GED can be employed as distance of EDHs. This algorithm is completely independent on cost function which is difficult to be defined exactly. (2) Computing distance of EDHs with earth mover distance (EMD) which takes neighborhood bins into account so as to compute distance of EDHs correctly. A set of experiments demonstrate that the newly presented algorithm is available for classifying and clustering images and is immune to the planar rotation of images. Compared with GED from spectral seriation, our algorithm can capture the structure change of graphs better and consume 12.79% time used by the former one. The average classification rate is 5% and average clustering rate is 25% higher than the spectral seriation method. [Copyright &y& Elsevier]

Abstract: -Means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and inefficient for solving clustering problems in large data sets. Recently, a new version of the -means algorithm, the global -means algorithm has been developed. It is an incremental algorithm that dynamically adds one cluster center at a time and uses each data point as a candidate for the -th cluster center. Results of numerical experiments show that the global -means algorithm considerably outperforms the -means algorithms. In this paper, a new version of the global -means algorithm is proposed. A starting point for the -th cluster center in this algorithm is computed by minimizing an auxiliary cluster function. Results of numerical experiments on 14 data sets demonstrate the superiority of the new algorithm, however, it requires more computational time than the global -means algorithm. [Copyright &y& Elsevier]

Abstract: Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we efficiently solve two subtree-comparison problems on a set of phylogenetic trees which have practical applications to analyze the evolution and co-evolution genes clustering of genomic sequences. Let be a set of k phylogenetic trees such that the leaves of each tree are drawn from and the leaves for two arbitrary trees are not necessary the same, where n is the maximum number of the leaves among the k trees. We present a linear-time algorithm to find all the leaf-agreement descendant subtrees. By further extending this result, we present a linear-time algorithm to find all the leaf-agreement isomorphic descendant subtrees. Based on our algorithms, a web-based system using input tree files from TreeBASE is also implemented. [Copyright &y& Elsevier]

Abstract: For positive integers , an -labeling of a digraph D is a function f from into the set of nonnegative integers such that if x is adjacent to y in D and if x is of distance two to y in D. Elements of the image of f are called labels. The -labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an -labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. [Copyright &y& Elsevier]

Abstract: In this paper, we will derive a solver for a symmetric strongly nonsingular higher order generator representable semiseparable plus band matrix. The solver we will derive is based on the Levinson algorithm, which is used for solving strongly nonsingular Toeplitz systems. In the first part an solver for a semiseparable matrix of semiseparability rank p is derived, and in a second part we derive an solver for a band matrix with bandwidth . Both solvers are constructed in a similar way: firstly a Yule–Walker-like equation needs to be solved, and secondly this solution is used for solving a linear equation with an arbitrary right-hand side. Finally, a combination of the above methods is presented to solve linear systems with semiseparable plus band coefficient matrices. The overall complexity of this solver is plus lower order terms. In the final section numerical experiments are performed. Attention is paid to the timing and the accuracy of the described methods. [Copyright &y& Elsevier]

Abstract: Any set of C 2 planar boundary data (two points with associated velocities and acceleration vectors) can be interpolated by a PH curve of degree 9. In the generic case there are four such curves [R.T. Farouki, J. Manjunathaiah, S. Jee, Design of rational cam profiles with Pythagorean Hodograph curves, Mech. Mach. Theory 33 (1998) 669–682]. In this paper we give a detailed description and a qualitative analysis of these solutions. In particular we label the four solutions and compare their fairness from the point of view of possible application. For this purpose we consider the Hermite data taken from an analytical curve and study the behavior of the solutions for decreasing step-size h. This allows us to identify explicitly the solution which—for sufficiently small step-size—matches the shape of the curve with a high precision (the approximation order is 6). Consequently we are able to develop a highly robust, fast and precise algorithm converting analytical curves or curves described in G-code into a C 2 continuous PH spline curve of degree 9. [Copyright &y& Elsevier]

Abstract: In this paper, the problem of providing a fully predictable execution environment for critical and hard real-time applications on embedded and DSP-based platforms is studied from the viewpoint of system architecture and operation. We introduce a set of homogenous models for time, signals and tasks, which will further serve as a basis for describing the architecture and operation of a particular hard real-time kernel – “HARETICK”. The kernel provides support for concurrent operation of hard real-time tasks (the HRT execution environment), using non-preemptive scheduling algorithms, along with soft real-time tasks (the SRT environment), using classical, preemptive, priority-based scheduling algorithms. A set of applications has been developed to test the correct operation of the HARETICK kernel according to the theoretical models and to evaluate its abilities to provide high predictability of execution for critical applications. Some of the main testing results are also discussed in the paper. [Copyright &y& Elsevier]

Abstract: In this paper we present a novel approximate algorithm to calculate the top-k closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity and space complexity and guarantees a solution within a factor of the exact one, where t ∈{1,2,…,∞} denotes the Minkowski metrics L t of interest and d the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most d +1 sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm behaves as an exact algorithm in low dimensional spaces; it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; in any case it returns a solution within a small error to the exact one. [Copyright &y& Elsevier]

Though a large body of research has focused on tracking and identifying objects from the domain of colour or grey-scale images, there is a relative dearth in the literature on complex articulated/non-rigid motion reconstruction from a collection of low density feature points. In this paper, we propose a segment-based articulated matching algorithm to establish a crucial self-initialising identification in model-based point-feature tracking of articulated motion with near-rigid segments. We avoid common assumptions such as pose similarity or small motion with respect to the model, and assume no prior knowledge of a specific movement from which to restrict pose identification. Experimental results based on synthetic pose and real-world human motion capture data demonstrate the ability of the algorithm to perform the identification task. [Copyright &y& Elsevier]