Search

Referring to the issue that the hop value of the range-free DV-hop positioning algorithm could not reflect the distance between two nodes within the communication range, this paper proposes an algorithm named as HCRDV-Hop. According to the proposed algorithm, the distance measured by hops between two nodes is re-treated as the specific value with dividing the received signal strength (denoted as RSSI) between nodes with the maximum average signal strength of nodes (RSSImax). Based on that, we also introduce the mathematical reasoning as well as provide the implementation procedures of the proposed algorithm. Moreover, the simulation verification is then elaborated in order to evaluate the algorithm performance. According to the simulation result, we discover that the proposed HCRDV-Hop algorithm reveals better performance in the distribution of node positioning deviations and the relative positioning deviations. [ABSTRACT FROM AUTHOR]

It has been known that when an assisted driving item is added to the Hamiltonian of the main system, the efficiency of the resultant adiabatic evolution can be significantly improved. In some special cases, it can be seen that, only by adding an assisted driving Hamiltonian can the resultant adiabatic evolution work. So it seems that, the additional driving Hamiltonian plays an important role in adiabatic computing. In this paper, we show five kinds of possible forms of the driving Hamiltonian, and analyses the performance of the algorithms. We find that the former fourth kinds of driving Hamiltonian may still cause the adiabatic algorithm lose their efficiency when the overlap of the initial and final states equals some special value. More importantly, we find that only the final kinds of the driving Hamiltonian can be extended. By modifying its interpolating functions, the final kind of adiabatic algorithm can suit any fidelity of the systems to keep the adiabatic evolution always be valid. Finally, the time complexity of the extended algorithm is better than the original adiabatic algorithm, which owns a constant running time complexity. Although the time complexity is shifted to the complexity of implementing the driving Hamiltonian added. [ABSTRACT FROM AUTHOR]

Advanced Metering Infrastructure (AMI) realizes a two-way communication of electricity data through by interconnecting with a computer network as the core component of the smart grid. Meanwhile, it brings many new security threats and the traditional intrusion detection method can’t satisfy the security requirements of AMI. In this paper, an intrusion detection system based on Online Sequence Extreme Learning Machine (OS-ELM) is established, which is used to detecting the attack in AMI and carrying out the comparative analysis with other algorithms. Simulation results show that, compared with other intrusion detection methods, intrusion detection method based on OS-ELM is more superior in detection speed and accuracy. [ABSTRACT FROM AUTHOR]

In 1979 Haralick famously introduced a method for analyzing the texture of an image: a set of statistics extracted from the co-occurrence matrix. In this paper we investigate novel sets of texture descriptors extracted from the co-occurrence matrix; in addition, we compare and combine different strategies for extending these descriptors. The following approaches are compared: the standard approach proposed by Haralick, two methods that consider the co-occurrence matrix as a three-dimensional shape, a gray-level run-length set of features and the direct use of the co-occurrence matrix projected onto a lower dimensional subspace by principal component analysis. Texture descriptors are extracted from the co-occurrence matrix evaluated at multiple scales. Moreover, the descriptors are extracted not only from the entire co-occurrence matrix but also from subwindows. The resulting texture descriptors are used to train a support vector machine and ensembles. Results show that our novel extraction methods improve the performance of standard methods. We validate our approach across six medical datasets representing different image classification problems using the Wilcoxon signed rank test. The source code used for the approaches tested in this paper will be available at: http://www.dei.unipd.it/wdyn/?IDsezione=3314&IDgruppo_pass=124&preview=. [ABSTRACT FROM AUTHOR]

Recent studies show that individuals in a social network can be divided into different groups of densely connected communities, and these individuals who bridge different communities, referred to as structural hole spanners, have great potential to acquire resources/information from communities and thus benefit from the access. Structural hole spanners are crucial in many real applications such as community detections, diffusion controls, viral marketing, etc. In spite of their importance, little attention has been paid to them. Particularly, how to accurately characterize the structural hole spanners and how to devise efficient yet scalable algorithms to find them in a large social network are fundamental issues. In this paper, we study the top-$k$ structural hole spanner problem. We first provide a novel model to measure the quality of structural hole spanners through exploiting the structural hole spanner properties. Due to its NP-hardness, we then devise two efficient yet scalable algorithms, by developing innovative filtering techniques that can filter out unlikely solutions as quickly as possible, while the proposed techniques are built up on fast estimations of the upper and lower bounds on the cost of an optimal solution and make use of articulation points in real social networks. We finally conduct extensive experiments to validate the effectiveness of the proposed model, and to evaluate the performance of the proposed algorithms using real world datasets. The experimental results demonstrate that the proposed model can capture the characteristics of structural hole spanners accurately, and the structural hole spanners found by the proposed algorithms are much better than those by existing algorithms in all considered social networks, while the running times of the proposed algorithms are very fast. [ABSTRACT FROM AUTHOR]

Reversing is the notion of thinking or working in reverse. Computer science textbooks and tutors recognize it primarily in the form of recursion. However, recursion is only one form of reversing. Reversing appears in the computer science curriculum in many other forms, at various intellectual levels, in a variety of fundamental courses. As such, it is too important a notion to be left unexplored. In this paper we discuss reversing in the context of two theoretical frameworks - as a fundamental idea in computer science, in the context of Schwill's model of fundamental ideas, and as a powerful problem solving means, in the context of Schoenfeld's cognitive model of problem solving. We recognize seven different forms of reversing, and demonstrate the essential role of each in algorithm or proof design. Our focus in the paper is conceptual, yet we briefly note our initial experimental experience, with student difficulties in both the invocation and utilization of reversing. We then discuss cognitive aspects of the teaching of reversing and offer ways to assimilate its awareness and elaborate its fundamental role in computer science. [ABSTRACT FROM AUTHOR]

Abstract: Associative-classification is a promising classification method based on association-rule mining. Significant amount of work has already been dedicated to the process of building a classifier based on association rules. However, relatively small amount of research has been performed in association-rule mining from multi-label data. In such data each example can belong, and thus should be classified, to more than one class. This paper aims at the most demanding, with respect to computational cost, part in associative-classification, which is efficient generation of association rules. This task can be achieved using different frequent pattern mining methods. In this paper, we propose a new method that is based on the state-of-the-art tree-projection-based frequent pattern mining algorithm. This algorithm is modified to improve its efficiency and extended to accommodate the multi-label recurrent-item associative-classification rule generation. The proposed algorithm is tested and compared with A priori-based associative-classification rule generator on two large datasets. [Copyright &y& Elsevier]

Abstract: The interconnection network considered in this paper is the folded hypercube that is an attractive variance of the well-known hypercube. The folded hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. In this paper, we study the path embedding aspects, bipanconnectivity and -panconnectivity, of the -dimensional folded hypercube. A bipartite graph is bipanconnected if each pair of vertices and are joined by the bipanconnected paths that include a path of each length satisfying and is even, where is the number of vertices, and denotes the shortest distance between and . A graph is -panconnected if each pair of vertices and are joined by the paths that include a path of each length ranging from to . In this paper, we introduce a new graph called the Path-of-Ladders. By presenting algorithms to embed the Path-of-Ladders into the folded hypercube, we show that the -dimensional folded hypercube is bipanconnected for is an odd number. We also show that the -dimensional folded hypercube is strictly -panconnected for is an even number. That is, each pair of vertices are joined by the paths that include a path of each length ranging from to ; and the value reaches the lower bound of the problem. [Copyright &y& Elsevier]

The main objective of this paper is to describe a realistic framework to understand parallel performance of high-dimensional image processing algorithms in the context of heterogeneous networks of workstations (NOWs). As a case study, this paper explores techniques for mapping hyperspectral image analysis techniques onto fully heterogeneous NOWs. Hyperspectral imaging is a new technique in remote sensing that has gained tremendous popularity in many research areas, including satellite imaging and aerial reconnaissance. The automation of techniques able to transform massive amounts of hyperspectral data into scientific understanding in valid response times is critical for space-based Earth science and planetary exploration. Using an evaluation strategy which is based on comparing the efficiency achieved by an heterogeneous algorithm on a fully heterogeneous NOW with that evidenced by its homogeneous version on a homogeneous NOW with the same aggregate performance as the heterogeneous one, we develop a detailed analysis of parallel algorithms that integrate the spatial and spectral information in the image data through mathematical morphology concepts. For comparative purposes, performance data for the tested algorithms on Thunderhead (a large-scale Beowulf cluster at NASA’s Goddard Space Flight Center) are also provided. Our detailed investigation of the parallel properties of the proposed morphological algorithms provides several intriguing findings that may help image analysts in selection of parallel techniques and strategies for specific applications. [ABSTRACT FROM AUTHOR]

A commonly used strategy to improve search accuracy is through feedback techniques. Most existing work on feedback relies on positive information, and has been extensively studied in information retrieval. However, when a query topic is difficult and the results from the first-pass retrieval are very poor, it is impossible to extract enough useful terms from a few positive documents. Therefore, the positive feedback strategy is incapable to improve retrieval in this situation. Contrarily, there is a relatively large number of negative documents in the top of the result list, and it has been confirmed that negative feedback strategy is an important and useful way for adapting this scenario by several recent studies. In this paper, we consider a scenario when the search results are so poor that there are at most three relevant documents in the top twenty documents. Then, we conduct a novel study of multiple strategies for relevance feedback using both positive and negative examples from the first-pass retrieval to improve retrieval accuracy for such difficult queries. Experimental results on these TREC collections show that the proposed language model based multiple model feedback method which is generally more effective than both the baseline method and the methods using only positive or negative model. [ABSTRACT FROM AUTHOR]

Protein-Protein Interaction (PPI) extraction is an important task in the biomedical information extraction. Presently, many machine learning methods for PPI extraction have achieved promising results. However, the performance is still not satisfactory. One reason is that the semantic resources were basically ignored. In this paper, we propose a multiple-kernel learning-based approach to extract PPIs, combining the feature-based kernel, tree kernel and semantic kernel. Particularly, we extend the shortest path-enclosed tree kernel (SPT) by a dynamic extended strategy to retrieve the richer syntactic information. Our semantic kernel calculates the protein-protein pair similarity and the context similarity based on two semantic resources: WordNet and Medical Subject Heading (MeSH). We evaluate our method with Support Vector Machine (SVM) and achieve an F-score of 69.40% and an AUC of 92.00%, which show that our method outperforms most of the state-of-the-art systems by integrating semantic information. [ABSTRACT FROM AUTHOR]

Time-course gene expression datasets, which record continuous biological processes of genes, have recently been used to predict gene function. However, only few positive genes can be obtained from annotation databases, such as gene ontology (GO). To obtain more useful information and effectively predict gene function, gene annotations are clustered together to form a learnable and effective learning system. In this paper, we propose a novel multi-instance hierarchical clustering (MIHC) method to establish a learning system by clustering GO and compare this method with other learning system establishment methods. Multi-label support vector machine classifier and multi-label K-nearest neighbor classifier are used to verify these methods in four yeast time-course gene expression datasets. The MIHC method shows good performance, which serves as a guide to annotators or refines the annotation in detail. [ABSTRACT FROM AUTHOR]

Numerous digitization and ontological initiatives have focused on translating biological knowledge from narrative text to machine-readable formats. In this paper, we describe two workflows for knowledge extraction and semantic annotation of text data objects featured in an online biodiversity aggregator, the Encyclopedia of Life. One workflow tags text with DBpedia URIs based on keywords. Another workflow finds taxon names in text using GNRD for the purpose of building a species association network. Both workflows work well: the annotation workflow has an F1 Score of 0.941 and the association algorithm has an F1 Score of 0.885. Existing text annotators such as Terminizer and DBpedia Spotlight performed well, but require some optimization to be useful in the ecology and evolution domain. Important future work includes scaling up and improving accuracy through the use of distributional semantics. [ABSTRACT FROM AUTHOR]

Hundreds of millions of figures are available in biomedical literature, representing important biomedical experimental evidence. This ever-increasing sheer volume has made it difficult for scientists to effectively and accurately access figures of their interest, the process of which is crucial for validating research facts and for formulating or testing novel research hypotheses. Current figure search applications can't fully meet this challenge as the “bag of figures” assumption doesn't take into account the relationship among figures. In our previous study, hundreds of biomedical researchers have annotated articles in which they serve as corresponding authors. They ranked each figure in their paper based on a figure's importance at their discretion, referred to as “figure ranking”. Using this collection of annotated data, we investigated computational approaches to automatically rank figures. We exploited and extended the state-of-the-art listwise learning-to-rank algorithms and developed a new supervised-learning model BioFigRank. The cross-validation results show that BioFigRank yielded the best performance compared with other state-of-the-art computational models, and the greedy feature selection can further boost the ranking performance significantly. Furthermore, we carry out the evaluation by comparing BioFigRank with three-level competitive domain-specific human experts: (1) First Author, (2) Non-Author-In-Domain-Expert who is not the author nor co-author of an article but who works in the same field of the corresponding author of the article, and (3) Non-Author-Out-Domain-Expert who is not the author nor co-author of an article and who may or may not work in the same field of the corresponding author of an article. Our results show that BioFigRank outperforms Non-Author-Out-Domain-Expert and performs as well as Non-Author-In-Domain-Expert. Although BioFigRank underperforms First Author, since most biomedical researchers are either in- or out-domain-experts for an article, we conclude that BioFigRank represents an artificial intelligence system that offers expert-level intelligence to help biomedical researchers to navigate increasingly proliferated big data efficiently. [ABSTRACT FROM AUTHOR]

Image encryption is an important and effective technique to protect image security. In this paper, a novel image encryption algorithm combining Julia sets and Hilbert curves is proposed. The algorithm utilizes Julia sets’ parameters to generate a random sequence as the initial keys and gets the final encryption keys by scrambling the initial keys through the Hilbert curve. The final cipher image is obtained by modulo arithmetic and diffuse operation. In this method, it needs only a few parameters for the key generation, which greatly reduces the storage space. Moreover, because of the Julia sets’ properties, such as infiniteness and chaotic characteristics, the keys have high sensitivity even to a tiny perturbation. The experimental results indicate that the algorithm has large key space, good statistical property, high sensitivity for the keys, and effective resistance to the chosen-plaintext attack. [ABSTRACT FROM AUTHOR]

Automatic text categorization is one of the key techniques in information retrieval and the data mining field. The classification is usually time-consuming when the training dataset is large and high-dimensional. Many methods have been proposed to solve this problem, but few can achieve satisfactory efficiency. In this paper, we present a method which combines the Latent Dirichlet Allocation (LDA) algorithm and the Support Vector Machine (SVM). LDA is first used to generate reduced dimensional representation of topics as feature in VSM. It is able to reduce features dramatically but keeps the necessary semantic information. The Support Vector Machine (SVM) is then employed to classify the data based on the generated features. We evaluate the algorithm on 20 Newsgroups and Reuters-21578 datasets, respectively. The experimental results show that the classification based on our proposed LDA+SVM model achieves high performance in terms of precision, recall and F1 measure. Further, it can achieve this within a much shorter time-frame. Our process improves greatly upon the previous work in this field and displays strong potential to achieve a streamlined classification process for a wide range of applications. [ABSTRACT FROM AUTHOR]

With great potential for assisting radiological image interpretation and decision making, content-based image retrieval in the medical domain has become a hot topic in recent years. Many methods to enhance the performance of content-based medical image retrieval have been proposed, among which the relevance feedback (RF) scheme is one of the most promising. Given user feedback information, RF algorithms interactively learn a user’s preferences to bridge the “semantic gap” between low-level computerized visual features and high-level human semantic perception and thus improve retrieval performance. However, most existing RF algorithms perform in the original high-dimensional feature space and ignore the manifold structure of the low-level visual features of images. In this paper, we propose a new method, termed dual-force ISOMAP (DFISOMAP), for content-based medical image retrieval. Under the assumption that medical images lie on a low-dimensional manifold embedded in a high-dimensional ambient space, DFISOMAP operates in the following three stages. First, the geometric structure of positive examples in the learned low-dimensional embedding is preserved according to the isometric feature mapping (ISOMAP) criterion. To precisely model the geometric structure, a reconstruction error constraint is also added. Second, the average distance between positive and negative examples is maximized to separate them; this margin maximization acts as a force that pushes negative examples far away from positive examples. Finally, the similarity propagation technique is utilized to provide negative examples with another force that will pull them back into the negative sample set. We evaluate the proposed method on a subset of the IRMA medical image dataset with a RF-based medical image retrieval framework. Experimental results show that DFISOMAP outperforms popular approaches for content-based medical image retrieval in terms of accuracy and stability. [ABSTRACT FROM AUTHOR]

Biclustering has emerged as an important approach to the analysis of large-scale datasets. A biclustering technique identifies a subset of rows that exhibit similar patterns on a subset of columns in a data matrix. Many biclustering methods have been proposed, and most, if not all, algorithms are developed to detect regions of “coherence” patterns. These methods perform unsatisfactorily if the purpose is to identify biclusters of a constant level. This paper presents a two-step biclustering method to identify constant level biclusters for binary or quantitative data. This algorithm identifies the maximal dimensional submatrix such that the proportion of non-signals is less than a pre-specified tolerance δ. The proposed method has much higher sensitivity and slightly lower specificity than several prominent biclustering methods from the analysis of two synthetic datasets. It was further compared with the Bimax method for two real datasets. The proposed method was shown to perform the most robust in terms of sensitivity, number of biclusters and number of serotype-specific biclusters identified. However, dichotomization using different signal level thresholds usually leads to different sets of biclusters; this also occurs in the present analysis. [ABSTRACT FROM AUTHOR]

Minimum squared error based classification (MSEC) method establishes a unique classification model for all the test samples. However, this classification model may be not optimal for each test sample. This paper proposes an improved MSEC (IMSEC) method, which is tailored for each test sample. The proposed method first roughly identifies the possible classes of the test sample, and then establishes a minimum squared error (MSE) model based on the training samples from these possible classes of the test sample. We apply our method to face recognition. The experimental results on several datasets show that IMSEC outperforms MSEC and the other state-of-the-art methods in terms of accuracy. [ABSTRACT FROM AUTHOR]

Texts in natural scenes carry rich semantic information, which can be used to assist a wide range of applications, such as object recognition, image/video retrieval, mapping/navigation, and human computer interaction. However, most existing systems are designed to detect and recognize horizontal (or near-horizontal) texts. Due to the increasing popularity of mobile-computing devices and applications, detecting texts of varying orientations from natural images under less controlled conditions has become an important but challenging task. In this paper, we propose a new algorithm to detect texts of varying orientations. Our algorithm is based on a two-level classification scheme and two sets of features specially designed for capturing the intrinsic characteristics of texts. To better evaluate the proposed method and compare it with the competing algorithms, we generate a comprehensive dataset with various types of texts in diverse real-world scenes. We also propose a new evaluation protocol, which is more suitable for benchmarking algorithms for detecting texts in varying orientations. Experiments on benchmark datasets demonstrate that our system compares favorably with the state-of-the-art algorithms when handling horizontal texts and achieves significantly enhanced performance on variant texts in complex natural scenes. [ABSTRACT FROM AUTHOR]

Text tokenization is a fundamental pre-processing step for almost all the information processing applications. This task is nontrivial for the scarce resourced languages such as Urdu, as there is inconsistent use of space between words. In this paper a morpheme matching based approach has been proposed for Urdu text tokenization, along with some other algorithms to solve the additional issues of boundary detection of compound words, affixation, reduplication, names and abbreviations. This study resulted into 97.28% precision, 93.71% recall, and 95.46% F1-measure; while tokenizing a corpus of 57000 words by using a morpheme list with 6400 entries. [ABSTRACT FROM AUTHOR]

Tensor subspace transformation, a commonly used subspace transformation technique, has gained more and more popularity over the past few years because many objects in the real world can be naturally represented as multidimensional arrays, i.e. tensors. For example, a RGB facial image can be represented as a three-dimensional array (or 3rd-order tensor). The first two dimensionalities (or modes) represent the facial spatial information and the third dimensionality (or mode) represents the color space information. Each mode of the tensor may express a different semantic meaning. Thus different transformation strategies should be applied to different modes of the tensor according to their semantic meanings to obtain the best performance. To the best of our knowledge, there are no existing tensor subspace transformation algorithm which implements different transformation strategies on different modes of a tensor accordingly. In this paper, we propose a fusion tensor subspace transformation framework, a novel idea where different transformation strategies are implemented on separate modes of a tensor. Under the framework, we propose the Fusion Tensor Color Space (FTCS) model for face recognition. [ABSTRACT FROM AUTHOR]

Drug-drug interaction (DDI) detection is particularly important for patient safety. However, the amount of biomedical literature regarding drug interactions is increasing rapidly. Therefore, there is a need to develop an effective approach for the automatic extraction of DDI information from the biomedical literature. In this paper, we present a Stacked Generalization-based approach for automatic DDI extraction. The approach combines the feature-based, graph and tree kernels and, therefore, reduces the risk of missing important features. In addition, it introduces some domain knowledge based features (the keyword, semantic type, and DrugBank features) into the feature-based kernel, which contribute to the performance improvement. More specifically, the approach applies Stacked generalization to automatically learn the weights from the training data and assign them to three individual kernels to achieve a much better performance than each individual kernel. The experimental results show that our approach can achieve a better performance of 69.24% in F-score compared with other systems in the DDI Extraction 2011 challenge task. [ABSTRACT FROM AUTHOR]

Information overload is a serious problem in modern society and many solutions such as recommender system have been proposed to filter out irrelevant information. In the literature, researchers have been mainly dedicated to improving the recommendation performance (accuracy and diversity) of the algorithms while they have overlooked the influence of topology of the online user-object bipartite networks. In this paper, we find that some information provided by the bipartite networks is not only redundant but also misleading. With such “less can be more” feature, we design some algorithms to improve the recommendation performance by eliminating some links from the original networks. Moreover, we propose a hybrid method combining the time-aware and topology-aware link removal algorithms to extract the backbone which contains the essential information for the recommender systems. From the practical point of view, our method can improve the performance and reduce the computational time of the recommendation system, thus improving both of their effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

The biomedical text mining community has focused on developing techniques to automatically extract important relations between biological components and semantic events involving genes or proteins from literature. In this paper, we propose a novel approach for mining relations and events in the biomedical literature using approximate subgraph matching. Extraction of such knowledge is performed by searching for an approximate subgraph isomorphism between key contextual dependencies and input sentence graphs. Our approach significantly increases the chance of retrieving relations or events encoded within complex dependency contexts by introducing error tolerance into the graph matching process, while maintaining the extraction precision at a high level. When evaluated on practical tasks, it achieves a 51.12% F-score in extracting nine types of biological events on the GE task of the BioNLP-ST 2011 and an 84.22% F-score in detecting protein-residue associations. The performance is comparable to the reported systems across these tasks, and thus demonstrates the generalizability of our proposed approach. [ABSTRACT FROM AUTHOR]

Causal ordering is a useful tool for mobile distributed systems (MDS) to reduce the non-determinism induced by three main aspects: host mobility, asynchronous execution, and unpredictable communication delays. Several causal protocols for MDS exist. Most of them, in order to reduce the overhead and the computational cost over wireless channels and mobile hosts (MH), ensure causal ordering at and according to the causal view of the Base Stations. Nevertheless, these protocols introduce certain disadvantage, such as unnecessary inhibition at the delivery of messages. In this paper, we present an efficient causal protocol for groupware that satisfies the MDS's constraints, avoiding unnecessary inhibitions and ensuring the causal delivery based on the view of the MHs. One interesting aspect of our protocol is that it dynamically adapts the causal information attached to each message based on the number of messages with immediate dependency relation, and this is not directly proportional to the number of MHs. [ABSTRACT FROM AUTHOR]

The one-sample-per-person problem has become an active research topic for face recognition in recent years because of its challenges and significance for real-world applications. However, achieving relatively higher recognition accuracy is still a difficult problem due to, usually, too few training samples being available and variations of illumination and expression. To alleviate the negative effects caused by these unfavorable factors, in this paper we propose a more accurate spectral feature image-based 2DLDA (two-dimensional linear discriminant analysis) ensemble algorithm for face recognition, with one sample image per person. In our algorithm, multi-resolution spectral feature images are constructed to represent the face images; this can greatly enlarge the training set. The proposed method is inspired by our finding that, among these spectral feature images, features extracted from some orientations and scales using 2DLDA are not sensitive to variations of illumination and expression. In order to maintain the positive characteristics of these filters and to make correct category assignments, the strategy of classifier committee learning (CCL) is designed to combine the results obtained from different spectral feature images. Using the above strategies, the negative effects caused by those unfavorable factors can be alleviated efficiently in face recognition. Experimental results on the standard databases demonstrate the feasibility and efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

Abstract: Text retrieval has received a lot of attention in computer science. In the text retrieval field, the most widely-adopted similarity technique is using vector space models (VSM) to evaluate the weight of terms and using Cosine, Jaccard or Dice to measure the similarity between the query and the texts. However, these similarity techniques do not consider the effect of the sequence of the information. In this paper, we propose an integrated text retrieval (ITR) mechanism that takes the advantage of both VSM and longest common subsequence (LCS) algorithm. The key idea of the ITR mechanism is to use LCS to re-evaluate the weight of terms, so that the sequence and weight relationships between the query and the texts can be considered simultaneously. The results of mathematical analysis show that the ITR mechanism can increase the similarity on Jaccard and Dice similarity measurements when a sequential relationship exists between the query and the texts. [Copyright &y& Elsevier]

Abstract: In the -set agreement problem, each process (in a set of processes) proposes a value and has to decide a proposed value in such a way that at most different values are decided. While this problem can easily be solved in asynchronous systems prone to process crashes when , it cannot be solved when . For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the -set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases (consensus) and (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for -set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted , that is such that (the weakest class for ), and (the weakest class for ). (b) The second is an investigation of the structure of that shows that is the combination of two failure detector classes (that is new) and (they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the -set agreement problem in message-passing systems. (d) Finally, the last contribution is a -based algorithm that solves the -set agreement problem. This algorithm provides us with a new algorithmic insight on the way the -set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for -set agreement in message-passing systems. [Copyright &y& Elsevier]

The Chained-Cubic Tree (CCT) interconnection network topology was recently proposed as a continuation for the extended efforts in the area of interconnection networks’ performance improvement. This topology, which promises to exhibit the best properties of the hypercube and tree topologies, needs to be deeply investigated in order to evaluate its performance among other interconnection networks’ topologies. This work comes as a complementary effort, in which the load balancing technique is investigated as one of the most important aspects of performance improvement. This paper proposes a new load balancing algorithm on CCT interconnection networks. The proposed algorithm, which is called Hybrid Dynamic Parallel Scheduling Algorithm (HD-PSA), is a combination of two common load balancing strategies; dynamic load balancing and parallel scheduling. The performance of the proposed algorithm is evaluated both, analytically and experimentally, in terms of various performance metrics; including, execution time, load balancing accuracy, communication cost, number of tasks hops, and tasks locality. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an algorithm for convex polygon decomposition around a given set of locations. Given an -vertex convex polygon and a set of points positioned arbitrarily inside , the task is to divide into equal-area convex parts, each containing exactly one point of . The algorithm runs in time . [Copyright &y& Elsevier]

ion is a major concept in computer science and serves as a powerful tool in software development. Pattern-oriented instruction (POI) is a pedagogical approach that incorporates patterns in an introductory computer science course in order to structure the learning of algorithmic problem solving. This paper examines abstraction processes in the course of solving an algorithmic problem and highlights three distinct, although interrelated, facets of abstraction: pattern recognition, black-boxing, and structure identification. A study that examined the influence of the POI approach on students' abstraction skills is described; students who learned according to the POI approach were compared with students who learned in a traditional manner with regard to analogical reasoning and problem decomposition and solution, as well as verbal expression. The three facets of abstraction were used to analyze students' abstraction skills and their competency in algorithmic problem solving. [ABSTRACT FROM AUTHOR]

Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-Miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-Miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the Slicing-STS-Miner is an order of magnitude faster than STS-Miner for large data sets. [ABSTRACT FROM AUTHOR]

Automated Web service discovery requires Web service capability specifications of a high precision. Semantic-based approaches are inherently more precise than conventional keyword-based approaches. This paper proposes to build capability specifications of Web services based on an environment ontology, the main concepts of which are the environment entities in a particular application domain and their interactions. For each environment entity, there is a tree-like hierarchical state machine modeling the effects that are to be achieved by the Web services on this environment entity. The proposed approach is based on the assumption that the Web service capability specifications, built on the effects of the Web services on the environment entities, are more accessible and observable. Algorithms for constructing the domain environment ontology and the matchmaking between the Web service capability specifications are presented to show how Web service discovery is supported. An example on Travel Service is given to illustrate this proposed approach. [ABSTRACT FROM AUTHOR]

Semisupervised clustering algorithms partition a given data set using limited supervision from the user. The success of these algorithms depends on the type of supervision and also on the kind of dissimilarity measure used while creating partitions of the space. This paper proposes a clustering algorithm that uses supervision in terms of relative comparisons, viz., x is closer toy than to z. The proposed clustering algorithm simultaneously learns the underlying dissimilarity measure while finding compact clusters in the given data set using relative comparisons. Through our experimental studies on high-dimensional textual data sets, we demonstrate that the proposed algorithm achieves higher accuracy and is more robust than similar algorithms using pairwise constraints for supervision. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph such that each edge is weighted by nonnegative real . Let be a vertex designated as a source, be a positive integer, and be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition of and a set of trees of such that consists of at most terminals and each spans . The objective is to minimize , where denotes the sum of weights of all edges in . In this paper, we propose a -approximation algorithm to the CMTR, where is the best achievable approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Earlier work has developed the underpinnings of the IC-Scheduling Theory, a framework for scheduling computations having intertask dependencies—modeled via directed acyclic graphs (DAGs)—for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation ..., which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-Scheduling Theory in two ways: by expanding significantly the repertoire of DAGs that the Theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive," in the sense that they grow outward from their sources, or "reductive," in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word and nonempty words satisfying , the minimal local period associated with the factorization is the length of the shortest square at position . The critical factorization theorem shows that for any word, there is always a factorization whose minimal local period is equal to the minimal period (or global period) of the word. Crochemore and Perrin presented a linear time algorithm (in the length of the word) that finds a critical factorization from the computation of the maximal suffixes of the word with respect to two total orderings on words: the lexicographic ordering related to a fixed total ordering on the alphabet, and the lexicographic ordering obtained by reversing the order of letters in the alphabet. Here, by refining Crochemore and Perrin’s algorithm, we give a version of the critical factorization theorem for partial words (such sequences may contain “do not know” symbols or “holes”). Our proof provides an efficient algorithm which computes a critical factorization when one exists. Our results extend those of Blanchet-Sadri and Duncan for partial words with one hole. A World Wide Web server interface at http://www.uncg.edu/mat/research/cft2/ has been established for automated use of the program. [Copyright &y& Elsevier]

Given an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes). We consider a suitable storage scheme and develop appropriate algorithms for projected ANN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and ANN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data. [ABSTRACT FROM AUTHOR]

Abstract: History independent data structures, presented by Micciancio, are data structures that possess a strong security property: even if an intruder manages to get a copy of the data structure, the memory layout of the structure yields no additional information on the history of operations applied on the structure beyond the information obtainable from the content itself. Naor and Teague proposed a stronger notion of history independence in which the intruder may break into the system several times without being noticed and still obtain no additional information from reading the memory layout of the data structure. An open question posed by Naor and Teague is whether these two notions are equally hard to obtain. In this paper we provide a separation between the two requirements for comparison-based algorithms. We show very strong lower bounds for obtaining the stronger notion of history independence for a large class of data structures, including, for example, the heap and the queue abstract data structures. We also provide complementary upper bounds showing that the heap abstract data structure may be made weakly history independent in the comparison based model without incurring any additional (asymptotic) cost on any of its operations. (A similar result is easy for the queue.) Thus, we obtain the first separation between the two notions of history independence. The gap we obtain is exponential: some operations may be executed in logarithmic time (or even in constant time) with the weaker definition, but require linear time with the stronger definition. [Copyright &y& Elsevier]

The paper is intended to be a survey of all the important aspects and results that have shaped the field of quantum computation and quantum information. The reader is first familiarized with those features and principles of quantum mechanics providing a more efficient and secure information processing. Their applications to the general theory of information, cryptography, algorithms, computational complexity and error-correction are then discussed. Prospects for building a practical quantum computer are also analyzed. [ABSTRACT FROM AUTHOR]

The subtree transfer (STT) distance is one of the distance metric for comparing phylogenies. Previous work on computing the STT distance considered degree-3 trees only. In this paper, we give an approximation algorithm for the STT distance for degree-d trees with arbitrary d and with generalized STT operations. Also, some NP-hardness results related to STT distance are presented. [ABSTRACT FROM AUTHOR]