Algorithms on Evolving Data

In many real-world applications, an algorithmic problems need to be solved on input data sets that are constantly changing. For example, search engines need to find a ranking of web-pages based on a changing web-graph. We formulate and study a new stochastic model for computation on evolving data sets. In this framework the input data changes gradually over time and the algorithm can only track these changes by probing the data set. The goal is to maintain an output that is close to the correct output with a limit on the number of probes. We apply this framework to the problems of sorting and selection as well as the problem of community detection in networks, and obtain close-to-optimal algorithms in each case.