空间Skyline查询

障碍环境中空间Skyline查询方法李松;窦雅男;张丽平;郝晓红【期刊名称】《计算机科学与探索》【年(卷),期】2018(012)012【摘要】为了弥补现有的研究成果对处理障碍环境下空间Skyline查询问题的不足,提出了在障碍环境下基于Voronoi图的空间Skyline查询方法.该方法在实际应用中可以用来解决多目标决策问题.依据查询点集合是否发生变化提出了两种情况下的障碍环境中空间Skyline查询(spatial Skyline queries in obstacle space,OSSQ)方法:一种是静态查询点的障碍环境中空间Skyline查询(static query points of Skyline query in obstacle space,STA_OSSQ)方法,该查询方法主要包括约剪数据集和支配检查两个过程,最后得到Skyline集合;另一种是动态查询点状态下的障碍环境中Skyline查询(dynamic query points of Skyline query in obstacle space,DYN_OSSQ)方法,该方法主要处理了查询点动态增加和减少情况下障碍环境中空间Skyline查询问题.理论研究和实验表明所提出的方法具有较高的效率.【总页数】9页(P1882-1890)【作者】李松;窦雅男;张丽平;郝晓红【作者单位】哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080【正文语种】中文【中图分类】TP311.13【相关文献】1.障碍空间中基于R+树的空间Skyline查询方法 [J], 李松;李爽;张丽平;郝晓红2.一种障碍空间数据库中的连续反k近邻查询方法 [J], 谷峪;于晓楠;于戈3.障碍物环境中的路网最近邻查询方法 [J], 李林;张丽平;李松4.道路网环境下K-支配空间Skyline查询方法 [J], 李松; 窦雅男; 郝晓红; 张丽平; 郝忠孝5.会展空间室内环境中无障碍设计的研究 [J], 郭无霜;胡平因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于压缩策略的高维空间子空间skyline查询算法孟熠;刘玉葆;李启睿【期刊名称】《计算机研究与发展》【年(卷),期】2013(050)0z1【摘要】skyline操作就是找出数据集中不被其他数据点支配的点的集合,但是随着数据属性维度的不断增多,通常人们只对数据集的某几个属性感兴趣,高维空间子空间skyline计算就是发现数据集中在某几个特定维度上不被其他点支配的点的集合,skyline计算在数据量大时其时间花销是非常大的,快速的返回结果才是人们能接受的.基于此提出了一个RSky算法,在原有CSky算法的基础上,指出并改进了其存在的3处明显不足,并根据InvertS索引的特性提出了一个压缩扫描策略,通过设置每个维度的下限来控制要处理的桶,除去不必要处理的桶和不可能是skyline的点,从而减少了点与点之间的比较次数.实验结果表明了RSky算法的有效性.【总页数】8页(P101-108)【作者】孟熠;刘玉葆;李启睿【作者单位】中山大学信息科学与技术学院广州 510006;中山大学信息科学与技术学院广州 510006;中山大学信息科学与技术学院广州 510006【正文语种】中文【中图分类】TP301【相关文献】1.障碍空间中基于R+树的空间Skyline查询方法 [J], 李松;李爽;张丽平;郝晓红2.基于高维空间的在线高效子空间Skyline算法——CSky [J], 周红福;宫学庆;郑凯;周傲英3.一种基于排序子空间的高维聚类算法及其可视化研究 [J], 刘勘;周晓峥;周洞汝4.一种采用Z曲线高维空间范围查询算法 [J], 徐红波;郝忠孝5.基于网格和队列触发的多维空间Skyline查询算法 [J], 张斌;孟凡荣;闫秋艳因版权原因，仅展示原文概要，查看原文内容请购买。

第１３卷㊀第６期Ｖｏｌ．１３Ｎｏ．６㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２３年６月㊀Ｊｕｎ．２０２３㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２３）０６－００３０－０９中图分类号：ＴＰ３１１文献标志码：Ａ基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询李晨阳１，董雷刚２，孙国豪３，于㊀泉４（１吉林化工学院信息与控制工程学院，吉林吉林１３２０２２；２白城师范学院计算机科学学院，吉林白城１３７０００；３东华大学计算机科学与技术学院，上海２０１６２０；４蚂蚁科技集团股份有限公司，杭州３１００１２）摘㊀要：在移动互联网环境下，空间文本ｓｋｙｌｉｎｅ查询可以有效支持用户在空间和关键词方面的查询㊂随着需求的多样性，基于用户经常会同时考虑空间距离㊁数值型信息㊁关键词和时间等因素对查询结果的影响，提出了基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询（ＴｉｍｅｂａｓｅｄＳｐａｔｉａｌＴｅｘｔＫｅｙｗｏｒｄＳｋｙｌｉｎｅＱｕｅｒｙ，ＴＳＴＫＳＱ），用来查找在空间㊁数值㊁关键词和时间都满足条件的优秀对象，设计了基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询的索引结构ＳＴＴＲ－Ｔｒｅｅ，提出了关键词㊁时间和时空关键词相关性的评价函数，在裁剪策略的基础上提出了ｓｋｙｌｉｎｅ查询算法㊂通过实验结果分析，验证了算法的准确性和有效性㊂关键词：空间文本ｓｋｙｌｉｎｅ查询；关键词相关性；时间相关性；时空关键词相关性；ＳＴＴＲ－Ｔｒｅｅ索引ＴｉｍｅｂａｓｅｄｓｐａｔｉａｌｔｅｘｔｋｅｙｗｏｒｄｓｋｙｌｉｎｅｑｕｅｒｙＬＩＣｈｅｎｙａｎｇ１，ＤＯＮＧＬｅｉｇａｎｇ２，ＳＵＮＧｕｏｈａｏ３，ＹＵＱｕａｎ４（１ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｎｔｒｏｌＥｎｇｉｎｅｅｒｉｎｇ，ＪｉｌｉｎＩｎｓｔｉｔｕｔｅｏｆＣｈｅｍｉｃａｌＴｅｃｈｎｏｌｏｇｙ，Ｊｉｌｉｎ１３２０２２，Ｃｈｉｎａ；２ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＢａｉｃｈｅｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，ＢａｉｃｈｅｎｇＪｉｌｉｎ１３７０００，Ｃｈｉｎａ；３ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＤｏｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０１６２０，Ｃｈｉｎａ；４ＡｎｔＴｅｃｈｎｏｌｏｇｙＧｒｏｕｐＣｏ．，Ｌｔｄ，Ｈａｎｇｚｈｏｕ３１００１２，Ｃｈｉｎａ）ʌＡｂｓｔｒａｃｔɔＩｎｔｈｅｍｏｂｉｌｅＩｎｔｅｒｎｅｔｅｎｖｉｒｏｎｍｅｎｔ，ｓｐａｔｉａｌｔｅｘｔｓｋｙｌｉｎｅｑｕｅｒｉｅｓｃａｎｅｆｆｅｃｔｉｖｅｌｙｓｕｐｐｏｒｔｕｓｅｒｓᶄｑｕｅｒｉｅｓｉｎｔｅｒｍｓｏｆｓｐａｃｅａｎｄｋｅｙｗｏｒｄｓ．Ｗｉｔｈｔｈｅｄｉｖｅｒｓｉｔｙｏｆｎｅｅｄｓ，ｂａｓｅｄｏｎｔｈｅｆａｃｔｔｈａｔｕｓｅｒｓｏｆｔｅｎｃｏｎｓｉｄｅｒｔｈｅｉｎｆｌｕｅｎｃｅｏｆｓｐａｔｉａｌｄｉｓｔａｎｃｅ，ｎｕｍｅｒｉｃａｌｉｎｆｏｒｍａｔｉｏｎ，ｋｅｙｗｏｒｄｓａｎｄｔｉｍｅｏｎｑｕｅｒｙｒｅｓｕｌｔｓａｔｔｈｅｓａｍｅｔｉｍｅ，ａＴｉｍｅｂａｓｅｄＳｐａｔｉａｌＴｅｘｔＫｅｙｗｏｒｄＳｋｙｌｉｎｅＱｕｅｒｙ（ＴＳＴＫＳＱ）ｉｓｐｒｏｐｏｓｅｄｔｏｆｉｎｄｔｈｅｓｐａｔｉａｌ，ｎｕｍｅｒｉｃａｌ，ｋｅｙｗｏｒｄａｎｄｔｉｍｅａｒｅｓａｔｉｓｆｉｅｄｗｉｔｈｔｈｅｃｏｎｄｉｔｉｏｎｓｏｆｔｈｅｅｘｃｅｌｌｅｎｔｏｂｊｅｃｔ．ＴｈｅｉｎｄｅｘｓｔｒｕｃｔｕｒｅＳＴＴＲ－Ｔｒｅｅｆｏｒｔｉｍｅｂａｓｅｄｓｐａｔｉａｌｔｅｘｔｋｅｙｗｏｒｄｓｋｙｌｉｎｅｑｕｅｒｙｉｓｄｅｓｉｇｎｅｄ，ｔｈｅｅｖａｌｕａｔｉｏｎｆｕｎｃｔｉｏｎｓｏｆｋｅｙｗｏｒｄ，ｔｉｍｅａｎｄｓｐａｔｉｏ－ｔｅｍｐｏｒａｌｋｅｙｗｏｒｄｒｅｌｅｖａｎｃｅｉｓｐｒｏｐｏｓｅｄ，ａｎｄｔｈｅｓｋｙｌｉｎｅｑｕｅｒｙａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｏｎｔｈｅｂａｓｉｓｏｆｔｈｅｔａｉｌｏｒｉｎｇｓｔｒａｔｅｇｙ．Ｔｈｅａｃｃｕｒａｃｙａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅａｌｇｏｒｉｔｈｍａｒｅｖｅｒｉｆｉｅｄｔｈｒｏｕｇｈｔｈｅａｎａｌｙｓｉｓｏｆｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓ．ʌＫｅｙｗｏｒｄｓɔｓｐａｔｉａｌｔｅｘｔｓｋｙｌｉｎｅｑｕｅｒｙ；ｋｅｙｗｏｒｄｓｒｅｌｅｖａｎｃｅ；ｔｉｍｅｃｏｒｒｅｌａｔｉｏｎ；ｔｅｍｐｏｒａｌｓｐａｔｉａｌｋｅｙｗｏｒｄｒｅｌｅｖａｎｃｅ；ＳＴＴＲ－Ｔｒｅｅｉｎｄｅｘ基金项目：吉林省自然科学基金项目（ＹＤＺＪ２０２２０１ＺＹＴＳ６６６）；吉林省教育厅科学研究项目（ＪＪＫＨ２０２１０００５ＫＪ）㊂作者简介：李晨阳（１９９９－），男，硕士研究生，主要研究方向：数据查询与优化；董雷刚（１９８２－），男，博士，副教授，硕士生导师，主要研究方向：数据查询与优化；孙国豪（１９９０－），男，博士，副教授，主要研究方向：大数据；于㊀泉（１９９１－），男，学士，高级工程师，主要研究方向：数据挖掘㊂通讯作者：董雷刚㊀㊀Ｅｍａｉｌ：Ｌｇｄｏｎｇ０１０＠１６３．ｃｏｍ收稿日期：２０２３－０２－２１０㊀引㊀言科技的发展产生了海量的数据信息，在移动通信和互联网技术快速发展的背景下，用户对互联网中的数据信息提出了具有特定的查询需求㊂２００１年，Ｂöｒｚｓöｎｙｉ等人在文献［１］中首次将ｓｋｙｌｉｎｅ查询应用于数据库领域，作为一种高效的数据检索方式，被广泛应用于多目标决策㊁市场分析和数据挖掘等多个领域中㊂Ｓｋｙｌｉｎｅ查询的结果为一组ｓｋｙｌｉｎｅ对象，这些ｓｋｙｌｉｎｅ对象均不能被同一数据集中其它任何对象支配㊂在实际应用中，用户对查询的要求越来越多，现有的空间文本ｓｋｙｌｉｎｅ查询算法在计算时考虑的因素较少，无法满足用户需求㊂例如，用户计划在某天晚上与朋友聚餐，需要预定一个２０：００－２２：００时间段可以营业㊁距离火车站近㊁价格低㊁服务质量好，且最好拥有停车场的饭店㊂在表１中列出了４个饭店的信息，包含了饭店到查询点的空间距离㊁饭店的人均消费价格㊁用户评分㊁关键词信息以及营业时间㊂表１㊀饭店信息Ｔａｂ．１㊀Ｈｏｔｅｌｉｎｆｏｒｍａｔｉｏｎ饭店名称空间距离／Ｋｍ人均价格／元用户评分关键词营业时间ａ３．６９０８停车场㊁空调５：３０－９：００ｂ４６０７ｗｉｆｉ㊁空调１０：００－２２：００ｃ２．２９０８停车场２２：００－３：００ｄ４．５８０７ｗｉｆｉ㊁停车场１１：００－１４：００㊁１７：３０－２４：００㊀㊀由于此类查询同时包括空间位置㊁数值型信息㊁关键词以及时间４个属性，以往的空间文本ｓｋｙｌｉｎｅ查询不能直接解决此类问题㊂如，文献［２］中提出了空间多关键词ｓｋｙｌｉｎｅ查询算法ＳＫＳ，将空间距离和文本相似度相结合，建立了加权距离的空间文本支配模型㊂ＳＫＳ算法主要考虑了加权距离和数值型属性，并没有考虑时间属性对查询结果的影响㊂文献［３］中提出了已知时间的空间文本ｓｋｙｌｉｎｅ查询ＴＳＴＳＱ，ＴＳＴＳＱ中考虑了查询点和对象间的空间距离㊁查询关键词与对象包含的关键词间的文本相关性以及查询时间段和对象包含时间段的时间相关性３个属性㊂在查询时通过计算空间文本相关性函数ｋｄ（ｑ，ｏ）和时间文本相关性函数ｋｔ（ｑ，ｏ）来判断对象间的支配关系㊂然而，此查询并没有考虑数值型信息对查询结果的影响，查询结果集具有一定的缺陷㊂当前文献考虑的都是时间㊁空间距离㊁数值型信息和关键词中的若干个因素，并没有将这４个因素同时考虑进去进行研究，而同时考虑这４个因素后将会为用户返回更适合用户偏好的结果集㊂基于此，本文将时间㊁空间距离㊁数值型信息和关键词几个因素相结合，提出一种基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询，构建基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询的索引结构以及查询算法，满足用户更多和更具体的查询需求㊂１㊀相关工作最开始对ｓｋｙｌｉｎｅ查询的研究是以数值型属性为支配判断条件找到最优候选集，文献［４］中介绍了最近邻ＮＮ算法和分支界限ＢＢＳ算法，其中，最近邻搜索策略是基于Ｒ∗－Ｔｒｅｅ索引对象，ＢＢＳ算法是在ＮＮ算法的基础上进行改进，ＢＢＳ算法只对可能包含ｓｋｙｌｉｎｅ点的Ｒ树节点进行访问，不会重复检索，其内存开销明显小于ＮＮ算法㊂然而，上述查询没有考虑空间属性对查询结果的影响㊂随着进一步的研究，文献［５］考虑了空间属性，提出了欧式空间和路网空间中的ｓｋｙｌｉｎｅ查询问题；文献［６］中将Ｋ－支配应用到道路网ｓｋｙｌｉｎｅ查询中，提出了道路网环境下Ｋ－支配空间ｓｋｙｌｉｎｅ查询方法，来处理多属性数据对象㊂在实际应用中只考虑空间属性并不能满足用户的偏好性需求，用户的偏好性需求一般通过关键词等文本信息来描述，文献［７］提出将空间位置和查询关键词作为查询条件，使用Ｖｏｒｏｎｏｉ进行空间数据管理，建立路网中每个点的主导区域来求解最优查询结果㊂考虑在实际应用中欧式距离的局限性，文献［８］提出了基于曼哈顿距离的空间ｓｋｙｌｉｎｅ查询；文献［９］提出使用Ｒ∗树索引空间和文本数据，文本数据采用倒排文件索引结构，并添加到Ｒ∗树上，该索引结构插入数据的速度比Ｒ树快，并且比传统的空间索引花费时间少；文献［１０］提出了加权空间ｓｋｙｌｉｎｅ查询，每个兴趣点都有不同的重要性，给每个兴趣点分配不同的权重，并使用加权欧几里得距离来获取ｓｋｙｌｉｎｅ点集㊂以上文献虽然在一定程度上解决了ｓｋｙｌｉｎｅ查询和空间文本ｓｋｙｌｉｎｅ查询等问题，但随着用户的偏好性需求不断增加，以往的ｓｋｙｌｉｎｅ查询已经不能满足用户的需求，需要考虑其他因素对查询结果的影响㊂在移动互联网环境下，文献［１１］将方向这一属性应用到空间ｓｋｙｌｉｎｅ查询中，提出了基于方向的空间ｓｋｙｌｉｎｅ，该查询从不同方向检索最优候选对象，查询结果为不同方向上的ｓｋｙｌｉｎｅ对象，并提出了伪ｓｋｙｌｉｎｅ的概念，如果某一方向上没有ｓｋｙｌｉｎｅ对象，则用伪ｓｋｙｌｉｎｅ对象替代㊂考虑到用户社交对查询的影响，文献［１２］提出了基于社交的空间文本ｓｋｙｌｉｎｅ查询，设计了新的评价函数来计算用户的社交相关性㊂为了提高查询结果的质量，引入了受限ｓｋｙｌｉｎｅ，当ｓｋｙｌｉｎｅ查询返回的结果少于设定的阈值时，需要进行受限ｓｋｙｌｉｎｅ查找，最后返回的是ｓｋｙｌｉｎｅ对象和受限ｓｋｙｌｉｎｅ对象㊂文献［１３］将空间关键字查询与社交数据相结合，提出了路网地理社交ｔｏｐ－ｋ和ｓｋｙｌｉｎｅ关键词查询，通过对象的空间信１３第６期李晨阳，等：基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询息㊁文本信息和社交网络信息来进行查询㊂考虑到时间在查询中的重要作用㊂文献［１４］将时间信息与空间关键词查询结合，同时考虑对象与查询点之间的位置相关性㊁文本相关性和时间相关性，并且定义了两个评价函数来满足用户的不同需求㊂文献［１５］提出了在路网中有效处理具有时变属性的对象的ｓｋｙｌｉｎｅ查询问题㊂文献［１６］将时间属性应用到Ｔｏｐ－ｋ查询中，根据用户的空间位置和时间，为用户返回ｋ条旅行时间最短的路线㊂综上所述，现有算法并不能解决带有时间的空间文本关键词ｓｋｙｌｉｎｅ查询问题，因此本文提出一种基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询，获得那些在时间㊁空间㊁文本㊁数值４个方面具有最优表现的对象集合，以满足用户更具体的偏好需求㊂２㊀问题定义为了清晰地判断对象间的支配关系，本节将着重介绍查询点ｑ与对象ｏ之间的空间距离㊁关键词相关性㊁时间相关性以及时空关键词相关性的评价函数㊂２．１㊀空间距离ＳＤ（ｑ，ｏ）＝ｄ（ｑ，ｏ）（１）㊀㊀其中，ｄ（ｑ，ｏ）表示查询点和对象点间的欧式距离，则查询点与对象点间的空间距离就是两点间的欧式距离㊂２．２㊀关键词相关性假设查询关键词有ｎ个，对象包含的关键词有ｍ个，则有㊀㊀㊀㊀㊀㊀㊀㊀ＫＲ（ｑ，ｏ）＝ðｎｉ＝１Ｖｉ（２）Ｖｉ＝ωｉｑｋｉɘｏｋｊʂ００ｑｋｉɘｏｋｊ＝０{ｉɪ１，ｎ[]，ｊɪ１，ｍ[]()（３）其中，｜ｑｋｉɘｏｋｊ｜ʂ０表示查询关键词与对象包含的关键词相交；｜ｑｋｉɘｏｋｊ｜＝０表示查询关键词与对象包含的关键词不相交；ωｉ表示查询关键词的权重㊂每个查询关键词的权重有两种设定情况，一是由用户根据偏好对每个查询关键词进行设定，其二是默认所有查询关键词的权重相等㊂Ｖｉ表示每个查询关键词与对象包含的关键词的相关性，则关键词相关性就是每个查询关键词与对象包含的关键词的相关性之和㊂以表１中包含的对象为例，其中包含了饭店到查询点的空间距离㊁饭店的人均消费价格㊁用户评分㊁关键词信息以及营业时间等信息㊂假设用户查询的关键词为 ｗｉｆｉ 和 空调 ，关键词的权重根据用户的偏好设定，设用户对 ｗｉｆｉ 的偏好权重为０．６，对 空调 的偏好权重为０．４，则对象ａ㊁ｂ㊁ｃ㊁ｄ的关键词相关性分别为０．４㊁１㊁０㊁０．６，如果用户没有设置关键词的权重，则默认所有查询关键词的权重相等，此时对象ａ㊁ｂ㊁ｃ㊁ｄ的关键词相关性分别为０．５㊁１㊁０㊁０．５㊂２．３㊀时间相关性ＴＣ（ｑ，ｏ）＝ｑｔｑɘｏｔｑｑｔｑ（４）㊀㊀其中，｜ｑｔｑɘｏｔｑ｜表示查询时间段与对象包含的时间段之间相交的数值，｜ｑｔｑ｜表示查询时间段的数值，则时间相关性就是查询时间段和对象包含的时间段间相交的数值与查询时间段的数值的比值㊂以表１中包含的对象为例，假设用户查询的时间段是２０：００－２２：００，则对象ａ㊁ｂ㊁ｃ㊁ｄ的时间相关性分别为０㊁１㊁０㊁１㊂为了对某个对象的空间距离㊁关键词相关性及时间相关性有一个综合评价，本文提出了时空关键词相关性函数来衡量一个对象同时在空间㊁时间㊁文本上的优劣程度㊂其中，α是一个平衡系数，用来平衡关键词相关性与时间相关性间的权重，在没有用户设定的情况下，默认二者权重相等㊂本文设定时空关键词相关性的数值越小对象越优㊂２．４㊀时空关键词相关性㊀ＴＳＫＲ（ｑ，ｏ）＝ＳＤ（ｑ，ｏ）αＫＲ（ｑ，ｏ）＋（１－α）ＴＣ（ｑ，ｏ）（５）㊀㊀以表１中包含的对象为例，假设用户查询的关键词为 ｗｉｆｉ 和 空调 ，用户查询的时间段是２０：００－２２：００，默认所有查询关键词的权重相等㊂根据计算，对象ｃ的关键词相关性为０，对象ａ和对象ｃ的时间相关性都为０㊂因此，对象ａ㊁ｃ不必进行计算可以根据算法提前裁剪，而对象ｂ㊁ｄ的时空关键词相关性分别为４㊁６，说明对象ｂ优于ｄ㊂定义１（数值型信息支配）㊀给定数据集中具有ｎ维数值型属性的任意两个对象ｏｉ㊁ｏｊ，如果ｏｉ在其ｍ维数值型属性中至少有一维属性优于ｏｊ，则称在ｍ维数值型属性上ｏｉ支配ｏｊ，记为ｏｉ≺ＮＩｏｊ㊂本文设定数值型属性的数值越小对象表现越优，但在表１中用户评分属性一般是数值越大越好㊂如果遇到某一数值型属性值越大对象越优的情况，则先将对象ｏ进行预处理：ｏｉᶄ＝ｍａｘｉ－ｏｉ，其中ｍａｘｉ表示第ｉ维数值型属性的最大值，ｏｉ表示对象ｏ在第ｉ维数值型属性的取值㊂２３智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀定义２（基于时间的空间文本关键词支配）㊀给定查询点ｑ和空间数据集Ｄ中的任意两个对象ｏｉ㊁ｏｊ，如果ｏｉ㊁ｏｊ同时满足ｏｉ≺ＮＩｏｊ且ＴＳＫＲ（ｑ，ｏｉ）ɤＴＳＫＲ（ｑ，ｏｊ），则称ｏｉ基于时间的空间文本关键词支配ｏｊ，记为ｏｉ≺ＴＳＴＫｏｊ㊂以表１中包含的对象为例，假设用户需要预定晚上２０：００－２２：００与其当前位置距离近㊁价格低㊁服务质量好，最好拥有 ｗｉｆｉ 和 空调 的饭店㊂根据计算对象ｂ㊁ｄ的时空关键词相关性分别为４㊁６，并且根据对象ｂ和ｄ的数值型信息可知ｂ≺ＮＩｄ，所以由定义２可知，ｂ≺ＴＳＴＫｄ㊂定义３（基于时间的空间文本关键词ｓｋｙｌｉｎｅ）㊀给定一个数据集Ｄ，基于时间的空间文本关键词ｓｋｙｌｉｎｅ就是从该数据集中返回那些不能被其它任何对象支配对象的集合㊂即，当且仅当∀ｏᶄɪＤ㊁ｏᶄɲＴＳＴＫｏ时ｏɪＴＳＴＫＳ㊂由定义２中的例子可得，基于时间的空间文本关键词ｓｋｙｌｉｎｅ为｛ｂ｝㊂３㊀ＳＴＴＲ－Ｔｒｅｅ索引为了高效地获取ｓｋｙｌｉｎｅ对象，需要建立相关索引结构㊂虽然Ｒ－Ｔｒｅｅ［１７］是一种经典的空间索引数据结构，但其只包含对象的空间信息，随后学者们又提出了ＩＲ－Ｔｒｅｅ［１８］㊁ＩＲ２－Ｔｒｅｅ［１９］等空间索引，也不能同时存储对象的空间㊁数值型信息㊁关键词及时间等信息㊂因此，本文提出一种可以同时存储对象的空间㊁数值型信息㊁关键词及时间等信息的ＳＴＴＲ－Ｔｒｅｅ索引㊂ＳＴＴＲ－Ｔｒｅｅ索引结构如图１所示㊂11010101110111111001111111010100010101010001010110011011I n v e r t e d F i l e -N 1I n v e r t e d F i l e -N 2I n v e r t e d F i l e -N 3I n v e r t e d F i l e -N 4N 5N 6S Fm b r c n pT i m eN u mT e x t P -N 4N u mT e x t P -N 3N u mT e x t P -N 2N u mT e x t P -N 1s fl o c a t i o n i d t i m eN 1N 2N 3N 4O 1O 2O 5O 4O 6O 3O 8O 7O 9O 10图１㊀ＳＴＴＲ－Ｔｒｅｅ索引Ｆｉｇ．１㊀ＳＴＴＲ－Ｔｒｅｅｉｎｄｅｘ㊀㊀ＳＴＴＲ－Ｔｒｅｅ索引中叶子结点主要包含以下信息：对象的空间位置信息（ｌｏｃａｔｉｏｎ）㊁对象在数据集中的标识符（ｉｄ）㊁对象包含的时间段信息（ｔｉｍｅ）㊁指向该结点的文件倒排表的指针（ＩｎｖｅｒｔｅｄＦｉｌｅ）㊂文件倒排表中的关键词是由该结点包含的所有对象关键词的并集组成㊂对象ｏ１㊁ｏ２㊁ｏ４㊁ｏ５㊁ｏ６包含的时间段信息见表２，叶子结点的文件倒排表见表３㊂表２㊀对象的时间段信息Ｔａｂ．２㊀Ｔｉｍｅｐｅｒｉｏｄｉｎｆｏｒｍａｔｉｏｎｏｆｏｂｊｅｃｔｓ对象时间段Ｏ１６：００－８：００Ｏ２９：００－１２：００Ｏ４１０：００－１７：００Ｏ５８：００－２０：００Ｏ６１８：００－２４：００表３㊀叶子结点文件倒排表Ｔａｂ．３㊀ＩｎｖｅｒｔｅｄｌｉｓｔｏｆｌｅａｆｎｏｄｅｆｉｌｅｓＩｎｖｅｒｔｅｄＦｉｌｅ－Ｎ１ＩｎｖｅｒｔｅｄＦｉｌｅ－Ｎ２ＩｎｖｅｒｔｅｄＦｉｌｅ－Ｎ３ＩｎｖｅｒｔｅｄＦｉｌｅ－Ｎ４ｋ１：ｏ１㊁ｏ２ｋ１：ｋ１：ｋ１：ｏ９㊁ｏ１０ｋ２：ｏ５ｋ２：ｏ６ｋ２：ｋ２：ｋ３：ｋ３：ｋ３：ｋ３：ｋ４：ｏ２㊁ｏ５ｋ４：ｏ４ｋ４：ｏ３㊁ｏ８ｋ４：ｏ７ｋ５：ｋ５：ｋ５：ｋ５：ｏ９㊁ｏ１０ｋ６：ｏ１㊁ｏ５ｋ６：ｏ４ｋ６：ｏ８ｋ６：ｋ７：ｋ７：ｋ７：ｋ７：ｏ７㊁ｏ９ｋ８：ｋ８：ｏ４㊁ｏ６ｋ８：ｏ３ｋ８：ｏ９㊀㊀图１中，ｓｆ表示该结点对应的签名文件，结点的签名文件是由该结点中所有对象的签名文件进行ｏｒ操作产生㊂在ＳＴＴＲ－Ｔｒｅｅ中，假设签名文件为一串３３第６期李晨阳，等：基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询８位的二进制码，通过设定的ｈａｓｈ函数将关键词映射到每一位二进制码中㊂如果二进制码中的位为１，则表示该位包含对应的关键词，若二进制码中的位为０，则表示该位不包含对应的关键词㊂例如，在ＳＴＴＲ－Ｔｒｅｅ中，假设ｏ１㊁ｏ２㊁ｏ５的签名文件分别为１００１００００㊁０１０００１００㊁０００１０１００，将ｏ１㊁ｏ２㊁ｏ５的签名文件进行ｏｒ操作，生成结点Ｎ１的签名文件１１０１０１００㊂同理，其它结点以同样的方式生成相应的签名文件㊂算法在执行查询过程时，首先查询关键词与结点包含的关键词进行匹配，将查询关键词的签名文件与结点包含的签名文件执行ａｎｄ操作，若两个二进制签名文件执行ａｎｄ操作的结果与查询关键词生成的二进制签名文件相同，则表示该结点包含查询关键词，反之则不包含㊂例如，查询关键词生成的签名文件为０００００１０１，对于ＳＴＴＲ－Ｔｒｅｅ根节点，将查询签名文件与根结点的签名文件进行ａｎｄ操作，０００００１０１ａｎｄ１１０１１１１１＝０００００１０１，此结果表示根结点包含查询关键词㊂ＮｕｍＴｅｘｔＰ表示指向该结点的数值型信息的指针，结点的数值型信息同时包含了该结点的所有对象的数值型信息㊂叶子结点的数值型信息见表４㊂表４㊀数值型信息Ｔａｂ．４㊀ＮｕｍｅｒｉｃａｌｉｎｆｏｒｍａｔｉｏｎＮｕｍＴｅｘｔＰ－Ｎ１对象名称人均价格用户评分ＮｕｍＴｅｘｔＰ－Ｎ２对象名称人均价格用户评分ＮｕｍＴｅｘｔＰ－Ｎ３对象名称人均价格用户评分ＮｕｍＴｅｘｔＰ－Ｎ４对象名称人均价格用户评分Ｏ１７７８．５Ｏ４５５８．５Ｏ３９５９．２Ｏ７６６７．５Ｏ２６５８．８Ｏ６７１７．６Ｏ８１１０９．５Ｏ９５２７．１Ｏ５８１９Ｏ１０７３８．２㊀㊀非叶子结点主要包含以下信息：该结点所有子结点的最小边界矩形（ｍｂｒ）㊁指向该结点的子结点指针（ｃｎｐ）㊁该结点包含的所有子结点时间段的并集（Ｔｉｍｅ）㊁该结点对应的签名文件（ＳＦ），结点的签名文件是由所有子结点的签名文件进行ｏｒ操作产生的㊂结点Ｎ１㊁Ｎ２㊁Ｎ５包含的时间段信息见表５㊂表５㊀结点的时间段信息Ｔａｂ．５㊀Ｔｉｍｅｐｅｒｉｏｄｉｎｆｏｒｍａｔｉｏｎｏｆｎｏｄｅｓ结点时间段Ｎ１６：００－２０：００Ｎ２１０：００－１７：００㊁１８：００－２４：００Ｎ５６：００－２４：００４㊀算法描述本节根据ＳＴＴＲ－Ｔｒｅｅ索引提出了ＴＳＴＫＳＱ的裁剪策略和算法㊂ＴＳＴＫＳＱ算法在遍历ＳＴＴＲ－Ｔｒｅｅ索引时，先判断结点是否在查询范围之内，然后将结点包含的关键词和时间段信息与查询关键词和时间段信息进行相交判定；算法从空间㊁关键词和时间３个属性对空间数据集上的对象进行过滤；当算法遍历至叶子结点时，将筛选出关键词相关和时间相关的对象进行数值型信息支配和基于时间的空间文本关键词支配关系判断，最终获取查询结果集㊂４．１㊀裁剪策略ＴＳＴＫＳＱ算法在遍历ＳＴＴＲ－Ｔｒｅｅ索引时，对结点采用如下裁剪策略：（１）若查询关键词与结点包含的关键词不相交，则不必进行时间段相交的判断，直接将结点进行剪枝㊂（２）若查询时间段与结点包含的时间段不相交，则不必进行关键词相交的判断，直接将结点进行剪枝㊂（３）若同时满足查询关键词与结点包含的关键词相交，以及查询时间段与结点包含的时间段相交，则对其子结点进行重复判断，直到筛选出满足条件的候选对象，否则将结点进行剪枝㊂在基于ＳＴＴＲ－Ｔｒｅｅ的查询算法和裁剪算法中，本文使用优先队列对候选集Ｃ和结果集Ｒ进行维护，优先队列中的对象按照ＴＳＫＲ的非递减顺序出队列㊂定理１［３］㊀在按照ＴＳＫＲ的非递减顺序出队列的优先队列中，首个出队列的对象ｏ必为ｓｋｙｌｉｎｅ对象㊂定理２㊀给定数据集中的任意两个对象ｏｉ㊁ｏｊ，如果ｏｉ与ｏｊ之间不存在数值型信息支配，则ｏｉ与ｏｊ之间也不存在基于时间的空间文本关键词支配㊂证明㊀由于ｏｉ与ｏｊ之间不存在数值型信息支配关系，根据定义２可知，ｏｉ与ｏｊ之间不能同时满足ｏｉ≺ＮＩｏｊ且ＴＳＫＲ（ｑ，ｏｉ）ɤＴＳＫＲ（ｑ，ｏｊ），所以ｏｉ与ｏｊ之间也不存在基于时间的空间文本关键词支配㊂４３智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀例如，表１中的对象ａ和ｂ，由于ａ在用户评分这一属性上支配ｂ，而ｂ在人均价格这一属性上支配ａ，所以二者不存在数值型信息支配关系，因此二者也不存在基于时间的空间文本关键词支配关系㊂定理３［３］㊀在按照ＴＳＫＲ的非递减顺序出队列的优先队列中，若已出队列的对象为ｏ，在ｏ之后出队列的任意对象为ｏᶄ，必有ｏᶄɲＴＳＴＫｏ㊂定理４㊀在按照ＴＳＫＲ的非递减顺序出队列的优先队列中，设先出队列的对象为ｏ，后出队列的对象为ｏᶄ，若ｏｉ≺ＮＩｏᶄ，则ｏ≺ＴＳＴＫｏᶄ㊂证明㊀根据优先队列的性质可知，ＴＳＫＲ（ｑ，ｏ）ɤＴＳＫＲ（ｑ，ｏᶄ），根据定义２可知，ｏ≺ＴＳＴＫｏᶄ㊂例如定义２中的例子，对象ｂ和ｄ的ＴＳＫＲ分别为４㊁６，因此先出队列的对象为ｂ，后出队列的对象为ｄ，又因为ｂ≺ＮＩｄ，所以ｂ≺ＴＳＴＫｄ㊂在基于ＳＴＴＲ－Ｔｒｅｅ的ＴＳＴＫＳＱ算法中，本文对候选对象采用如下裁剪策略：按照ＴＳＫＲ的非递减顺序出队列的优先队列中，设当前出候选集队列的对象为ｏ，当前结果集中的任一对象为ｓｐ，若ｓｐ≺ＮＩｏ，则裁剪ｏ，否则将对象ｏ放入结果集中㊂证明㊀根据优先队列的性质可知，ＴＳＫＲ（ｑ，ｓｐ）ɤＴＳＫＲ（ｑ，ｏ），若ｓｐ≺ＮＩｏ，根据定义２可知ｓｐ基于时间的空间文本关键词支配ｏ，此时对象ｏ可以被裁剪，反之，若ｓｐ与ｏ之间不存在数值型信息支配关系，根据定理２，ｓｐ与ｏ之间也不存在基于时间的空间文本关键词支配，所以ｏ为ｓｋｙｌｉｎｅ对象，放入结果集中㊂４．２㊀算法算法１㊀ＴＳＴＫＳＱ算法输入㊀查询点ｑ㊁查询关键词ｑｋ㊁查询时间段ｑｔｑ㊁查询范围ｒ㊁ＳＴＴＲ－Ｔｒｅｅ索引㊁空间对象点集Ｏ输出㊀查询结果集Ｒ１㊀Ｒ＝∅；Ｃ＝∅；㊀／／Ｒ存放查询结果集，Ｃ存放候选集２㊀ＷｈｉｌｅｎｏｔＳｔａｃｋ．ｉｓＥｍｐｔｙ（）ｄｏ㊀／／以深度优先遍历索引３㊀㊀Ｎ＝Ｓｔａｃｋ．ｐｏｐ（）；４㊀㊀Ｉｆｄ（ｑ，Ｎ）＜ｒ㊀／／若结点在查询范围之内５㊀㊀ＩｆｑｋɘＮｋʂ∅／／若查询关键词与结点包含的关键词相交６㊀㊀ＩｆｑｔｑɘＮｔｑʂ∅／／若查询时间段与结点包含的时间段相交７㊀㊀ＩｆＮ．ｉｓＬｅａｆ（）ｔｈｅｎ８㊀㊀㊀ＦｏｒｅａｃｈｏｉｎＮｄｏ９㊀㊀㊀Ｉｆｑｋɘｏｋʂ∅１０㊀㊀㊀Ｉｆｑｔｑɘｏｔｑʂ∅１１㊀㊀㊀ＣѳＮｅｗＰｒｉｏｒｉｔｙＱｕｅｕｅ；／／按照ＴＳＫＲ的非递减顺序初始化优先队列１２㊀㊀㊀Ｃ．Ｅｎｑｕｅｕｅ（ｏ）；㊀／／将对象ｏ放入候选集优先队列中１３㊀㊀㊀Ｅｌｓｅ１４㊀㊀㊀Ｓｔａｃｋ．ｐｕｓｈ（Ｎ．ＣｈｉｌｄＮｏｄｅ）；㊀／／将孩子结点进栈１５㊀ｅｎｄＷｈｉｌｅ１６㊀ＲѳＮｅｗＰｒｉｏｒｉｔｙＱｕｅｕｅ；㊀／／按照ＴＳＫＲ的非递减顺序初始化优先队列１７㊀Ｒ＝ｄｏｍｉｎａｔｅＣｏｍｐｔｉｎｇ（ｑ，Ｃ）；㊀／／对候选集中的对象进行支配计算１８㊀ｒｅｔｕｒｎＲ；算法１是基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询的具体过程㊂第２－３行以栈的方式维护索引，第４－７行对查询范围内的结点进行判断，筛选出查询关键词与结点包含关键词相交以及查询时间段与结点包含时间段相交的结点，直到遍历至叶子结点㊂第８－１２行遍历叶子结点，筛选出查询关键词与对象包含关键词相交以及查询时间段与对象包含时间段相交的对象，将对象放入ＴＳＫＲ的非递减候选集优先队列中㊂第１６－１８行将候选集中的对象进行支配计算，把不被支配的对象放入结果集队列中㊂由于第１７行中ｄｏｍｉｎａｔｅＣｏｍｐｔｉｎｇ（）算法需要判断所有候选对象间的支配关系，导致算法整体查询效率下降，因此需要加入高效的裁剪策略来提升查询效率㊂算法２㊀ｄｏｍｉｎａｔｅＣｏｍｐｕｔｉｎｇ（）算法输入㊀候选集Ｃ㊁查询点ｑ㊁查询关键词ｑｋ㊁查询时间段ｑｔｑ输出㊀查询结果集Ｒ１㊀ＲѳｇｅｔＣＦｉｒｓｔ（）；㊀／／将Ｃ中首个出队列对象放入结果集中２㊀ＷｈｉｌｅｎｏｔＣ．ｉｓＥｍｐｔｙ（）ｄｏ３㊀㊀ｏ＝Ｃ．Ｄｅｑｕｅｕｅ（）；４㊀㊀ＩｆｓｐＮｕｍｅｒｉｃＴｙｐｅＤｏｍｉｎａｔｅｏ㊀／／判断结果集中的对象ｓｐ是否数值型信息支配对象ｏ５㊀㊀㊀ｃｏｎｔｉｎｅ；６㊀㊀Ｅｌｓｅ７㊀㊀㊀ｉｎｓｅｒｔｏｉｎｔｏＲ８㊀ｅｎｄＷｈｉｌｅ５３第６期李晨阳，等：基于时间的空间文本关键词ｓｋｙｌｉｎｅ查询９㊀ｒｅｔｕｒｎＲ算法２是判断候选集对象间支配关系的裁剪算法㊂第１行是将候选集中首个出队列对象放入结果集中㊂第２－３行若候选集队列非空时，依次取出候选集中的对象进行判断，第４－７行若候选对象被结果集中的对象基于时间的空间文本关键词支配则删除候选对象，否则将对象放入结果集中㊂以图１㊁表２ 表５中包含的数据为例，假设查询关键词为ｋ１㊁ｋ２㊁ｋ４，生成对应二进制签名文件为１１０１００００，查询时间段为１０：００－１２：００，默认各结点在查询范围之内，并且数值型属性的要求为人均价格低㊁用户评分高㊂具体查询过程如下：首先，筛选出查询关键词和查询时间与对象的关键词和时间相交的候选对象㊂从根节点开始，将查询二进制签名文件与结点包含的签名文件进行ａｎｄ操作，１１０１００００ａｎｄ１１０１１１１１＝１１０１００００表示根节点包含查询关键词，并且根节点的时间段包含查询时间段，然后对其孩子结点进行重复判定，１１０１００００ａｎｄ１１０１０１０１＝１１０１００００表示结点Ｎ５包含查询关键词，并且结点Ｎ５的时间段包含查询时间段，１１０１００００ａｎｄ１００１１１１１＝１００１００００表示结点Ｎ６不包含查询关键词，则对Ｎ６及其孩子结点进行裁剪，不必进行后续判定提高了查询效率，继续对结点Ｎ５的孩子结点Ｎ１㊁Ｎ２进行判断，１１０１００００ａｎｄ１１０１０１００＝１１０１００００表示结点Ｎ１包含查询关键词，并且结点Ｎ１的时间段包含查询时间段，１１０１００００ａｎｄ０１０１０１０１＝０１０１００００表示结点Ｎ２不包含查询关键词，直接进行剪枝，此时得到叶子结点Ｎ１中的对象ｏ１㊁ｏ２㊁ｏ５，由于ｏ１的时间段与查询时间段不相交，删除ｏ１，而ｏ２㊁ｏ５满足查询关键词与查询时间都相交，此时得到候选集对象ｏ２㊁ｏ５㊂之后，判断候选对象间的支配关系㊂假设查询点与对象ｏ２㊁ｏ５的空间距离分别为１㊁２，根据计算ｏ２㊁ｏ５的ＴＳＫＲ分别为１．２㊁２．４，将ｏ２㊁ｏ５按照ＴＳＫＲ的非递减顺序放入候选集队列中，将第一个出队列的对象ｏ２直接加入结果集中，然后ｏ５出队列，由于ｏ２与ｏ５间不能构成数值型信息支配，因此将ｏ５加入结果集中，此时遍历完所有候选对象，得到最终结果集｛ｏ２㊁ｏ５｝㊂５㊀实验结果与分析实验采用的硬件设备为６４位Ｗｉｎｄｏｗｓ１０操作系统，Ｉｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）ｉ５－７２００ＵＣＰＵ＠２．５０ＧＨｚ处理器，８Ｇ内存；采用Ｊａｖａ语言实现算法，集成开发环境为ＩｎｔｅｌｌｉＪＩＤＥＡＣｏｍｍｕｎｉｔｙＥｄｉｔｉｏｎ２０２１．１．３，ＪＤＫ版本为１１．０．１１㊂实验数据来源于ｙｅｌｐ网站的开源数据集，该数据集中包括克利夫兰㊁多伦多等１１个城市１５０３４６个商户的信息㊂实验将数据集中的经纬度作为对象的空间位置信息，价格㊁星级等作为对象的数值型信息，商户的分类作为对象的关键词信息，营业时间作为对象的时间信息㊂通过是否使用裁剪策略ＴＳＴＫＳＱ与ＮＴＳＴＫＳＱ测试算法的有效性，每次测试均取相同环境下１０次测试的平均值为最终结果㊂５．１㊀查询关键词数量的影响为了测试查询关键词的数量对算法的影响，设置数值型属性为２维，查询点的空间位置和查询时间段固定不变，查询关键词１ ５个㊂查询关键词数量变化对算法的影响如图２所示㊂18001500120090060030012345关键词的数量时间/msT S T K S Q N T S T K S Q图２㊀查询关键词数量的影响Ｆｉｇ．２㊀Ｉｍｐａｃｔｏｆｔｈｅｎｕｍｂｅｒｏｆｑｕｅｒｙｋｅｙｗｏｒｄｓ㊀㊀从图２中可知，随着查询关键词数量的增加，算法整体的运行时间也不断增加㊂对于不使用裁剪策略ＮＴＳＴＫＳＱ进行查询时，算法需要遍历所有数据集中的对象，将查询关键词与每个对象包含的关键词一一比较，直到筛选出所有包含查询关键词的对象，而随着查询关键词数量的增加，包含查询关键词的对象也越来越多，因此整体查询时间呈上升趋势，而使用裁剪策略ＴＳＴＫＳＱ进行查询时，算法的查询时间明显少于使用裁剪策略ＮＴＳＴＫＳＱ的查询时间㊂由于使用裁剪策略ＴＳＴＫＳＱ时，算法根据ＳＴＴＲ－Ｔｒｅｅ结点的签名文件进行操作时，提前裁剪了不包含查询关键词的结点，不必进行后续的判断，因而极大地提升了算法的执行效率㊂５．２㊀数值型属性维度的影响为了测试数值型属性维度对算法的影响，设置了２个查询关键词，查询点的空间位置和查询时间段固定不变，数值型属性维度从１维变化到５维㊂数值型属性维度的变化对算法的影响如图３所示㊂６３智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀。

Skyline服务查询实验实验内容：应用BNL算法和SFS算法对QWS数据集进行skyline服务查询算法介绍及实现：➢BNL算法该算法首先在内存中开辟有一块窗口，用于存放从文件中读入的疑似是SP的数据。

还有临时文件T，当内存中的窗口满时，原本需要插入到窗口中的点将被保存在临时文件中。

算法的流程如下：从存放需要查询的数据的文件F中，读取一个数据点p，与窗口中的所有点比较（如果窗口为空，则直接插入），根据比较结果不同执行下面三种操作。

●窗口中存在一点q，q点支配p点，则p点不可能是SP成员，将p点丢弃。

●p点支配窗口中的一个或多个点，则被p点支配的所有点不可能是SP成员，将它们删去。

●p点与窗口内所有的点都不相互支配，若窗口的容量仍够存放p点则插入p点，否则将p点插入临时文件T中。

当所有点都读取完并执行完上述操作时，窗口中在临时文件中加入第一个点之前就已经加入的点作为SP输出。

将临时文件T作为数据来源，即作为存放需要查询的数据的文件F，新建一个空白的临时文件T'，从1开始循环执行该过程。

知道所有的点或者被丢弃，或者被作为SP输出。

具体实现（python）：def BNL(len1,len2,data_array):reslist = []for i in range(len1):if len(reslist) == 0:reslist.append(i)else:deletelist=[]remain = Truefor k in reslist:kqicnt = 0iqkcnt = 0for t in range(len2):if data_array[i][t] >= data_array[k][t]:iqkcnt = iqkcnt + 1if data_array[i][t] <= data_array[k][t]:kqicnt = kqicnt + 1if kqicnt == 9:remain = Falsebreakif iqkcnt == 9:deletelist.append(k)if len(deletelist) > 0:reslist = [reslist[p] for p in range(0, len(reslist), 1 ) if p not in deletelist]if remain:reslist.append(i)return reslist➢SFS算法在BNL的基础上先对数据进行预处理（排序），使得加入的点一定是SP，减少删除的开销具体实现（python）：def SFS(data,len1,len2):reslist = []reslist.append(0)for i in range(1,len1):remain = Truefor k in reslist:kqicnt = 0for t in range(len2):if data[i][t] <= data[k][t]:kqicnt = kqicnt + 1if kqicnt == 9:remain = Falsebreakif remain:reslist.append(i)return reslistQoS服务数据randdataset产生的Qos服务数据集放在了QoSdata文件中，通过传入该数据集检验上面的算法实验结果分析：BNL运行结果（数据较多，截图不全）：SFS运行结果（数据较多，截图不全）：运行速率分析BNL算法：SFS算法：。

《外包空间数据库中范围和移动k近邻skyline的查询验证》篇一一、引言随着空间数据库的广泛应用，对外包空间数据库中范围和移动k近邻查询的需求日益增长。

Skyline查询作为一种重要的空间查询技术，能够有效地找出给定空间范围内的多个目标对象，以构建多维度的轮廓（Skyline）进行信息可视化与挖掘。

本篇论文主要讨论如何对外包空间数据库中范围和移动k近邻的Skyline查询进行验证，以保障查询的准确性和高效性。

二、外包空间数据库与Skyline查询概述外包空间数据库（Outsourced Spatial Database）是一种将空间数据存储在云端或外部服务器上的数据库系统。

其优点在于可以充分利用云计算资源，提高数据处理和存储的效率。

Skyline查询则是一种基于空间对象的多维轮廓查询技术，它能够找出给定空间范围内的多个目标对象，并将它们根据一定规则组合成轮廓图谱。

这种查询技术常用于空间数据分析、地图生成等场景。

三、范围和移动k近邻Skyline查询范围和移动k近邻Skyline查询是外包空间数据库中常见的两种查询需求。

其中，范围k近邻查询是指在给定空间范围内，查找距离指定目标点最近的k个点；而移动k近邻查询则是指在一段时间内，找出离移动点最近的k个点。

这两种查询都需要利用Skyline技术来构建多维度的轮廓图谱，以支持后续的信息挖掘和可视化工作。

四、查询验证方法为了保障外包空间数据库中范围和移动k近邻Skyline查询的准确性和高效性，我们需要采用一系列的验证方法。

首先，我们可以通过设计合理的测试用例来验证查询的正确性。

这些测试用例应该涵盖不同的空间范围、目标点、距离等参数条件，以确保在各种情况下都能得到正确的结果。

其次，我们可以利用已有的数据集进行验证，通过将我们的查询结果与已知的正确结果进行比较，来评估我们的算法性能和准确性。

此外，我们还可以采用一些性能评估指标来衡量我们的算法在处理大规模数据时的效率。

《外包空间数据库中范围和移动k近邻skyline的查询验证》篇一一、引言随着大数据时代的来临，空间数据库的应用越来越广泛。

在处理空间数据时，范围查询和移动k近邻查询是两种常见的操作。

同时，Skyline查询作为一种多维度数据查询的重要手段，在空间数据库中也有着广泛的应用。

本文将探讨外包空间数据库中范围和移动k近邻Skyline的查询验证问题，旨在为相关领域的研究和应用提供参考。

二、范围查询的验证范围查询是空间数据库中常见的一种查询方式，其目的是在给定的空间范围内查找满足条件的数据。

为了验证范围查询的准确性，我们需要从以下几个方面进行考虑：1. 查询准确性的评估：通过对比实际查询结果与预期结果，评估范围查询的准确性。

这需要借助一定的评估指标，如准确率、召回率等。

2. 空间索引的优化：空间索引是提高范围查询效率的关键。

我们需要根据数据的特点和查询需求，选择合适的空间索引策略，如R树、四叉树等，并对其性能进行优化。

3. 查询性能的评估：通过对比不同查询策略的执行时间、内存消耗等指标，评估范围查询的性能。

这有助于我们选择最优的查询策略，提高查询效率。

三、移动k近邻查询的验证移动k近邻查询是一种动态的查询方式，用于在移动对象周围查找k个最近的邻居。

为了验证移动k近邻查询的准确性，我们需要关注以下几个方面：1. 移动对象的数据处理：在移动k近邻查询中，移动对象的数据处理至关重要。

我们需要设计合适的数据结构，如轨迹点列表、空间索引等，以支持动态的查询需求。

2. 查询算法的优化：针对移动k近邻查询，我们需要设计高效的查询算法。

这包括计算移动对象与其它对象的距离、选择合适的邻居等操作。

通过优化算法，可以提高查询的准确性和效率。

3. 实时性的保证：移动k近邻查询要求系统能够实时地返回结果。

因此，我们需要关注系统的实时性，确保在短时间内完成查询并返回结果。

四、Skyline查询的验证Skyline查询是一种多维度数据查询的重要手段，用于查找在多个维度上均优于其他数据的数据集。

《外包空间数据库中范围和移动k近邻skyline的查询验证》篇一一、引言随着空间数据库技术的不断发展，外包空间数据库已成为现代信息处理领域的重要研究课题。

在空间数据库中，范围查询和移动k近邻查询是两种常见的查询需求。

Skyline查询则是一种能够获取多维空间中对象之间关系的重要技术。

本文旨在探讨外包空间数据库中范围和移动k近邻的Skyline查询验证方法，以及相应的技术和应用场景。

二、背景介绍随着空间数据规模的扩大和数据处理技术的快速发展，外包空间数据库得到了广泛的应用。

范围查询、移动k近邻查询以及Skyline查询作为空间数据库的三大关键查询需求，具有非常重要的实际意义。

然而，对于如何在这些复杂的多维空间数据中进行有效的查询验证仍然是一个亟待解决的问题。

三、外包空间数据库的范式和基础概念3.1 外包空间数据库概述外包空间数据库是指将部分或全部的空间数据存储在外部服务器上，通过分布式计算和存储技术实现对空间数据的处理和查询。

这种技术能够有效地解决大规模空间数据处理和存储的问题。

3.2 范围查询和移动k近邻查询范围查询是指在给定的一组数据中，找出满足某种空间范围的点。

而移动k近邻查询则是对于某一特定点的移动路径上，查找与其最近的k个邻居。

这两种查询是空间数据库中的常见需求，广泛应用于许多领域如路径规划、目标跟踪等。

3.3 Skyline查询概念Skyline查询是一种在多维空间中获取对象之间关系的重要技术。

它能够找出在给定方向上具有最高可见度的点集，即Skyline 点集。

Skyline查询在许多领域如城市规划、交通规划等都有广泛的应用。

四、范围和移动k近邻Skyline的查询验证方法4.1 范围查询的验证方法针对范围查询的验证方法主要包括以下几步：首先，确定要查询的空间范围；其次，执行范围查询操作，获取结果；最后，将结果与预期结果进行对比验证。

这需要依赖有效的数据集和准确的算法来实现。

4.2 移动k近邻的查询验证方法对于移动k近邻的查询验证，除了与范围查询相似的步骤外，还需要关注点移动后的近邻变化情况。

《外包空间数据库中范围和移动k近邻skyline的查询验证》篇一一、引言随着空间数据库的广泛应用，查询验证技术显得尤为重要。

外包空间数据库的查询验证在确保数据的准确性和安全性方面具有不可替代的作用。

其中，范围和移动K近邻Skyline查询验证在许多场景中都有着广泛的应用。

本文旨在深入探讨这一领域的理论与实践，并为其在现实中的应用提供一定的指导。

二、背景及意义外包空间数据库的查询验证主要包括对查询结果准确性的验证以及对数据安全性的保障。

在空间数据库中，范围和移动K近邻Skyline查询是一种常见的查询方式，它可以用于寻找给定范围内的K个最近邻或最远邻对象，并在此基础上进行进一步的分析和操作。

因此，对于这种查询的验证不仅有助于提高查询结果的准确性，也有助于保障数据的安全性。

三、方法与步骤1. 定义问题：首先，我们需要明确范围和移动K近邻Skyline 查询的具体定义和要求。

这包括对空间范围、K值、近邻或远邻的定义等。

2. 数据准备：准备相应的空间数据集，包括点、线、面等空间对象以及其属性信息。

3. 算法设计：设计有效的算法来执行范围和移动K近邻Skyline查询。

这需要考虑到查询的效率、准确性以及数据的安全性。

4. 查询验证：通过对比算法执行结果与实际结果，验证查询的准确性。

同时，还需要对数据进行安全性的验证，确保数据在传输和存储过程中不会被篡改或泄露。

5. 结果分析：对验证结果进行分析，总结算法的优缺点，提出改进措施。

四、实践应用范围和移动K近邻Skyline查询验证在许多领域都有广泛的应用。

例如，在智能交通系统中，可以通过该查询验证来查找附近的最优路径；在地理信息系统中，可以用于查找特定范围内的地理对象；在移动计算和网络应用中，可以用于寻找移动对象的K近邻等。

这些应用都需要对查询结果进行准确的验证，以确保数据的准确性和安全性。

五、实验与结果为了验证范围和移动K近邻Skyline查询的准确性，我们进行了实验。

一种分布式环境下的skyline查询算法Skyline计算就是从一个数据集中找到不被其他数据点支配的所有点的集合.如果一个数据a支配另一个数据b，那么a的每一维属性值都不比b对应属性值“差”，而且必须至少有一个属性值比b的“好”.“差”和“好”无统一定义，[PS严伟榆1；S*2；Z1，Y，PZ]可以根据用户的选择和喜好定义.例如，一个游客到了某个海滨城市，当他在选择旅馆时，希望找一家的价格相对便宜而其距离海边的距离相对近一点的旅馆.如图1每个点代表一个旅馆，横坐标和纵坐标分别表示该旅馆的价格及其到海边的距离.显然如果旅馆a与b相比其价格便宜且距离海边更近，则a比b好（a支配b），但通常情况下距离海边越近的旅馆其房价也越高.skyline操作返回的旅馆集合在图中用黑点标识，非skyline集合中没有一个旅馆在价格和距离上比这些skyline集合中的更优，故游客只需考虑s kyline集合中的旅馆.近年来，skyline 查询逐渐成为数据库领域的一个研究热点，它在多标准决策、数据挖掘、数据库可视化和偏好查询等领域具有潜在的应用前景.最近10 年, 国内外对skyline 计算及其相关问题的研究主要包括3个方面:①集中式数据库上的skyline 计算，已有的算法包括文献［1］中的块嵌套环算法(BNL)和分治算法(D&C)、文献［2］中的位图算法(Bitmap)和索引算法(Index)、最近邻算法［3］(NN)、分枝界限算法［4］(BBS)等;②分布式数据库上的skyline 计算,已有的算法包括普通分布式环境下的skyline 计算［5］、移动自组织网络［6］下的skyline 计算和文献［7］中的关于对等网络(P2P) 上的skyline计算等;③其它skyline 计算:任意子空间上的skyline 计算［8］、在所有子空间上的sky line 计算［9-10］(skycube)、在数据流上的skyline计算［11］等.本文主要讨论的是普通分布式环境下的的skyline 计算，与文献［5］中的数据呈垂直分布所不同的是本文中的数据是水平分布的.针对如何将局部skyline子集合并成全局skyline集合这个问题，提出了一种“区域划分”的合并思想，并通过实验证明了算法的有效性.1 问题描述文献［5］提出了第1个分布式数据库上的skyline算法，此算法适用于数据垂直分布的情况，即数据对象的各个维度值分别存放在不同的服务器上.算法思想是：首先将各维上的数据排序，然后用轮循的方式依次访问各维，直到某一个数据点p通过此按序访问在各个维度上都被访问到为止.此时可以将所有还未在任何维度被访问过的数据点除去，因为它们都被点p所支配，skyline集合一定包含在已经被访问到的对象集合中.与文献［5］不同，本文考虑的是数据水平分布的情况，即数据集合随机的分布在不同的服务器中.因为当一个数据点p是一个全局skyline点时，它一定也属于某个局部skyline集合，所以当用户需要进行全局的skyline查询时，可以先访问各个局部服务器计算出局部skyline集合，再把局部结果上传到核心服务器上进行下一步全局结果的查询，系统结构如图2所示.2.1 skyline的定义定义1 支配关系,设在数据集A的维度为d.A中存在2个对象q1,q2，各维度上的值分别为( x1, x2, …, xd)和(y1, y2, …, yd），若i,xi≤yi都成立，且j满足xj＜yj(1≤i,j≤d)，则称q1支配q2，表示为Dominate(q1,q2).各个维度上的支配关系应由具体的需求而定，为了描述方便，本文假定各个维度上的支配关系统一为“定义2 skyline集合,所有不被任何其它点所支配的点的集合称为skyline集合，简称SP.在此定义局部的skyline集合为SPi.2.2 BNL算法文献［12］对已有集中式的skyline查询算法做了详细的说明和比较，集中式s kyline查询可分为不带索引和带索引两大类，BNL属不带索引算法.此算法的优点是实现简单，适用于任何维的数据，无须对数据进行任何索引或预处理.它满足skyline计算算法对正确性、公平性的要求.BNL算法的基本思想是：在内存中设置一个窗口保存当前不被其它点所支配的点.读取数据p与窗口内的点一一比较.此时，比较的结果有3种可能：1）p点被窗口中的1个点支配.此时p点一定是非SP点，直接丢弃;2）p点支配窗口中的1个或多个点.将被支配点从窗口中删除，同时将p点插入窗口;3）p点与窗口中的所有点都不存在支配关系.此时，如果窗口中有足够的空间，就将p点插入窗口队列中，若空间不够，则将p点写入一个临时队列中.假设第1个插入到临时队列的是m点，当所有的数据都被访问了一遍时，可以确定窗口中所有在m点之前被访问到的点一定是skyline点，可以直接输出.然后将临时队列中的数据点与窗口中的剩余数据点进行下一轮比较，直到临时队列为空.3 区域划分与多窗口收集算法3.1 区域划分思想首先需要确定一个划分点，可以先对各个局部skyline集合的每一维度求出1个平均值，由所有维度的平均值构成1个局部的中值.然后把所有的局部中值再进行1次平均得到1个全局中值作为划分点.为了便于描述，这里用av(x1,x2,…,x n)表示全局中值，用SP表示skyline集合，第i个局部skyline集合就是SPi ，同时以三维数据空间作为操作对象.用全局中值av(x1,x2,…,xn)对SPi中的数据点进行二叉区域划分，在划分的过程中同时对区域进行动态编号.划分的原则是：从第1维开始逐层划分，如果p(x1) 3.2 划分区域之间的制约关系描述以三维数据为例，在任意2个局部服务器上的对应8个区域：S110,S101,S10 0,S011,S010,S001,S000,S111 中：1）除编号为000和111的区域之外，在任何2台局部服务器上的区域如果其编号互逆的区域一定不存在制约关系.如在局部服务器Qi 上的划分区域S110和服务器Qj 上的划分区域S001中的数据没有制约关系;2）在任何2台局部服务器上的区域如果其编号不同但是1的个数相同的区域不存在制约关系.如在局部服务器Qi 上的划分区域S110和Qj 上的划分区域S 011中的数据一定不存在制约关系;3）特殊区域S111和S000:在每个局部服务器上的SPi进行区域划分时，区域S111和S000至多只有1个区域不空;4）在任何2台局部服务器上，相同编号的划分区域之间的支配关系是双向的.例如，Qi 上的划分区域S110 可能存在数据对象制约Qj 上的划分区域S110中的数据对象，反之亦然;5）在任何2台局部服务器上，编号中1的个数多的划分区域单向支配编号中1的个数少的划分区域.例如，Qi 上的划分区域S110 可能存在数据对象制约Qj 上的划分区域S100中的数据对象；但是Qj 上的划分区域S100中一定不存在数据对象制约Qi 上的划分区域S110中的数据对象.在合并局部skyline集合计算全局skyline集合时，可以根据以上5个规则按区域进行合并，对于没有制约关系的区域可以不再进行制约判断，直接合并；对相同编号的区域采取双向制约判断，删除非全局skyline点；用编号中1的个数多的区域对编号中1的个数少的区域进行单向支配判断，删除非全局skyline点. [PS严伟榆3；S*2；X*2，BP]4 实验分析实验环境：CPU主频为3.0GHz，内存为2GB，硬盘是WD7200转／500GB 的PC机；操作系统是Microsoft Windows XP Professional SP2，编程语言选用的是Microsoft Visual C# 2005.实验平台的部署：在1台PC机上模拟生成了1个核心服务器端和3个局部服务器端.测试数据集：实验对独立数据、正关联数据和反关联数据3类数据进行测试，数据随机生成.实验在三维数据空间下对以下2个算法进行比较分析.1）计算出各个服务器上的局部skyline集，然后汇总到核心服务器上，再用一次BNL算法计算全局skyline;2）计算出各个服务器上的局部skyline集，然后汇总到核心服务器上，采用“区域划分和多窗口收集”算法计算全局skyline.为了便于描述，以下称算法1）为DC算法，算法2）为PC算法.图4反映了3类数据集上当数据集合增大时，PC算法和DC算法的时间效率.[JP2]图4中，横坐标表示数据集合的大小/个，纵坐标表示时间/s.[FL）][PS严伟榆4；S*2；X1，BP，DY#][FL（K2] 实验结果分析：从图4中可以看出，在正关联数据集和独立数据集上，2个算法执行效率相当.在反关联数据集上，当待测数据集较大时，PC算法的执行效率较DC算法有一定改善.说明待测数据集的类型对算法有一定的影响，当全局skyline集合的规模增大时，PC算法的执行效率较高.5 结语本文提出的分布式数据库下当数据水平分布时，通过对局部skyline集合进行区域划分编码后再进行全局skyline查询的算法，可以在合并环节减少数据的匹配次数.实验结果表明当全局skyline集合的规模较大时，算法执行效率有所提高.下一步的研究工作将就高维数据集下的查询和skyline的并行计算展开.。