2011
Report
Unknown
A1.1.1 Lo stato dell'arte: tecnologia ed utenti
Falchi Fabrizio, Ippolito Valentina, Loschiavo Domenico, Lucchese Claudio, Lungarotti Francesca, Melani, Alessio, Minelli, Sam, Pialli Saverio, Rossi Silvia, Salvadori Sauro, Scartoni Rita, Scopigno Roberto, Tavanti Francesca, La Torre Francesco, Venturini Rossano
This document reports the state of the art related to the technologies of interest of the VISITO Tuscany projectSource: Project report, VISITO Tuscany, 2011
Falchi Fabrizio, Ippolito Valentina, Loschiavo Domenico, Lucchese Claudio, Lungarotti Francesca, Melani, Alessio, Minelli, Sam, Pialli Saverio, Rossi Silvia, Salvadori Sauro, Scartoni Rita, Scopigno Roberto, Tavanti Francesca, La Torre Francesco, Venturini Rossano
This document reports the state of the art related to the technologies of interest of the VISITO Tuscany projectSource: Project report, VISITO Tuscany, 2011
See at: CNR ExploRA
2011
Report
Unknown
Componente per la creazione di suggerimenti da comportamenti collettivi
Lucchese C., Venturini R.
The document presents our system of suggestion of point of interests that has been developed within the Visito Tuscany project. -Progetto: VIsual Support to Interactive TOurism in Tuscany -Acronimo: VISITO Tuscany -Grant agreement: D57E09000050007Source: Project report, VISITO Tuscany, 2011
Lucchese C., Venturini R.
The document presents our system of suggestion of point of interests that has been developed within the Visito Tuscany project. -Progetto: VIsual Support to Interactive TOurism in Tuscany -Acronimo: VISITO Tuscany -Grant agreement: D57E09000050007Source: Project report, VISITO Tuscany, 2011
See at: CNR ExploRA
2011
Report
Unknown
VISITO Tuscany - Progetto dell'architettura della piattaforma VISITO Tuscany
Atzori M., Bazzoni G., Bolettieri P., La Torre F., Loschiavo D., Lucchese C., Manfrin S., Martinelli F., Melani A., Naldi C., Pironi A., Rubichi A., Venturini R., Zanetti N.
Il documento è inquadrato nell'Obiettivo Operativo 2 del Progetto VISITO Tuscany, nel quale viene elaborata la progettazione dell'intero sistema. In particolare in questo documento verrà descritta l'architettura del sistema sulla base del Reference Model for Open Distributed Processing (RM-ODP) che prevede cinque viste: enterprise, information, computational, engineering e technology.Source: Project report, VISITO Tuscany, 2011
Atzori M., Bazzoni G., Bolettieri P., La Torre F., Loschiavo D., Lucchese C., Manfrin S., Martinelli F., Melani A., Naldi C., Pironi A., Rubichi A., Venturini R., Zanetti N.
Il documento è inquadrato nell'Obiettivo Operativo 2 del Progetto VISITO Tuscany, nel quale viene elaborata la progettazione dell'intero sistema. In particolare in questo documento verrà descritta l'architettura del sistema sulla base del Reference Model for Open Distributed Processing (RM-ODP) che prevede cinque viste: enterprise, information, computational, engineering e technology.Source: Project report, VISITO Tuscany, 2011
See at: CNR ExploRA
2011
Conference article
Open Access
Distribution-aware compressed full-text indexes
Ferragina P., Sirén, J., Venturini R.
In this paper we address the problem of building a compressed self-index that, given a distribution for the pattern queries and a bound on the space occupancy, minimizes the expected query-time within that index-space bound. We solve this problem by exploiting a reduction to the problem of finding a minimum weight K-link path in a particular Directed Acyclic Graph. Interestingly enough, our solution is independent of the underlying compressed index in use. Our experiments compare this optimal strategy with several other standard approaches, showing its effectiveness in practice.Source: Algorithms - ESA 2011. 19th Annual European Symposium, pp. 760–771, Saarbrucken, Germany, 5-9 September 2011
DOI: 10.1007/978-3-642-23719-5_64
DOI: 10.1007/s00453-013-9782-3
Project(s): MIDAS
Metrics:
Ferragina P., Sirén, J., Venturini R.
In this paper we address the problem of building a compressed self-index that, given a distribution for the pattern queries and a bound on the space occupancy, minimizes the expected query-time within that index-space bound. We solve this problem by exploiting a reduction to the problem of finding a minimum weight K-link path in a particular Directed Acyclic Graph. Interestingly enough, our solution is independent of the underlying compressed index in use. Our experiments compare this optimal strategy with several other standard approaches, showing its effectiveness in practice.Source: Algorithms - ESA 2011. 19th Annual European Symposium, pp. 760–771, Saarbrucken, Germany, 5-9 September 2011
DOI: 10.1007/978-3-642-23719-5_64
DOI: 10.1007/s00453-013-9782-3
Project(s): MIDAS
Metrics:
See at:
HELDA - Digital Repository of the University of Helsinki 
| Algorithmica | doi.org 
| Algorithmica | www.springerlink.com | CNR ExploRA
2011
Conference article
Restricted
Space-efficient substring occurrence estimation
Orlandi Alessio, Venturini Rossano
We study the problem of estimating the number of occurrences of substrings in textual data: A text T on some alphabet Sigma of size sigma is preprocessed and an index I is built. The index is used in lieu of the text to answer queries of the form CountH(P), returning an approximated number of the occurrences of an arbitrary pattern P as a substring of T. The problem has its main application in selectivity estimation related to the LIKE predicate in textual databases. Our focus is on obtaining an algorithmic solution with guaranteed error rates and small footprint. To achieve that, we first enrich previous work in the area of compressed text-indexing providing an optimal data structure that requires (|T|log sigma/l) bits where l e 1 is the additive error on any answer. We also approach the issue of guaranteeing exact answers for sufficiently frequent patterns, providing a data structure whose size scales with the amount of such patterns. Our theoretical findings are sustained by experiments showing the practical impact of our data structures.Source: 30th symposium on Principles of Database Systems of Data, PODS 2011, pp. 95–106, Athens, Greece, 12-16 June 2011
DOI: 10.1145/1989284.1989300
DOI: 10.1007/s00453-014-9936-y
Metrics:
Orlandi Alessio, Venturini Rossano
We study the problem of estimating the number of occurrences of substrings in textual data: A text T on some alphabet Sigma of size sigma is preprocessed and an index I is built. The index is used in lieu of the text to answer queries of the form CountH(P), returning an approximated number of the occurrences of an arbitrary pattern P as a substring of T. The problem has its main application in selectivity estimation related to the LIKE predicate in textual databases. Our focus is on obtaining an algorithmic solution with guaranteed error rates and small footprint. To achieve that, we first enrich previous work in the area of compressed text-indexing providing an optimal data structure that requires (|T|log sigma/l) bits where l e 1 is the additive error on any answer. We also approach the issue of guaranteeing exact answers for sufficiently frequent patterns, providing a data structure whose size scales with the amount of such patterns. Our theoretical findings are sustained by experiments showing the practical impact of our data structures.Source: 30th symposium on Principles of Database Systems of Data, PODS 2011, pp. 95–106, Athens, Greece, 12-16 June 2011
DOI: 10.1145/1989284.1989300
DOI: 10.1007/s00453-014-9936-y
Metrics:
See at:
Algorithmica | doi.org | portal.acm.org | CNR ExploRA
2011
Contribution to conference
Open Access
Recommendations for the long tail by Term-Query Graph
Bonchi F., Perego R., Silvestri F., Vahabi H., Venturini R.
We define a new approach to the query recommendation problem. In particular, our main goal is to design a model enabling the generation of query suggestions also for rare and previously unseen queries. In other words we are targeting queries in the long tail. The model is based on a graph having two sets of nodes: Term nodes, and Query nodes. The graph induces a Markov chain on which a generic random walker starts from a subset of Term nodes, moves along Query nodes, and restarts (with a given probability) only from the same initial subset of Term nodes. Computing the stationary distribution of such a Markov chain is equivalent to extracting the so-called Center-piece Subgraph from the graph associated with the Markov chain itself. Given a query, we extract its terms and we set the restart subset to this term set. Therefore, we do not require a query to have been previously observed for the recommending model to be able to generate suggestions.Source: 20th international conference companion on World Wide Web, WWW'11, pp. 15–16, Hyderabad, India, 28 March - 1 April 2011
DOI: 10.1145/1963192.1963201
Metrics:
Bonchi F., Perego R., Silvestri F., Vahabi H., Venturini R.
We define a new approach to the query recommendation problem. In particular, our main goal is to design a model enabling the generation of query suggestions also for rare and previously unseen queries. In other words we are targeting queries in the long tail. The model is based on a graph having two sets of nodes: Term nodes, and Query nodes. The graph induces a Markov chain on which a generic random walker starts from a subset of Term nodes, moves along Query nodes, and restarts (with a given probability) only from the same initial subset of Term nodes. Computing the stationary distribution of such a Markov chain is equivalent to extracting the so-called Center-piece Subgraph from the graph associated with the Markov chain itself. Given a query, we extract its terms and we set the restart subset to this term set. Therefore, we do not require a query to have been previously observed for the recommending model to be able to generate suggestions.Source: 20th international conference companion on World Wide Web, WWW'11, pp. 15–16, Hyderabad, India, 28 March - 1 April 2011
DOI: 10.1145/1963192.1963201
Metrics:
See at:
hpc.isti.cnr.it | dl.acm.org | doi.org | CNR ExploRA
2011
Journal article
Open Access
On optimally partitioning a text to improve its compression
Ferragina P., Nitto I., Venturini R.
In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in Buchsbaum et al. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina et al. (J. ACM 52:688-713, 2005; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184-193, 2005) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum et al. in J. ACM 50(6):825-851, 2003; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp. 129-143, 2003), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum et al. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina et al. in J. ACM 52:688-713, 2005; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log n/log log n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939-942, 2008). In this paper we provide the first algorithm which computes in O(nlog 1+ε n) time and O(n) space, a partition of T whose compressed output is guaranteeSource: Algorithmica 61 (2011): 51–74. doi:10.1007/s00453-010-9437-6
DOI: 10.1007/s00453-010-9437-6
DOI: 10.48550/arxiv.0906.4692
DOI: 10.1007/978-3-642-04128-0_38
Metrics:
Ferragina P., Nitto I., Venturini R.
In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in Buchsbaum et al. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina et al. (J. ACM 52:688-713, 2005; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184-193, 2005) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum et al. in J. ACM 50(6):825-851, 2003; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp. 129-143, 2003), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum et al. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina et al. in J. ACM 52:688-713, 2005; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log n/log log n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939-942, 2008). In this paper we provide the first algorithm which computes in O(nlog 1+ε n) time and O(n) space, a partition of T whose compressed output is guaranteeSource: Algorithmica 61 (2011): 51–74. doi:10.1007/s00453-010-9437-6
DOI: 10.1007/s00453-010-9437-6
DOI: 10.48550/arxiv.0906.4692
DOI: 10.1007/978-3-642-04128-0_38
Metrics:
See at:
arXiv.org e-Print Archive | Algorithmica | doi.org | Algorithmica | doi.org | www.springerlink.com | CNR ExploRA