School of Engineering Department of Computer Science and Engineering 128 Efficient Queries over Database Supervisor: WONG Raymond Chi Wing / CSE Student: SHU Tian / DSCT Course: UROP1100, Summer The shortest path query is a fundamental problem in spatial networks and is applied in various database and data mining algorithms. As related algorithms often involve frequent queries of the shortest path or distance between two given vertices, a type of data structure called distance oracle is established to store preprocessed information and perform efficient computations of such queries. Literature [1] proposed an efficient distance and path oracle on dynamic road networks named Update Efficient (UE). The oracle employs a randomization technique and supports efficient maintenance of weight updates. This report will briefly introduce some essentials of UE, propose a more efficient update algorithm inspired by literature [2], and provide an analysis of update time complexity with a smaller constant. [1] Victor Junqiu Wei, Raymond Chi-Wing Wong, and Cheng Long. Architecture-intact oracle for fastest path and time queries on dynamic spatial networks. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 1841-1856, New York, NY, USA, 2020. Association for Computing Machinery. [2] Dian Ouyang, Long Yuan, Lu Qin, Lijun Chang, Ying Zhang, and Xuemin Lin. Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proc. VLDB Endow., 13(5):602-615, jan 2020. Knowledge Discovery over Database Supervisor: WONG Raymond Chi Wing / CSE Student: LU Weiqi / COSC SU Hong / DSCT Course: UROP2100, Summer UROP2100, Spring UROP3100, Summer Co-location patterns and Causality are two well studied fields nowadays. The problem of mining causalities among co-location patterns is an important primitive in knowledge discovery, with wideranging applications from ecosystem to praxiology and epidemiology. However, there are still some limitations in solving the above problem. Many causality mining models lack full utilization of the temporal dimension. And one major challenge of Granger causality test is that it only guarantees the cause precedes the effect in time. To tackle these limitations, this report proposes a novel and scalable model for mining causality from co-location patterns based on Granger causality and designs an algorithm for approximating direct causes from Granger causes based on unique causal information. And extensive experiments are conducted on real-world datasets to evaluate our result and compare it with others.
RkJQdWJsaXNoZXIy NDk5Njg=