（计算机软件与理论专业论文）minmax：数据流上一种ann查询处理技术.pdf

东北大学硕士学位论文摘要 m i l l m a ) 【：数据流上一种a n n 查询处理技术 摘要 随着科技的发展和互联网的流行，数据流以及相关的应用正受到人们广泛的关注。 在数据流环境下，很多情况下需要对其进行不同类型的复杂查询，而这一类查询往往对 系统的实时性和准确性有着很高的要求。 本文讨论了当前比较流行的复杂查询算法，其中包括有n n 算法、r _ t h e 算法、q n 算法等，并对其进行深入地分析。由于上述算法对于当前数据有着很大程度的依赖性， 数据结构比较复杂，当数据随时间发生变化时，需要对整个数据结构进行重新构建，往 往达不到数据流上复杂查询所需要的实时性和准确性的要求，因此，这些方法不适用于 完成在数据流上的复杂查询。 由此，本文提出了一种全新的m i l l - m a 】【查询算法，提出了候选区域( c 姐d i d a t e & g i ) 的概念。主要思想是通过对数据的分析计算，在整个数据区域内划分出一个子 区域：候选区域，并利用候选区域对新到来数据进行过滤处理，最后生成当前查询结果。 当候选区域所对应的查询结果过期后，通过与后台系统通信获得新的数据信息来更新当 前查询结果。在数据流环境中，该方法对于数据点随时问发生变化以及查询点随时间发 生变化的情况均适用。同时，在查询点随时间变化的情况下，本文对c r 技术进行了改 进，提出了一种增强了的c r 算法，解决查询点动态变化的情况，并拥有更高的查询效 率。在整个查询处理过程中，c r 算法以及其增强算法计算准确、效率很高，实现了在 数据流上m i n - m a ) 【查询的实时性。 大量的实验和分析证明，本文提出的基于c r 技术的m i n m 舣查询算法及其增强算 法适用于数据流上查询点和数据点随时间发生变化的情况，具有较高的实时性和准确 t 性。 关键词：a n n 查询；数据流；m i n m 强；滑动窗口；候选区域；实时性 一m 东北大学硕士学位论文摘要 m i n m a x ：a na n n q u e r y1 1 e c h n i q u ei nd a t as t r e a m a b s t r a c t a st h ed e v e l 叩m e n to f t c c l 【i l o l o g y & i i 】_ t e l n e t ，d a l as t l 锄柚di t sr e l a t c da p p l i c a t i o nl l a v e b e e np a y e dm o 聆a n dm o 糟a t t e n 右o no n h 咖s 订e 锄，t b e r ca r cm 趾yc o m p h c a t e dq l l e 械e s 趾d t 1 1 e q l l c r i e sn e e dm l | c hm o r e a l - t i m e & u r i 够 h it l l i sp a p e r ，w ed i s c u s s m ep o p m 孤a l g o r i t h ma t 舢tc o m p l i c a t e dq u e r i e s ，s u c ha sn n ， r 1 k e ，a 1 叮n 锄do m 叮a l g 耐t l l i 璐ni sn o ts u i t a b l ef o rt h e a l g o r i t b m sw h e n l ed a t 鹪o r t h eq l l e r i e sh a v eb 啪c h a i l g e db a u t h e s ca l g o r m m 岱r e l yo n 蚀峙d a t as 劬l c t i l r e w h e nt l l e d a t 嬲c h 强g e d ，t 1 1 ed a t a 鼬c t l l r ：em u s tb er d b i l i l d e d s ot h c yc 龇n o tm a l 【e 也er e q u e s e t si n r e a l t i m e 粕dn o tg o o dw a yt 0h 锄d l i n go m n p l i c a t e dq u e r i e si n 纰s 幻黜 s o ，w ep r o p o an e wm e t h o dd b o i l ta n n i m i n - m a x ) q u e r i e s 锄dai d e a 蛐o d c r ( c 跹d id a _ t e r e i g i o n ) 1 1 1 e 胱l i np o i n to f c r i s t o f o 】曲a 叭br e 西o n 舶吼也ew l l o l ed a t a r e g i o n ，a n d m a k eu o f t h e c r t o 丘l t e ro m e rd a t a s w h m ek e yd a ：c a i s 缸e o u t ，w ec 锄 g e n e r a t en e wk e yd a t a 丘d mc 锄m i l n i c 触g 、啊t l lt h eb a c k g r o u n ds y s t e m t h i sa l g o r i m mc a i l u s eb o lt h ed 椭a n dt h eq u e r i e sc h 觚g i n go nd a 忸s 协 锄e i i v i r o 砌e n t w ba l e n h 锄c en l e a l g o r i t h mw h c nt h eq u e r i e sa r ec h a n g i l l g ，雒d 血ce l l l l 锄c e dc ra l g o r i t l l mi sm o r ee 伍c i e m 趾da c c u r a t e t h ea l g o r i t l l mp e f f b m se x c e l l 曲t 柚dm a k e s s s st l l e q ：r i 】n gb e i n gar c a l - t i l n e m c t l l o do nc k l t a s n 、跚 m a n ye x 拼：r i i n e n 乜a n d 岫i n g sp r o o f 也a tt h em e t h o dw ep r o p o s ew h i c hi sb a do n 恤 t c c l l n o l o g yo f c r & e i l h a n c e dc r a r er e a l 一缸l ea n da c u r i t ew a y si nd a t as 们锄w h b o t l l t h e 出i 组sa d 血eq u e r i e sc l l a i l g i i l g k e yw o r d s ： a n nq u e r y ；嘲讹锄；i n i n m a x ；s l i d i n gw 1 n d o w ；c 觚d i d a t cr c g i ；r e a l 劬e v 一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 旅见 签字 日期：0 力 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：璇见导师签名：孑专学位论文作者签名：驭见导师签名：孑专 签字日期：o 。7 ，f签字日期：如。 ，f 东北大学硕士学位论文 第一章绪论 第一章绪论 随着科技的发展和互联网的流行，数据流以及相关的应用正受到人们广泛的关注。 在数据流环境下，很多情况下需要对其进行不同类型的复杂查询，而这一类查询往往对 系统的实时性和准确性有着很高的要求。 1 1 研究背景 数据流及其相关技术的发展与流行，在数据流上对当前数据构建索引，并对其进行 相关查询有着广泛的应用，如何高效地在频繁变化的数据流上进行复杂查询，正越来越 多地受到人们的关注。 传统的n n ( n e a 糟s t i 曲b o l 】r ) 【1 4 博法是通过计算关键点与其相对应的邻居节点的 信息数据，将节点较均匀的分配到很多个子区域中去，每个区域内部近似于一个聚类， 区域与区域之间则相对独立，且有着自己各自的区域属性。在通过n n 算法对数据进行 划分之后，可以高效、正确地对整个数据集合进行相应的信息检索。 m b r 【蜘以及r - 1 确算法喁d 0 1 贝是基于n n 算法基础只上提出的新的算法来解决n n 问题，虽然在进行复杂查询上有着良好的效率，但其只适用于固定不变的数据，同时还 需要大量的预处理，实旌起来有一定的局限性。同时，m b r 和r - 1 k e 类型的数据结构 一旦数据本身发生变化，维护和更新起来所需要处理的数据量也将大幅度加大，因此这 种高效的n n 、r - 1 慨类型的查询算法在数据流上并不适用。 a 套i n 算法【1 1 d 4 】是一种基于n n 和r - t r e e 算法之上的支持多查询点进行复杂查询的 算法，其主要思想是通过对多查询点的分析计算，用一个特殊的、能代表其他的查询点 特征的点来对整个数据集合进行复杂查询，能有在一定程度上提高查询效率。 1 2 问题的提出 有这样一个问题，假设有所个人想要在最短的时间内集合于某一地点。限于当前时 刻的交通限制，可能会有捍个参考集合地点，随着时间的变化，交通条件也会相应地发 生变化( 例如：某种交通工具在某一时间段会没有班次，而在另一段时间则会有新的班 次的交通工具可供选择) ，这样，供参考的集合地点也会发生变化，而随着时间的变化， 人的坐标也会发生变化。这样若把人看作是查询点，参考的集合地点看作是数据点，则 一1 一 东北大学硕士学位论文第一章绪论 整个供查询数据集合由于随着时间的推移实在不停的发生变化的，因此可以看作是一个 数据流。如图1 1 所示，随着时间的变化，供查询的数据也发生着相应的变化，我们可 以把曾经出现的数据、当前的数据、以及未来某一时刻可能出现的数据看作是整个数据 流，而当前时刻供查询的数据就看作是当前时刻滑动窗口内所包含的数据，同时把人看 作是当前时刻的查询点，这样我们可以把整个集合问题看作是一个数据流【1 5 ，1 6 1 问题，便 于我们在后面的章节里进行分析、讨论。 田s 睁罡璺阴畸田 图1 1 问题描述数据流 f i g 1 1w h a t i s t t l e p r o b l 锄一da t as h 锄 我们查询的结果是要找出在某一时刻滑动窗口内的所有数据点中的某一点，使其满 足所有查询点均到达该点所需要的时间最短。也就是说，我们当前所面临的是一个在数 据流上的关于多查询点的复杂查询问题。 矾 口l + o 吨 驰 数据点 查询点 图i 2 f 懈- m i l i 查询实例 f g 1 2a l l 咖n p l e o f a m a m i n q 唧 一2 一 + 函 西囝 东北大学硕士学位论文第一章绪逢 由此，我们可以在这个应用背景下面构建出一个数学模型，如图1 2 所示，我们把 人看作时查询点，用星形符号表示，而集合地点看作是数据点，用椭圆形符号表示，整 个计算的最终目的是在这个坐标系下，通过计算分析，来找到那个距离3 个查询点的最 大距离值最小的那个点，如图1 2 所示，图中的数据点西为我们所求的当前时刻的查询 结果，这样，整个问题就转化为了一个二维坐标系下面的一个m i 小m 烈查询问题。 相比传统的n n 以及r - 1 - r e e 类型的数据结构，数据流上的数据则有着更新速度快、 单位时间内数据量大的特点。为此，本文提出了一种新的基于数据流的m a ) 【一m i i l 查询方 法，进而提高了在数据流上进行复杂查询的查询效率。 由于是在数据流上对数据进行复杂查询处理，数据的变化频率很快，传统的n n 、 r - 1 r e e 技术则是将数据都存放在一个固定的数据结构中，一旦数据发生变化，需要更叛 整个数据结构来维护，代价昂贵，从而导致数据处理的效率低下。为此，本文提出了一 种利用数据的候选区域来对数据进行过滤处理的技术。首先系统按照流的形式来分析处 理数据，划分出一个候选区域，如果新数据落在候选区域之内则对其进行深度处理分析， 若落在候选区域之外，由于该数据对当前的查询结果并不影响，暂时将其放在后台，待 有空闲时间的时候对该数据进行分析处理，看是否会在未来的某一时刻成为新的查询结 果，并保存相关数据，一旦某时刻的查询结果过期，则通过对后台处理的数据进行分析， 从而产生新的查询结果。 1 3 本文讨论的重点 本文讨论的重点为分两个部分： 第一个部分为在数据流上基于数据点随时间发生变化的情况下，应用c r 技术的查 询策略。这个部分我们通过分析指出在简单的加i n - m a x 查询策略在查询的过程中，存在 着相当程度的冗余操作，无法实现数据流上对于数据查询的即时性要求，从而提出了关 于c r ( 候选区域) 的概念，以及相对应的过滤机制，引入了基于c r 技术的关于处理 在数据流上数据点随时间发生变化的查询策略。这种查询策略分为前台系统和后台系统 两个部分，前台只需要处理极少量的分析和计算并通过与后台传送信息的通信方式即可 达到对于当前滑动窗口下的m i n m a ) 【查询，后台系统则是对数据进行详细分析，计算并 生成当前时刻以及未来某一时刻的有用信息，并时刻与前台系统保持通信。这一查询策 略能够较高质量的满足用户的即时性和正确性的查询需求。 第二个部分为在数据流上基于查询点随时间发生变化的情况下，应用c r 技术的查 一3 一 东北大学硕士学位论文第一章绪论 询策略。这个部分通过对c r 技术的分析，在前一部分基于数据点变化的c r 技术应用 的基础上，进行了进一步的深入讨论，实现并解决了c r 技术在查询点随时间发生变化 的情况下的查询策略。之后又对这种解决手段进行了深入的分析讨论，从而进一步的对 其进行改进，提出了一种增强的c r 查询策略这种策略能够更高效、准确地在数据流 上基于查询点随时间发生变化的情况下进行m i n - m 弘查询，能够满足用户的即时性和准 确性的查询需求。 1 4 本文的组织结构 本文的组织结构安排如下： 第一章为引言，主要介绍研究背景和现实意义。 第二章主要介绍当前i n j n - m a x 查询的相关工作。 第三章给出本文的问题定义，其中包括讨论问题所需定义、定理和证明等相关知识， 以及本文所要讨论问题的详细描述 第四章介绍在数据点变化下的m i n m a x 查询算法。 第五章介绍在查询点变化下的m i l l m 戤查询算法。 第六章通过实验对在数据流上的m a x 血算法进彳亍测试并对实验结果进行分析。 第七章总结全文并对未来工作进行展望。 一4 一 东北大学硕士学位论文 第二章相关工作 第二章相关工作 对于m i n - m a x 查询，传统的方法是将所有的数据首先进行预处理，对那些属性或者 分布相对接近的点进行聚类，从而达到将整个数据集化分成多个小区域的效果，例如很 多a n n 算法【1 7 。2 ”均包含i i l i n m a x 查询，通常是先将整个数据集划分成多个区域，然后 在这些区域内对数据进行进一步地划分，直到数据聚类达到一定程度。随后，某些算法 对已经聚类好的数据构建成m b r 类型1 2 2 伽或者是r - 1 慨【2 7 8 1 的树型结构来进行 m i n - m a x 查询。某些算法则是基于某种过滤机制选择那些可能包含查询结果的区域进行 深度查询，从而达到对数据的高效准确查询。然而这类a n n 算法只是对于固定数据有 着良好的性能，并给予支持；当数据发生变化时，则必须通过对整个数据结构进行修改。 从本质上说，对于某些数据进行必须的重复计算，很大程度上，增加了计算负担，实时 性相对较差，因此这类a n n 【2 9 捌1 算法在数据流上进行即时查询检索贝l j 并不适用 而c p m 【3 2 1 技术解决了在动态更新的数据上的复杂查询，但这种查询处理方式在某种 程度上仍然需要对数据进行大量地预处理，并且随着数据的维度逐渐增加，计算中的性 能也将随之下降，并不完善。 本章重点介绍这三个领域中与本文研究内容相关的工作。 2 1n n 查询技术 n n ( n e a r e s tn e i g h b o ) 查询技术是一种在整个数据集合中要求查询到与查询点距离 最小的数据点查询技术。其中，数据点集合是按照空间分布来进行索引的，同时通过设 定一些边界来限制查询范围。相临近的数据点之间会聚类到相同子区域中，同时，子区 域之间也通过某种规则进行聚合，直到最后聚合成一个区域。假设有一个区域和一个 查询点霉，则m i r l d i s ，办表示查询点擘与区域及其子区域历包含中距离最近的数据 点的距离；m i n d i s t ( l ，2 ) 表示区域l 与区域飓及其所包含的子区域中的距离最短的 某两数据点之间的距离。n n 查询就是围绕删s 心r ，力和m i n d i s t c l ，飓) 这两种属性 对整个数据集进行分析计算的查询技术。这种查询技术目前包含两种最基本、最流行的 方法，他们分别是基于m b r 的查询方法和基于r ，i r e e 的查询方法。 2 1 1 基于m b r 的方法 m b r 算法的主要思想就是通过对数据集中的所有数据进行分析计算，取锝所有数 一5 一 东北大学硕士学位论文第二章相关工作 据的相关信息之后，对整个数据集合进行聚类操作，生成好多个独立的子区间集合，每 个子区间集合为一个空间范围，具有固定的边界，所有包含在这个边界内部的数据均属 于这个子区间，区间与区间之间的关系只有包含或者不相交两种。在每个子区间内部， 如果这个予区间所包含的数据点过多，则需要进一步的划分，即将这个区间进行划分， 生成被这个区间所包含的子区间，直到所有的予区间都足够小，包含的数据点足够少为 止 如图2 1 所示，整个数据集首先被划分成2 个子区间l 和飓，之后，由于之前的 设定，发现区同l 和2 所包含的数据点数量均超过所设定的阀值，因此需要对区间l 和m 进行进一步的划分，区间m 内部又划分成了2 和炳两个区间，而区间2 内部又 划分成了5 和两个区间，划分之后，当前所有的最低级区间所包含的数据点数量均 符合设定的要求，系统不在划分需要注意的是，m b r 算法生成的区域一般都是矩形 ( 限于2 维空间坐标中) ，且每个数据点都分布在包含该数据点区域的边界上图2 1 中可以清楚的看到这些特征这种做法的好处就是，在查询点找到一个子区域之后，可 以通过判断该查询点与这个子区域的边界之间的距离即可确定查询点与该子区域内部 所有数据点之间的距离。从而能够在很大程度上对数据点进行过滤，能够很好的提高查 询效率 p i p 1 图2 1 m b r 算法 f 磕2 1m b r a i g o 郦雠 一6 一 东北大学硕士学位论文第二章相关工作 当完成整个n n 区间的划分之后，就可以在整个数据集上进行查询操作了。如图2 1 所示，查询点g 需要找到距离g 最近的数据点，则首先搜索距离g 点最近的m b r 区间， m 是距离g 点最近的区间，则在区间l 的边界上找距离g 最近的子区间，依此类推， 直到找到最小级别的予区间为止。之后再从当前检索到的子区间内部对数据点进行分析 查询，最后找到距离g 最近的那个数据点即数据点殷，找到了数据点p 5 ，之后，在通过 数据点p 5 到查询点g 的距离来过滤掉那些距离口距离大于这个距离的区间，同时对小于 这个距离值的区间的子区间进行进一步的过滤，整个过程结束即生成了最后的查询结 果。 2 1 2 基于r - n 也e 的方法 r - t r 甜1 1 4 l 的技术是基于m b r 发展而来的，如图2 2 所示为r - n r c e 的数据结构。 首先，在构造r t r 之前，需要使用n n 算法对整个数据集进行分析计算，生成 m b r 区间，之后再利用生成的m b r 区间来构造r 1 k e 。我们将最开始整个数据集划分 成的那两个区间，放到r t h e 的根节点下面，即他们作为第一层叶子节点存储在r - t k e 的树形结构中。之后再逐缀的将每一个叶子节点进行细分，将每个叶子节点所对应的 m b r 区间所包含的子区间生成其所对应的新的叶子节点，作为当前叶子节点的孩子节 点存在r 1 b e 的树形结构中。通过递归调用，最后生成了整个r j h e 。 詹 图2 2 r - t r 算法 f i 舀2 2r - 1 嘴a l g o r i m m 一7 一 东北大学硕士学位论文第二章相关工作 如图2 2 所示，整个区间最开始被划分为2 个区间即1 和m ，则将这两个区间作 为根节点的叶子节点存放在r - t r 结构中之后首先对区间l 进行分析，将区间l 所包含的子区间3 和 i ：作为区间l 的孩子节点存放到r - t b e 的数据结构中。当区间 为最小区问时，即这个区间足够小到不能再被细分，将该区间所包含的数据点作为该区 间在r - 1 r c e 上所对应的节点的子节点存放到r - 1 h e 的数据结构中去，也就是说此时将 数据点p l ，优，d 作为区间所对应的节点的子节点存储在r - 1 h e 中。同理对区间飓进 行递归操作，最后生成整个r - t h e 。 下面给出关于基于r t r 数据结构进行m b r 查询点的相关算法其中算法2 1 是 基于r 1 h e 的深度优先算法进行对r - 1 r e e 进行遍历查询的。 输入：q 向w ，y 印加砂 输出：d 出r 辱m e 删 1 i f n o d ei sa ni i i t e n n e d i a l en o d e 2 s o ne l 州e sn j mn o d ea c c o r d i n gt om i n d i g 删，q ) i nl i s t 3 f e p e a l 4 鲥n e 蛆咖n j 疗d m l i 髓 5 i f m 如d i s 删，q ) b e s i ；d 硫 6 d f r m e 删，q ) 汕r e c l l r s i 彻 7 咖t nm i l l d i s n j ，q p 吨e s t _ d 碗o r 鞠do f l i s t s e l ，i e a f i 础 9 f o r 眦h p o h np j m n o d e 1 0 i f i p j q i b e s l d 硫 11best r m 萨咄 1 2 b c s t j i s 卢l p j q l，u p d a 把c u n n tr t r 在对r - 1 r e e 进行查询时，只需要对整个r - 1 慨进行遍历查找即可，其中每个节点 均存储着其所包含区域的信息。如算法2 1 所示，其中通过一个循环表达式来将遍历整 个r - t r e e 结构，对于当前的节点，首先判断他是否是叶子节点。如果是，则分析该叶 子节点所包含的所有数据信息，如果不是，则继续遍历这个中间节点的子节点，通过递 归调用来继续对该节点进行n n 查询。 一8 一 东北大学硕士学位论文 第二章相关工作 2 2a n n 查询技术 n n ( a g g r e g a t e n e a 删；t n e i g h b o r ) 算法，是一种支持多查询点的n n 查询，假设， 是一个单调递增的函数q t 仙舶 为查询点集合。则某个数据点p 和q 聚合距离定义 为碱，f p ，钡p ，g i i ，l p ，啦i ) ，其中慨g l i 为数据点p 与查询点g i 之间的绝对距离。给定 一个静态的数据集卢p l ，轴) ，则心n 查询的返回结果为局和距离最小的那个数据 点。如图2 3 所示，当聚合函数为s 眦时的状况，所对应的a n n 查询结果为数据点舶， 其中数据点内符合删细b ，q 户条件。 p 6 p 1 图2 3 h m i 查询例子 f 皓2 3a ne x 锄p l eo f a n nq u e i y p 1 2 2 2 1 基于s p m 的a n n 查询技术 所谓的s p m 【2 5 铡全称为s i i l g l e p o i n t m e t h o d ，是一种在多查询点的环境中，试图通过 一些关键点来代表全部的查询点，从而简化查询过程的一类算法。下面简单介绍几种基 于不同聚合函数下的s p m 策略算法。 一9 一 l 生竖查型兰垡笙奎 箜三主塑羞三堡 图2 4 聚合函数为s 啪的s p m 示例 f i g 2 4 a ne x a m p l eo f s p mw h a g g e r 鲥彻f 弧c 戗o ni ss 啪 如图2 4 所示，图中3 个空心点为查询点，当前的查询聚合函数为s 啪函数，由于 每次都需要将数据点与所有的查询点进行比较计算才能对其进行判断处理，计算过程比 较复杂，因此，我们根据s 啪函数的计算特征用图中的实心点来代表全部的3 个查询点， 这样，整个查询环境就可以化简成为基于单一查询点的n n 查询。大大的简化的整个查 询处理过程。 图2 5 聚合函数为m 缸的s p m 示饲 f 培2 5a ne x 锄p l eo f s p mw h a g g e r a t i o n 缸i 甜o ni s 雠 同理，图2 5 中为聚合函数为m a x 的a n n 查询，根据m 觚函数的特征，我们选取 距离3 个查询点均相同的点即图中实心点来作为代表点，通过取两两点连线的中垂线交 于一点，该点就是使用这种算法的代表点。这样，整个查询环境化简为基于单一查询点 的n n 查询 一1 0 东北大学硕士学位论文 第二章相关工作 图2 6 聚合函数为m i f i 的s p m 示倒 f i g 2 5a l le x 锄p i eo f s p mw l l a g 鲥州0 nf i l f 洲伽i sm i n 图2 6 中是聚合函数为m i i l 的s p m 示例，其中代表点的取法为，在整个数据集中寻 找一点，使得该点到所有查询点的距离之和最小。即图2 6 中边长最长的边9 2 、9 3 所对 应的查询点q 1 为该算法的代表点。同理，在选取了代表点之后，整个查询环境化简为基 于单一查询点的n n 查询。 算法2 1 给出s p m 的相关算法。 算法2 1s p m 鲫口，俨哪p d 新趣n 聊靠咖缸归岸酬 输入：q 向，y p 加p 输出：日r 删 叫 1 r e p e 砒 2 g 毗t l i e i l 嘲a n np jo f q ，峭i 1 1 9 a n y i n c 佗m e n t a la n na l g o 咖m 3 咖p u t ef ( a d i s t 晒，q ) ，p j ) 4 i n s e r t m t o h e 印h 5 w et i l e 矗r s te n h y po f hh 鹬f ( a d i s t 【h q 啊砂( f i a d i s t ( p j ，q ) ，v ) 6 d e h 唧 ， j ，勺b 驴，) ，其中毋是在时刻，f 出现的序列元素。 囝一s 畸罡固a s 瞬田 图3 2 数据流和滑动窗口的概念 f 逸3 2d 鼬s 吐e a m & s 蛄d i n gw m d o w 如图3 2 所示，整个阴影区域所包含的所有的数据点代表了整个数据流。其中数据 一1 6 一 东北大学硕士学位论文第三章m i n 州a x 查询 点是按照时间顺序，从左到右进行排序的是一个无穷有序序列。其中左边的阴影区域 所包含的数据点为过未来的某一时刻能够到来的数据点，中间的阴影区域所包含的数据 点为当前时刻的数据点，最右边的阴影区域所包含的数据点为过去某一时刻的数据点， 这些数据点在当前时刻已经过期了 3 1 4 滑动窗口 设r 是一个时间长度，p r 是一个变化的时刻，则称s w 【f 乃f 】为s 的一个时间间隔 为r 的滑动窗口，其中f 和r 的单位相同，并且f 为相对于s 的起始观测时刻的时间距 离。 显然，s w 卜弘f 】是随着f 的变化而滑动的，故称其为滑动窗口 如图3 2 所示，图中中间的那段阴影区域所包含的数据点即时当前时刻的数据点， 那么这段阴影区域就被我们成为当前时刻的滑动窗口。滑动窗口内的数据为我们当前时 刻系统能够访问到的数据点的集合有着较高的时效性，在滑动窗口内的数据点，每时 每刻都在发生着变化。 3 1 5 最大值( m a xv a i u e ) 对于某个数据点来说，其距离所有查询点的权值距离中的最大值，我们称之为该数 据点的最大值，一般情况下用m 觚v a i 来表示，例如m a x v a l u e ( 画) ：咖a x d i s t ( g j ，痂) ， d i s t ( 卯，西) ，d i s 如。，凶) ) 。 如图3 1 中，数据点痂的最大值( m 觚、枷u e ) 则是数据点西与查询点口1 的权值距离， 其大小为d i s 的f ，砌。 3 1 6 最小值( m i nv a l u e ) 在整个数据集合，存在着某个数据点，它的最大值小于其他任何数据属于数据集合 中的数据点的最大值，我们把这个数据点的最大值，称作整个数据集中最大值中的最小 值，一般情况下，用m n v a l 鹏来表示，例如m i n v a l u 踟眦m 戤v a l l l e ( 西d ， m a x v a l u o 吼) ，m a x - v a l u 磊) 。 如图3 3 所示，数据点盔的m 强v a l 为数据点数据点西与数据点西之间的权值距 离。通过一系列的分析、计算，我们最后知道在整个数据集合中，没有任何点的m 觚v a l 要比数据点西的m 醒v a j u e 小，也就是说，数据点西的瑚xv a l u c 要小于其他任何包含 在数据集合内的数据点的m 戤v a l ，我们将数据点西的m 戤v a i l l c 成为整个数据集的最 一1 7 东北大学硕士学位论文 第三章m i n - m a x 查询 大值中的最小值。我们后面讨论的关于数据流上m i n - m 觚的查询问题就是要找到对于不 同时刻，整个数据集的最小值问题。 囝函 数据点 + 查询点 。西 囝函 囝而 i n i nv a l 嘴 磊妒3 图3 3m m m “查询中的最小值 f i g 3 3m i n 训u co f m n m “q u e r y i i l g 3 2m i i l m a x 查询 假设有m 个数据点和n 个查询点，给定某数据点西，所有查询点与该数据点之间的 距离的最大值为d 姊，则如垆m a d i s t 国j ，呦，d i s c ( 赫，砌) 。( 1 f 聊，lg 挖) ， 这样我们最后要求的结果，即数据点与所有查询点距离最大值中的最小值。可以表示为： i l 他产m i n ( d 函幻，d 砩) 。 这里，上面所说的d i s t 就可以看作是之前我们提到的权值距离概念，他等于数据点 与查询点之间的绝对距离乘上一个相关的系数，这里讨论的系数可以看作是交通工具行 驶速度的倒数。而数据点与所有查询点距离最大值中的最小值的概念，用前一小节所讨 论的m xv a l u e 、m i i l v a i u e 概念可以解释为那个m a xv a l 要小于所有包含于当前数据集 中其他数据点的n l m xv a l l l e 值的数据点，即整个数据集中的m i nv a l l l c 值所对应的数据 点。 下面我们结合图表来对m i n m 瓤查询的流程作一个直观的介绍。 一1 8 一 下 g 东北大学硕士学位论文第三章m i n x 查询 v n 个查询点对应的d i 娥卯西) 图3 4m i 州m 戤查询的计算过程 f 弛3 。41 1 艟s b k ho f am i r 卜舶a xq r ya i 擘o f i 强 如图3 4 所示，其中在图的最下面，每一个椭圆形区域均代表着一个包含在整个数 据集合中的一个数据点。可以在图3 5 中的找到其相对应的一个数据点，椭圆形边框内 的每个点代表这个数据点与某个查询点之同的权值距离即d i s t ( g t ，呦，图3 4 中每个椭 圆形区域中共包含了3 个点，他表示m i n - m a x 查询系统的当前时刻，存在着3 个查询点， 每个数据点与3 个查询点中的某个查询点之间的权值距离用图3 4 中椭圆形边框所包含 的某一个点来表示。在图3 4 的中间部分有个大的椭圆形区域，他代表着整个m i n 姗x 查询系统在当前时刻所有数据点所对应的呦xv a l l l c 值的集合，其中椭圆形边框所包含 的每一个点，在图3 4 的底层都会找到一个椭圆形区域所代表的数据点与之相对应，用 箭头来表示其对应关系，即椭圆形区域所代表的数据点指向代表他的姗xv a l 的那个 点，这个点的值等于他所对应数据点的椭圆形区域内进行m 觚运算所得的值。在图3 4 的最上方有一个点，他表示整个m i n m 觚系统当前时刻的m i nv a l u e ，通过对下层的m 戤 v a l l l e 集合进行m i n 运算所得到的结果。 这样，基本的i i l i n i n 积查询的计算过程既是从图3 4 的最低层开始，首先计算的是 某一个数据点到达所有查询点所需要的权值距离，然后取其中的最大值( m 觚、枷l l e ) 存储 到第二层中代表数据点的对应节点，然后在第二层计算所有节点所代表关于其数据点的 最大值所组成的集合中的最小值( m i nv a l u e ) ，从而得到最终的查询结果，该结果所对应 的数据点就是我们要找的m i n _ m a x 查询结果。图3 5 中数据点盔为图3 4 中m i n - 啦x 查 1 9 东北大学硕士学位论文第三章m i n x 查询 询的最终结果所对应的数据点。 9 1 + 囝西 囝函 。数据点 + 查询点 囝啦 囝 西 固 函 图3 5 m i n - m “查询结果 f 嘻3 5t h e 锄s w e ro f m i n - m 戤q u e 呵 3 3 问题定义 基于m i n m a 】【查询以及数据流的相关定义，下面给出本文将讨论的主要问题。 随着时间的推移，当前滑动窗口中的数据点时刻发生着变化，如何即时、高效、准 确的计算关于查询点在出当前时刻所对应的滑动窗口中数据点集合中的m i n v a l l l c ，将是 本文讨论的主要问题之一。 另外，随着时间的推移，有时候，查询点也会发生变化，在这种情况下