Efficient Filtering in Micro-blogging Systems: We Won't Get Flooded Again

In the last years, micro-blogging systems have encountered a large success. Twitter for instance claims more than 200 million accounts after 5 years of existence with more than 200 million tweets a day leading to 350 billion delivered tweets. Micro-blogging systems rely on the all-or-nothing paradigm: a user receives all the posts from an account s/he follows. A consequence for a user isthe risk of flooding, i.e., the number of posts received from all the accounts s/he follows implies a time-consuming scan of his list of postings to read news that match his interests. Meanwhile these systems receive all posts and deliver each of them to all the followers of the publishing accounts, whether they are interested by the news or not. To avoid user flooding and to significantly diminish the number of posts to be delivered, we propose in this paper three filtering structures for micro-blogging systems. They allow to efficiently retrieve the followers of an account that could be interested by a post s/he published. We compare analytically these structures and confirm our analysis experimentally on synthetical datasets and on a real Twitter dataset which consists of more than 2.1 million users, 15.7 million tweets and 148.5 million publisher-follower relationships