基于Flink的k-支配skyline体并行求解算法

A k-dominant skyline body parallel solving algorithm based on Flink

k-支配skyline算法弱化了数据点之间的支配关系,更适合高维数据。k-支配skyline体适应于多名用户使用k-支配skyline算法查询,而现有的求解算法在时间效率和代码扩展性方面都有待提高。因此,提出了面向多用户的k-支配skyline体求解优化算法MKSSOA,该算法对每名用户的候选集和中间集分别进行存储,同时在k-支配检查过程中利用2集合中数据点出现的先后次序将候选集中的非k-支配skyline点存储到对应用户的中间集中,以便下一名用户筛选使用,这样可以减少数据点之间的比较次数,避免重复计算,从而提升查询效率。同时,提出了面向多用户的k-支配skyline体并行求解算法MKSPSA,通过Apache Flink并行处理框架有效减少了数据点的比较时间。理论研究和实验结果显示,提出的算法具有较高的效率,能很好地处理多用户k-支配skyline问题。

The k-dominated skyline algorithm weakens the domination relationship between data points and is more suitable for high-dimensional data.k-dominated skyline bodies are suitable for multiple users to query with the k-dominated skyline algorithm,but the existing solution algorithms need to be improved in terms of time efficiency and code scalability.Therefore,this paper proposes an optimization algorithm for solving k-dominated skyline bodies.This algorithm stores the candidate set and the intermediate set for each user separately,and stores the non-k-dominated skyline points in the candidate set to the intermediate set of the corresponding user in the order of appearance of data points in the two sets during the k-domination checking process,so that the next user can filter and use them,which can reduce the number of comparisons between data points,avoids double counting,and improve query efficiency.A multi-user k-dominated skyline body parallel solving algorithm is also proposed,which effectively reduces the comparison time of data points through the Apache Flink parallel processing framework.The theoretical study and experimental data show that the proposed algorithm is highly efficient and can handle the multi-user k-dominated skyline problem well.