Navegación

Búsqueda

Búsqueda avanzada

El autor Nieves R. Brisaboa ha publicado 8 artículo(s):

1 - Un índice espacio-temporal compacto para consultas time-slice y time-interval

La indexación de datos espacio-temporales es fundamental para responder de manera eficiente consultas acerca de objetos móviles que se encuentran en una región durante un instante o intervalo temporal determinado. Esto es de interés, por ejemplo, para detectar embarcaciones que invaden zonas de navegación prohibidas. Este artículo presenta un índice espacio-temporal compacto (eficiente en espacio) que permite responder ambos tipos de consultas. La evaluación experimental muestra que el índice propuesto es competitivo en tiempo al compararlo con el MVR-Tree usando significativamente menos espacio.

Autores: Nieves R. Brisaboa / Ramón Casares / Andrea Rodríguez / Miguel Romero / Diego Seco / 
Palabras Clave: espacio-temporal - estructura de datos compacta - indexación - Objeto móvil

2 - Exploiting SIMD instructions in current processors to improve classical string algorithms

Algorithms and data structures for efficient representation and processing of large databases can be combined with advances in computer architecture, as hardware-aware implementations that exploit particular hardware features. For example, many algorithms have been adapted to exploit the architecture of GPUs, FPGAs, or general-purpose CPUs providing instructions included for particular application domains.
In this paper we explore how the Intel SSE4.2 (Streaming SIMD Extensions) SIMD (Single Instruction Multiple Data) instructions included in Intel/AMD processors can improve the performance of algorithms for text indexing and searching. The SSE4.2 instruction subset provides instructions for text processing. Our implementations are mainly based on the followings: POPCOUNT counts the number of 1 bits in a word of up to 64 bits, PCMPESTRI compares two strings of length up to 16 bytes and returns the result as a binary mask.
Despite the benefits these features can bring to text processing, they have been rarely used or evaluated in the existing literature. We present case studies and experimental results that show how much text/string algorithms can benefit from the SIMD extensions. Particularly, we focus on the rank and select operations in sequences of bits and bytes, and the Horspool string search algorithm.

Autores: Susana Ladra / Oscar Pedreira / Jose Duato / Nieves R. Brisaboa / 
Palabras Clave:

3 - Reducción de la Complejidad Externa en Búsquedas por Similitud usando Técnicas de Clustering

La búsqueda por similitud tiene como finalidad determinar los objetos más semejantes o cercanos a uno dado. Los espacios métricos constituyen un modelo matemático que permite formalizar dicha búsqueda y que han dado lugar a diversos métodos, que tienen como objetivo principal reducir el número de evaluaciones de la función de distancia y el tamaño del índice. Las soluciones existentes son métodos basados en pivotes, que obtienen un número reducido de evaluaciones pero requieren cantidades importantes de espacio, y métodos basados en clustering, que necesitan poco espacio pero incrementan el número de evaluaciones. En este trabajo presentamos una nueva estrategia de clustering con sus algoritmos para búsquedas por rango y kNN que, reduciendo progresivamente el tamaño del cluster, disminuye significativamente la complejidad externa, un componente de la complejidad de los métodos existentes, con lo que se reduce el número de evaluaciones de la función de distancia.

Autores: Luis G. Ares / Nieves R. Brisaboa / Alberto Ordoñez / Oscar Pedreira / 
Palabras Clave: espacios métricos - Reducción de cluster - úsqueda por similitud

5 - Trayectorias semánticas en aplicaciones de Mobile Workforce Management

Los smartphones actuales presentan continuamente mejoras en sus características y en la actualidad incluyen diversos sensores que capturan información de muy diversos tipos (localización, aceleración lineal, etc.). Un proceso industrial que podría beneficiarse mucho de esta información es el de Mobile Workforce Management (MWM). Sin embargo, existen varios problemas que lo impiden: i) hoy en día el nivel de abstracción de las actividades que son identificadas es demasiado bajo (por ejemplo, moviéndose en vez de realizando una inspección en un cliente, o parado en vez de cargando un camión en la instalación de un cliente), ii) los trabajos de investigación se centran en el uso de algoritmos que contrastan la información geográfica con los datos del GPS, o en algoritmos de aprendizaje aplicados a los datos de los sensores, pero existen pocos resultados de investigación que combinen ambos tipos de datos, y iii) la información contextual procedente de los repositorios de información geográfica o del software MWM es raramente usada. En este artículo se presenta una nueva metodología que convierte los datos crudos capturados por los sensores de los dispositivos móviles en trayectorias anotadas con actividades semánticas en un alto nivel de abstracción. La metodología está basada en la definición de taxonomías de actividades que pueden ser adaptadas fácilmente a las necesidades de cualquier empresa. Estas taxonomías describen los valores esperados para cada una de las variables que son recogidas en el sistema usando predicados definidos mediante un lenguaje de especificación de patrones.

Autores: Nieves R. Brisaboa / Miguel R. Luaces / Cristina Martínez Pérez / Ángeles S. Places / 
Palabras Clave: datos de sensores - mobile workforce management - Sistemas de Informacíon Geográfica - trayectorias semánticas

6 - A compact representation for trips over networks built on self-indexes

This work has been previously published in Information Systems (ISSN: 0306-4379) vol. 28 (November 2018), pages 1-28 and DOI https://doi.org/10.1016/j.is.2018.06.010. The last measured impact factor of that journal is 2.551.Representing the movements of objects (trips) over a network in a compact way while retaining the capability of exploiting such data effectively is an important challenge of real applications. We present a new Compact Trip Representation (CTR) that handles the spatio-temporal data associated with users’ trips over transportation networks. Depending on the network and types of queries, nodes in the network can represent intersections, stops, or even street segments.CTR represents separately sequences of nodes and the time instants when users traverse these nodes. The spatial component is handled with a data structure based on the well-known Compressed Suffix Array, which provides both a compact representation and interesting indexing capabilities. The temporal component is self-indexed with either a Hu–Tucker-shaped Wavelet-Tree or a Wavelet Matrix that solve range-interval queries efficiently. We show how CTR can solve relevant counting-based spatial, temporal, and spatio-temporal queries over large sets of trips. Experimental results show the space requirements (around 50-70% of the space needed by a compact non-indexed baseline) and query efficiency (most queries are solved in <1 ms) of CTR.

Autores: Nieves R. Brisaboa / Antonio Fariña / Daniil Galaktionov / M. Andrea Rodríguez / 
Palabras Clave: Compression - Counting queries - Self-index - Transportation networks - User trajectories

7 - Aplicación de Tecnología de Líneas de Producto Software a Sistemas de Gestión del Trabajo en Movilidad

En este artículo presentamos el trabajo que en el Laboratorio de Bases de Datos estamos realizando en el marco de GEMA, un proyecto de investigación financiado en la convocatoria Conecta-PEME 2018. El objetivo de GEMA es construir una Línea de Producto Software para generar aplicaciones GTM que incorporen módulos avanzados de gestión y explotación de la movilidad como: planificación de rutas, agendas dinámicas y horarios; trayectorias semánticas; y almacenamiento compacto y explotación de la información móvil para la toma de decisión gerencial. Describimos aquí la motivación y los objetivos concretos del proyecto y principales retos a afrontar, y los avances ya realizados.

Autores: Alejandro Cortiñas / Oscar Pedreira / Miguel R. Luaces / Ángeles S. Places / Nieves R. Brisaboa / 
Palabras Clave: Líneas de Producto Software - proyecto investigación - trabajo en movilidad

8 - Two-Dimensional Block Trees

Brisaboa, N. R.; Gagie, T.; Gomez Brandon, A.; Navarro, G.: «Two-Dimensional Block Trees», en Proceedings of the 2018 Data Compression Conference (DCC 2018), IEEE Computer Society, Snowbird, Utah (Estados Unidos), 2018, pp. 227-236.GGS Class: 2DOI: 10.1109/DCC.2018.00031The Block Tree (BT) is a novel compact data structure designed to compress sequence collections. It obtains compression ratios close to Lempel-Ziv and supports efficient direct access to any substring. The BT divides the text recursively into fixed-size blocks and those appearing earlier are represented with pointers. On repetitive collections, a few blocks can represent all the others, and thus the BT reduces the size by orders of magnitude. In this paper we extend the BT to two dimensions, to exploit repetitiveness in collections of images, graphs, and maps. This two-dimensional Block Tree divides the image regularly into subimages and replaces some of them by pointers to other occurrences thereof. We develop a specific variant aimed at compressing the adjacency matrices of Web graphs, obtaining space reductions of up to 50% compared with the k2-tree, which is the best alternative supporting direct and reverse navigation in the graph.

Autores: Nieves R. Brisaboa / Travis Gagie / Adrián Gómez Brandón  / Gonzalo Navarro / 
Palabras Clave: Compact data structures - Compression - Images - Web graphs