UROP Proceedings 2020-21

School of Engineering Department of Computer Science and Engineering 144 Efficient Queries over Database Supervisor: WONG Raymond Chi Wing / CSE Student: PATUPAT Albert John Lalim / DSCT Course: UROP1100, Fall Personalized PageRank (PPR) - also known as Random Walk with Restart - is one of the most deeply studied node proximity measures in the graph data mining community. Specifically, for frequently-evolving graphs, it is typically required to recompute PPR values which immediately reflect changes, and hence, lightweight index-free approximate algorithms are preferred for this use case. The state-of-the-art approach FORA achieves both efficiency and theoretical guarantees, but its theoretical analysis and implementation details show room for improvement. Thus, this study implemented the proposed algorithm in the recent theoretical analysis improving FORA. Results of rigorous testing show that the proposed algorithm is consistently faster than FORA and other state-of-the-art algorithms. For future work, this study could motivate faster FORA-like algorithms for PPR-related queries. Efficient Queries over Database Supervisor: WONG Raymond Chi Wing / CSE Student: LIU Zichen / DSCT Course: UROP1100, Spring There are various types of queries over database, and they play an important role in many areas nowadays. However, these queries usually turn out to be NP-hard, and the exact algorithms are sophisticated. This project mainly focusing on the following 3 cases: queries of the fastest path over a dynamic network; queries associated with spatial keywords; queries about spatial crowdsourcing and ridesharing. This semester, the project mainly focused on understanding relevant areas and the classic algorithms. Learning how to efficiently solve a query problem with good approximate algorithms is the first step of the research. The report will show the progress. Efficient Queries over Database Supervisor: WONG Raymond Chi Wing / CSE Student: ORAZALIN Alibek / MATH-CS Course: UROP2100, Spring Given a directed weighted graph G, our aim is to answer the shortest distance, path queries by also permitting updates on the weights of edges. This problem, of course, has many applications such as finding shortest distance between two points in a map where weight of the edge or the time to pass a portion of the road changes (due to various reasons, such as weather conditions, traffic jams and accidents); finding the most optimal transaction between currencies (by considering logarithms of ratios). This abstract summarizes the progress on optimizing the study of fast path and distance queries on a dynamic spatial network.