XDist： an effective XML keyword search system with re-ranking model based on keyword distribution

Keyword search enables web users to easily access XML data without understanding the complex data schemas. However, the native ambiguity of keyword search makes it arduous to select qualified relevant results matching keywords. To solve this problem, researchers have made much effort on establishing ranking models distinguishing relevant and irrelevant passages, such as the highly cited TF＊IDF and BM25. However, these statistic based ranking methods mostly consider term frequency, inverse document frequency and length as ranking factors, ignoring the distribution and connection information between different keywords. Hence, these widely used ranking methods are powerless on recognizing irrelevant results when they are with high term frequency, indicating a performance limitation. In this paper, a new searching system XDist is accordingly proposed to attack the problems aforementioned. In XDist, we firstly use the semantic query model maximal lowest common ancestor （MAXLCA） to recognize the returned results of a given query, and then these candidate results are ranked by BM25. Especially, XDist re-ranks the top several results by a combined distribution measurement （CDM） which considers four measure criterions： term proximity, intersection of keyword classes, degree of integration among keywords and quantity variance of keywords. The weights of the four measures in CDM are trained by a listwise learning to optimize method. The experimental results on the evaluation platform of INEX show that the re-ranking method CDM can effectively improve the performance of the baseline BM25 by 22% under iP[0.01] and 18% under MAiP. Also the semantic model MAXLCA and the search engine XDist perform the best in their respective related fields.     

Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver

The problem of finding the optimal correspondence between two sets of geometric entities or features is known to be NP-hard in the worst case. This problem appears in many real scenarios such as fingerprint comparisons, image matching and global localization of mobile robots. The inherent complexity of the problem can be avoided by suboptimal solutions, but these could fail with high noise or corrupted data. The correspondence problem has an interesting equivalent formulation in finding a maximum clique in an association graph. We have developed a novel algorithm to solve the correspondence problem between two sets of features based on an efficient solution to the Maximum Clique Problem using bit parallelism. It outperforms an equivalent non bit parallel algorithm in a number of experiments with simulated and real data from two different correspondence problems. This article validates for the first time, to the best of our knowledge, that bit parallel optimization techniques can greatly reduce computational cost, thus making feasible the use of an exact solution in real correspondence search problems despite their inherent NP computational complexity.     

Optimal multiple-seams search for image resizing with smoothness and shape prior

Content-aware image resizing is of increasing relevance to allow high-quality image and video to be displayed on devices with different resolution. We present a novel method to find multiple seams simultaneously with global optimality for image resizing, incorporating both region smoothness and seam shape prior using a 3-D graph-theoretic approach. The globally optimal seams can be simultaneously achieved by solving a maximum flow problem based on an arc-weighted graph representation. Representing the resizing problem in an arc-weighted graph, we can incorporate a wide spectrum of constraints into the formulation, thus improving resizing results. By removing or inserting those multiple seams, the goal of content-aware image resizing is achieved. Due to simultaneous detection of multiple seams, our algorithm exhibits several good features: the ability to handle both crossing and non-crossing-seam cases, the ability to incorporate various feasible geometry constraints, and the ability to incorporate the seams importance, region smoothness and shape prior information. The proposed method was implemented and experimented on a variety of image data and compared with the state of the art in image resizing.     

AlineaGA—a genetic algorithm with local search optimization for multiple sequence alignment

The alignment and comparison of DNA, RNA and Protein sequences is one of the most common and important tasks in Bioinformatics. However, due to the size and complexity of the search space involved, the search for the best possible alignment for a set of sequences is not trivial. Genetic Algorithms have a predisposition for optimizing general combinatorial problems and therefore are serious candidates for solving multiple sequence alignment tasks. Local search optimization can be used to refine the solutions explored by Genetic Algorithms. We have designed a Genetic Algorithm which incorporates local search for this purpose: AlineaGA. We have tested AlineaGA with representative sequence sets of the globin family. We also compare the achieved results with the results provided by T-COFFEE.     

The higher-order Levenberg–Marquardt method with Armijo type line search for nonlinear equations

To save more Jacobian calculations and achieve a faster convergence rate, Yang [A higher-order Levenberg-Marquardt method for nonlinear equations, Appl. Math. Comput. 219(22)(2013), pp. 10682–10694, doi:10.1016/j.amc.2013.04.033, 65H10] proposed a higher-order Levenberg–Marquardt (LM) method by computing the LM step and another two approximate LM steps for nonlinear equations. Under the local error bound condition, global and local convergence of this method is proved by using trust region technique. However, it is clear that the last two approximate LM steps may be not necessarily a descent direction, and standard line search technique cannot be used directly to obtain the convergence properties of this higher-order LM method. Hence, in this paper, we employ the nonmonotone second-order Armijo line search proposed by Zhou [On the convergence of the modified Levenberg-Marquardt method with a nonmonotone second order Armijo type line search, J. Comput. Appl. Math. 239 (2013), pp. 152–161] to guarantee the global convergence of this higher-order LM method. Moreover, the local convergence is also preserved under the local error bound condition. Numerical results show that the new method is efficient.     

A robust motion estimation with center-biased diamond search and its parallel architecture for motion-compensated de-interlace

For motion compensated de-interlace, the accuracy and reliability of the motion vectors have a significant impact on the performance of the motion compensated interpolation. In order to improve the robustness of motion vector, a novel motion estimation algorithm with center-biased diamond search and its parallel VLSI architecture are proposed in this paper. Experiments show that it works better than conventional motion estimation algorithms in terms of motion compensation error and robustness, and its architecture overcomes the irregular data flow and achieves high efficiency. It also efficiently reuses data and reduces the control overhead. So, it is highly suitable for HDTV applications.     

Correction to: Can search result summaries enhance the web search efficiency and experiences of the visually impaired users?

There are limited studies that are addressing the challenges of visually impaired (VI) users when viewing search results on a search engine interface by using a screen reader. This study investigates the effect of providing an overview of search results to VI users. We present a novel interactive search engine interface called InteractSE to support VI users during the results exploration stage in order to improve their interactive experience and web search efficiency. An overview of the search results is generated using an unsupervised machine learning approach to present the discovered concepts via a formal concept analysis that is domain-independent. These concepts are arranged in a multi-level tree following a hierarchical order and covering all retrieved documents that share maximal features. The InteractSE interface was evaluated by 16 legally blind users and compared with the Google search engine interface for complex search tasks. The evaluation results were obtained based on both quantitative (as task completion time) and qualitative (as participants’ feedback) measures. These results are promising and indicate that InteractSE enhances the search efficiency and consequently advances user experience. Our observations and analysis of the user interactions and feedback yielded design suggestions to support VI users when exploring and interacting with search results.

     

Scalable parallel word search in multicore/multiprocessor systems

This paper presents a parallel algorithm for fast word search to determine the set of biological words of an input DNA sequence. The algorithm is designed to scale well on state-of-the-art multiprocessor/multicore systems for large inputs and large maximum word sizes. The pattern exhibited by many sequential solutions to this problem is a repetitive execution over a large input DNA sequence, and the generation of large amounts of output data to store and retrieve the words determined by the algorithm. As we show, this pattern does not lend itself to straightforward standard parallelization techniques. The proposed algorithm aims to achieve three major goals to overcome the drawbacks of embarrassingly parallel solution techniques: (i) to impose a high degree of cache locality on a problem that, by nature, tends to exhibit nonlocal access patterns, (ii) to be lock free or largely reduce the need for data access locking, and (iii) to enable an even distribution of the overall processing load among multiple threads. We present an implementation and performance evaluation of the proposed algorithm on DNA sequences of various sizes for different organisms on a dual processor quad-core system with a total of 8 cores. We compare the performance of the parallel word search implementation with a sequential implementation and with an embarrassingly parallel implementation. The results show that the proposed algorithm far outperforms the embarrassingly parallel strategy and achieves a speed-up’s of up to 6.9 on our 8-core test system.     

Business process management with the user requirements notation

A number of recent initiatives in both academia and industry have sought to achieve improvements in e-businesses through the utilization of Business Process Management (BPM) methodologies and tools. However there are still some inadequacies that need to be addressed when it comes to achieving alignment between business goals and business processes. The User Requirements Notation (URN), recently standardized by ITU-T, has some unique features and capabilities beyond what is available in other notations that can help address alignment issues. In this paper, a URN-based framework and its supporting toolset are introduced which provide business process monitoring and performance management capabilities integrated across the BPM lifecycle. The framework extends the URN notation with Key Performance Indicators (KPIs) and other concepts to measure and align processes and goals. An example process for controlling access to a healthcare data warehouse is used to illustrate and evaluate the framework. Early results indicate the feasibility of the approach.     

Recursive formulations for multibody systems with frictional joints based on the interaction between bodies

In practice, the clearances of joints in a great number of mechanical systems are well under control. In these cases, some of the existing methods become unpractical because of the little differences in the order of magnitude between relative movements and computational errors. Assuming that the effects of impacts are negligible, we proved that both locations and forces of contacts in joints can be fully determined by parts of joint reaction forces. Based on this fact, a method particularly suited for multibody systems possessing frictional joints with tiny clearances is presented. In order to improve the efficiency of computation, recursive formulations are proposed based on the interactions between bodies. The proposed recursive formulations can improve the computation of joint reaction forces. With the methodology presented in this paper, not only the motion of bodies in a multibody system but also the details about the contacts in joints, such as forces of contacts and locations of contact points, can be obtained. Even with the assumption of impact free, the instants of possible impacts can be detected without relying upon any ambiguous parameters, as indicated by numerical examples in this paper.     

Provably good multiprocessor scheduling with resource sharing

We present a 12(1+3R/(4m)) competitive algorithm for scheduling implicit-deadline sporadic tasks on a platform comprising m processors, where a task may request one of R shared resources.     

Network Design with Edge-Connectivity and Degree Constraints

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.     

Searching for Complex Human Activities with No Visual Examples

We describe a method of representing human activities that allows a collection of motions to be queried without examples, using a simple and effective query language. Our approach is based on units of activity at segments of the body, that can be composed across space and across the body to produce complex queries. The presence of search units is inferred automatically by tracking the body, lifting the tracks to 3D and comparing to models trained using motion capture data. Our models of short time scale limb behaviour are built using labelled motion capture set. We show results for a large range of queries applied to a collection of complex motion and activity. We compare with discriminative methods applied to tracker data; our method offers significantly improved performance. We show experimental evidence that our method is robust to view direction and is unaffected by some important changes of clothing.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

Contact type dependency of texture classification in a whiskered mobile robot

Actuated artificial whiskers modeled on rat macrovibrissae can provide effective tactile sensor systems for autonomous robots. This article focuses on texture classification using artificial whiskers and addresses a limitation of previous studies, namely, their use of whisker deflection signals obtained under relatively constrained experimental conditions. Here we consider the classification of signals obtained from a whiskered robot required to explore different surface textures from a range of orientations and distances. This procedure resulted in a variety of deflection signals for any given texture. Using a standard Gaussian classifier we show, using both hand-picked features and ones derived from studies of rat vibrissal processing, that a robust rough-smooth discrimination is achievable without any knowledge of how the whisker interacts with the investigated object. On the other hand, finer discriminations appear to require knowledge of the target’s relative position and/or of the manner in which the whisker contact its surface. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.

On the application of the minimum polynomial extrapolation method to incompressible flows with heat transfer

In this paper, the Minimum Polynomial Extrapolation method (MPE) is used to accelerate the convergence of the Characteristic–Based–Split (CBS) scheme for the numerical solution of steady state incompressible flows with heat transfer. The CBS scheme is a fractional step method for the solution of the Navier–Stokes equations while the MPE method is a vector extrapolation method which transforms the original sequence into another sequence converging to the same limit faster then the original one without the explicit knowledge of the sequence generator. The developed algorithm is tested on a two-dimensional benchmark problem (buoyancy–driven convection problem) where the Navier–Stokes equations are coupled with the temperature equation. The obtained results show the feature of the extrapolation procedure to the CBS scheme and the reduction of the computational time of the simulation.     

Modulo Constraints and the Complexity of Typechecking XML Views

The typechecking problem for transformations of relational data into tree data is the following: given a relational-to-XML transformation P, and an XML type d, decide whether for every database instance the result of the transformation P on satisfies d. TreeQL programs with projection-free conjunctive queries (see Alon et al. in ACM Trans. Comput. Log. 4(3):315–354, 2003) are considered as transformations and DTDs with arbitrary regular expressions as XML types. A non-elementary upper bound for the typechecking problem was already given by Alon et al. (ACM Trans. Comput. Log. 4(3):315–354, 2003) (although in a more general setting, where equality and negation in projection-free conjunctive queries and additional universal integrity constraints are allowed). In this paper we show that the typechecking problem is coNEXPTIME-complete. As an intermediate step we consider the following problem, which can be formulated independently of XML notions. Given a set of triples of the form (φ,k,j), where φ is a projection-free conjunctive query and k,j are natural numbers, decide whether there exists a database such that, for each triple (φ,k,j) in the set, there exists a natural number α, such that there are exactly k+j*α tuples satisfying the query φ in . Our main technical contribution consists of a NEXPTIME algorithm for the last problem. Partially supported by Polish Ministry of Science and Higher Education research project N206 022 31/3660, 2006/2009. This paper is an extended version of 20, where the coNEXPTIME upper bound was shown.     

A large-scale distributed framework for information retrieval in large dynamic search spaces

One of the main problems facing human analysts dealing with large amounts of dynamic data is that important information may not be assessed in time to aid the decision making process. We present a novel distributed processing framework called Intelligent Foraging, Gathering and Matching (I-FGM) that addresses this problem by concentrating on resource allocation and adapting to computational needs in real-time. It serves as an umbrella framework in which the various tools and techniques available in information retrieval can be used effectively and efficiently. We implement a prototype of I-FGM and validate it through both empirical studies and theoretical performance analysis.     

An approximation-based load-balancing algorithm with admission control for cluster web servers with dynamic workloads

The growth of web-based applications in business and e-commerce is building up demands for high performance web servers for better throughputs and lower user-perceived latency. These demands are leading to a widespread substitution of powerful single servers by robust newcomers, cluster web servers, in many enterprise companies. In this respect the load-balancing algorithms play an important role in boosting the performance of cluster servers. The previous load-balancing algorithms which were designed for the handling of static contents in web services suffer from significant performance degradation under dynamic and database-driven workloads. Regarding this, we propose an approximation-based load-balancing algorithm with admission control for cluster-based web servers in this study. Since it is difficult to accurately determine the loads of web servers through feedbacks from distributed agents in web servers, we propose an analytical model of a web server to estimate the web servers’ loads. To achieve this, the algorithm classifies requests based on their service times and track numbers of outstanding requests for each class of each web server node and also based on their resource demands to dynamically estimate the loads of each node. For the error handling of the model a proportional integral (PI) controller from control theory is used. Then the estimated available capacity of each web server is used for load balancing and admission control decisions. The implementation results with a standard benchmark confirm the effectiveness of the proposed scheme, which improves both the mean response time and the throughput of the cluster compared to rival load-balancing algorithms, and also avoids situations in which the cluster is overloaded, even when the request rates are beyond the cluster capacity.