主权项 |
1.一种实时移动空间关键字近似Top-k查询方法,其特征在于包括以下步骤:Step1查询点q发送查询关键字、ε,δ给服务器,服务器执行剪枝方法,获得候选集合CR;Step2设t-1时刻,将CR中的数据对象随机划分成L个子域,记录每个子域中对象数量m<sub>j</sub>,根据ε,δ及<img file="FDA00002728072000011.GIF" wi="142" he="55" />确定样本容量|S|,服务器随机产生|S|-k个1~L之间的自然数,记为Y<sub>1</sub>,Y<sub>2</sub>,…,Y<sub>|S|-k</sub>,对任意Y<sub>i</sub>(1≤i≤|S|-k),<img file="FDA00002728072000012.GIF" wi="437" he="112" />其中1≤j≤L,对任意j(1≤j≤L),服务器计算产生的随机数中等于j的个数并记为s<sub>j</sub>,并根据历史信息计算阈值ζ,即<img file="FDA00002728072000013.GIF" wi="511" he="114" />其中,ζ<sup>t-1</sup>表示抽样后返回该时刻的查询结果,并向Z<sub>j</sub>子域发送(m<sub>j</sub>,s<sub>j</sub>,ζ),1≤j≤L;Step3当子域Z<sub>j</sub>接收到服务器发送的(mj,s<sub>j</sub>,ζ)时,该子域向服务器发送t-1时刻按降序排列的数据及对应对象ID,每个子域计算<img file="FDA00002728072000014.GIF" wi="416" he="62" />中大于等于<img file="FDA00002728072000015.GIF" wi="98" he="88" />的个数,并向服务器传送数据信息;Step4服务器接收各子域数据后,输出该时刻前k个最大值及其对应的数据对象。若查询q关键字已经修改,转Step1,若收到可用数据继续执行。 |