Dynamic Skyline Path Query Method Over Multi-attribute Temporal Graphs

In recent years,with the rapid development of the Internet,research on graphs has become increasingly widespread.Path research on graphs has always been a hot topic,and for static graph path queries,there are many mature algorithms and data structures that can find the shortest path.However,these algorithms ignore the time factor and are limited in application.As for path queries on temporal graphs,it mainly involves problems such as earliest arrival time,shortest path,and latest departure time path,etc.Research in this area mainly focuses on single-constraint paths,ignoring the case of multi-constraint conditions,which cannot meet the diverse query needs of users.In order to solve the optimal path query problem with multiple constraints,scholars have proposed the skyline path query problem.skyline path query is a method of querying multiple optimal paths,which is an extension of skyline query.skyline path query has been widely used in web-based applications,such as traffic network,map search,etc.However,current skyline path queries mainly focus on multi constraint path queries on static graphs,without considering path queries on temporal graphs.In addition,existing skyline path query methods can only query for quantifiable elements and cannot meet the personalized needs of users.In response to the problems and challenges in path queries mentioned above,this paper proposes a skyline path query problem over multi-attribute temporal graphs.To solve this problem,this paper designs an index called Main Point(MP)and a query algorithm based on this index.At the same time,considering the dynamic changes in the temporal graph,this paper also proposes the skyline path query problem over the globally updated temporal graphs,and solves this problem by utilizing the dynamic update of MP index and the partition based skyline path query index.The main research content and innovations of the paper are as follows:(1)In order to solve the problem of single-constraint and cannot meet the diverse query needs of users in traditional path research,this paper proposes a multi-attribute skyline path query problem based on temporal graphs.This problem considers multiconstraint conditions and time factors and can meet the personalized needs of users.To solve this problem,we first construct an index called MP,which is divided into two stages: MP node search and Mout set construction.Based on this index,we propose an efficient algorithm for skyline path query on multi-attribute temporal graphs.(2)Considering that the temporal graph will change with time,we also propose a skyline path query problem on temporal graphs based on global updates.To solve this problem,we use the dynamic update of the MP index to incrementally calculate the optimal skyline path and use the sliding window and skyline path query index based on partition to perform the query.The sliding window is used to update and maintain data in real-time,and the skyline path query index based on partition is used to calculate the optimal skyline path of the current window,mainly including spatial partitioning,data mapping,partial relationship dominance tree,and dominance relationship calculation stages.(3)This paper conducts multiple comparative algorithm experiments on multiple real and synthetic datasets,and the experimental results show that the algorithm proposed in this paper has better performance and can respond to user query needs faster,which proves the effectiveness and feasibility of the algorithm.