Relevant bibliographies by topics / Edit distanve

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Edit distanve'

Author: Grafiati
Published: 4 June 2021
Last updated: 7 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Edit distanve.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Edit distanve"

1

Hyyrö, Heikki, and Shunsuke Inenaga. "Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions." International Journal of Foundations of Computer Science 29, no. 04 (2018): 623–45. http://dx.doi.org/10.1142/s0129054118410083.

Full text
Abstract:
Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302–312, 2004] proposed a method (KP) based on a “dynamic edit distance table” that allows one to efficiently maintain unit cost edit distance information between two strings [Formula: see text] of length [Formula: see text] and [Formula: see text] of length [Formula: see text] when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, [Formula: see text], to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in [Formula: see text] time per single edit, where [Formula: see text] is the maximum weight of the cost function. The work noted that the [Formula: see text] space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing [Formula: see text] and [Formula: see text]. Let [Formula: see text] and [Formula: see text] be the lengths of RLE compressed versions of [Formula: see text] and [Formula: see text], respectively. We propose how to store the dynamic edit distance table using [Formula: see text] space while maintaining the same time complexity as the previous methods for uncompressed strings.
APA, Harvard, Vancouver, ISO, and other styles
2

Akutsu, Tatsuya, Daiji Fukagawa, and Atsuhiro Takasu. "Approximating Tree Edit Distance through String Edit Distance." Algorithmica 57, no. 2 (2008): 325–48. http://dx.doi.org/10.1007/s00453-008-9213-z.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kim, HyunJin. "A k-mismatch string matching for generalized edit distance using diagonal skipping method." PLOS ONE 16, no. 5 (2021): e0251047. http://dx.doi.org/10.1371/journal.pone.0251047.

Full text
Abstract:
This paper proposes an approximate string matching with k-mismatches when calculating the generalized edit distance. When the edit distance is generalized, more sophisticated string matching can be provided. However, the execution time increases because of the bundle of complex computations for calculating complicated edit distances. The computational costs for finding which steps or edit distances are over k-mismatches cannot be significant in the generalized edit distance metric. Therefore, we can reduce the execution time by determining steps over k-mismatches and then skipping them. The diagonal step calculations using the pruning register skips unnecessary distance calculations over k-mismatches. The overhead of control statements and reordered memory accesses can be amortized by skipping multiple steps. Even though the proposed skipping method requires additional overhead, the proposed scheme’s practical embodiments show that the execution time of string matching is reduced significantly when k is small.
APA, Harvard, Vancouver, ISO, and other styles
4

Jie Wei. "Markov edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 3 (2004): 311–21. http://dx.doi.org/10.1109/tpami.2004.1262315.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kari, Lila, Stavros Konstantinidis, Steffen Kopecki, and Meng Yang. "Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers." Algorithms 11, no. 11 (2018): 165. http://dx.doi.org/10.3390/a11110165.

Full text
Abstract:
The concept of edit distance and its variants has applications in many areas such as computational linguistics, bioinformatics, and synchronization error detection in data communications. Here, we revisit the problem of computing the inner edit distance of a regular language given via a Nondeterministic Finite Automaton (NFA). This problem relates to the inherent maximal error-detecting capability of the language in question. We present two efficient algorithms for solving this problem, both of which execute in time O ( r 2 n 2 d ) , where r is the cardinality of the alphabet involved, n is the number of transitions in the given NFA, and d is the computed edit distance. We have implemented one of the two algorithms and present here a set of performance tests. The correctness of the algorithms is based on the connection between word distances and error detection and the fact that nondeterministic transducers can be used to represent the errors (resp., edit operations) involved in error-detection (resp., in word distances).
APA, Harvard, Vancouver, ISO, and other styles
6

Kovács, Gábor, Gábor Árpád Németh, Zoltán Pap, and Mahadevan Subramaniam. "Deriving Compact Test Suites for Telecommunication Software Using Distance Metrics." Journal of Communications Software and Systems 5, no. 2 (2009): 57. http://dx.doi.org/10.24138/jcomss.v5i2.205.

Full text
Abstract:
This paper proposes a string edit distance based test selection method to generate compact test sets for telecommunications software. Following the results of previous research, a trace in a test set is considered to be redundant if its edit distance from others is less than a given parameter. The algorithm first determines the minimum cardinality of the target test set inaccordance with the provided parameter, then it selects the test set with the highest sum of internal edit distances. The selection problem is reduced to an assignment problem in bipartite graphs.
APA, Harvard, Vancouver, ISO, and other styles
7

Kalenkova, Anna A., and Danil A. Kolesnikov. "Application of Genetic Algorithms for Finding Edit Distance between Process Models." Modeling and Analysis of Information Systems 25, no. 6 (2018): 711–25. http://dx.doi.org/10.18255/1818-1015-2018-6-711-725.

Full text
Abstract:
Finding graph-edit distance (graph similarity) is an important task in many computer science areas, such as image analysis, machine learning, chemicalinformatics. Recently, with the development of process mining techniques, it became important to adapt and apply existing graph analysis methods to examine process models (annotated graphs) discovered from event data. In particular, finding graph-edit distance techniques can be used to reveal patterns (subprocesses), compare discovered process models. As it was shown experimentally and theoretically justified, exact methods for finding graph-edit distances between discovered process models (and graphs in general) are computationally expensive and can be applied to small models only. In this paper, we present and assess accuracy and performance characteristics of an inexact genetic algorithm applied to find distances between process models discovered from event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from event logs by using different process discovery algorithms. We show that the genetic algorithm allows us to dramatically reduce the time of comparison and produces results which are close to the optimal solutions (minimal graph edit distances calculated by the exact search algorithm).
APA, Harvard, Vancouver, ISO, and other styles
8

McGrane, Martin, and Michael A. Charleston. "Biological Network Edit Distance." Journal of Computational Biology 23, no. 9 (2016): 776–88. http://dx.doi.org/10.1089/cmb.2016.0062.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ristad, E. S., and P. N. Yianilos. "Learning string-edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 20, no. 5 (1998): 522–32. http://dx.doi.org/10.1109/34.682181.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Myers, R., R. C. Wison, and E. R. Hancock. "Bayesian graph edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 22, no. 6 (2000): 628–35. http://dx.doi.org/10.1109/34.862201.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Edit distanve"

1

Mallmann, Rafael Mendes. "Arquiteturas em hardware para o alinhamento local de sequências biológicas." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2010. http://hdl.handle.net/10183/56841.

Full text
Abstract:
Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas.<br>Bioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.
APA, Harvard, Vancouver, ISO, and other styles
2

Ahmed, Algabli Shaima. "Learning the Graph Edit Distance through embedding the graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2020. http://hdl.handle.net/10803/669612.

Full text
Abstract:
Els gràfics són estructures de dades abstractes que s’utilitzen per modelar problemes reals amb dues entitats bàsiques: nodes i vores. Cada node o vèrtex representa un punt d'interès rellevant d'un problema i cada vora representa la relació entre aquests punts. Es poden atribuir nodes i vores per augmentar la precisió del model, cosa que significa que aquests atributs podrien variar des de vectors de característiques fins a etiquetes de descripció. A causa d'aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per ordinador, la biomèdica i l'anàlisi de xarxa, etc., la primera part d'aquesta tesi presenta un mètode general per aprendre automàticament els costos d'edició que comporta l'edició de gràfics. Distància. El mètode es basa en incrustar parells de gràfics i el seu mapeig de node a node de veritat terrestre en un espai euclidià. D’aquesta manera, l’algoritme d’aprenentatge no necessita calcular cap concordança de gràfics tolerant als errors, que és l’inconvenient principal d’altres mètodes a causa de la seva intrínseca complexitat computacional exponencial. No obstant això, el mètode d’aprenentatge té la principal restricció que els costos d’edició han de ser constants. A continuació, posem a prova aquest mètode amb diverses bases de dades gràfiques i també l’aplicem per realitzar el registre d’imatges. A la segona part de la tesi, aquest mètode es particularitza a la verificació d’empremtes dactilars. Les dues diferències principals respecte a l’altre mètode són que només definim els costos d’edició de substitució als nodes. Per tant, suposem que els gràfics no tenen arestes. I també, el mètode d’aprenentatge no es basa en una classificació lineal sinó en una regressió lineal.<br>Los gráficos son estructuras de datos abstractas que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada borde representa la relación entre estos puntos. Se podrían atribuir nodos y bordes para aumentar la precisión del modelo, lo que significa que estos atributos podrían variar de vectores de características a etiquetas de descripción. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como visión por computadora, biomédicos y análisis de redes, etc. La primera parte de esta tesis presenta un método general para aprender automáticamente los costos de edición involucrados en la Edición de Gráficos Distancia. El método se basa en incrustar pares de gráficos y su mapeo de nodo a nodo de verdad fundamental en un espacio euclidiano. De esta manera, el algoritmo de aprendizaje no necesita calcular ninguna coincidencia de gráfico tolerante a errores, que es el principal inconveniente de otros métodos debido a su complejidad computacional exponencial intrínseca. Sin embargo, el método de aprendizaje tiene la principal restricción de que los costos de edición deben ser constantes. Luego probamos este método con varias bases de datos de gráficos y también lo aplicamos para realizar el registro de imágenes. En la segunda parte de la tesis, este método se especializa en la verificación de huellas digitales. Las dos diferencias principales con respecto al otro método son que solo definimos los costos de edición de sustitución en los nodos. Por lo tanto, suponemos que los gráficos no tienen aristas. Y también, el método de aprendizaje no se basa en una clasificación lineal sino en una regresión lineal.<br>Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the model, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.
APA, Harvard, Vancouver, ISO, and other styles
3

Samuelsson, Axel. "Weighting Edit Distance to Improve Spelling Correction in Music Entity Search." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-210036.

Full text
Abstract:
This master’s thesis project undertook investigation of whether the extant Damerau- Levenshtein edit distance measurement between two strings could be made more useful for detecting and adjusting misspellings in a search query. The idea was to use the knowledge that many users type their queries using the QWERTY keyboard layout, and weighting the edit distance in a manner that makes it cheaper to correct misspellings caused by confusion of nearer keys. Two different weighting approaches were tested, one with a linear spread from 2/9 to 2 depending on the keyboard distance, and the other had neighbors preferred over non-neighbors (either with half the cost or no cost at all). They were tested against an unweighted baseline as well as inverted versions of themselves (nearer keys more expensive to replace) against a dataset of 1,162,145 searches. No significant improvement in the retrieval of search results were observed when compared to the baseline. However, each of the weightings performed better than its corresponding inversion on a p &lt; 0.05 significance level. This means that while the weighted edit distance did not outperform the baseline, the data still clearly points toward a correlation between the physical position of keys on the keyboard, and what spelling mistakes are made.<br>Detta examensarbete åtog sig att undersöka om det etablerade Damerau-Levenshtein-avståndet som mäter avståndet kan anpassas för att bättre hitta och korrigera stavningsfel i sökfrågor. Tanken var att använda det faktum att många användare skriver sina sökfrågor på ett tangentbord med QWERTY-layout, och att vikta ändrings- avståndet så att det blir billigare att korrigera stavfel orsakade av hopblandning av två knappar som är närmare varandra. Två olika viktningar testades, en hade vikterna utspridda linjärt mellan 2/9 och 2, och den andra föredrog grannar över icke-grannar (antingen halva kostnaden eller ingen alls). De testades mot ett oviktat referensavstånd samt inversen av sig själva (så att närmare knappar blev dyrare att byta ut) mot ett dataset bestående av 1 162 145 sökningar. Ingen signifikant förbättring uppmättes gentemot referensen. Däremot presterade var och en av viktningarna bättre än sin inverterade motpart på konfidensnivå p &lt; 0,05. Det innebär att trots att de viktade distansavstånden inte presterade bättre än referensen så pekar datan tydligt mot en korrelation mellan den fysiska positioneringen av knapparna på tangentbordet och vilka stavningsmisstag som begås.
APA, Harvard, Vancouver, ISO, and other styles
4

Sullivan, Jennifer Niamh. "Approaching intonational distance and change." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5619.

Full text
Abstract:
The main aim of this thesis is to begin to extend phonetic distance measurements to the domain of intonation. Existing studies of segmental phonetic distance have strong associations with historical linguistic questions. I begin with this context and demonstrate problems with the use of feature systems in these segmental measures. Then I attempt to draw strands from the disparate fields of quantitative historical linguistics and intonation together. The intonation of Belfast and Glasgow English provides a central case study for this. Previous work suggests that both varieties display nuclear rises on statements, yet they have never been formally compared. This thesis presents two main hypotheses on the source of these statement rises: the Alignment hypothesis and the Transfer hypothesis. The Alignment hypothesis posits that statement rises were originally more typical statement falls but have changed into rises over time through gradual phonetic change to the location of the pitch peak. The Transfer hypothesis considers that statement rises have come about through pragmatic transfer of rises onto a statement context, either from question rises or continuation rises. I evaluate these hypotheses using the primary parameters of alignment and scaling as phonetic distance measurements. The main data set consists of data from 3 Belfast English and 3 Glasgow English speakers in a Sentence reading task and Map task. The results crucially indicate that the origin of the statement rises in Belfast and Glasgow English respectively may be different. The Glasgow statement nuclear tones show support for the Alignment hypothesis, while the Belfast nuclear tones fit best with the Transfer hypothesis. The fundamental differences between Glasgow and Belfast are the earlier alignment of the peak (H) in Glasgow and the presence of a final low (L) tonal target in Glasgow and a final high (H) target in Belfast. The scaling of the final H in Belfast statements suggests that the transfer may be from continuation rather than from question rises. I then present a proposal for an overall measure of intonational distance, showing problems with parameter weighting, comparing like with like, and distinguishing between chance resemblance and genuine historical connections. The thesis concludes with an assessment of the benefits that intonational analysis could bring to improving segmental phonetic distance measures.
APA, Harvard, Vancouver, ISO, and other styles
5

Røkenes, Håkon Drolsum. "Graph-based Natural Language Processing : Graph edit distance applied to the task of detecting plagiarism." Thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for datateknikk og informasjonsvitenskap, 2012. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-20778.

Full text
Abstract:
The focus of this thesis is the exploration of graph-based similarity, in the context of natural language processing. The work is motivated by a need for richer representations of text. A graph edit distance algorithm was implemented, that calculates the difference between graphs. Sentences were represented by means of dependency graphs, which consist of words connected by dependencies. A dependency graph captures the syntactic structure of a sentence. The graph-based similarity approach was applied to the problem of detecting plagiarism, and was compared against state of the art systems. The key advantages of graph-based textual representations are mainly word order indifference and the ability to capture similarity between words, based on the sentence structure. The approach was compared against contributions made to the PAN plagiarism detection challenge at the CLEF 2011 conference, and would have achieved a 5th place out of 10 contestants. The evaluation results suggest that the approach can be applicable to the task of detecting plagiarism, but require some fine tuning on input parameters. The evaluation results demonstrated that dependency graphs are best represented by directed edges. The graph edit distance algorithm scored best with a combination of node and edge label matching. Different edit weights were applied, which increased performance. Keywords: Graph Edit Distance, Natural Language Processing, Dependency Graphs, Plagiarism Detection
APA, Harvard, Vancouver, ISO, and other styles
6

Dosi, Shubham. "Optimization and Further Development of an Algorithm for Driver Intention Detection with Fuzzy Logic and Edit Distance." Master's thesis, Universitätsbibliothek Chemnitz, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-202567.

Full text
Abstract:
Inspired by the idea of vision zero, there is a lot of work that needs to be done in the field of advance driver assistance systems to develop more safer systems. Driver intention detection with a prediction of upcoming behavior of the driver is one possible solution to reduce the fatalities in road traffic. Driver intention detection provides an early warning of the driver's behavior to an Advanced Driver Assistance Systems (ADAS) and at the same time reduces the risk of non-essential warnings. This will significantly reduce the problem of warning dilemma and the system will become more safer. A driving maneuver prediction can be regarded as an implementation of driver's behavior. So the aim of this thesis is to determine the driver's intention by early prediction of a driving maneuver using Controller Area Network (CAN) bus data. The focus of this thesis is to optimize and further develop an algorithm for driver intention detection with fuzzy logic and edit distance method. At first the basics concerning driver's intention detection are described as there exists different ways to determine it. This work basically uses CAN bus data to determine a driver's intention. The algorithm overview with the design parameters are described next to have an idea about the functioning of the algorithm. Then different implementation tasks are explained for optimization and further development of the algorithm. The main aim to execute these implementation tasks is to improve the overall performance of the algorithm concerning True Positive Rate (TPR), False Positive Rate (FPR) and earliness values. At the end, the results are validated to check the algorithm performance with different possibilities and a test drive is performed to evaluate the real time capability of the algorithm. Lastly the use of driver intention detection algorithm for an ADAS to make it more safer is described in details. The early warning information can be feed to an ADAS, for example, an automatic collision avoidance or a lane change assistance ADAS to further improve safety for these systems.
APA, Harvard, Vancouver, ISO, and other styles
7

Ibragimov, Rashid [Verfasser], and Jan [Akademischer Betreuer] Baumbach. "Exact and heuristic algorithms for network alignment using graph edit distance models / Rashid Ibragimov. Betreuer: Prof. Dr. Jan Baumbach." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2015. http://d-nb.info/1067098542/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Schulz, Drew. "PiaNote: A Sight-Reading Program That Algorithmically Generates Music Based on Human Performance." DigitalCommons@CalPoly, 2016. https://digitalcommons.calpoly.edu/theses/1579.

Full text
Abstract:
Sight-reading is the act of performing a piece of music at first sight. This can be a difficult task to master, because it requires extensive knowledge of music theory, practice, quick thinking, and most importantly, a wide variety of musical material. A musician can only effectively sight-read with a new piece of music. This not only requires many resources, but also musical pieces that are challenging while also within a player's abilities. This thesis presents PiaNote, a sight-reading web application for pianists that algorithmically generates music based on human performance. PiaNote's goal is to alleviate some of the hassles pianists face when sight-reading. PiaNote presents musicians with algorithmically generated pieces, ensuring that a musician never sees the same piece of music twice. PiaNote also monitors player performances in order to intelligently present music that is challenging, but within the player's abilities. As a result, PiaNote offers a sight-reading experience that is tailored to the player. On a broader level, this thesis explores different methods in effectively creating a sight-reading application. We evaluate PiaNote with a user study involving novice piano players. The players actively practice with PiaNote over three fifteen-minute sessions. At the end of the study, users are asked to determine whether PiaNote is an effective practice tool that improves both their confidence in sight-reading and their sight-reading abilities. Results suggest that PiaNote does improve user's sight-reading confidence and abilities, but further research must be conducted to clearly validate PiaNote's effectiveness. We conclude that PiaNote has potential to become an effective sight-reading application with slight improvements and further research.
APA, Harvard, Vancouver, ISO, and other styles
9

Nguyen, Hong-Thinh. "Approximate string matching distance for image classification." Thesis, Saint-Etienne, 2014. http://www.theses.fr/2014STET4029/document.

Full text
Abstract:
L'augmentation exponentielle du nombre d'images nécessite des moyens efficaces pour les classer en fonction de leur contenu visuel. Le sac de mot visuel (Bag-Of-visual-Words, BOW), en raison de sa simplicité et de sa robustesse, devient l'approche la plus populaire. Malheureusement, cette approche ne prend pas en compte de l'information spatiale, ce qui joue un rôle important dans les catégories de modélisation d'image. Récemment, Lazebnik ont introduit la représentation pyramidale spatiale (Spatial Pyramid Representation, SPR) qui a incorporé avec succès l'information spatiale dans le modèle BOW. Néanmoins, ce système de correspondance rigide empêche la SPR de gérer les variations et les transformations d'image. L'objectif principal de cette thèse est d'étudier un modèle de chaîne de correspondance plus souple qui prend l'avantage d'histogrammes de BOW locaux et se rapproche de la correspondance de la chaîne. Notre première contribution est basée sur une représentation en chaîne et une nouvelle distance d'édition (String Matching Distance, SMD) bien adapté pour les chaînes de l'histogramme qui peut calculer efficacement par programmation dynamique. Un noyau d'édition correspondant comprenant à la fois d'une pondération et d'un système pyramidal est également dérivée. La seconde contribution est une version étendue de SMD qui remplace les opérations d'insertion et de suppression par les opérations de fusion entre les symboles successifs, ce qui apporte de la souplesse labours et correspond aux images. Toutes les distances proposées sont évaluées sur plusieurs jeux de données tâche de classification et sont comparés avec plusieurs approches concurrentes<br>The exponential increasing of the number of images requires efficient ways to classify them based on their visual content. The most successful and popular approach is the Bag of visual Word (BoW) representation due to its simplicity and robustness. Unfortunately, this approach fails to capture the spatial image layout, which plays an important roles in modeling image categories. Recently, Lazebnik et al (2006) introduced the Spatial Pyramid Representation (SPR) which successfully incorporated spatial information into the BoW model. The idea of their approach is to split the image into a pyramidal grid and to represent each grid cell as a BoW. Assuming that images belonging to the same class have similar spatial distributions, it is possible to use a pairwise matching as similarity measurement. However, this rigid matching scheme prevents SPR to cope with image variations and transformations. The main objective of this dissertation is to study a more flexible string matching model. Keeping the idea of local BoW histograms, we introduce a new class of edit distance to compare strings of local histograms. Our first contribution is a string based image representation model and a new edit distance (called SMD for String Matching Distance) well suited for strings composed of symbols which are local BoWs. The new distance benefits from an efficient Dynamic Programming algorithm. A corresponding edit kernel including both a weighting and a pyramidal scheme is also derived. The performance is evaluated on classification tasks and compared to the standard method and several related methods. The new method outperforms other methods thanks to its ability to detect and ignore identical successive regions inside images. Our second contribution is to propose an extended version of SMD replacing insertion and deletion operations by merging operations between successive symbols. In this approach, the number of sub regions ie. the grid divisions may vary according to the visual content. We describe two algorithms to compute this merge-based distance. The first one is a greedy version which is efficient but can produce a non optimal edit script. The other one is an optimal version but it requires a 4th degree polynomial complexity. All the proposed distances are evaluated on several datasets and are shown to outperform comparable existing methods
APA, Harvard, Vancouver, ISO, and other styles
10

Afzal, Zeeshan. "Towards Secure Multipath TCP Communication." Licentiate thesis, Karlstads universitet, Institutionen för matematik och datavetenskap (from 2013), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-48172.

Full text
Abstract:
The evolution in networking coupled with an increasing demand to improve user experience has led to different proposals to extend the standard TCP. Multipath TCP (MPTCP) is one such extension that has the potential to overcome few inherent limitations in the standard TCP. While MPTCP's design and deployment progresses, most of the focus has been on its compatibility. The security aspect is confined to making sure that the MPTCP protocol itself offers the same security level as the standard TCP. The topic of this thesis is to investigate the unexpected security implications raised by using MPTCP in the traditional networking environment. The Internet of today has security middle-boxes that perform traffic analysis to detect intrusions and attacks. Such middle-boxes make use of different assumptions about the traffic, e.g., traffic from a single connection always arrives along the same path. This along with many other assumptions may not be true anymore with the advent of MPTCP as traffic can be fragmented and sent over multiple paths simultaneously. We investigate how practical it is to evade a security middle-box by fragmenting and sending traffic across multiple paths using MPTCP. Realistic attack traffic is used to evaluate such attacks against Snort IDS to show that these attacks are feasible. We then go on to propose possible solutions to detect such attacks and implement them in an MPTCP proxy. The proxy aims to extend the MPTCP performance advantages to servers that only support standard TCP, while ensuring that intrusions can be detected as before. Finally, we investigate the potential MPTCP scenario where security middle-boxes only have access to some of the traffic. We propose and implement an algorithm to perform intrusion detection in such situations and achieve a nearly 90% detection accuracy. Another contribution of this work is a tool, that converts IDS rules into equivalent attack traffic to automate the evaluation of a middle-box.<br>Multipath TCP (MPTCP) is an extension to standard TCP that is close to being standardized. The design of the protocol is progressing, but most of the focus has so far been on its compatibility. The security aspect is confined to making sure that the MPTCP protocol itself offers the same security level as standard TCP. The topic of this thesis is to investigate the unexpected security implications raised by using MPTCP in a traditional networking environment. Today, the security middleboxes make use of different assumptions that may not be true anymore with the advent of MPTCP.We investigate how practical it is to evade a security middlebox by fragmenting and sending traffic across multiple paths using MPTCP. Realistic attack traffic generated from a tool that is also presented in this thesis is used to show that these attacks are feasible. We then go on to propose possible solutions to detect such attacks and implement them in an MPTCP proxy. The proxy aims to extend secure MPTCP performance advantages. We also investigate the MPTCP scenario where security middleboxes can only observe some of the traffic. We propose and implement an algorithm to perform intrusion detection in such situations and achieve a high detection accuracy.<br>HITS
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Edit distanve"

1

Riesen, Kaspar. Structural Pattern Recognition with Graph Edit Distance. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-27252-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Litwin, Edith, Mariana Maggio, Carina Lion, Marilina Lipsman, Anahí Mansur, and Hebe Roig. Homenaje a Edith Litwin. Eudeba, 2014.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Riesen, Kaspar. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. Springer, 2016.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bridging the Gap Between Graph Edit Distance and Kernel Machines (Series in Machine Perception and Artificial Intelligence). World Scientific Publishing Company, 2007.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Edit distanve"

1

Lipton, Richard J. "Edit Distance." In The P=NP Question and Gödel’s Lost Letter. Springer US, 2010. http://dx.doi.org/10.1007/978-1-4419-7155-5_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Akutsu, Tatsuya, Daiji Fukagawa, and Atsuhiro Takasu. "Approximating Tree Edit Distance Through String Edit Distance." In Algorithms and Computation. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11940128_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Serratosa, Francesc, Xavier Cortés, and Carlos-Francisco Moreno. "Graph Edit Distance or Graph Edit Pseudo-Distance?" In Lecture Notes in Computer Science. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-49055-7_47.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Riesen, Kaspar. "Graph Edit Distance." In Structural Pattern Recognition with Graph Edit Distance. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-27252-8_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kao, Ming-Yang. "Block Edit Distance." In Encyclopedia of Algorithms. Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_50.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Combier, Camille, Guillaume Damiand, and Christine Solnon. "Map Edit Distance vs. Graph Edit Distance for Matching Images." In Graph-Based Representations in Pattern Recognition. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38221-5_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Riesen, Kaspar, Miquel Ferrer, Rolf Dornberger, and Horst Bunke. "Greedy Graph Edit Distance." In Machine Learning and Data Mining in Pattern Recognition. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-21024-7_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Riesen, Kaspar. "Bipartite Graph Edit Distance." In Structural Pattern Recognition with Graph Edit Distance. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-27252-8_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Aratsu, Taku, Kouichi Hirata, and Tetsuji Kuboyama. "Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-95891-8_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bernard, Marc, Amaury Habrard, and Marc Sebban. "Learning Stochastic Tree Edit Distance." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11871842_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Edit distanve"

1

Pucher, Daniel, and Walter G. Kropatsch. "Segmentation Edit Distance." In 2018 24th International Conference on Pattern Recognition (ICPR). IEEE, 2018. http://dx.doi.org/10.1109/icpr.2018.8545613.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ibragimov, Rashid, Maximilian Malek, Jan Baumbach, and Jiong Guo. "Multiple graph edit distance." In GECCO '14: Genetic and Evolutionary Computation Conference. ACM, 2014. http://dx.doi.org/10.1145/2576768.2598390.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Zade, Himanshu, Santosh Arvind Adimoolam, Sai Gollapudi, Anind K. Dey, and Venkatesh Choppella. "Edit distance modulo bisimulation." In CHI '14: CHI Conference on Human Factors in Computing Systems. ACM, 2014. http://dx.doi.org/10.1145/2556288.2557191.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

de la Higuera, Colin, and Luisa Micó. "A Contextual Normalised Edit Distance." In 2008 First International Workshop on Similarity Search and Applications (SISAP '08). IEEE, 2008. http://dx.doi.org/10.1109/sisap.2008.17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. "Edit distance for timed automata." In HSCC'14: 17th International Conference on Hybrid Systems: Computation and Control. ACM, 2014. http://dx.doi.org/10.1145/2562059.2562141.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Muhammad Fuad, Muhammad Marwan, and Pierre-Francois Marteau. "The extended edit distance metric." In 2008 International Workshop on Content-Based Multimedia Indexing. IEEE, 2008. http://dx.doi.org/10.1109/cbmi.2008.4564953.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Jordaan, Ilicia, and Linda Marshall. "Edit Distance-based Digraph Similarity." In the 2015 Annual Research Conference. ACM Press, 2015. http://dx.doi.org/10.1145/2815782.2815792.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Robles-Kelly and Hancock. "Edit distance from graph spectra." In ICCV 2003: 9th International Conference on Computer Vision. IEEE, 2003. http://dx.doi.org/10.1109/iccv.2003.1238347.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

de la Higuera, Colin, and Luisa Mico. "A contextual normalised edit distance." In 2008 IEEE 24th International Conference on Data Engineeing workshop (ICDE Workshop 2008). IEEE, 2008. http://dx.doi.org/10.1109/icdew.2008.4498345.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

DAI, Xinyan, Xiao Yan, Kaiwen Zhou, Yuxuan Wang, Han Yang, and James Cheng. "Convolutional Embedding for Edit Distance." In SIGIR '20: The 43rd International ACM SIGIR conference on research and development in Information Retrieval. ACM, 2020. http://dx.doi.org/10.1145/3397271.3401045.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Edit distanve"

1

McCallum, Andrew, Kedar Bellare, and Fernando Pereira. A Conditional Random Field for Discriminatively-Trained Finite-State String Edit Distance. Defense Technical Information Center, 2005. http://dx.doi.org/10.21236/ada440386.

Full text
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography