Lab of Advanced Algorithms and Applications

The Lab of Advanced Algorithms and Applications (A³, read "a-cube") is mainly devoted to the design, analysis and experimentation of algorithms and data structures for storing, compressing, mining and retrieving information from large amounts of textual data like Web repositories, XML file collections, textual databases, genomic/DNA sequences.


We are developing a new semantic-annotation technology for short textual fragments, called TAGME [ACM CIKM 2010, IEEE Software 2012]. This tool has been applied succesfully to many contexts concerning with the clustering, the classification and the similarity-comparison of short texts. We are also studying the design of of “Multi-objective” data compressor, a novel paradigm in which optimization techniques are plugged into the design of data compressors. For example, in the Bicriteria Data Compression ([ACM-SIAM SODA14], [ESA2014] to appear), the compressor solves the following problem: "return a compressed file which minimizes the compressed space provided that the decompression time is less than T". Similarly, the compressor can "return a compressed file which minimizes the decompression time provided that the compressed space is less than S bits". A third line of research is a classic one for our group lasting for 20 years now and regarding the design of compressed indexes for big data (such as String B-tree [JACM 1999] and FM-index [JACM 2005]). Recently we have designed cache-oblivious compressed version of those indexes for dictionaries of strings [ESA 2013], and distribution-ware compressed indexes for data collections [Algorithmica 2013].

Current Partnerships

  • Bassilichi
  • Cerved Group
  • Google (Zurich)
  • Yahoo! Research (Barcelona)
  • Net7
  • SpazioDati
  • Tiscali Italia

Current Grants

  • [2014] Yahoo! Faculty Research and Engagement Program 2014
  • [2013-2015] Regione Toscana, Net7, StudioFlu, SpazioDati
  • [2013-2014] Bassilichi
  • [2013-2014] Google Research Award
  • [2012-2014] Italian MIUR-PRIN Project "ARS-Technomedia"
  • [2011-2012] Telecom Italia Working Capital
  • [2010] Google Research Award
  • [2010-2012] Italian MIUR-PRIN Project "The Mad Web"
  • [2006-2011] Yahoo! Research
  • [2009-2012] Italian MIUR-FIRB Project "Linguistica"

Latest News

ICWSM 2015 accepted paper » May 23, 2015

We are glad to announce that our paper “On Analyzing Hashtags in Twitter” has been accepted at the 9th International AAAI Conference on Web and Social Media (ICWSM 2015).

In this paper we build a novel graph upon hashtags and (Wikipedia) entities (HE-Graph) and we exploit it to address two challenging problems regarding the “meaning of hashtags”: hashtags relatedness and hashtag classification.

We also constructed two datasets for hashtags relatedness and classification. We are happy to release them to the research community, together with the HE-graph we constructed (Hashtag Datasets).

WWW 2015 accepted papers » January 26, 2015

We announce that our papers “Compressed indexes for string-searching in labeled graphs” and “GERBIL – General Entity Annotator Benchmark” have been accepted at the 24th International World Wide Web Conference (WWW 2015) conference.

See you in Florence ;)

“Partitioned Elias-Fano Indexes” wins the SIGIR Best paper award » July 18, 2014

We are glad to announce that Giuseppe Ottaviano and Rossano Venturini’s “Partitioned Elias-Fano Indexes” won the SIGIR 2014 Best Paper Award. Here’s a link to the article.

Yahoo Faculty Research and Engagement Program award » July 18, 2014

We are happy to announce that Rossano Venturini has been awarded with a Yahoo Faculty Research and Engagement Program (FREP)The project involves the design and the experimentation of compressed data structures for indexing users’ personal collections of documents which grow and change frequently in the time.