Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 5
Encontrada(s) 1 página(s)

RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Which fast nearest neighbour search algorithm to use?

  • Serrano Díaz-Carrasco, Aureo
  • Micó, Luisa
  • Oncina, Jose
Choosing which fast Nearest Neighbour search algorithm to use depends on the task we face. Usually kd-tree search algorithm is selected when the similarity function is the Euclidean or the Manhattan distances. Generic fast search algorithms (algorithms that works with any distance function) are only used when there is not specific fast search algorithms for the involved distance function. In this work we show that in real data problems generic search algorithms (i.e. MDF-tree) can be faster that specific ones (i.e. kd-tree).
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

The most probable string: an algorithmic study

  • Higuera, Colin de la
  • Oncina, Jose
The problem of finding the consensus (most probable string) for a distribution generated by a weighted finite automaton or a probabilistic grammar is related to a number of important questions: computing the distance between two distributions or finding the best translation (the most probable one) given a probabilistic finite state transducer. The problem is undecidable with general weights and is NP-hard if the automaton is probabilistic. We give a pseudo-polynomial algorithm that solves a decision problem directly associated with the consensus string and answers if there is a (reasonably short) string whose probability is larger than a given bound in time polynomial in the the size of this bound, both for probabilistic finite automata and probabilistic context-free grammars. We also study a randomized algorithm solving the same problem. Finally, we report links between the length of the consensus string and the probability of this string.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

MirBot: A Multimodal Interactive Image Retrieval System

  • Pertusa, Antonio
  • Gallego, Antonio-Javier
  • Bernabeu, Marisa
  • Gallego, Antonio-Javier|||/items/8f865afc-8f63-4e0d-9408-bebc7ba836d0
  • Pertusa, Antonio|||/items/3bf633ff-4d49-4aaa-a004-abcf6fed3540
This study presents a multimodal interactive image retrieval system for smartphones (MirBot). The application is designed as a collaborative game where users can categorize photographs according to the WordNet hierarchy. After taking a picture, the region of interest of the target can be selected, and the image information is sent with a set of metadata to a server in order to classify the object. The user can validate the category proposed by the system to improve future queries. The result is a labeled database with a structure similar to ImageNet, but with contents selected by the users, fully marked with regions of interest, and with novel metadata that can be useful to constrain the search space in a future work. The MirBot app is freely available on the Apple app store.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Finding the most probable string and the consensus string: an algorithmic study

  • Higuera, Colin de la
  • Oncina, Jose
The problem of finding the most probable string for a distribution generated by a weighted finite automaton is related to a number of important questions: computing the distance between two distributions or finding the best translation (the most probable one) given a probabilistic finite state transducer. The problem is undecidable with general weights and is $\NP$-hard if the automaton is probabilistic. In this paper we give a pseudo-polynomial algorithm which computes the most probable string in time polynomial in the inverse of the probability of this string itself. We also give a randomised algorithm solving the same problem and discuss the case where the distribution is generated by other types of machines.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Uso eficiente de pivotes aplicado a la búsqueda aproximada en algoritmos rápidos sobre espacios métricos, Efficient use of pivots for approximate search in metric spaces

  • Socorro Llanes, Raisa
  • Micó, Luisa
El contexto de este trabajo es la búsqueda rápida de vecinos más cercanos en espacios métricos. Uno de los objetivos de estos algoritmos es la reducción del tiempo de respuesta durante la búsqueda. Reducir el tiempo de respuesta consiste muchas veces en reducir el número de distancias a calcular, debido al alto coste computacional que de por sí pueden tener las distancias a utilizar en ciertas aplicaciones. Nosotros proponemos una nueva versión y mejoras de un algoritmo recientemente publicado, PiAESA, variante del algoritmo AESA, usado como referencia en este área por sus buenos resultados desde hace más de 20 años. La nueva versión es más simple y permite una mejor comprensión del algoritmo y sus parámetros. Además, se ha conseguido aumentar la eficiencia definiendo una versión aproximada. Los resultados empíricos obtenidos utilizando datos artificiales y reales confirman una mejora en los resultados de la versión aproximada, con un alto porcentaje de una respuesta correcta (dada por un algoritmo exacto).