Efficient Random Walk Based Query Processing on Massive Graphs

S. Wang

Random walk based queries on graphs find extensive applications in search engines, social recommendations, community detection, spam detections, and so on. In the era of big data, one big challenge is how to handle the random walk based queries efficiently and effectively since such queries are typically processed in large batches and a regular manner by many IT companies, like Twitter, Pinterest, and Tencent. This project aims to devise more efficient solutions for the random walk based queries by considering many aspects including developing new algorithms with improved time complexity, devising novel index structures with bounded space consumption, exploring new hardware or distributed computing, and considering new models of random walks for improved accuracy.