Min-Max：数据流上一种ANN查询处理技术

《Min-Max：数据流上一种ANN查询处理技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名：旅见签字日期：0力．／．／学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容

2、编入有关数据库进行检索、交流。(如作者和导师同意网上交流，请在下方签名：否则视为不同意)学位论文作者签名：璇见导师签名：孑专学位论文作者签名：驭见导师签名：孑专签字日期：o。．7．，．f签字日期：如。>．，·f东北大学硕士学位论文第一章绪论随着科技的发展和互联网的流行，数据流以及相关的应用正受到人们广泛的关注。在数据流环境下，很多情况下需要对其进行不同类型的复杂查询，而这一类查询往往对系统的实时性和准确性有着很高的要求。1．1研究背景数据流及其相关技术的发展与流行，在数据流上对当前数据构建索引，并对其进行相关查询有着广泛的应用，

3、如何高效地在频繁变化的数据流上进行复杂查询，正越来越多地受到人们的关注。传统的NN(nea糟st∞i曲bol】r)【14博法是通过计算关键点与其相对应的邻居节点的信息数据，将节点较均匀的分配到很多个子区域中去，每个区域内部近似于一个聚类，区域与区域之间则相对独立，且有着自己各自的区域属性。在通过NN算法对数据进行划分之后，可以高效、正确地对整个数据集合进行相应的信息检索。MBR【蜘以及R-1确算法喁d01贝Ⅱ是基于NN算法基础只上提出的新的算法来解决NN问题，虽然在进行复杂查询上有着良好的效率，但其只适用于固定不变的数据，同时还

4、需要大量的预处理，实旌起来有一定的局限性。同时，MBR和R-1ke类型的数据结构一旦数据本身发生变化，维护和更新起来所需要处理的数据量也将大幅度加大，因此这种高效的NN、R-1慨类型的查询算法在数据流上并不适用。A套IN算法【11d4】是一种基于NN和R-Tree算法之上的支持多查询点进行复杂查询的算法，其主要思想是通过对多查询点的分析计算，用一个特殊的、能代表其他的查询点特征的点来对整个数据集合进行复杂查询，能有在一定程度上提高查询效率。1．2问题的提出有这样一个问题，假设有所个人想要在最短的时间内集合于某一地点。限于当前时刻

5、的交通限制，可能会有捍个参考集合地点，随着时间的变化，交通条件也会相应地发生变化(例如：某种交通工具在某一时间段会没有班次，而在另一段时间则会有新的班次的交通工具可供选择)，这样，供参考的集合地点也会发生变化，而随着时间的变化，人的坐标也会发生变化。这样若把人看作是查询点，参考的集合地点看作是数据点，则一1一东北大学硕士学位论文第一章绪论整个供查询数据集合由于随着时间的推移实在不停的发生变化的，因此可以看作是一个数据流。如图1．1所示，随着时间的变化，供查询的数据也发生着相应的变化，我们可以把曾经出现的数据、当前的数据、以及未来

6、某一时刻可能出现的数据看作是整个数据流，而当前时刻供查询的数据就看作是当前时刻滑动窗口内所包含的数据，同时把人看作是当前时刻的查询点，这样我们可以把整个集合问题看作是一个数据流【15，161问题，便于我们在后面的章节里进行分析、讨论。田·s睁罡璺阴畸田图1．1问题描述．数据流Fig．1．1Whatisttleprobl锄一datash℃锄我们查询的结果是要找出在某一时刻滑动窗口内的所有数据点中的某一点，使其满足所有查询点均到达该点所需要的时间最短。也就是说，我们当前所面临的是一个在数据流上的关于多查询点的复杂查询问题。◇矾口l+

7、o吨驰数据点查询点图I．2f懈-milI查询实例F．g．1．2All咖npleofama》minq唧一2一◇+函◇西囝东北大学硕士学位论文第一章绪逢由此，我们可以在这个应用背景下面构建出一个数学模型，如图1．2所示，我们把人看作时查询点，用星形符号表示，而集合地点看作是数据点，用椭圆形符号表示，整个计算的最终目的是在这个坐标系下，通过计算分析，来找到那个距离3个查询点的最大距离值最小的那个点，如图1．2所示，图中的数据点西为我们所求的当前时刻的查询结果，这样，整个问题就转化为了一个二维坐标系下面的一个mi小m烈查询问题。相比传统

8、的NN以及R-1-ree类型的数据结构，数据流上的数据则有着更新速度快、单位时间内数据量大的特点。为此，本文提出了一种新的基于数据流的ma)【一miIl查询方法，进而提高了在数据流上进行复杂查询的查询效率。由于是在数据流上对数据进行复杂查询处理，数据的变化频率很