1 |
A Fast Multi-pattern Matching Algorithm for Network ProcessorsWu, Pao-chin 10 September 2006 (has links)
There are more and more Internet services such as video on demand, voice over IP,Blog, and so on. The network quality is important for providing good services. P2P technology can decentralize the usage of bandwidth, so a server can provide services with lower bandwidth. The bandwidth is filled by P2P traffic if we don¡¦t limit the usage of P2P applications, so we need a service controller that can limit the P2P traffic to provide better quality for other applications.
The traditional network systems use software solutions or hardware solutions. The software solutions offer flexibility but have low performance; The hardware solutions offer highest speed but are inflexible and expensive to modify or upgrade. there is another solution known as network processors. A network processor can be programmed and has been optimizede for packet procecssing.
We need a good service classifier to classify P2P traffic, then we can limit it. The performance of a signature based service classifier is dominated by the speed of its pattern
matching algorithm. In this paper, we proposed a fast ulti-pattern matching algorithm by improving WM algorithm. Serveral algorithms are implemented on IXP2400 network
processor for performance evaluation, and our proposed algorithm outperforms other algorithms if its parameters are properly set.
|
2 |
Speaker independent isolated word recognitionMwangi, Elijah January 1987 (has links)
The work presented in this thesis concerns the recognition of isolated words using a pattern matching approach. In such a system, an unknown speech utterance, which is to be identified, is transformed into a pattern of characteristic features. These features are then compared with a set of pre-stored reference patterns that were generated from the vocabulary words. The unknown word is identified as that vocabulary word for which the reference pattern gives the best match. One of the major difficul ties in the pattern comparison process is that speech patterns, obtained from the same word, exhibit non-linear temporal fluctuations and thus a high degree of redundancy. The initial part of this thesis considers various dynamic time warping techniques used for normalizing the temporal differences between speech patterns. Redundancy removal methods are also considered, and their effect on the recognition accuracy is assessed. Although the use of dynamic time warping algorithms provide considerable improvement in the accuracy of isolated word recognition schemes, the performance is ultimately limited by their poor ability to discriminate between acoustically similar words. Methods for enhancing the identification rate among acoustically similar words, by using common pattern features for similar sounding regions, are investigated. Pattern matching based, speaker independent systems, can only operate with a high recognition rate, by using multiple reference patterns for each of the words included in the vocabulary. These patterns are obtained from the utterances of a group of speakers. The use of multiple reference patterns, not only leads to a large increase in the memory requirements of the recognizer, but also an increase in the computational load. A recognition system is proposed in this thesis, which overcomes these difficulties by (i) employing vector quantization techniques to reduce the storage of reference patterns, and (ii) eliminating the need for dynamic time warping which reduces the computational complexity of the system. Finally, a method of identifying the acoustic structure of an utterance in terms of voiced, unvoiced, and silence segments by using fuzzy set theory is proposed. The acoustic structure is then employed to enhance the recognition accuracy of a conventional isolated word recognizer.
|
3 |
A SCALABLE ARCHITECTURE FOR HIGH SPEED DNA PATTERN MATCHINGKATAM, SHRAVANTHI 21 May 2002 (has links)
No description available.
|
4 |
Graph pattern matching on social network analysisWang, Xin January 2013 (has links)
Graph pattern matching is fundamental to social network analysis. Its effectiveness for identifying social communities and social positions, making recommendations and so on has been repeatedly demonstrated. However, the social network analysis raises new challenges to graph pattern matching. As real-life social graphs are typically large, it is often prohibitively expensive to conduct graph pattern matching over such large graphs, e.g., NP-complete for subgraph isomorphism, cubic time for bounded simulation, and quadratic time for simulation. These hinder the applicability of graph pattern matching on social network analysis. In response to these challenges, the thesis presents a series of effective techniques for querying large, dynamic, and distributively stored social networks. First of all, we propose a notion of query preserving graph compression, to compress large social graphs relative to a class Q of queries. We then develop both batch and incremental compression strategies for two commonly used pattern queries. Via both theoretical analysis and experimental studies, we show that (1) using compressed graphs Gr benefits graph pattern matching dramatically; and (2) the computation of Gr as well as its maintenance can be processed efficiently. Secondly, we investigate the distributed graph pattern matching problem, and explore parallel computation for graph pattern matching. We show that our techniques possess following performance guarantees: (1) each site is visited only once; (2) the total network traffic is independent of the size of G; and (3) the response time is decided by the size of largest fragment of G rather than the size of entire G. Furthermore, we show how these distributed algorithms can be implemented in the MapReduce framework. Thirdly, we study the problem of answering graph pattern matching using views since view based techniques have proven an effective technique for speeding up query evaluation. We propose a notion of pattern containment to characterise graph pattern matching using views, and introduce efficient algorithms to answer graph pattern matching using views. Moreover, we identify three problems related to graph pattern containment, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Fourthly, we revise graph pattern matching by supporting a designated output node, which we treat as “query focus”. We then introduce algorithms for computing the top-k relevant matches w.r.t. the output node for both acyclic and cyclic pattern graphs, respectively, with early termination property. Furthermore, we investigate the diversified top-k matching problem, and develop an approximation algorithm with performance guarantee and a heuristic algorithm with early termination property. Finally, we introduce an expert search system, called ExpFinder, for large and dynamic social networks. ExpFinder identifies top-k experts in social networks by graph pattern matching, and copes with the sheer size of real-life social networks by integrating incremental graph pattern matching, query preserving compression and top-k matching computation. In particular, we also introduce bounded (resp. unbounded) incremental algorithms to maintain the weighted landmark vectors which are used for incremental maintenance for cached results.
|
5 |
An investigation into sub-surface strain measurement using X-ray radioscopyDrew, Richard John January 1999 (has links)
There are numerous techniques used to measure strain. Most are only capable of taking surface measurements. The penetrating nature of X-rays has been used to measure deformation, and thus strain, but only with radiographic images. Radioscopic techniques are faster and do not require film processing, but produce less detailed results than digitised radiographic images. The research covered by this thesis tested radioscopic images and showed them to be suitable for strain measurement. The thesis includes details of the design and capabilities of the radioscopic equipment. Pin cushion distortion is a common feature of radioscopic images, and an automatic method of identifying, and correcting for the distortion was implemented.
|
6 |
Development of a natural language interface system that allows the user population to tailor the system iteratively to their own requirementsSidhu, Jadvinder Singh January 1997 (has links)
No description available.
|
7 |
A Simultaneous Position and Orientation Estimate Feature Finder for Machine VisionPrice, Sean Thomas 03 May 2000 (has links)
Correlation-based translated-feature finding techniques are fast and effective in identifying targets in test images despite unknown translation. Information involving both translation and in-plane orientation of targets, however, is important in many industrial machine vision applications such as manufacturing and quality assurance. A traditional correlation based technique that expands the search criteria to include in-plane orientation is based upon use of a bank of filters that each implement a feature finding operation for one rotation of the target. This computational complexity of this approach is inversely proportional to the resolution of the orientation estimate.
This thesis develops a correlation based method for translation and in-plane orientation feature finding that requires only two underlying correlation filter operations. A composite filter is constructed from a specially arranged and complex weighted sum of the set of the translated exemplar filters contained the usual filter bank. The arrangement allows for robust peak location detection yielding the target position and the multiplier angle that is extracted from the amplitude of the peak output response supplys an orientation estimate. A demonstration system using two such filters in an iterative fashion to counteract different sources of interference produced results accurate to plus or minus 1 degree 100 times faster than the traditional system.
|
8 |
Formalisme CSP (Constraint Satisfaction Problem) et localisation de motifs structurés dans les textes génomiquesThebault, Patricia 12 July 2004 (has links) (PDF)
La recherche d'occurrences de gènes d'ARN dans les séquences<br /> génomiques est un problème dont l'importance est renouvelée par la<br /> découverte récente de très nombreux ARN fonctionnels, opérant<br /> souvent en interaction avec d'autres molécules.<br /><br />Le formalisme des réseaux de contraintes est approprié à cette problématique aussi bien sur le plan de la modélisation que sur les développements algorithmiques qu'il permet de proposer. <br /><br /> Après une analyse et une comparaison des outils existants plongés dans le cadre des réseaux de contraintes, nous<br /> montrons comment l'utilisation conjointe des réseaux de contraintes,<br /> des techniques de résolution associées et des algorithmes et<br /> structures de données du "pattern matching" permet de modéliser et de<br /> rechercher efficacement des motifs structurés en interaction (faisant<br /> intervenir plusieurs textes génomiques simultanément).
|
9 |
Evolutionary study of the Hox gene family with matrix-based bioinformatics approachesThomas-Chollier, Morgane 27 June 2008 (has links)
Hox transcription factors are extensively investigated in diverse fields of molecular and evolutionary biology. Hox genes belong to the family of homeobox transcription factors characterised by a 60 amino acids region called homeodomain. These genes are evolutionary conserved and play crucial roles in the development of animals. In particular, they are involved in the specification of segmental identity, and in the tetrapod limb differentiation. In vertebrates, this family of genes can be divided into 14 groups of homology. Common methods to classify Hox proteins focus on the homeodomain. Classification is however hampered by the high conservation of this short domain. Since phylogenetic tree reconstruction is time-consuming, it is not suitable to classify the growing number of Hox sequences. The first goal of this thesis is therefore to design an automated approach to classify vertebrate Hox proteins in their groups of homology. This approach classifies Hox proteins on the basis of their scores for a combination of protein generalised profiles. The resulting program, HoxPred, combines predictive accuracy and time efficiency. We used this program to detect and classify Hox genes in several teleost fish genomes. In particular, it allowed us to clarify the evolutionary history of the HoxC1a genes in teleosts. Overall, HoxPred could efficiently contribute to the bioinformatics toolbox commonly used to annotate vertebrate Hox sequences. This program was then evaluated in non-vertebrate species. Although not intended for the classification of Hox proteins in distantly related species, HoxPred showed a high accuracy in bilaterians. It has also given insights into the evolutionary relationships between bilaterian posterior Hox genes, which are notoriously difficult to classify with phylogenetic trees.
As transcription factors, Hox proteins regulate target genes by specifically binding DNA on cis-regulatory elements. Only a few of these target genes have been identified so far. The second goal of this work was to evaluate whether it is possible to apply computational approaches to detect Hox cis-regulatory elements in genomic sequences. Regulatory Sequence Analysis Tools (RSAT) is a suite of bioinformatics tools dedicated to the detection of cis-regulatory elements in genomes. We participated to the development of matrix-based pattern matching approaches in RSAT. After having performed a statistical validation of the pattern-matching scores, we focused on a study case based on the vertebrate HoxB1 protein, which binds DNA with its cofactors Pbx and Meis. This study aimed at predicting combinations of cis-regulatory elements for these three transcription factors.
|
10 |
Metabolic Network Alignments and their ApplicationsCheng, Qiong 01 December 2009 (has links)
The accumulation of high-throughput genomic and proteomic data allows for the reconstruction of the increasingly large and complex metabolic networks. In order to analyze the accumulated data and reconstructed networks, it is critical to identify network patterns and evolutionary relations between metabolic networks. But even finding similar networks becomes computationally challenging. The dissertation addresses these challenges with discrete optimization and the corresponding algorithmic techniques. Based on the property of the gene duplication and function sharing in biological network,we have formulated the network alignment problem which asks the optimal vertex-to-vertex mapping allowing path contraction, vertex deletion, and vertex insertions. We have proposed the first polynomial time algorithm for aligning an acyclic metabolic pattern pathway with an arbitrary metabolic network. We also have proposed a polynomial-time algorithm for patterns with small treewidth and implemented it for series-parallel patterns which are commonly found among metabolic networks. We have developed the metabolic network alignment tool for free public use. We have performed pairwise mapping of all pathways among five organisms and found a set of statistically significant pathway similarities. We also have applied the network alignment to identifying inconsistency, inferring missing enzymes, and finding potential candidates.
|
Page generated in 0.1035 seconds