一种面向社交活动组织的时间聚合查询方法

摘要

.一种面向社交活动组织的时间聚合查询方法，包括下列步骤：步骤1.建立索引结构SB*-Tree；步骤2、SB*-Tree的具体操作；步骤3.查询，具体包括获取参与时间区间、获得候选方案、最优方案选择。本发明为了能够更有效地解决“确定聚会时间难”的问题，基于现有的SB-Tree，对它的结构进行拓展，提出了一种新的索引结构和查询技术，能够有效地解决上述提出的三个问题。本发明最终实现的功能是能够根据参与人员自己提交的意向时间，为聚会活动提供最优的举办时间，能够保证最多的人员参加活动。而人数的计算采用count聚合函数。

主权项

一种面向社交活动组织的时间聚合查询方法，包括下列步骤：步骤1.建立索引结构SB*‑Tree针对SB‑Tree进行拓展，建立SB*‑Tree树形数据结构；SB*‑Tree与SB‑Tree不同的是：SB*‑Tree中每个时间区间N.I_i增加了其对应的参与人员ID的集合N.s_i；SB*‑Tree树包含一个最大分支因子b和最大叶子容量l；SB*‑Tree的中间节点最大能够包括b个时间区间，叶子节点最多能够包括l个时间区间，它们共同决定了SB*‑Tree的布局；关于SB*‑Tree的结构的详细描述如下：首先，表1列举了结构中使用的符号，如下所示：表1符号列表1.1中间节点：每个中间节点有三层结构，分别为N.t_i、N.v_i、N.s_i，另外还有一个指向子树的指针N.c_i；每个中间节点最多能够表示b个连续的时间区间，并且要保证该节点至少是半满的，即至少表示个时间区间；假设一个中间节点N表示了j个时间区间，分别为N.I₁，N.I₂，N.I₃，……，N.I_j；节点中存储了j‑1个不同的时间点，分别为N.t₁，N.t₂，N.t₃，……，N.t_j‑1；其中N.t_i表示第i个区间的结束时间，也是i+1个区间的开始时间；同时每个时间区间N.I_i都有对应的参与人数N.v_i，参与人员的ID的集合N.s_i和指向下一个子节点的指针N.c_i；1.2叶子节点叶子节点最多能够表示l个连续的时间区间，并且必须至少表示个时间区间；其结构与中间节点类似，也有三层结构，分别为N.t_i、N.v_i、N.s_i，只是没有指向下一个子节点的指针；1.3根节点根节点的结构与中间节点相同，同时最多能够表示b个连续的时间区间，但是最少只要表示2个时间区间即可；1.4节点性质对于每个非叶子节点N，所有在以N.c_i为根的节点中的瞬时时间点都要严格小于N.t_i,同时以N.c_i+1为根的节点中的所有瞬时时间点都要严格大于N.t_i；步骤2、SB*‑Tree的具体操作2.1区间定义：考虑第i个时间区间N.I_i，N.I_i的开始时间记为start(N.I_i)，结束时间记为end(N.I_i)；2.1.1 start(N.I_i)的取值如下：如果i>1，start(N.I_i)＝N.t_i‑1；如果i＝1且N为根节点，start(N.I_i)＝‑∞；如果i＝1且N有父节点N′，而且N′的第k个指针指向N，即N′.c_k＝N,则start(N.I_i)＝start(N′.I_k)2.1.2 end(N.I_i)的取值如下：如果i<j，end(N.I_i)＝N.t_i；如果i＝j且N为根节点，end(N.I_i)＝+∞；如果i＝j且N有父节点N′，而且N′的第k个指针指向N，即N′.c_k＝N,则end(N.I_i)＝end(N′.I_k)；2.1.3区间的定义如下：如果start(N.I_i)≠‑∞，则区间表示为[start(N.I_i),end(N.I_i))如果start(N.I_i)＝‑∞，则区间表示为(‑∞,end(N.I_i))2.2插入：假设插入一条记录<I,name>，name表示用户的唯一标识，I表示用户的空闲时间；我们调用过程Insert(N,<I,name>)来完成插入操作，Insert(N,<I,name>)表示向以N为根的子树中插入<I,name>；Insert(N,<I,name>)的具体操作为：对于所有满足的i，(1)如果那么其区间对应的参与人数加1，参与人员集合添加该name(2)如果且N是叶子节点，则将要插入的记录添加到该节点，修改相应值；(3)如果且N不是叶子节点，调用过程Insert(N.c_i,<I,name>)；2.3删除：假设删除一条记录<I,name>，name表示用户的唯一标识，I表示用户的空闲时间；删除操作与插入操作类似，我们记为delete(N,<I,name>)具体操作如下：对于所有满足的i，(1)如果那么该区间对应的参与人数减1，参与人员集合删除该name；(2)如果且N是叶子节点，则在该节点删除相应信息；(3)如果且N不是叶子节点，调用过程delete(N.c_i,<I,name>)；2.4节点分裂：之前提到每个节点都有最大的容量，所以当该节点表示的时间区间过多时，就会导致溢出，此时需要进行节点分裂操作；因为插入的时间区间都是添加到叶子节点的，所以首先是叶子节点会发生溢出；当叶子节点执行完分裂操作后，可能会导致其父节点溢出，则进行父节点的分裂操作；假设当节点N发生溢出时包含了n个时间区间，则当N为叶子节点时，n＝l+1或n＝l+2；当N为非叶子节点时，n＝b+1；将节点N的分裂过程记为split(N)，具体操作如下：241)将节点N分裂成N₁和N₂242)N₁包含前一半的区间，即N₁包含N.t₁,……,以及对应的参与人数N.v₁,……,和参与人员集合N.s₁,……,如果N不是叶子节点，N₁还要包含N.c₁……,243)N₂包含剩余的区间，即N₂包含……，N.t_n‑1以及对应的参与人数……，N.v_n和参与人员集合……，N.s_n如果N不是叶子节点，N₂还要包含……，N.c_n244)如果N是根节点，那么创建一个新的根节点N_root，其中并且指向N₁和N₂245)如果N不是根节点，假设N有父节点N'，并且N′.c_j＝N，则前j‑1个区间保持不变，从第j+1个区间到最后的区间往右移一位；再令N′.c_j＝N₁，N′.c_j+1＝N₂如果N′溢出，则调用split(N′)2.5区间合并和节点合并当发生插入或者删除操作后，可能会出现两个相邻区间的参与人数是相同的并且参与人员都相同的情况，这时就需要将两个相邻区间进行合并；区间合并分为两种情况：(251)两个相邻的区间在同一个叶子节点中，假设它们分别为N.I_j和N.I_j+1，那么有N.v_j＝N.v_j+1，N.s_j＝N.s_j+1，后进行如下操作：2511)删除N.t_j,N.v_j+1和N.s_j+12512)从第j+2个区间到最后的区间往前移一位2513)如果节点N经过合并后包含的区间少于调用nmerge(N)(252)两个相邻的区间在两个相邻的叶子节点中，因为这种情况比较复杂，且不容易出现，暂不作考虑；区间合并后，可能会使叶子节点达不到半满状态，此时需要进行节点合并来防止这种情况发生；节点合并的策略是：如果非根节点没有达到半满状态，首先从包含时间数量超过容量一般的相邻节点中移动一个时间区间到该节点；如果不存在这样的有“多余”时间区间的节点，那么就将该节点与其相邻的节点进行合并；记节点合并的过程为nmerge(N)，具体操作如下：2521)如果N是根节点并且N有且仅有1个子节点，那么将N.c₁作为新的根，删除原来的根节点N2522)如果N不是根节点，假设N最多能够包含n个时间区间(如果N是叶子节点，n＝l；如果N是非叶子节点,n＝b)；现在N包含了个时间区间，接下来判断N的兄弟节点的情况；2523)如果N的右边兄弟节点N_right包含了至少个时间区间，那么就把N_right的第一个区间添加到N中去；2524)如果N的左边兄弟节点N_left包含了至少个时间区间，那么就将N_left的最后一个区间添加到N开头中去；2525)进行两个节点的合并；假设这两个节点分别为N₁和N₂，N₁为左节点，N₂为右节点；假设N₁包含j₁个时间区间，N₂包含j₂个时间区间；j₁和j₂中其中一个为假设N_p是N₁和N₂共同的父节点，并且N_p.c_k＝N₁，N_p.c_k+1＝N₂，将N₁和N₂合并为一个新的区间N_new，N_new包含了j₁+j₂个时间区间，并删除N₁和N₂；在N_p中，将N_p.I_k和N_p.I_k+1合并成一个区间，并指向N_new；如果节点N_p包含的区间少于调用nmerge(N_p)步骤3.查询为了获得活动组织的最优时间结果，需要进行三个步骤的操作：3.1获取参与时间区间这一步中，通过遍历SB*‑Tree，可以得到所有时间区间以及对应的参与人数和参与人员(统称为区间信息)；遍历的方法为：从树的根节点出发，沿路径遍历到每一个叶子节点；当沿一条路径遍历到一个叶子节点N_leaf时，沿从根节点到叶子节点的路径，将路径上每个节点上节点N对应某一特定的N.v_t和N.s_t都加到叶子节点N_leaf的所有N_leaf.v_i和N_leaf.s_i上，其中t由路径确定。然后输出所有区间N_leaf.I_i，N_leaf.v_i，N_leaf.s_i3.2获得候选方案根据第一步得到的时间区间可能不满足最小持续时间duration；所以为了得到满足活动最小持续时间duration的候选方案，需要对遍历SB*‑Tree树得到的时间区间信息进行判断和调整，将区间大小小于duration的区间与相邻区间进行合并，使新的区间能够满足duration；具体操作如下：假设遍历SB*‑Tree后得到了m个时间区间，分别为I₁，I₂，…，I_m，它们按从小到大的顺序排列；每个区间I_i对应着它的区间信息：参与人数I_i.V和参与人员I_i.S；i＝1开始：如果I_i的大小≥duration，直接输出I_i，I_i.V和I_i.S；如果I_i的大小<duration，则与后面的区间进行合并，直到合并的新区间的大小满足duration；3.3最优方案选择通过第二步得到所有候选方案后，根据快速排序将所有方案按照人数从多到小进行排序，返回最优的时间方案；同时根据用户需要，也可以返回TopK的方案。