Search results for "Matching"

Graph matching for efficient classifiers adaptation

2011

In this work we present an adaptation algorithm focused on the description of the measurement changes under different acquisition conditions. The adaptation is carried out by transforming the manifold in the first observation conditions into the corresponding manifold in the second. The eventually non-linear transform is based on vector quantization and graph matching. The transfer learning mapping is defined in an unsupervised manner. Once this mapping has been defined, the labeled samples in the first are projected into the second domain, thus allowing the application of any classifier in the transformed domain. Experiments on VHR series of images show the validity of the proposed method …

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

1997

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem1. The motivation for its algorithmic study is mainly theoretical. LetA1:n1,?,1:nd be a text matrix withN=n1?ndentries andB1:m1,?,1:mr be a pattern matrix withM=m1?mrentries, whered?r?1 (the matrix entries are taken from an ordered alphabet ?). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(logN) time withN2/nmaxprocessors, wherenmax=max(n1,?,nd), such that …

How adolescents navigate Wikipedia to answer questions / ¿Cómo navegan los adolescentes en Wikipedia para contestar preguntas?

2015

AbstractIn one experiment, we explored how high school students use hyperlink relevance cues while they navigate to answer questions from hypertexts. Current evidence has shown that students may navigate by either performing a deep semantic analysis of the relationship between the question and the existing hyperlinks, or by matching words in the question to words in the hyperlink labels. We focused on how students combine both cues during navigation, and how comprehension skills relate to the use of such cues. Our study revealed that 14 year old students (N = 53) selected hyperlinks by relying to a similar degree on both word matching and semantic overlap. Furthermore, when there was a conf…

Definition of a Model-Based Detector of Curvilinear Regions

2007

This paper describes a new approach for detection of curvilinear regions. These features detection can be useful for any matching based algorithm such as stereoscopic vision. Our detector is based on curvilinear structure model, defined observing the real world. Then, we propose a multi-scale search algorithm of curvilinear regions and we report some preliminary results.

Probabilistic techniques for bridging the semantic gap in schema alignment

Connecting pieces of informations from heterogeneous sources sharing the same domain is an open challenge in Semantic Web, Big Data and business communities. The main problem in this research area is to bridge the expressiveness gap between relational databases and ontologies. In general, an ontology is more expressive and captures more semantic information behind data than a relational database does. On the other side, databases are the most common used persistent storage system and they grant benefits such as security and data integrity but they need to be managed by expert users. The problem is quite significant above all when enterprise or corporate ontologies are used to share infomation…

Reverse-Safe Text Indexing

2021

We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstruction of the data they encode (i.e., they cannot be easily reversed). A data structure D is called z - reverse-safe when there exist at least z datasets with the same set of answers as the ones stored by D . The main challenge is to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and has size close to the size of the original dataset it encodes. Given a text of length n and an integer z , we propose an algorithm that constructs a z -reverse-safe data structure ( z -RSDS) that has size O(n) and answers decision and counting pattern matc…

Using dense stereo matching techniques in survey

2013

In recent years there has been an enormous increase in the dissemination of modelling techniques known as dense stereo matching (DSM) or image-based modelling (IBM) using free, low cost, open source software, especially applications involving the survey of cultural heritage (architecture, archaeology, and town planning). The algorithms used by these software programmes process photographic datasets and provide a 3D model of the scene in question. During complex survey and 3D restitution procedures, these techniques save time (processing) and money: these advantages Can he useful to any professional. This is why it is important to identify the real potential and limits of these software prog…

On a Conjecture on Bidimensional Words

2003

We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.

Time-Efficient Quantum Walks for 3-Distinctness

2013

We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.

On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching

2010

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of Parikh vector q (a “jumbled string”) in the text s requires to find a substring t of s with p(t) = q. The corresponding decision problem is to verify whether at least one such match exists. So, for example for the alphabet Σ = {a, b, c}, the string s = abaccbabaaa has Parikh vector p(s) = (6,3,2), and the Parikh vector q = (2,1,1) appears once in s in position (1,4). Like its more precise counterpart, the renown Exact String Matching, Jumbled Pattern Matching has ubiquitous applications, e.g., string matching with a dyslectic word processor, table rearrangements, …