1.一种基于物联网数据流滑动窗口模型的快速区间查询方法，其特征在于，包括如下步骤：

1)在服务器中建立基于(ε,L)‑ARE‑problem的数据结构D，所述数据结构D在任意时间点t，t＞0，使用的内存位的数量为所述数据结构D包括4个独立的哈希函数hj，j∈{1,2,3,4}，以及与哈希函数分别对应的

4个哈希表Bj，j∈{1,2,3,4}；其中，每个哈希表包含g个桶，g＝{1,...,n/24}，g∈N*；每个桶包含8个槽，记为s[q]，q＝{1,2,...,8}；

↑ ↓

任一槽s[q]包括三部分：s.Fp、s.P 和s.P ，s.Fp用于存储物联网数据流δ中对应元素的↑

指纹；s.P 用于存储指向链接的单元格列表的指针，该指针首先按照时间戳的升序排列，然↓

后按偏移值的升序排列；s.P 用于存储指向链接的单元列表的指针，该指针首先按照时间戳的升序排列，然后按偏移值的降序排列；

↑ ↓

对于链接的单元格列表中的任一单元格，记为c，由s.P 或s.P 指向，包含三个部分：c.Ts，c.O和c.Pt，其中，c.Ts用于存储物联网数据流δ中对应元素的时间戳；c.O用于存储对应元素在物联网数据流δ中的偏移量；c.Pt用于存储指向该链接的单元格列表的下一个单元格的指针；

t

对于在时间点t，物联网数据流δ连续生成的n个最新元素中的任一元素e ，采用 表示t

元素e 所在块的值， 哈希函数hj使用 作为其关键字，映射到其对应哈希表中的位置，记为

所述数据结构D还包括一个独立的哈希函数f，f的使用范围为 对于在时t

间点t，物联网数据流δ连续生成的n个最新元素中的任一元素e ，通过哈希函数f产生这个元素的指纹，记为

2)在时间点t，输入查询区间I＝[a,b]，通过数据结构D判断查询区间I的端点元素a、b分别与滑动窗口W(t,n)的交集是否为空集；

B

首先，判断端点元素a：设置元素a的时间戳，记为Tt；设置元素a所在块的值，记为a ；设O

置元素a所在块内偏移量，记为a ；生成端点元素a在4个哈希表中散列桶的位置，Bj[hjB B

(a)]，以及生成元素a的指纹f(a)；

B ↓

当哈希表中4个散列桶中存在一个槽，记为s[a]，使得s.Fp＝f(a)，设置c为s.P 指向链接的单元格列表的第一个单元格，并且当c≠NULL，c.Ts≤(t mod n)，设置c指向c的下一个单元格指针，则当元素a在物联网数据流δ中偏移量大于其块内偏移量时，判定端点元素a与滑动窗口W(t,n)的交集不为空集；

B O

其次，判断端点元素b：设置元素b所在块的值，记为b；b所在块内偏移量，记为b ；生成B B

端点元素b在4个哈希表中散列桶的位置，Bj[hj(b)]，以及生成元素b的指纹f(b)；

B ↑

当哈希表中4个散列桶中存在一个槽，记为s[b]，使得s.Fp＝f(b)，设置c为s.P 指向链接的单元格列表的第一个单元格，并且当c≠NULL，c.Ts≤(t mod n)，设置c指向c的下一个单元格指针，则当元素b在物联网数据流δ中偏移量大于其块内偏移量，判定端点元素b与滑动窗口W(t,n)的交集不为空集；

当查询区间I的两个端点元素a、b与滑动窗口W(t,n)的交集均为空集时，查询区间

2.根据权利要求1所述的基于物联网数据流滑动窗口模型的快速区间查询方法，其特征在于，所述数据结构D支持数据插入，所述数据插入过程为：t t

在时间点t，物联网数据流δ连续生成的n个最新元素中的任一元素e ，元素e 所在块的t

值为 设置元素 e 的时 间戳 ，记为 存储 于环绕计 数器中 ，且t

设置元素e 所在块内偏移量，记为t B t B

生成元素e在4个哈希表中散列桶的位置Bj[hj(et)]和元素e的指纹f(et)；

B ↑

如果4个散列桶中存在一个槽s[q]使得s.Fp＝f(et)，设置s.P 指向的链接单元格列表↓

中的第一个单元格为c1、s.P指向的链接单元格列表中的第一个单元格为c2；

当c1≠NULL， 或c1.Ts≤(t mod n)时，则删除c1.Pt指向的子列表中的单元格，否则，将c1指向c1的下一个单元格指针；

当c2≠NULL， 或c2.Ts≤(t mod n)时，则删除c2.Pt指向的子列表中的单元格，否则，将c2指向c2的下一个单元格指针；

B

如果4个散列桶中不存在一个槽s[q]使得s.Fp＝f(et)，则在4个散列桶中找到空闲槽最小的桶，断开该空闲槽与相邻被占用的空闲槽的连接，生成两个新的单元格，分别记单元↑ ↓ B

格c1和c2，同时设置s.P指向c1，s.P指向c2，设置s.Fp＝f(et)；

当c1≠NULL且c2≠NULL时，设置 和c1.Pt＝NULL，设置和c2.Pt＝NULL。

3.根据权利要求2所述的基于物联网数据流滑动窗口模型的快速区间查询方法，其特征在于，所述数据结构D支持数据更新，所述数据更新过程为：t

当物联网数据流δ在时间点t新到达的元素e 插入数据结构D后，如果t mod n≠0，则元t

素e停止更新；

↑

如果t mod n＝0，则对于四个哈希表的任一桶中的任意一个槽：设置c为s.P指向链接的单元格列表的第一个单元格，当c≠NULL，如果c.Ts≤n，则删除c和c.Pt所指向的子列表，↓

否则，c＝c.Pt；设置c为s.P 指向链接的单元格列表的第一个单元格，当c≠NULL，如果c.Ts≤n，删除c和c.Pt所指向的子列表；否则，c＝c.Pt。

4.根据权利要求3所述的基于物联网数据流滑动窗口模型的快速区间查询方法，其特征在于，所述数据结构D对任意长度不超过L的查询区间的空查询、数据插入和数据更新均具有常数时间成本。