CNR Author
operator:
and / or
Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2020
Journal article
Open Access
Practical trade-offs for the prefix-sum problem
Pibiri Ge, Venturini R
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.Source: SOFTWARE-PRACTICE & EXPERIENCE
DOI: 10.1002/spe.2918
DOI: 10.48550/arxiv.2006.14552
Project(s): BigDataGrapes
Metrics:
Pibiri Ge, Venturini R
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.Source: SOFTWARE-PRACTICE & EXPERIENCE
DOI: 10.1002/spe.2918
DOI: 10.48550/arxiv.2006.14552
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive 
| Software Practice and Experience | CNR IRIS | onlinelibrary.wiley.com | Software Practice and Experience 
| doi.org | CNR IRIS
2020
Journal article
Open Access
Techniques for inverted index compression
Pibiri Ge, Venturini R
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.Source: ACM COMPUTING SURVEYS, vol. 53 (issue 6)
DOI: 10.1145/3415148
DOI: 10.48550/arxiv.1908.10598
Project(s): BigDataGrapes
Metrics:
Pibiri Ge, Venturini R
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.Source: ACM COMPUTING SURVEYS, vol. 53 (issue 6)
DOI: 10.1145/3415148
DOI: 10.48550/arxiv.1908.10598
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | ACM Computing Surveys | dl.acm.org | CNR IRIS | ISTI Repository | ACM Computing Surveys | doi.org | 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