We address the problem of compressing and indexing a sorted dictionary of strings to support efficient lookups and more sophisticated operations, such as prefix, predecessor, and range searches. This problem occurs as a key task in a plethora of applications, and thus it has been deeply investigated in the literature since the introduction of tries in the ’60s. We introduce a new data structure, called the COmpressed COllapsed Trie (CoCo-trie), that hinges on a pool of techniques to compress subtries (of arbitrary depth) into succinctly-encoded and efficiently-searchable trie macro-nodes with a possibly large fan-out. Then, we observe that the choice of the subtries to compress depends on the trie structure and its edge labels. Hence, we develop a data-aware optimisation approach that selects the best subtries to compress via the above pool of succinct encodings, with the overall goal of minimising the total space occupancy and still achieving efficient query time. We also investigate some variants of this approach that induce interesting space–time trade-offs in the CoCo-trie design. Our experimental evaluation on six diverse and large datasets (representing URLs, XML data, DNA and protein sequences, database records, and search-engine dictionaries) shows that the space–time performance of well-established and highly-engineered data structures solving this problem is very input-sensitive. Conversely, our CoCo-trie provides a robust and uniform improvement over all competitors for half of the datasets, and it results on the Pareto space–time frontier for the others, thus offering new competitive trade-offs.

As nowadays Machine Learning (ML) techniques are generating huge data collections, the problem of how to efficiently engineer their storage and operations is becoming of paramount importance. In this article we propose a new lossless compression scheme for real-valued matrices which achieves efficient performance in terms of compression ratio and time for linear-algebra operations. Experiments show that, as a compressor, our tool is clearly superior to gzip and it is usually within 20% of xz in terms of compression ratio. In addition, our compressed format supports matrix-vector multiplications in time and space proportional to the size of the compressed representation, unlike gzip and xz that require the full decompression of the compressed matrix. To our knowledge our lossless compressor is the first one achieving time and space complexities which match the theoretical limit expressed by the k -th order statistical entropy of the input. To achieve further time/space reductions, we propose column-reordering algorithms hinging on a novel column-similarity score. Our experiments on various data sets of ML matrices show that our column reordering can yield a further reduction of up to 16% in the peak memory usage during matrix-vector multiplication. Finally, we compare our proposal against the state-of-the-art Compressed Linear Algebra (CLA) approach showing that ours runs always at least twice faster (in a multi-thread setting), and achieves better compressed space occupancy and peak memory usage. This experimentally confirms the provably effective theoretical bounds we show for our compressed-matrix approach.

Ride sharing has a tremendous potential to reduce the number of vehicles needed to serve a certain mobility demand. However, although ride sourcing services have flourished in recent years and are widely available worldwide (e.g. Uber, Didi, Lyft, Via), known ride sharing techniques still suffer severe scalability limitations, especially if the goal is combining multiple on-demand ride requests into a single trip within a large urban area. In the context of on-demand mobility systems, a complete enumeration of all candidate trip requests is unfortunately not a practical approach to find the optimal ride sharing solution. An efficient filtering approach is therefore needed in order to avoid both the storage of quadratic shortest-path lookup tables, as well as the exhaustive pairwise comparison of all mobility requests, with their GPS coordinates and time constraints. In this paper we present a ride sharing algorithm, which combined with the shareability networks method, is able to substantially speed up known approaches while only minimally impacting on the quality of the computed solution. The key building block is a novellocality filter, which allows to build a pruned version of the shareability network more efficiently in time and space than previous works. We corroborate this novel proposal with a large set of experiments executed over a dataset consisting of one month of trip requests (~106) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a$5\times $speed-up, or even more during so-called “rush times”, and it is robust under different traffic conditions.