An efficient subscription index for publication matching in the cloud
- 格式：pdf
- 大小：1.11 MB
- 文档页数：11
Knowledge-Based Systems110(2016)110–120Contents lists available at ScienceDirectKnowle d ge-Base d Systemsjournal homepage:/locate/knosysAn efficient subscription index for publication matching in the cloudZongmin Cui a,∗,Zongda Wu b,∗,Caixue Zhou a,Guangyong Gao a,Jing Yu a,Zhiqiang Zhao a,Bin Wu ca School of Information Science and Technology,Jiujiang University,Jiujiang,Jiangxi,Chinab Oujiang College,Wenzhou University,Wenzhou,Zhejiang,Chinac School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan,Hubei,Chinaa r t i c l e i n f oArticle history:Received14January2016Revised10July2016Accepted11July2016Available online15July2016Keywords:Publish/subscribeMatchingPredicateIndexa b s t r a c tPublish/subscribe has been successfully used in a variety of information dissemination applications.How-ever,in a cloud computing environment,the enormous amount of information results in a very high re-quirement for the computing performance of a publish/subscribe method.In this paper,we propose anefficient index called Enindex for publish/subscribe matching.First,we group all the subscriptions sub-mitted by subscribers,based on the key attributes(i.e.,the most frequent attributes occurring in thesubscriptions).Second,we group all the predicates contained in the subscriptions,according to three ba-sic operators:≥(greater),=(equal),and≤(less),so as to remove the repeated predicates,and thus reducethe memory overhead.Finally,we propose an effective index structure to combine the grouped subscrip-tions together with the grouped predicates.Enindex not only has a small memory overhead,but also cansupport efficient publish/subscribe matching and online subscription updating.We conduct extensive ex-periments on synthetic datasets,and the experimental results demonstrate the superiority of the Enindexover state-of-the-art methods in terms of memory overhead and computing efficiency.©2016Elsevier B.V.All rights reserved.1.IntroductionToday,publish/subscribe(or P/S for short)systems are becom-ing increasingly popular and important,which have been success-fully applied in a variety of information dissemination applicationssuch as online advertising[17],stock market[21],e-commerce[30]and social network[31].A P/S system includes two roles:datapublisher and data subscriber.A publisher publishes data(such asfiles,pictures and videos)in the form of publications.A publicationcontains a group of predicates to describe the characteristics of itsassociated data.A subscriber online subscribes the data publishedby publishers.A subscription also contains a group of predicatesto describe what data the subscriber is interested in.The intercon-nection between the two roles can be achieved by a client/servermodel[15]or a distributed network[8,24].If a publication matchesa subscription,i.e.,their predicates match each other,the P/S sys-tem has to ensure a timely delivery of the data associated with thepublication to the subscriber.∗Corresponding author.E-mail addresses:cuizm01@(Z.Cui),zongda1983@(Z.Wu),charlesjjjx@(C.Zhou),gaoguangyong@(G.Gao),yujingellemma@(J.Yu),zq_zhao@(Z.Zhao),wubincs@(B.Wu).Recently,P/S systems have began to be widely used to cloudcomputing environments[1,12].However,the enormous amountof information on the cloud raises many new challenges.In cloudcomputing,there exist a large number of subscriptions and pub-lications,resulting in a high performance requirement for a P/Ssystem in terms of memory overhead and computing efficiency.Inaddition,the online arrivals of subscriptions also require the onlineupdating of subscriptions.P/S matching has been extensively stud-ied in the last one decade;however,most of existing P/S matchingmethods are not designed for cloud computing.As a result,theycannot satisfy the above requirements,thus difficult to be appliedto cloud computing environments immediately.For example,an index method called K-index is proposed in[26],where a predicate contained in a subscription often needsto be rewritten into a group of equality predicates,consequently,greatly increasing the number of predicates and the memory over-head,and in turn,reducing the efficiency of P/S matching.The BE-tree[11]is a state-of-the-art method,where the number of treenodes would increase with the increasing of predicate attributes.As the number of attributes increases,a BE-tree would generate alarge number of tree nodes,incurring an inefficient performanceon P/S matching.Recently,a two-level index method called Opin-dex is proposed in[30],which performs better than both K-indexand BE-tree in terms of computing efficiency.However,in Opindex,/10.1016/j.knosys.2016.07.0170950-7051/©2016Elsevier B.V.All rights reserved.Z.Cui et al./Knowledge-Based Systems110(2016)110–120111there still exist many repeated predicates,making the index struc-ture relatively complex,i.e.,the computing cost of its P/S matching needs to be further optimized.In short,Opindex still cannot well satisfy the performance requirements in cloud computing.In[10], a static index method on a road network is proposed,which can only support static P/S matching without taking into consideration the online updating problem of subscriptions.In order to meet the performance requirements of cloud com-puting for memory overhead and computing efficiency,in this pa-per,we propose an efficient subscription index called Enindex for P/S matching.First,we group the subscriptions based on the key attributes(i.e.,the most frequent attributes occurring in the sub-scriptions).Second,we group the predicates in the subscriptions, according to three basic relational operators(≥,=,≤),to remove repeated predicates and as a result improve the memory over-head.Finally,we build connections from the grouped subscriptions to the grouped predicates,consequently,generating the Enindex structure.Based on the index structure,P/S matching achieves bet-ter computing performance with much smaller memory overhead. Specifically,Enindex has the following four features:(1)it mini-mizes the computing cost of P/S matching;(2)it removes the re-peated predicates to minimize the memory overhead;(3)it divides normal P/S matching into disjunctive matching and conjunctive matching,thereby improving the computing efficiency of predicate judgement operations;and(4)it provides an effective update algo-rithm to online update the subscriptions.In addition,we conduct experimental evaluations to compare Enindex against state-of-the-art methods(K-index,BE-tree and Opindex)in terms of memory overhead,index construction,subscription update and computing efficiency.The rest of this paper is organized as follows.In Section2, we present the problem statement of P/S matching in cloud com-puting.In Section3,we describe the index structure of Enin-dex.In Section4,we discuss the improvement of the Enindex.In Section5,we compare the Enindex with existing methods by ex-periments.In Sections6and7,we review the related works and conclude this paper.2.Problem statementIn a P/S system,when subscribing data,a subscriber needs to use a boolean expression that consists of predicates to describe the subscription;when publishing data,a publisher also needs to use a boolean expression to describe the publication associated with the data.Finally,the P/S system performs P/S matching between all the subscriptions and each publication,and then timely delivers the data associated with each matched publication to the related subscribers.In this section,we present the system model that we use,and then formulate the problem that we study.2.1.System modelTo improve the computing performance of P/S matching,we propose an efficient subscription index method called Enindex.The system model of Enindex is presented in Fig.1,which consists of six modules(1)–(6).As shown in Fig.1,Enindex includes two roles:subscribers and publishers,whose processingflows are de-scribed as follows.•Subscriber.First,in the module(1),a subscriber submits sub-scriptions to a P/S system by using predicates to describe pub-lications interested him.Second,the module(2)selects a small number of key attributes from all the subscriptions,and then based on them,groups the subscriptions.Third,the module(3) groups the subscription predicates according to relational oper-ators(≥,=,≤),where the repeated predicates are removed soFig.1.The system model of Enindex.Table1A running example of subscriptions.s1A=2∧B=3s2A≤8∧C=6∧E≥2s3B≤4∧C=6∧E∈[2,9]s4B=3s5D≥8∧E≤9s6B=3∧C≤4∧D≥6as to reduce the memory overhead.Finally,the module(4)con-structs the index structure by adding pointers from the groupedsubscriptions to the grouped predicates.•Publisher.In the module(5),a publisher publishes data in the form of publications.A publication contains a group of equalitypredicates used to describe the characteristics of its associateddata.•P/S matching.The module(6)performs matching operations between all the subscriptions and each new publication,andtimely delivers the data associated with the publication to thesubscribers of the matched subscriptions.2.2.Publication matchingA predicate p is the most basic unit of a subscription,whichincludes an attribute p.a ttr,an operator p.o per and an operandp.o pnd.It can determine a boolean value(0or1)for any valuex of the attribute p.a ttr,denoted by p(x),which indicates whetheror not the predicate constraint of p is satisfied by x.For exam-ple,given a predicate p:A≥5,we have p.at t r=A,p.oper=≥,p.opnd=5,p(4)=0and p(5)=1.Here,p.o per can be all the re-lational operators(>,≥,=,=,<,≤).However,to simplify thepresentation,we below ignore the relational operators(>,=,<)due to their similarity to(≥,=,≤).In addition,a subscriptionis a combination of predicates in either conjunctive normal form(CNF)or disjunctive normal form(DNF).To simplify the presen-tation,we assume that a subscription is represented in CNF(DNFwill be discussed in Section4).Now,a subscription s that consistsof n predicates can be represented as s:(p1∧p2∧...∧p n). Example1.A set of subscriptions S={s1,s2,...,s6}is shown in Table1,which will be used as the running example in the rest ofthis paper.A publication supplied by a publisher is also a combination ofpredicates.However,each predicate in a publication includes onlyan equality operator.Hence,a publication b consisting of m equal-ity predicates can defined as b:(q1∧q2∧...∧q m).A publication also takes along with data,so all of its equality predicates are ac-tually used to describe the characteristics of its data.For example, given a product data r about iPhone and its associated publication112Z.Cui et al./Knowledge-Based Systems110(2016)110–120Table2A summary of notations.Notations Denotationsp A predicate that consists of an attribute p.a ttr,an operatorp.o per and an operand p.o pnds A subscription consisting of predicatesS All the subscriptions in the P/S systemb A publication consisting of equality predicates and associateddataB A set of publicationsa A key attributeA All the key attributes of SL(S)All the subscription lists from S grouped by AL(a)A subscription list corresponding to the key attribute a,i.e.,L(a)⊂L(S)P(S)All the predicate lists from S grouped by basic operators(≥,=,≤)b:(model=iphone6s∧color=pink∧price=900∧size=64G), if a subscription s matches b successfully,the product data r will be delivered to the subscriber who submits s.Formally,P/S match-ing can be defined as follows.Definition1(Publication Matching).A subscription s is called to match a publication b successfully(denoted by s∼b),if and only if s and b meet the following condition:∀p∃q(p∈s∧q∈b→p.at t r=q.at t r∧p(q.opnd)=1)A successful matching between a subscription s and a publica-tion b means that,(1)for each predicate p in s,there has to be a predicate q in b,which has the same attribute with p(i.e.,p.at t r= q.at t r);and(2)the operand q.o pnd(i.e.,the value of the attribute q.a ttr)meets the predicate constraint of p(i.e.,p(q.opnd)=1).For example,given a subscription s5:(D≥8∧E≤9),and two publi-cations b2:(D=10)and b3:(D=10∧E=5),s5does not match b2because the attribute E of s5does not appear in b2;however, s5matches b3because the two attributes D and E of s5both ap-pear in b3,and the operands10and5of s5respectively meet the predicate constraints(D≥8)and(E≤9).Now,the problem that we study in this paper can be defined as how to as efficiently as possiblefind out all the subscriptions from a large number of subscriptions S,which match a given publica-tion b successfully,i.e.,how to as efficiently as possible obtain the subscription set S∗={s|s∈S∧s∼b}.3.Index structureThis section shows the process of how to construct an index structure for the subscriptions S in advance,and how to perform publication matching based on the index structure.For conve-nience,Table2summarizes the key notations in this paper,which will be explained again as they are used.3.1.Subscription groupingIn order to minimize the number of candidate subscriptions participating in P/S matching,we present an effective approach to group the subscriptions S,based on the key attributes of the subscriptions.Therefore,the key attributes play an important role, which are from the most frequent attributes occurring in the sub-scriptions S.Definition2(Key Attribute).Given a set of subscriptions S,an at-tribute set A is the key attribute set of S,if and only if A meets the following three conditions:•For each subscription s∈S,there exists at least one corre-sponding attribute in A,which appears in the subscription s,i.e.,∀s∃p(s∈S∧p∈s∧→p.at t r∈A).•Let (a)denote the frequency of occurrence of an attribute a in all the subscriptions S.Then,∀s∀p1∀p2(s∈S∧p1∈s∧p2∈s∧p1.at t r∈A∧p2.at t r/∈A→(p1.at t r)≥(p2.at t r)),i.e., for each subscription s,the key attribute of s is the most frequent among all the attributes of s.•In the subscriptions S,there is no another attribute set A , which satisfies the above two conditions,and has a smaller size than A.Now,according to the key attribute set A={a1,a2,...,a n},the subscriptions S can be divided into n mutually disjoint subscription lists:L(S)=L(a1)∪L(a2)∪...∪L(a n)In the above formula,L(a i)denotes a subscription list related to the key attribute a i,that is,L(a i)={s|s∈S∧∃p(p∈s∧p.at t r=a i)}.From Definition1,we know that if s∼b, all the attributes occurring in the subscription s have to also ap-pear in the publication b.In other words,sࣁb,if s contains an attribute a that does not appear in b.Therefore,when perform-ing P/S matching,we only need to take into consideration the sub-scriptions whose key attributes appears in a publication b,instead of all the subscriptions S,consequently,effectively improving the computing performance.This is the motivation why we group the subscriptions.Algorithm1details the subscription grouping process,which takes a set of subscriptions S as input,and the grouped subscrip-tion lists L(S)as output.First,the algorithm selects a key attribute a by counting the frequency of occurrence of each attribute in S(Step3).Second,it represents each subscription based on the key attribute a(Steps4–5),i.e.,inserts each subscription into L(a). Third,it removes the represented subscription from S(Step6).Fi-nally,all the subscriptions represented by a are combined to a sub-scription list L(a),and then stored into L(S)(Step8).It can be seen that the time complexity of Algorithm1is equal to O(|S|),i.e., equal to the number of subscriptions.Example2.Fig.2shows two subscription lists constructed based on the subscriptions presented in Example1.Here,the input of the algorithm is S={s1,s2,...,s6}.In the first loop,B is the most frequent attribute,which appears4times in S,so it is selected as a key attribute.As a result,thefirst subscription list is L(B)={s1,s3,s4,s6}.In the second loop,S is changed to S={s2,s5},so E is another key attribute,and the sec-ond subscription list is L(E)={s2,s5}.Below,we illustrate how the grouped subscriptions are used to improve the P/S matching performance.For the subscriptions given in Example1,the key attribute set is A={B,E},and theAlgorithm1Subscription groupingInput:S,a set of subscriptionsOutput:L(S),the grouped subscription lists1:L(S)←2:while S= do3:select the attribute a that has the greatest frequency of oc-currences in S,and set L(a)←4:for all s∈{t he subscriptions that contain a}do5:insert s into L(a),i.e.,L(a)←L(a)∪{s}6:S←S−{s}7:end for8:insert the subscription list L(a)into L(S),i.e.,L(S)←L(S)∪L(a)9:end while10:return L(S)Z.Cui et al./Knowledge-Based Systems110(2016)110–120113Fig.2.The subscription lists.subscription lists are L(B)and L(E).Now,given a publication b4: (A=2∧E=6),because b4does not contain the attribute B,we conclude that all the subscriptions in L(B)are failed to match b4, i.e.,it is not necessary to perform matching operations between the subscriptions in L(B)and the publication b4.In other words, we only need to judge whether the subscriptions in L(E)match b4.Thus,we conclude that based on key attributes,the number of subscriptions participating in P/S matching can be reduced effec-tively,resulting in the improvement on computing performance. 3.2.Predicate groupingIn a P/S system,there are many subscriptions that contain the same predicates.In order to remove the repeated predicates and thus reduce the memory overhead,we present an effective ap-proach to divide the predicates that appear in the subscriptions S into several predicate lists,making the divided predicates different from each other.As a result,a predicate if appearing in a predicate list will never appear again in another predicate list.Formally,the predicate grouping can be defined as follows.Definition3(Predicate grouping).Given a set of subscriptions S, a set of predicate lists P is the predicate group of S(denoted by P(S))if meeting the following three conditions:•All the subscriptions in S are divided according to three basic relational operators(≥,=,≤),i.e.,there are three predicate lists in P altogether.•There is a connection from S to each predicate list in P.•Each predicate of S appears in P only once.Thus,the predicate group of S is represented as a combination of three predicate lists,which is shown as:P(S)=P(≥)∪P(=)∪P(≤)Algorithm2details the predicate grouping process.It takes a set of subscriptions S as input and the grouped predicate lists P(S) as output.Algorithm2groups a predicate p in a subscription ac-cording to the operator(≥,=,≤)corresponding to p.o per(Step5). Meanwhile,if a predicate has appeared in P(S),it would be not inserted into P(S)again(Step4).It can be seen that the time com-plexity of Algorithm2is O(n·|S|),where n denote the average number of predicates contained in each subscription.Example 3.Fig.3shows the predicate grouping result of Algorithm2for the subscriptions in Example1.It can be seen that for the predicate B=3that repeatedly ap-pears in the subscriptions s1,s4and s6,it would appear in the predicate list P(=)only once.Algorithm2Predicate groupingInput:S,a set of subscriptionsOutput:P(S),the grouped predicate lists1:P(≥)←P(=)←P(≤)←2:for all s∈S do3:for all p∈s do4:if p/∈P(≥)∪P(=)∪P(≤)then5:insert the predicate p into the list P(p.oper),i.e., P(p.oper)←P(p.oper)∪{p}6:end if7:end for8:end for9:build the pointers from S to P(≥),P(=)and P(≤)10:return P(≥)∪P(=)∪P(≤)Fig.3.The predicate lists.3.3.Subscription indexingAfter subscription grouping and predicate grouping,we cre-ate pointer connections from the grouped subscription lists to the grouped predicate lists,to combine them together,thereby,form-ing the subscription index structure.Algorithm3details the construction of a subscription index, which uses the grouped subscription lists L(S)and the grouped predicate lists P(S)as input,and the subscription index I S as out-put.First,Algorithm3creates a pointer connection from the sub-scription s to the predicate p(Step5).Second,it counts the num-ber of connections from s(Step6),and uses it as the count value of the node s.In Algorithm4,the publication matching is com-pleted only when the execution number of matching operations is equal to the count value(i.e.,count(s)).It can be seen that the sub-scription index consists of the predicate lists P(S),the subscriptionAlgorithm3Subscription index constructionInput:(1)L(S),the subscription lists;and(2)P(S),the predicate listsOutput:I S,the subscription index1:combine L(S)and P(S)to form an initial subscription index, noted as I S2:for all s∈L(S)do3:update the index I S by setting count(s)←04:for all p∈s∧p∈P(S)do5:update I S by adding a pointer from s to p6:update I S by setting count(s)←count(s)+17:end for8:end for9:return I S114Z.Cui et al./Knowledge-Based Systems110(2016)110–120Algorithm4Publication matchingInput:(1)I S,the subscription index;and(2)B,a set of publica-tionsOutput:R,the set of subscribed data1:R←2:for all b∈B do3:for all a∈A∧a appearing in b do4:for all s∈L(a)do5:for all q∈b do6:for all p∈s do7:if p.at t r=q.at t r∧p(q.opnd)=1then8:count(s)←count(s)−19:end if10:end for11:end for12:if count(s)=0then13:add the data r i associated with b into R14:end if15:end for16:end for17:end for18:return RFig.4.The subscription index.lists L(S)and the pointer connections from L(S)to P(S).In addi-tion,the execution number of the condition judgement in Step4 is equal to n·|S|,where n denote the average number of pred-icates contained in each subscription,so the time complexity of Algorithm3is equal to O(n·|S|).Example4.Fig.4shows the subscription index constructed from the subscriptions in Example1.First,Algorithm3adds pointers from each subscription to its each predicate.Second,the algorithm counts the number of predi-cates for each subscription.The index structure is a preparation for the next step of publication matching.3.4.Publication matchingIf a subscription s matches a publication b successfully(i.e.,s∼b),the data associated to b should be delivered to the subscriber of s.Algorithm4shows the matching process between a set of sub-scriptions and a set of publications,which takes the subscription index I S and a set of publications B as input.Meanwhile,it outputs a set of subscribed data R.In Algorithm4,for each publication b,wefirst obtain its key at-tribute a(Steps2–3).If b does not contain any key attribute(Step 3),then b cannot match any subscription;otherwise,we conduct matching operations between b and each subscription s in the sub-scription list L(a)(Steps4–6).Meanwhile,if a publication predi-Table3A set of publications.Data Publication Equality predicatesr2b2D=10r3b3D=10∧E=5r4b4A=2∧E=6r5b5B=1∧C=6∧E=5cate q in b matches a subscription predicate p in s successfully, the count value count(s)subtracts1(Step8).Finally,if count(s)is equal to0,then it indicates that s matches b successfully,and we store the data associated with b into R(Step13).It can be seen that the time complexity of Algorithm4for matching all the pub-lications in B is equal to O(|B|·n1·n2·n3),where n1,n2and n3 denotes the average size of each subscription list in L(S),the av-erage size of each publication in B and the average size of each subscription in S,respectively.Example 5.Table3presents a set of publications B.The P/S matching result between Tables1and3is R={r3,r5}.Below,we illustrate how to conduct matching operations between publications and subscriptions.Here,the input of Algorithm4is the subscriptions in Table1and the publications in Table3.First,since b2includes no key attribute,it cannot match any subscription.Second,b3includes a key attribute E, so Algorithm4conducts matching between each subscription in L(E)={s2,s5}and b3.As a result,s5is successful to match b3but s2is failed to match b3.Thus,R={r3}.Third,b4cannot match any subscription.Fourth,b5includes all the key attributes B and E,so Algorithm4has to judge all the subscriptions.As a result,s3 matches b5.Thus,R={r3,r5}.From Algorithm4and Example5, we can see that for any given subscription s,Algorithm4searches all the publications in the system to obtain the matched ones, where a publication b matches the subscription s successfully if and only if all the predicates of b matches s successfully.In other words,Algorithm4can return all the matched publication for any subscription.3.5.Subscription updatingIn cloud computing,the online arrivals of subscriptions raises the problem of online updating subscriptions.Thus,the Enindex structure needs to support online updating of subscriptions,i.e., subscription addition and subscription deletion.A subscription ad-dition operation needs to insert a subscription into the Enindex structure.A subscription deletion operation needs to delete the related nodes and pointers from the Enindex structure.Thus,the subscription updating actually means the updating for the Enindex structure.Algorithm5details the subscription updating process,whose inputs are the subscription index I S,an update operatorδ(“addi-tion”or“deletion”)and an subscription s that needs to be updated. Then,the algorithm outputs the updated subscription index I S.In Algorithm5,for a subscription deletion operation(Steps1–7),if there is no any subscription pointing to p,p is useless,so we delete p and the pointer from s to p(Steps4–5).For a subscription ad-dition operation(Steps8–16),if s can be inserted into an existing subscription list,we only need to add related nodes and pointers (Steps10–11);otherwise,we have to create a new subscription list (Steps13–15).In addition,we can see that for a deletion operation or an addition operation,Algorithm5only needs to update the in-put subscription s and its associated nodes and pointers,so the time complexity of Algorithm5is equal to O(n),where n denotes the average number of predicates of a subscription.Z.Cui et al./Knowledge-Based Systems110(2016)110–120115Algorithm5Subscription updatingInput:(1)I S,the subscription index;(2)δ,a subscription updateoperator;and(3)s,an updated subscriptionOutput:I S,the updated subscription index1:ifδ=“deletion”then2:for all p∈{t he predicates pointed from s}do3:if there is no any other subscription pointing to p then4:delete p and the pointer from s to p5:end if6:end for7:S←S−{s},and update I S8:else9:if∃p∈s∧∃a∈A∧a=p.at t r then10:L(a)←L(a)∪s11:update I S by adding related nodes and pointers12:else13:S←S∪{s}14:select an attribute from s as the key attribute a15:update I S by adding a new subscription list L(a )16:end if17:end if 18:return IS,the updated subscription indexFig.5.The example of subscription updating.Example 6.For the subscriptions in Table1,the subscriberfirst deletes the subscription s3and then adds a new subscription s7:D ≥6.The updated index is shown in Fig.5.Below,we illustrate the above index updating process.First, Algorithm5performs the operation of deleting the subscription s3.Note that there are four predicates pointed from s3,i.e.,E≥2,C=6,B≤4and E≤9,where there is no subscription point-ing to B≤4.Thus,we need to delete s3and B≤4.Meanwhile, we should update the index by deleting the related pointers.Sec-ond,Algorithm5performs the operation of adding a subscription s7:D≥6.As D/∈A,A←(A∪{D}={B,D,E}).Thus,we add a new subscription list L(D).As the predicate D≥6already exists in the index,we only add a pointer from s7to D≥6.4.Index improvementIn Section 3.1,we use a simple strategy for the subscription grouping.In Section3.2,we only consider CNF.Thus,this section aims to improve the Enindex structure by using balance parame-ters and disjunctive operators.4.1.Balanced subscription groupingLet|S|be the total number of subscriptions,|A|the number of key attributes,and|L(A)|the average number of subscriptions inFig.6.The subscription grouping based on the parameters(|A|,|L(A)|).each subscription list of S.Enindex and Opindex both use a two-level index structure.However,Enindex minimizes|A|to increase |L(A)|,and Opindex maximizes|A|to decrease|L(A)|.Thus,thecomputing costs of matching a publication in Enindex and Opindex are both equal to the maximum value of|A|and|L(A)|,i.e.,=O(m ax(|A|,|L(A)|))It is known that ≥|S|,i.e.,if|A|=|L(A)|=|S|,the computing cost obtains the minimum value.Thus,to mini-mize ,we improves Enindex based on two balance parame-ters(|A|,|L(A)|).The process of improved subscription grouping is shown in Fig.6,which is based on the following two rules.•When updating subscriptions,we should balance the parame-ters|A|and|L(A)|as much as possible through maximizing or minimizing|A|.•When updating subscription lists,we should make the size of each subscription list as close to|L(A)|as possible,i.e.,a subscription should be inserted into a subscription list of the smallest size.4.2.Disjunctive operation processingIn a P/S system deployed on a cloud computing environment, there are often many collection operations(e.g.,B={3,6,9}).In the Enindex structure,a collection operation needs to be rewritten to a group of disjunctive operations,so as to support the collection operation.For example,B={3,6,9}should be rewritten to B=3∨B=6∨B=9.To keep compatibility with the proposed method,we divide the pointers in the Enindex structure into two types.A pointer point-ing to a conjunctive predicate continues to be painted by a black dotted line with arrow;however,we use a colorized line to de-note a pointer from a subscription(that contains disjunctive oper-ations).The same set of disjunctive operations use the same color.A set of colorized lines with the same color from a subscription only increases the count value of the subscription by one.During the publication matching,the count value of a subscription sub-tracts one if and only if at least one predicate connecting to the set of same color lines matches the publication successfully. Example7.For the subscription index shown in Fig.5,after in-serting a new subscription s8:(B={3,6}∨E≥2)∧(A≤8∨D≥6)∧c≤4,the updated subscription index is shown in Fig.7.Since s8includes all the key attributes and L(D)is the subscrip-tion list with the smallest size(because|L(D)|=1),we insert s8 into L(D).In s8,only B=6does not exist in the index,thus we add it into the index.In s8,there are two sets of disjunctive op-erations.Thus,there are two colors for(B={3,6}∨E≥2)and (A≤8∨D≥6)respectively.Finally,there are three conjunctive。
