Brown CS Blog

Professor Eli Upfal’s Research Group Publishes Three Papers

    Three papers from Professor Eli Upfal’s research group were recently accepted to Knowledge Discovery and Data Science (KDD’16), a top-tier conference in the Big Data research community. A total of 784 papers were submitted to the conference, of which 70 were accepted as full papers and 72 were accepted as poster papers. Eli’s group had two full papers and one poster paper accepted, which is a major achievement.

    TRIEST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size was a joint publication between Lead Researcher and Brown University PhD Candidate Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli. The paper tackles the problem of triangle counting in large massive graph. Their work proposes a new algorithm based on adaptive sampling, which provides high quality approximations of the number of triangles in large networks with probabilistic guarantees.

    ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages was co-written by Lead Researcher and Visiting Assistant Professor Matteo Riondato and Eli. The algorithm, ABRA, uses progressive random sampling, which allows it to automatically determine when the obtained approximation has the required quality. In their experimental evaluation, ABRA proved to be much faster than existing state-of-the-art methods. (On September 9, Two Sigma published an online article on ABRA here.)

    The last paper, Scalable Betweenness Centrality Maximization via Sampling, was written by Lead Researcher and Brown CS PhD Candidate Ahmad Mahmoody, Charalampos Tsourakakis, and Eli. In their work, they considered an extension of the classic betweenness centrality problem, where the goal was to find the most central "group" of nodes of a given size. Their method improved the state of the art algorithm by using a more efficient sampling algorithm, and provided a better theoretical guarantee.

    “I think good team work is a great tool to both increase the quality of the work and maintain high motivation which is then bound to lead to good results,” says Lorenzo when asked why Eli’s research group was so successful in getting their work published. “A well-functioning research group offers the possibility of having other qualified people to bounce off ideas and challenge your understanding of topics. Further, it is a chance of learning new skills working alongside other talented and motivated people.”

    For more information, click the link that follows to contact Brown CS Communications Outreach Specialist Jesse C. Polhemus