2025
Conference article
Open Access
kANNolo: sweet and smooth approximate k-nearest neighbors search
Delfino L., Erriquez D., Martinico S., Nardini F. M., Rulli C., Venturini R.
Approximate Nearest Neighbors (ANN) search is a crucial task in several applications like recommender systems and information retrieval. Current state-of-the-art ANN libraries, although being performance-oriented, often lack modularity and ease of use. This translates into them not being fully suitable for easy prototyping and testing of research ideas, an important feature to enable. We address these limitations by introducing kANNolo, a novel—research-oriented—ANN library written in Rust and explicitly designed to combine usability with performance effectively. kANNolo is the first ANN library that supports dense and sparse vector representations made available on top of different similarity measures, e.g., euclidean distance and inner product. Moreover, it also supports vector quantization techniques, e.g., Product Quantization, on top of the indexing strategies implemented. These functionalities are managed through Rust traits, allowing shared behaviors to be handled abstractly. This abstraction ensures flexibility and facilitates an easy integration of new components. In this work, we detail the architecture of kANNolo and demonstrate that its flexibility does not compromise performance. The experimental analysis shows that kANNolo achieves state-of-the-art performance in terms of speed-accuracy trade-off while allowing fast and easy prototyping, thus making kANNolo a valuable tool for advancing ANN research. Source code available on GitHub: https://github.com/TusKANNy/kannolo.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15575, pp. 400-406. Lucca, Italy, 6–10/04/2025
DOI: 10.1007/978-3-031-88717-8_29
DOI: 10.48550/arxiv.2501.06121
Project(s): EFRA
Metrics:
Delfino L., Erriquez D., Martinico S., Nardini F. M., Rulli C., Venturini R.
Approximate Nearest Neighbors (ANN) search is a crucial task in several applications like recommender systems and information retrieval. Current state-of-the-art ANN libraries, although being performance-oriented, often lack modularity and ease of use. This translates into them not being fully suitable for easy prototyping and testing of research ideas, an important feature to enable. We address these limitations by introducing kANNolo, a novel—research-oriented—ANN library written in Rust and explicitly designed to combine usability with performance effectively. kANNolo is the first ANN library that supports dense and sparse vector representations made available on top of different similarity measures, e.g., euclidean distance and inner product. Moreover, it also supports vector quantization techniques, e.g., Product Quantization, on top of the indexing strategies implemented. These functionalities are managed through Rust traits, allowing shared behaviors to be handled abstractly. This abstraction ensures flexibility and facilitates an easy integration of new components. In this work, we detail the architecture of kANNolo and demonstrate that its flexibility does not compromise performance. The experimental analysis shows that kANNolo achieves state-of-the-art performance in terms of speed-accuracy trade-off while allowing fast and easy prototyping, thus making kANNolo a valuable tool for advancing ANN research. Source code available on GitHub: https://github.com/TusKANNy/kannolo.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15575, pp. 400-406. Lucca, Italy, 6–10/04/2025
DOI: 10.1007/978-3-031-88717-8_29
DOI: 10.48550/arxiv.2501.06121
Project(s): EFRA
Metrics:
See at:
arXiv.org e-Print Archive 
| dl.acm.org | CNR IRIS | doi.org 
| doi.org | CNR IRIS | CNR IRIS
2024
Conference article
Open Access
Pairing clustered inverted indexes with κ-NN graphs for fast approximate retrieval over learned sparse representations
Bruch S., Nardini F. M., Rulli C., Venturini R.
Learned sparse representations form an effective and interpretable class of embeddings for text retrieval. While exact top-k retrieval over such embeddings faces efficiency challenges, a recent algorithm called Seismic has enabled remarkably fast, highly-accurate approximate retrieval. Seismic statically prunes inverted lists, organizes each list into geometrically-cohesive blocks, and augments each block with a summary vector. At query time, each inverted list associated with a query term is traversed one block at a time in an arbitrary order, with the inner product between the query and summaries determining if a block must be evaluated. When a block is deemed promising, its documents are fully evaluated with a forward index. Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions and significantly outperforms the winning graph-based submissions to the BigANN 2023 Challenge. In this work, we speed up Seismic further by introducing two innovations to its query processing subroutine. First, we traverse blocks in order of importance, rather than arbitrarily. Second, we take the list of documents retrieved by Seismic and expand it to include the neighbors of each document using an offline k-regular nearest neighbor graph; the expanded list is then ranked to produce the final top-k set. Experiments on two public datasets show that our extension, named SeismicWave, can reach almost-exact accuracy levels and is up to 2.2x faster than Seismic.DOI: 10.1145/3627673.3679977
DOI: 10.48550/arxiv.2408.04443
Project(s): EFRA
Metrics:
Bruch S., Nardini F. M., Rulli C., Venturini R.
Learned sparse representations form an effective and interpretable class of embeddings for text retrieval. While exact top-k retrieval over such embeddings faces efficiency challenges, a recent algorithm called Seismic has enabled remarkably fast, highly-accurate approximate retrieval. Seismic statically prunes inverted lists, organizes each list into geometrically-cohesive blocks, and augments each block with a summary vector. At query time, each inverted list associated with a query term is traversed one block at a time in an arbitrary order, with the inner product between the query and summaries determining if a block must be evaluated. When a block is deemed promising, its documents are fully evaluated with a forward index. Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions and significantly outperforms the winning graph-based submissions to the BigANN 2023 Challenge. In this work, we speed up Seismic further by introducing two innovations to its query processing subroutine. First, we traverse blocks in order of importance, rather than arbitrarily. Second, we take the list of documents retrieved by Seismic and expand it to include the neighbors of each document using an offline k-regular nearest neighbor graph; the expanded list is then ranked to produce the final top-k set. Experiments on two public datasets show that our extension, named SeismicWave, can reach almost-exact accuracy levels and is up to 2.2x faster than Seismic.DOI: 10.1145/3627673.3679977
DOI: 10.48550/arxiv.2408.04443
Project(s): EFRA
Metrics:
See at:
arXiv.org e-Print Archive | dl.acm.org | CNR IRIS | doi.org | doi.org | CNR IRIS
2024
Conference article
Open Access
Efficient multi-vector dense retrieval with bit vectors
Nardini F. M., Rulli C., Venturini R.
Dense retrieval techniques employ pre-trained large language models to build high-dimensional representations of queries and passages. These representations compute the relevance of a passage with respect to a query using efficient similarity measures. Multi-vector representations show improved effectiveness but come with a one-order-of-magnitude increase in memory footprint and query latency by encoding queries and documents on a per-token level. Recently, PLAID addressed these challenges by introducing a centroid-based term representation to reduce the memory impact of multi-vector systems. By exploiting a centroid interaction mechanism, PLAID filters out non-relevant documents, reducing the cost of successive ranking stages. This paper proposes "Efficient Multi-Vector Dense Retrieval with Bit Vectors" (EMVB), a novel framework for efficient query processing in multi-vector dense retrieval. First, EMVB employs a highly efficient pre-filtering step of passages using optimized bit vectors. Second, the computation of the centroid interaction happens column-wise, leveraging SIMD instructions to reduce latency. Third, EMVB uses Product Quantization (PQ) to reduce the memory footprint of storing vector representations while allowing for fast late interaction. Finally, we introduce a per-document term filtering method that further improves the efficiency of the final step. Experiments on MS MARCO and LoTTE demonstrate that EMVB is up to 2.8× faster and reduces the memory footprint by 1.8× without any loss in retrieval accuracy compared to PLAID.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 14609, pp. 3-17. Glasgow, UK, 24–28/03/2024
DOI: 10.1007/978-3-031-56060-6_1
Project(s): EFRA
Metrics:
Nardini F. M., Rulli C., Venturini R.
Dense retrieval techniques employ pre-trained large language models to build high-dimensional representations of queries and passages. These representations compute the relevance of a passage with respect to a query using efficient similarity measures. Multi-vector representations show improved effectiveness but come with a one-order-of-magnitude increase in memory footprint and query latency by encoding queries and documents on a per-token level. Recently, PLAID addressed these challenges by introducing a centroid-based term representation to reduce the memory impact of multi-vector systems. By exploiting a centroid interaction mechanism, PLAID filters out non-relevant documents, reducing the cost of successive ranking stages. This paper proposes "Efficient Multi-Vector Dense Retrieval with Bit Vectors" (EMVB), a novel framework for efficient query processing in multi-vector dense retrieval. First, EMVB employs a highly efficient pre-filtering step of passages using optimized bit vectors. Second, the computation of the centroid interaction happens column-wise, leveraging SIMD instructions to reduce latency. Third, EMVB uses Product Quantization (PQ) to reduce the memory footprint of storing vector representations while allowing for fast late interaction. Finally, we introduce a per-document term filtering method that further improves the efficiency of the final step. Experiments on MS MARCO and LoTTE demonstrate that EMVB is up to 2.8× faster and reduces the memory footprint by 1.8× without any loss in retrieval accuracy compared to PLAID.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 14609, pp. 3-17. Glasgow, UK, 24–28/03/2024
DOI: 10.1007/978-3-031-56060-6_1
Project(s): EFRA
Metrics:
See at:
CNR IRIS | link.springer.com | doi.org | Archivio della Ricerca - Università di Pisa | CNR IRIS | CNR IRIS
2024
Journal article
Open Access
Learning bivariate scoring functions for ranking
Nardini F. M., Trani R., Venturini R.
State-of-the-art Learning-to-Rank algorithms, e.g., MART, rely on univariate scoring functions to score a list of items. Univariate scoring functions score each item independently, i.e., without considering the other available items in the list. Nevertheless, ranking deals with producing an effective ordering of the items and comparisons between items are helpful to achieve this task. Bivariate scoring functions allow the model to exploit dependencies between the items in the list as they work by scoring pairs of items. In this paper, we exploit item dependencies in a novel framework—we call it the Lambda Bivariate (LB) framework—that allows to learn effective bivariate scoring functions for ranking using gradient boosting trees. We discuss the three main ingredients of LB: (i) the invariance to permutations property, (ii) the function aggregating the scores of all pairs into the per-item scores, and (iii) the optimization process to learn bivariate scoring functions for ranking using any differentiable loss functions. We apply LB to the Rank loss and we show that it results in learning a bivariate version of MART—we call it Bi- MART—that significantly outperforms all neural-network-based and tree-based state-of-the-art algorithms for Learning-to-Rank. To show the generality of LB with respect to other loss functions, we also discuss its application to the Softmax loss.Source: DISCOVER COMPUTING, vol. 27 (issue 1)
DOI: 10.1007/s10791-024-09444-7
Project(s): Algorithmic Problems and Machine Learning, EFRA
Metrics:
Nardini F. M., Trani R., Venturini R.
State-of-the-art Learning-to-Rank algorithms, e.g., MART, rely on univariate scoring functions to score a list of items. Univariate scoring functions score each item independently, i.e., without considering the other available items in the list. Nevertheless, ranking deals with producing an effective ordering of the items and comparisons between items are helpful to achieve this task. Bivariate scoring functions allow the model to exploit dependencies between the items in the list as they work by scoring pairs of items. In this paper, we exploit item dependencies in a novel framework—we call it the Lambda Bivariate (LB) framework—that allows to learn effective bivariate scoring functions for ranking using gradient boosting trees. We discuss the three main ingredients of LB: (i) the invariance to permutations property, (ii) the function aggregating the scores of all pairs into the per-item scores, and (iii) the optimization process to learn bivariate scoring functions for ranking using any differentiable loss functions. We apply LB to the Rank loss and we show that it results in learning a bivariate version of MART—we call it Bi- MART—that significantly outperforms all neural-network-based and tree-based state-of-the-art algorithms for Learning-to-Rank. To show the generality of LB with respect to other loss functions, we also discuss its application to the Softmax loss.Source: DISCOVER COMPUTING, vol. 27 (issue 1)
DOI: 10.1007/s10791-024-09444-7
Project(s): Algorithmic Problems and Machine Learning, EFRA
Metrics:
See at:
Discover Computing | CNR IRIS | link.springer.com | Software Heritage | Software Heritage | Software Heritage | Software Heritage | Software Heritage | Software Heritage | Software Heritage | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | GitHub | CNR IRIS
2024
Conference article
Open Access
Efficient and effective multi-vector dense retrieval with EMVB
Nardini F. M., Rulli C., Venturini R.
Dense retrieval techniques utilize large pre-trained language models to construct a high-dimensional representation of queries and passages. These representations assess the relevance of a passage concerning a query through efficient similarity measures. Multi-vector representations, while enhancing effectiveness, cause a one-order-of-magnitude increase in memory footprint and query latency by encoding queries and documents on a per-token level. The current state-of-the-art approach, namely PLAID, has introduced a centroid-based term representation to mitigate the memory impact of multi-vector systems. By employing a centroid interaction mechanism, PLAID filters out non-relevant documents, reducing the cost of subsequent ranking stages. This paper1 introduces "Efficient Multi-Vector dense retrieval with Bit vectors" (EMVB), a novel framework for efficient query processing in multi-vector dense retrieval. Firstly, EMVB utilizes an optimized bit vector pre-filtering step for passages, enhancing efficiency. Secondly, the computation of centroid interaction occurs column-wise, leveraging SIMD instructions to reduce latency. Thirdly, EMVB incorporates Product Quantization (PQ) to decrease the memory footprint of storing vector representations while facilitating fast late interaction. Lastly, a per-document term filtering method is introduced, further improving the efficiency of the final step. Experiments conducted on MS MARCO and LoTTE demonstrate that EMVB achieves up to a 2.8× speed improvement while reducing the memory footprint by 1.8×, without compromising retrieval accuracy compared to PLAID.Source: CEUR WORKSHOP PROCEEDINGS, vol. 3741, pp. 281-289. Villasimius, Sud Sardegna, Italy (virtual due to Covid-19 pandemic), 23-26/06/2024
Nardini F. M., Rulli C., Venturini R.
Dense retrieval techniques utilize large pre-trained language models to construct a high-dimensional representation of queries and passages. These representations assess the relevance of a passage concerning a query through efficient similarity measures. Multi-vector representations, while enhancing effectiveness, cause a one-order-of-magnitude increase in memory footprint and query latency by encoding queries and documents on a per-token level. The current state-of-the-art approach, namely PLAID, has introduced a centroid-based term representation to mitigate the memory impact of multi-vector systems. By employing a centroid interaction mechanism, PLAID filters out non-relevant documents, reducing the cost of subsequent ranking stages. This paper1 introduces "Efficient Multi-Vector dense retrieval with Bit vectors" (EMVB), a novel framework for efficient query processing in multi-vector dense retrieval. Firstly, EMVB utilizes an optimized bit vector pre-filtering step for passages, enhancing efficiency. Secondly, the computation of centroid interaction occurs column-wise, leveraging SIMD instructions to reduce latency. Thirdly, EMVB incorporates Product Quantization (PQ) to decrease the memory footprint of storing vector representations while facilitating fast late interaction. Lastly, a per-document term filtering method is introduced, further improving the efficiency of the final step. Experiments conducted on MS MARCO and LoTTE demonstrate that EMVB achieves up to a 2.8× speed improvement while reducing the memory footprint by 1.8×, without compromising retrieval accuracy compared to PLAID.Source: CEUR WORKSHOP PROCEEDINGS, vol. 3741, pp. 281-289. Villasimius, Sud Sardegna, Italy (virtual due to Covid-19 pandemic), 23-26/06/2024
See at:
ceur-ws.org | CNR IRIS | CNR IRIS
2022
Journal article
Open Access
Distilled neural networks for efficient learning to rank
Nardini Fm, Rulli C, Trani S, Venturini R
Recent studies in Learning to Rank have shown the possibility to effectively distill a neural network from an ensemble of regression trees. This result leads neural networks to become a natural competitor of tree-based ensembles on the ranking task. Nevertheless, ensembles of regression trees outperform neural models both in terms of efficiency and effectiveness, particularly when scoring on CPU. In this paper, we propose an approach for speeding up neural scoring time by applying a combination of Distillation, Pruning and Fast Matrix multiplication. We employ knowledge distillation to learn shallow neural networks from an ensemble of regression trees. Then, we exploit an efficiency-oriented pruning technique that performs a sparsification of the most computationally-intensive layers of the neural network that is then scored with optimized sparse matrix multiplication. Moreover, by studying both dense and sparse high performance matrix multiplication, we develop a scoring time prediction model which helps in devising neural network architectures that match the desired efficiency requirements. Comprehensive experiments on two public learning-to-rank datasets show that neural networks produced with our novel approach are competitive at any point of the effectiveness-efficiency trade-off when compared with tree-based ensembles, providing up to 4x scoring time speed-up without affecting the ranking quality.Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (ONLINE), vol. 35 (issue 5), pp. 4695-4712
DOI: 10.1109/tkde.2022.3152585
Metrics:
Nardini Fm, Rulli C, Trani S, Venturini R
Recent studies in Learning to Rank have shown the possibility to effectively distill a neural network from an ensemble of regression trees. This result leads neural networks to become a natural competitor of tree-based ensembles on the ranking task. Nevertheless, ensembles of regression trees outperform neural models both in terms of efficiency and effectiveness, particularly when scoring on CPU. In this paper, we propose an approach for speeding up neural scoring time by applying a combination of Distillation, Pruning and Fast Matrix multiplication. We employ knowledge distillation to learn shallow neural networks from an ensemble of regression trees. Then, we exploit an efficiency-oriented pruning technique that performs a sparsification of the most computationally-intensive layers of the neural network that is then scored with optimized sparse matrix multiplication. Moreover, by studying both dense and sparse high performance matrix multiplication, we develop a scoring time prediction model which helps in devising neural network architectures that match the desired efficiency requirements. Comprehensive experiments on two public learning-to-rank datasets show that neural networks produced with our novel approach are competitive at any point of the effectiveness-efficiency trade-off when compared with tree-based ensembles, providing up to 4x scoring time speed-up without affecting the ranking quality.Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (ONLINE), vol. 35 (issue 5), pp. 4695-4712
DOI: 10.1109/tkde.2022.3152585
Metrics:
See at:
CNR IRIS | ieeexplore.ieee.org | ISTI Repository | CNR IRIS | CNR IRIS
2021
Contribution to conference
Open Access
Compressed indexes for fast search of semantic data
Perego R, Pibiri Ge, Venturini R
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is devising a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. We propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30-60% less space and speeding up query execution by a factor of 2-81 times.DOI: 10.1109/icde51399.2021.00248
Project(s): BigDataGrapes
Metrics:
Perego R, Pibiri Ge, Venturini R
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is devising a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. We propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30-60% less space and speeding up query execution by a factor of 2-81 times.DOI: 10.1109/icde51399.2021.00248
Project(s): BigDataGrapes
Metrics:
See at:
CNR IRIS | ieeexplore.ieee.org | ISTI Repository | CNR IRIS | CNR IRIS
2021
Conference article
Open Access
TSXor: a simple time series compression algorithm
Bruno A, Nardini Fm, Pibiri Ge, Trani R, Venturini R
Time series are ubiquitous in computing as a key ingredient of many machine learning analytics, ranging from classification to forecasting. Typically, the training of such machine learning algorithms on time series requires to access the data in temporal order for several times. Therefore, a compression algorithm providing good compression ratios and fast decompression speed is desirable. In this paper, we present TSXor, a simple yet effective lossless compressor for time series. The main idea is to exploit the redundancy/similarity between close-in-time values through a window that acts as a cache, as to improve the compression ratio and decompression speed. We show that TSXor achieves up to 3× better compression and up to 2× faster decompression than the state of the art on real-world datasets.DOI: 10.1007/978-3-030-86692-1_18
Metrics:
Bruno A, Nardini Fm, Pibiri Ge, Trani R, Venturini R
Time series are ubiquitous in computing as a key ingredient of many machine learning analytics, ranging from classification to forecasting. Typically, the training of such machine learning algorithms on time series requires to access the data in temporal order for several times. Therefore, a compression algorithm providing good compression ratios and fast decompression speed is desirable. In this paper, we present TSXor, a simple yet effective lossless compressor for time series. The main idea is to exploit the redundancy/similarity between close-in-time values through a window that acts as a cache, as to improve the compression ratio and decompression speed. We show that TSXor achieves up to 3× better compression and up to 2× faster decompression than the state of the art on real-world datasets.DOI: 10.1007/978-3-030-86692-1_18
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | CNR IRIS | CNR IRIS
2021
Journal article
Open Access
Fast filtering of search results sorted by attribute
Nardini Fm, Trani R, Venturini R
Modern search services often provide multiple options to rank the search results, e.g., sort "by relevance", "by price" or "by discount" in e-commerce. While the traditional rank by relevance effectively places the relevant results in the top positions of the results list, the rank by attribute could place many marginally relevant results in the head of the results list leading to poor user experience. In the past, this issue has been addressed by investigating the relevance-aware filtering problem, which asks to select the subset of results maximizing the relevance of the attribute-sorted list. Recently, an exact algorithm has been proposed to solve this problem optimally. However, the high computational cost of the algorithm makes it impractical for the Web search scenario, which is characterized by huge lists of results and strict time constraints. For this reason, the problem is often solved using efficient yet inaccurate heuristic algorithms. In this paper, we first prove the performance bounds of the existing heuristics. We then propose two efficient and effective algorithms to solve the relevance-aware filtering problem. First, we propose OPT-Filtering, a novel exact algorithm that is faster than the existing state-of-the-art optimal algorithm. Second, we propose an approximate and even more efficient algorithm, ?-Filtering, which, given an allowed approximation error ?, finds a (1-?)-optimal filtering, i.e., the relevance of its solution is at least (1-?) times the optimum. We conduct a comprehensive evaluation of the two proposed algorithms against state-of-the-art competitors on two real-world public datasets. Experimental results show that OPT-Filtering achieves a significant speedup of up to two orders of magnitude with respect to the existing optimal solution, while ?-Filtering further improves this result by trading effectiveness for efficiency. In particular, experiments show that ?-Filtering can achieve quasi-optimal solutions while being faster than all state-of-the-art competitors in most of the tested configurations.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 40 (issue 2)
DOI: 10.1145/3477982
Metrics:
Nardini Fm, Trani R, Venturini R
Modern search services often provide multiple options to rank the search results, e.g., sort "by relevance", "by price" or "by discount" in e-commerce. While the traditional rank by relevance effectively places the relevant results in the top positions of the results list, the rank by attribute could place many marginally relevant results in the head of the results list leading to poor user experience. In the past, this issue has been addressed by investigating the relevance-aware filtering problem, which asks to select the subset of results maximizing the relevance of the attribute-sorted list. Recently, an exact algorithm has been proposed to solve this problem optimally. However, the high computational cost of the algorithm makes it impractical for the Web search scenario, which is characterized by huge lists of results and strict time constraints. For this reason, the problem is often solved using efficient yet inaccurate heuristic algorithms. In this paper, we first prove the performance bounds of the existing heuristics. We then propose two efficient and effective algorithms to solve the relevance-aware filtering problem. First, we propose OPT-Filtering, a novel exact algorithm that is faster than the existing state-of-the-art optimal algorithm. Second, we propose an approximate and even more efficient algorithm, ?-Filtering, which, given an allowed approximation error ?, finds a (1-?)-optimal filtering, i.e., the relevance of its solution is at least (1-?) times the optimum. We conduct a comprehensive evaluation of the two proposed algorithms against state-of-the-art competitors on two real-world public datasets. Experimental results show that OPT-Filtering achieves a significant speedup of up to two orders of magnitude with respect to the existing optimal solution, while ?-Filtering further improves this result by trading effectiveness for efficiency. In particular, experiments show that ?-Filtering can achieve quasi-optimal solutions while being faster than all state-of-the-art competitors in most of the tested configurations.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 40 (issue 2)
DOI: 10.1145/3477982
Metrics:
See at:
dl.acm.org | CNR IRIS | ISTI Repository | CNR IRIS | CNR IRIS
2020
Journal article
Open Access
Compressed indexes for fast search of semantic data
Pibiri G. E., Perego R., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is to devise a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. In this work, we propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis, conducted over a wide range of publicly available real-world datasets, reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30 - 60% less space and speeding up query execution by a factor of 2-81× .Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (PRINT), vol. 33 (issue 9), pp. 3187-3198
DOI: 10.1109/tkde.2020.2966609
DOI: 10.48550/arxiv.1904.07619
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Perego R., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is to devise a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. In this work, we propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis, conducted over a wide range of publicly available real-world datasets, reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30 - 60% less space and speeding up query execution by a factor of 2-81× .Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (PRINT), vol. 33 (issue 9), pp. 3187-3198
DOI: 10.1109/tkde.2020.2966609
DOI: 10.48550/arxiv.1904.07619
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | IEEE Transactions on Knowledge and Data Engineering | CNR IRIS | ieeexplore.ieee.org | ISTI Repository | IEEE Transactions on Knowledge and Data Engineering | doi.org | CNR IRIS | CNR IRIS
2020
Conference article
Open Access
Efficient and effective query auto-completion
Gog S, Pibiri Ge, Venturini R
Query Auto-Completion (QAC) is an ubiquitous feature of modern textual search systems, suggesting possible ways of completing the query being typed by the user. Efficiency is crucial to make the system have a real-time responsiveness when operating in the million-scale search space. Prior work has extensively advocated the use of a trie data structure for fast prefix-search operations in compact space. However, searching by prefix has little discovery power in that only completions that are prefixed by the query are returned. This may impact negatively the effectiveness of the QAC system, with a consequent monetary loss for real applications like Web Search Engines and eCommerce. In this work we describe the implementation that empowers a new QAC system at eBay, and discuss its efficiency/effectiveness in relation to other approaches at the state-of-the-art. The solution is based on the combination of an inverted index with succinct data structures, a much less explored direction in the literature. This system is replacing the previous implementation based on Apache SOLR that was not always able to meet the required service-level-agreement.DOI: 10.1145/3397271.3401432
DOI: 10.48550/arxiv.2005.06213
Project(s): BigDataGrapes
Metrics:
Gog S, Pibiri Ge, Venturini R
Query Auto-Completion (QAC) is an ubiquitous feature of modern textual search systems, suggesting possible ways of completing the query being typed by the user. Efficiency is crucial to make the system have a real-time responsiveness when operating in the million-scale search space. Prior work has extensively advocated the use of a trie data structure for fast prefix-search operations in compact space. However, searching by prefix has little discovery power in that only completions that are prefixed by the query are returned. This may impact negatively the effectiveness of the QAC system, with a consequent monetary loss for real applications like Web Search Engines and eCommerce. In this work we describe the implementation that empowers a new QAC system at eBay, and discuss its efficiency/effectiveness in relation to other approaches at the state-of-the-art. The solution is based on the combination of an inverted index with succinct data structures, a much less explored direction in the literature. This system is replacing the previous implementation based on Apache SOLR that was not always able to meet the required service-level-agreement.DOI: 10.1145/3397271.3401432
DOI: 10.48550/arxiv.2005.06213
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | arxiv.org | dl.acm.org | CNR IRIS | ISTI Repository | doi.org | doi.org | CNR IRIS | CNR IRIS
2019
Journal article
Open Access
Parallel Traversal of Large Ensembles of Decision Trees
Lettich F, Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. The deployment of such models is computationally demanding: to compute the final prediction, the whole ensemble must be traversed by accumulating the contributions of all its trees. In particular, traversal cost impacts applications where the number of candidate items is large, the time budget available to apply the learnt model to them is limited, and the users' expectations in terms of quality-of-service is high. Document ranking in web search, where sub-optimal ranking models are deployed to find a proper trade-off between efficiency and effectiveness of query answering, is probably the most typical example of this challenging issue. This paper investigates multi/many-core parallelization strategies for speeding up the traversal of large ensembles of regression trees thus obtaining machine-learnt models that are, at the same time, effective, fast, and scalable. Our best results are obtained by the GPU-based parallelization of the state-of-the-art algorithm, with speedups of up to 102.6x.Source: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (PRINT), vol. 30 (issue 9), pp. 2075-2089
DOI: 10.1109/tpds.2018.2860982
DOI: 10.5281/zenodo.2668378
DOI: 10.5281/zenodo.2668379
Project(s): BigDataGrapes
Metrics:
Lettich F, Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. The deployment of such models is computationally demanding: to compute the final prediction, the whole ensemble must be traversed by accumulating the contributions of all its trees. In particular, traversal cost impacts applications where the number of candidate items is large, the time budget available to apply the learnt model to them is limited, and the users' expectations in terms of quality-of-service is high. Document ranking in web search, where sub-optimal ranking models are deployed to find a proper trade-off between efficiency and effectiveness of query answering, is probably the most typical example of this challenging issue. This paper investigates multi/many-core parallelization strategies for speeding up the traversal of large ensembles of regression trees thus obtaining machine-learnt models that are, at the same time, effective, fast, and scalable. Our best results are obtained by the GPU-based parallelization of the state-of-the-art algorithm, with speedups of up to 102.6x.Source: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (PRINT), vol. 30 (issue 9), pp. 2075-2089
DOI: 10.1109/tpds.2018.2860982
DOI: 10.5281/zenodo.2668378
DOI: 10.5281/zenodo.2668379
Project(s): BigDataGrapes
Metrics:
See at:
IEEE Transactions on Parallel and Distributed Systems | ZENODO | ZENODO | Archivio istituzionale della ricerca - Università degli Studi di Venezia Ca' Foscari | CNR IRIS | ieeexplore.ieee.org | ISTI Repository | IEEE Transactions on Parallel and Distributed Systems | CNR IRIS | CNR IRIS
2019
Journal article
Open Access
Handling massive n-gram datasets efficiently
Pibiri G E, Venturini R
Two fundamental problems concern the handling of large n-gram language models: indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source. Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation. Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time. Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space. Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large textual sources poses the challenge of devising algorithms that make a parsimonious use of the disk. The state-of-the-art algorithm uses three sorting steps in external memory: we show an improved construction that requires only one sorting step by exploiting the properties of the extracted n-gram strings. With an extensive experimental analysis performed on billions of n-grams, we show an average improvement of 4.5 times on the total runtime of the previous approach.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 37 (issue 2)
DOI: 10.1145/3302913
DOI: 10.48550/arxiv.1806.09447
DOI: 10.5281/zenodo.3257994
DOI: 10.5281/zenodo.3257995
Project(s): BigDataGrapes
Metrics:
Pibiri G E, Venturini R
Two fundamental problems concern the handling of large n-gram language models: indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source. Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation. Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time. Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space. Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large textual sources poses the challenge of devising algorithms that make a parsimonious use of the disk. The state-of-the-art algorithm uses three sorting steps in external memory: we show an improved construction that requires only one sorting step by exploiting the properties of the extracted n-gram strings. With an extensive experimental analysis performed on billions of n-grams, we show an average improvement of 4.5 times on the total runtime of the previous approach.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 37 (issue 2)
DOI: 10.1145/3302913
DOI: 10.48550/arxiv.1806.09447
DOI: 10.5281/zenodo.3257994
DOI: 10.5281/zenodo.3257995
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | dl.acm.org | ZENODO | ZENODO | CNR IRIS | ISTI Repository | ACM Transactions on Information Systems | ACM Transactions on Information Systems | doi.org | CNR IRIS | CNR IRIS
2019
Conference article
Open Access
Fast Approximate Filtering of Search Results Sorted by Attribute
Nardini Fm, Trani R, Venturini R
Several Web search services enable their users with the possibility of sorting the list of results by a specific attribute, e.g., sort "by price" in e-commerce. However, sorting the results by attribute could bring marginally relevant results in the top positions thus leading to a poor user experience. This motivates the definition of the relevance-aware filtering problem. This problem asks to remove results from the attribute-sorted list to maximize its final overall relevance. Recently, an optimal solution to this problem has been proposed. However, it has strong limitations in the Web scenario due to its high computational cost. In this paper, we propose ?-Filtering: an efficient approximate algorithm with strong approximation guarantees on the relevance of the final list. More precisely, given an allowed approximation error ?, the proposed algorithm finds a(1-?)"optimal filtering, i.e., the relevance of its solution is at least (1-?) times the optimum. We conduct a comprehensive evaluation of ?-Filtering against state-of-the-art competitors on two real-world public datasets. Experiments show that ?-Filtering achieves the desired levels of effectiveness with a speedup of up to two orders of magnitude with respect to the optimal solution while guaranteeing very small approximation errors.DOI: 10.1145/3331184.3331227
Project(s): BigDataGrapes
Metrics:
Nardini Fm, Trani R, Venturini R
Several Web search services enable their users with the possibility of sorting the list of results by a specific attribute, e.g., sort "by price" in e-commerce. However, sorting the results by attribute could bring marginally relevant results in the top positions thus leading to a poor user experience. This motivates the definition of the relevance-aware filtering problem. This problem asks to remove results from the attribute-sorted list to maximize its final overall relevance. Recently, an optimal solution to this problem has been proposed. However, it has strong limitations in the Web scenario due to its high computational cost. In this paper, we propose ?-Filtering: an efficient approximate algorithm with strong approximation guarantees on the relevance of the final list. More precisely, given an allowed approximation error ?, the proposed algorithm finds a(1-?)"optimal filtering, i.e., the relevance of its solution is at least (1-?) times the optimum. We conduct a comprehensive evaluation of ?-Filtering against state-of-the-art competitors on two real-world public datasets. Experiments show that ?-Filtering achieves the desired levels of effectiveness with a speedup of up to two orders of magnitude with respect to the optimal solution while guaranteeing very small approximation errors.DOI: 10.1145/3331184.3331227
Project(s): BigDataGrapes
Metrics:
See at:
dl.acm.org | CNR IRIS | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2019
Journal article
Open Access
On optimally partitioning variable-byte codes
Pibiri Ge, Venturini R
The ubiquitous Variable-Byte encoding is one of the fastest compressed representation for integer sequences. However, its compression ratio is usually not competitive with other more sophisticated encoders, especially when the integers to be compressed are small that is the typical case for inverted indexes. This paper shows that the compression ratio of Variable-Byte can be improved by 2× by adopting a partitioned representation of the inverted lists. This makes Variable-Byte surprisingly competitive in space with the best bit-aligned encoders, hence disproving the folklore belief that Variable-Byte is space-inefficient for inverted index compression. Despite the significant space savings, we show that our optimization almost comes for free, given that: we introduce an optimal partitioning algorithm that does not affect indexing time because of its linear-time complexity; we show that the query processing speed of Variable-Byte is preserved, with an extensive experimental analysis and comparison with several other state-of-the-art encoders.Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (PRINT), vol. 32 (issue 9), pp. 1812-1823
DOI: 10.1109/tkde.2019.2911288
DOI: 10.48550/arxiv.1804.10949
Project(s): BigDataGrapes
Metrics:
Pibiri Ge, Venturini R
The ubiquitous Variable-Byte encoding is one of the fastest compressed representation for integer sequences. However, its compression ratio is usually not competitive with other more sophisticated encoders, especially when the integers to be compressed are small that is the typical case for inverted indexes. This paper shows that the compression ratio of Variable-Byte can be improved by 2× by adopting a partitioned representation of the inverted lists. This makes Variable-Byte surprisingly competitive in space with the best bit-aligned encoders, hence disproving the folklore belief that Variable-Byte is space-inefficient for inverted index compression. Despite the significant space savings, we show that our optimization almost comes for free, given that: we introduce an optimal partitioning algorithm that does not affect indexing time because of its linear-time complexity; we show that the query processing speed of Variable-Byte is preserved, with an extensive experimental analysis and comparison with several other state-of-the-art encoders.Source: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING (PRINT), vol. 32 (issue 9), pp. 1812-1823
DOI: 10.1109/tkde.2019.2911288
DOI: 10.48550/arxiv.1804.10949
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | IEEE Transactions on Knowledge and Data Engineering | CNR IRIS | ieeexplore.ieee.org | ISTI Repository | IEEE Transactions on Knowledge and Data Engineering | doi.org | CNR IRIS | CNR IRIS
2018
Conference article
Open Access
Efficient and effective query expansion for web search
Lucchese C, Nardini F M, Perego R, Trani R, Venturini R
Query Expansion (QE) techniques expand the user queries with additional terms, e.g., synonyms and acronyms, to enhance the system recall. State-of-the-art solutions employ machine learning methods to select the most suitable terms. However, most of them neglect the cost of processing the expanded queries, thus selecting effective, yet very expensive, terms. The goal of this paper is to enable QE in scenarios with tight time constraints proposing a QE framework based on structured queries and efficiency-aware term selection strategies. In particular, the proposed expansion selection strategies aim at capturing the efficiency and the effectiveness of the expansion candidates, as well as the dependencies among them. We evaluate our proposals by conducting an extensive experimental assessment on real-world search engine data and public TREC data. Results confirm that our approach leads to a remarkable efficiency improvement w.r.t. the state-of-the-art: a reduction of the retrieval time up to 30 times, with only a small loss of effectiveness.DOI: 10.1145/3269206.3269305
DOI: 10.5281/zenodo.2668248
DOI: 10.5281/zenodo.2668249
Project(s): BigDataGrapes
Metrics:
Lucchese C, Nardini F M, Perego R, Trani R, Venturini R
Query Expansion (QE) techniques expand the user queries with additional terms, e.g., synonyms and acronyms, to enhance the system recall. State-of-the-art solutions employ machine learning methods to select the most suitable terms. However, most of them neglect the cost of processing the expanded queries, thus selecting effective, yet very expensive, terms. The goal of this paper is to enable QE in scenarios with tight time constraints proposing a QE framework based on structured queries and efficiency-aware term selection strategies. In particular, the proposed expansion selection strategies aim at capturing the efficiency and the effectiveness of the expansion candidates, as well as the dependencies among them. We evaluate our proposals by conducting an extensive experimental assessment on real-world search engine data and public TREC data. Results confirm that our approach leads to a remarkable efficiency improvement w.r.t. the state-of-the-art: a reduction of the retrieval time up to 30 times, with only a small loss of effectiveness.DOI: 10.1145/3269206.3269305
DOI: 10.5281/zenodo.2668248
DOI: 10.5281/zenodo.2668249
Project(s): BigDataGrapes
Metrics:
See at:
dl.acm.org | ZENODO | ZENODO | CNR IRIS | ISTI Repository | zenodo.org | zenodo.org | doi.org | CNR IRIS | CNR IRIS
2018
Contribution to book
Open Access
Inverted Index Compression
Pibiri Ge, Venturini R
The data structure at the core of nowadays large-scale search engines, social networks and storage architectures is the inverted index, which can be regarded as being a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by search engines and stringent performance requirements dictated by the heavy load of user queries, the inverted lists often store several million (even billion) of integers and must be searched efficiently. In this scenario, compressing the inverted lists of the index appears as a mandatory design phase since it can introduce a twofold advantage over a non-compressed representation: feed faster memory levels with more data in order to speed up the query processing algorithms and reduce the number of storage machines needed to host the whole index. The scope of the chapter is the one of surveying the most important encoding algorithms developed for efficient inverted index compression.DOI: 10.1007/978-3-319-63962-8_52-1
DOI: 10.1007/978-3-319-77525-8_52
Metrics:
Pibiri Ge, Venturini R
The data structure at the core of nowadays large-scale search engines, social networks and storage architectures is the inverted index, which can be regarded as being a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by search engines and stringent performance requirements dictated by the heavy load of user queries, the inverted lists often store several million (even billion) of integers and must be searched efficiently. In this scenario, compressing the inverted lists of the index appears as a mandatory design phase since it can introduce a twofold advantage over a non-compressed representation: feed faster memory levels with more data in order to speed up the query processing algorithms and reduce the number of storage machines needed to host the whole index. The scope of the chapter is the one of surveying the most important encoding algorithms developed for efficient inverted index compression.DOI: 10.1007/978-3-319-63962-8_52-1
DOI: 10.1007/978-3-319-77525-8_52
Metrics:
See at:
CNR IRIS | ISTI Repository | CNR IRIS | CNR IRIS | link.springer.com | link.springer.com
2017
Conference article
Restricted
Multicore/Manycore parallel traversal of large forests of regression trees
Lettich F, Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of binary regression trees are currently considered one of the best solutions to address complex classification, regression, and ranking tasks. To evaluate these complex models over a continuous stream of data items with high throughput requirements, we need to optimize, and possibly parallelize, the traversal of thousands of trees, each including hundreds of nodes.Document ranking in Web Search is a typical example of this challenging scenario, where complex tree-based models are used to score query-document pairs and finally rank lists of document results for each incoming query (a.k.a. Learning-to-Rank). In this extended abstract, we briefly discuss some preliminary results concerning the parallelization strategies for QUICKSCORER - indeed the state-of-art scoring algorithm that exploits ensembles of decision trees - by using multicore CPUs (with SIMD coprocessors) and manycore GPUs. We show that QUICKSCORER, which transforms the traversal of thousands of decision trees in a linear access to array data structures, can be parallelized very effectively, by achieving very interesting speedups.DOI: 10.1109/hpcs.2017.154
Metrics:
Lettich F, Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of binary regression trees are currently considered one of the best solutions to address complex classification, regression, and ranking tasks. To evaluate these complex models over a continuous stream of data items with high throughput requirements, we need to optimize, and possibly parallelize, the traversal of thousands of trees, each including hundreds of nodes.Document ranking in Web Search is a typical example of this challenging scenario, where complex tree-based models are used to score query-document pairs and finally rank lists of document results for each incoming query (a.k.a. Learning-to-Rank). In this extended abstract, we briefly discuss some preliminary results concerning the parallelization strategies for QUICKSCORER - indeed the state-of-art scoring algorithm that exploits ensembles of decision trees - by using multicore CPUs (with SIMD coprocessors) and manycore GPUs. We show that QUICKSCORER, which transforms the traversal of thousands of decision trees in a linear access to array data structures, can be parallelized very effectively, by achieving very interesting speedups.DOI: 10.1109/hpcs.2017.154
Metrics:
See at:
doi.org | CNR IRIS | ieeexplore.ieee.org | CNR IRIS
2017
Conference article
Open Access
QuickScorer: efficient traversal of large ensembles of decision trees
Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of binary regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. Evaluating these models is a computationally demanding task as it needs to traverse thousands of trees with hundreds of nodes each. The cost of traversing such large forests of trees significantly impacts their application to big and stream input data, when the time budget available for each prediction is limited to guarantee a given processing throughput. Document ranking in Web search is a typical example of this challenging scenario, where the exploitation of tree-based models to score query-document pairs, and finally rank lists of documents for each incoming query, is the state-of-art method for ranking (a.k.a. Learning-to-Rank). This paper presents QuickScorer, a novel algorithm for the traversal of huge decision trees ensembles that, thanks to a cache- and CPU-aware design, provides a 9 speedup over best competitors.DOI: 10.1007/978-3-319-71273-4_36
Metrics:
Lucchese C, Nardini Fm, Orlando S, Perego R, Tonellotto N, Venturini R
Machine-learnt models based on additive ensembles of binary regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. Evaluating these models is a computationally demanding task as it needs to traverse thousands of trees with hundreds of nodes each. The cost of traversing such large forests of trees significantly impacts their application to big and stream input data, when the time budget available for each prediction is limited to guarantee a given processing throughput. Document ranking in Web search is a typical example of this challenging scenario, where the exploitation of tree-based models to score query-document pairs, and finally rank lists of documents for each incoming query, is the state-of-art method for ranking (a.k.a. Learning-to-Rank). This paper presents QuickScorer, a novel algorithm for the traversal of huge decision trees ensembles that, thanks to a cache- and CPU-aware design, provides a 9 speedup over best competitors.DOI: 10.1007/978-3-319-71273-4_36
Metrics:
See at:
arpi.unipi.it | doi.org | CNR IRIS | CNR IRIS | link.springer.com
2017
Journal article
Open Access
Clustered Elias-Fano Indexes
Pibiri Ge, Venturini R
In this article, we propose a new index representation based on clustering the collection of posting lists and, for each created cluster, building an ad hoc reference list with respect to which all lists in the cluster are encoded with Elias-Fano. We describe a posting lists clustering algorithm tailored for our encoder and two methods for building the reference list for a cluster. Both approaches are heuristic and differ in the way postings are added to the reference list: according to their frequency in the cluster or according to the number of bits necessary for their representation.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 36 (issue 1)
DOI: 10.1145/3052773
Project(s): SoBigData
Metrics:
Pibiri Ge, Venturini R
In this article, we propose a new index representation based on clustering the collection of posting lists and, for each created cluster, building an ad hoc reference list with respect to which all lists in the cluster are encoded with Elias-Fano. We describe a posting lists clustering algorithm tailored for our encoder and two methods for building the reference list for a cluster. Both approaches are heuristic and differ in the way postings are added to the reference list: according to their frequency in the cluster or according to the number of bits necessary for their representation.Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 36 (issue 1)
DOI: 10.1145/3052773
Project(s): SoBigData
Metrics:
See at:
ACM Transactions on Information Systems | dl.acm.org | CNR IRIS | ISTI Repository | ACM Transactions on Information Systems | CNR IRIS | CNR IRIS