Monthly Archives: October 2011

SIGMOD 2011: A memory efficient reachability data structure through bit vector compression

During the last year of my Utrecht master’s degree, I worked on a research project at the University of Oxford with Prof. Oege de Moor: reachability queries on large directed graphs. This work eventually led to a paper at ACM SIGMOD 2011, one of the largest international conferences on management of data. In this post, I will endeavour to convey the intuition behind our approach: bit vector compression using a specially designed scheme called PWAH.
Continue reading