基于时间条件提取序列的数据流偏好查询

doi:10.11772/j.issn.1001-9081.2021040786

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (3): 724-730.DOI: 10.11772/j.issn.1001-9081.2021040786

• 2021年中国计算机学会人工智能会议(CCFAI 2021) • 上一篇

基于时间条件提取序列的数据流偏好查询

李润泽, 孙雪姣()

烟台大学计算机与控制工程学院，山东烟台 264005

收稿日期:2021-05-14 修回日期:2021-06-02 接受日期:2021-06-24 发布日期:2021-11-09 出版日期:2022-03-10
通讯作者: 孙雪姣
作者简介:李润泽（1996—），男，河南焦作人，硕士研究生，主要研究方向：理论计算机科学、计算方法；
基金资助:
国家自然科学基金资助项目(62072392)

Data stream preference query based on extraction sequence according to temporal condition

Runze LI, Xuejiao SUN()

College of Computer and Control Engineering，Yantai university，Yantai Shandong 264005，China

Received:2021-05-14 Revised:2021-06-02 Accepted:2021-06-24 Online:2021-11-09 Published:2022-03-10
Contact: Xuejiao SUN
About author:LI Runze， born in 1996， M. S. candidate. His research interests include theoretical computer science， calculation method.
Supported by:
National Natural Science Foundation of China(62072392)

摘要/Abstract

摘要：

传统关于偏好推理、偏好查询的研究主要集中在对关系元组表示的单个对象的偏好上，而将时间条件偏好查询的方法扩展到数据流的提取序列中是一个挑战，遇到的问题主要包括对数据流中序列的提取、快速处理以得到占优序列和占优对象等。针对偏好数据流，首先，扩展了连续查询语言（CQL），提出专门为有效处理数据流上的时间条件偏好的查询语言StreamSeq，它允许对数据流中提取的序列进行时间条件偏好规范和推理；然后，设计了从数据流中按时间索引提取对象序列的算法和执行序列间占优对比的算法，根据输入的数据流返回满足偏好条件的占优序列；最后，使用两组数据集进行实验验证。在合成数据集上，当属性数、序列数、时间范围和时间滑动间隔为10、8、20 s、1 s时，提取序列算法和CQL等效算法的运行时间加速比为13.33；在真实数据集上，当时间范围和时间滑动间隔为40 s、1 s时，占优对比算法和mintopK、partition、incpartition的运行时间加速比为10.77、6.46、5.69。实验结果表明，与其他偏好查询算法相比，所提算法所需的运行时间少，得到结果的效率更高。

关键词: 偏好推理, 时间条件, 偏好查询, 连续查询语言, 提取序列, 占优对比

Abstract:

Traditional research on preference reasoning and preference query mainly focuses on the preference of a single object represented by a relational tuple. However， it is a challenge to extend the method of temporal conditional preference query to the extraction sequence of data stream. The problems encountered mainly include the extraction of sequences in data stream and the rapid processing to obtain the dominant sequences and dominant objects. According to the preference data stream， firstly， the Continuous Query Language （CQL） was extended and a special query language named StreamSeq was proposed to deal with the temporal conditional preference on the data stream effectively， which allows the temporal conditional preference specification and reasoning of the sequences extracted from the data stream. Then， an algorithm for extracting object sequences according to temporal index from data stream and an algorithm for performing dominant comparison between sequences were designed， and the dominant sequences satisfying preference condition were returned according to the input data stream. Finally， two sets of data were used for experimental verification. On the synthetic data set， when the number of generated attributes， sequence number， time range and time sliding interval were 10， 8， 20 s and 1 s， the running time acceleration ratio of sequence extraction algorithm and CQL equivalent algorithm was 13.33； on the real data set； when the time range and time sliding interval were 40 s and 1 s， the running time acceleration ratios of the dominant contrast algorithm to mintopK， partition， and incpartition were 10.77， 6.46 and 5.69. Experimental results show that compared with other preference query algorithms， the proposed method needs less running time and is more efficient in getting results.

Key words: preference reasoning, temporal condition, preference query, continuous query language, extraction sequence, dominant contrast

中图分类号:

TP391

李润泽, 孙雪姣. 基于时间条件提取序列的数据流偏好查询[J]. 计算机应用, 2022, 42(3): 724-730.

Runze LI, Xuejiao SUN. Data stream preference query based on extraction sequence according to temporal condition[J]. Journal of Computer Applications, 2022, 42(3): 724-730.

图/表 10

图1 运动员s的运动轨迹

Fig. 1 Trajectory of athlete s

图2 搜索树的查找过程

Fig. 2 Finding process of search tree

表1 合成数据生成参数

Tab. 1 Synthetic data generation parameters

参数	变量名	变量值	默认值
属性数	ATT	8， 10， 12， 14， 16	10
序列数	SEQ	4， 8， 16， 24， 32	8

表2 合成数据中用于提取序列的参数 (s)

Tab. 2 Parameters used to extract sequences in synthetic data

参数	变量名	变量值	默认值
时间范围	RAN	10， 20， 40， 60， 80， 100	20
时间滑动间隔	SLI	1， 10， 20， 30， 40	1

图3 合成数据中不同参数EXT sequences和CQL equivalent运行时间对比

Fig. 3 Comparison of time consumptions between EXT sequences and CQL equivalent with different parameters in synthetic data

表3 真实数据实验参数

Tab. 3 Experiment parameters of real data

属性	数量	时刻	属性	数量	时刻
比赛场次	64	64	动作	167 081	2 621
比赛队伍	32	32	移动方向	130 607	2 040
运动员	736	736	场上位置	137 621	2 150

表4 真实数据中用于提取序列的参数 (s)

Tab. 4 Parameters used to extract sequences in real data

参数	变量	默认值
时间范围	6， 12， 18， 24， 30	24
时间滑动间隔	1， 3， 6， 9， 12	1

图4 真实数据中不同参数EXT sequences和CQL equivalent运行时间对比

Fig. 4 Comparison of time consumptions between EXT sequences and CQL equivalent with different parameters in real data

表5 真实数据中用于占优对比的参数 (s)

Tab. 5 Parameters used to dominant contrast in real data

参数	变量	默认值
时间范围	5， 10， 20， 40， 80， 160	40
时间滑动间隔	1， 3， 6， 9， 12	1

图5 真实数据中不同参数连续查询算法运行时间对比

Fig. 5 Comparison of time consumptions among continuous query algorithms with different parameters in real data

参考文献 20

1	WU K H， ZHU Y Y， LI Q， et al. A distributed real-time data prediction framework for large-scale time-series data using stream processing［J］. International Journal of Intelligent Computing and Cybernetics， 2017， 10（2）： 145-165. 10.1108/ijicc-09-2016-0033
2	LUGHOFER E， PRATAMA M. On-line active learning in data stream regression using uncertainty sampling based on evolving generalized fuzzy models［J］. IEEE Transactions on Fuzzy Systems， 2018， 26（1）： 292-309. 10.1109/TFUZZ.2017.2654504
3	刘琴. 大数据分析下分布式数据流处理技术研究［J］. 软件工程， 2019， 22（12）： 44-46.
	LIU Q. Research on distributed data flow processing technology under big data analysis［J］. Software Engineering， 2019， 22（12）： 44-46.
4	GIACOMETTI A， AMO S D. Temporal conditional preferences over sequences of objects［C］// Proceedings of the 2007 International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2007： 246-253. 10.1109/ictai.2007.169
5	KIEßLING W， KÖSTLER G. Preference SQL-design， implementation， experiences［C］// Proceedings of the 28th International Conference on Very Large Databases. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 2002： 990-1001. 10.1016/b978-155860869-6/50098-6
6	SUN X J， LIU J L， WANG K. Operators of preference composition for CP-nets［J］. Expert Systems with Applications， 2017， 86： 32-41. 10.1016/j.eswa.2017.05.040
7	王卫星，刘兆伟. 基于时间敏感滑动窗口的CP-nets结构学习［J］. 南京大学学报， 2020， 56（2）： 175-185. 10.20965/ijat.2020.p0337
	WANG W X， LIU Z W. Learning of CP-nets structure based on a time-sensitive sliding window［J］. Journal of Nanjing University， 2020， 56（2）： 175-185. 10.20965/ijat.2020.p0337
8	AMO S D， PEREIRA F. Evaluation of continuous preference queries［J］ Journal of Information and Data Management， 2010， 1（3）： 503-518. 10.1109/cbms.2010.6042693
9	GARCÍA-GARCÍA F， CORRAL A， LRIBARNE L， et al. Efficient distance join query processing in distributed spatial data management systems［J］. Information Sciences， 2020， 512： 985-1008. 10.1016/j.ins.2019.10.030
10	SOUNDARARAJAN R， KUMAR S， GAYATHRI N， et al. Skyline query optimization for preferable product selection and recommendation system［J］. Wireless Personal Communications， 2021， 117（10）： 3091-3108. 10.1007/s11277-020-07592-9
11	KONTAKI M， GOUNARIS A， PAPADOPOULOS A N， et al. Continuous monitoring of distance-based outliers over data streams［C］// Proceedings of the 2011 International Conference on Data Engineering. Piscataway： IEEE， 2011： 135-146. 10.1109/icde.2011.5767923
12	REN W L， LIAN X， GHAZINOUR K. Effective and efficient top-k query processing over incomplete data streams［J］. Information Sciences， 2021， 544： 343-371. 10.1016/j.ins.2020.08.011
13	JIANG H， ZHU R， WANG B. EPF： a general framework for supporting continuous top-k queries over streaming data［J］. Cognitive Computation， 2020， 12（4）： 176-194. 10.1007/s12559-019-09661-z
14	BÖRZSÖNYI S， KOSSMANN D， STOCKER K. The skyline operator［C］// Proceedings of the 17th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2001： 421-430.
15	ARASU A， BABU S， WIDOM J. The CQL continuous query language： semantic foundations and query execution［J］ The International Journal on Very Large Data Bases， 2006， 15（2）： 121-142. 10.1007/s00778-004-0147-z
16	RIBEIRO M R， AMO S D， et al. StreamPref： a query language for temporal conditional preferences on data streams［J］. Journal of Intelligent Information Systems， 2019， 53（2）： 329-360. 10.1007/s10844-019-00560-1
17	栾艳红，孙雪姣. 基于 CP-net 偏好的关系数据库的Top-k实现［J］. 计算机研究与发展， 2019， 49（2）： 93-99.
	LUAN Y H， SUN X J. Top-k query of relational database based on CP-net［J］. Journal of Computer Research and Development， 2019， 49（2）： 93-99.
18	RIBEIRO M R， BARIONI M C， AMO S D， et al. Incremental evaluation of continuous preference queries［J］. Information Sciences， 2018， 453： 127-153. 10.1016/j.ins.2018.04.030
19	RIBEIRO M R， PEREIRA F S F， DIAS V V S. Efficient algorithms for processing preference queries［C］// Proceedings of the 31st Annual ACM Symposium on Applied Computing. New York： ACM， 2016： 972-979. 10.1145/2851613.2851659
20	RIBERO M R， BARIONI M C N， DE AMO S， et al. Soccer2014DS： a dataset containing player events from the 2014 World Cup［C］// Proceedings of the 32nd SBBD Dataset Showcase Workshop. Uberlandia： SBBD， 2017： 278-285.

[1]	张斌王莉杨延杰. 联合立场的过程跟踪式多任务谣言验证模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	李鸿邹俊颖谭茜成李贵洋. 面向医学图像分割的多注意力融合网络 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	张玉杰王帆. 基于改进麻雀搜索算法的照明控制优化方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	邵小萌张猛. 融合注意力机制的时间卷积知识追踪模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	王元龙刘晓敏张虎. 基于事件表示的机器阅读理解模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	李宗正, 周恺卿, 欧云, 丁雷. 基于基因交换的自适应人工鱼群算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 701-707.
[7]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[8]	谢新林肖毅续欣莹. 基于神经网络架构搜索的肺结节分类算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	王汇丰徐岩魏一铭王会真. 基于并联卷积与残差网络的图像超分辨率重建 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	刘尚旺张新明张非. 改进字体自适应神经网络的图像字符编辑方法 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	凡文俊赵曙光郭力争. 基于改进RetinaNet的船舶检测算法 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	郭可贵曹瑞万能汪晓尹悦唐旭明熊军林. 基于输电杆塔区域提取的图像匹配算法 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	盖荣丽高守传李明霞. 粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[14]	李蒙蒙刘艺李庚松郑奇斌秦伟任小广. 不平衡多分类算法综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	杜雨奇郑津王杨黄诚李平. 基于图卷积网络的文本分割模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

基于时间条件提取序列的数据流偏好查询

Data stream preference query based on extraction sequence according to temporal condition

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 20

相关文章 15

编辑推荐

Metrics