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

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

As the number of vehicles and devices equipped with GPS technology has grown explosively, an urgent need has arisen for time- and space-efficient data structures to represent their trajectories. The most commonly desired queries are the following: queries about an object’s trajectory, range queries and nearest neighbor queries. In this paper we consider that the objects can move freely and we present a new compressed data structure for storing their trajectories, based on a combination of logs and snapshots, with the logs storing sequences of the objects’ relative movements and the snapshots storing their absolute positions sampled at regular time intervals. We call our data structure ContaCT because it provides Constant-time access to Compressed Trajectories. Its logs are based on a compact partial-sums data structure that returns cumulative displacement in constant time, and allows us to compute in constant time any object’s position at any instant, enabling a speedup when processing several other queries. We have compared ContaCT experimentally with another compact data structure for trajectories, called GraCT, and witha classic spatio-temporal index, the MVR-tree. Our results show that ContaCT outperforms the MVR-tree by orders of magnitude in space and also outperforms the compressed representation in time performance.

Autores: Nieves R. Brisaboa / Travis Gagie / Adrián Gómez-Brandón / Gonzalo Navarro / Jose R. Parama / 
Palabras Clave: Compact data structures - Spatio-temporal query - Trajectories representation

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

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:

A pesar de la madurez tecnológica de los Sistemas de Información Geográfica, todavía existen retos de investigación relevantes en el campo relacionados con las problemáticas del almacenamiento y representación eficientes de la información. En este trabajo presentamos un proyecto de investigación en curso centrado en el desarrollo de nuevas estructuras de datos para almacenar información geográfica para contextos en los que se espera que se genere una cantidad de datos inmensa.

Autores: Nieves R. Brisaboa / Alejandro Cortiñas / Pablo Gutiérrez-Asorey / Miguel R. Luaces / Tirso V. Rodeiro / 
Palabras Clave: Compresión de datos - Geoinformática - Optimización

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

Autores: Nieves R. Brisaboa / Alejandro Cortiñas / Miguel R. Luaces /  Oscar Pedreira / 
Palabras Clave:

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

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

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

We present a compact data structure to represent both the duration and length of homogeneous segments of trajectories from moving objects in a way that, as a data warehouse, it allows us to efficiently answer cumulative queries. The division of trajectories into relevant segments has been studied in the literature under the topic of Trajectory Segmentation. In this paper, we design a data structure to compactly represent them and the algorithms to answer the more relevant queries. We experimentally evaluate our proposal in the real context of an enterprise with mobile workers (truck drivers) where we aim at analyzing the time they spend in different activities. To test our proposal under higher stress conditions we generated a huge amount of synthetic realistic trajectories and evaluated our system with those data to have a good idea about its space needs and its efficiency when answering different types of queries.

Autores: Nieves R. Brisaboa / Antonio Fariña / Gonzalo Navarro / Tirso V. Rodeiro / 
Palabras Clave: Aggregation - Data Structures - Multidimensional data