NEWS

RIT Scientist Yusaku Kaneta attended the 26^th International Symposium on String Processing and Information Retrieval (SPIRE 2019) in Segovia, Spain from October 7-9. He presented “Fast Identification of Heavy Hitters by Cached and Packed Group Testing”, a research paper written in collaboration with Dr. Takaeaki Uno and Hiroki Arimura. At this year’s conference, both theoretical and practical aspects of data compression were discussed at great length. Professors Alistair Moffat, Veli Mäkinen, and Gonzalo Navarro were the invited speakers and highlighted most recent advances in the field.

Dr. Kaneta presented the analysis and findings from his research on the approximate heavy hitters problem, which has been extensively studied in the database and computer networking communities, in the strict turnstile model. This included two novel techniques, caching candidates and packing bidirectional counters, that improves a randomized data structure. Caching candidates improves the query time for arbitrary updates and the second technique of packing bidirectional counters improves the update time for constant updates.

Fast Identification of Heavy Hitters by Cached and Packed Group Testing from Rakuten, Inc.

We would like to extend our gratitude to the organizers, collaborators, sponsors, and attendees of Spire 2019.