| 主权项 |
1. 一种在无线数据广播环境下的空间关键字检索的方法，其特征在于具体步骤如下：（1）对服务器端的文档进行预处理：对于服务器端的<i>N</i>个文档<i>D</i>={<i>d</i><sub>1</sub>, <i>d</i><sub>2</sub>, …,<i> d</i><sub><i>N</i></sub>}，每个文档<i>d</i><sub><i>i</i></sub>都包含位置信息<i>loc</i><sub><i>i</i></sub>以及文本信息<i>text</i><sub><i>i</i></sub>，其中，位置信息<i>loc</i><sub><i>i </i></sub>= (<i>x</i>,<i> y</i>)，表示文档所在位置的经纬度，文本信息<i>text</i><sub><i>i</i></sub>由若干个关键字（单词）组成；依次读取每个文档<i>d</i><sub><i>i</i></sub>的位置信息和文本信息，建立一种基于网格索引与倒排表结合的索引<i>I</i>；索引<i>I</i>分为两层：第一层为网格索引，第二层为倒排表；（2）以步骤(1)建立的索引<i>I</i>，通过无线信道，将索引<i>I</i>和文档集合周期性地广播；（3）移动终端提出空间关键字查询请求<i>Q</i> (<i>loc</i><sub><i>q</i></sub>, <i>text</i><sub><i>q</i></sub>, <i>radius</i>)：<i>loc</i><sub><i>q</i></sub>表示查询点的位置，<i>text</i><sub><i>q</i></sub>表示用户提交的关键字集合，要求返回距离查询点不超过<i>radius</i>，且包含的所有关键字<i>text</i><sub><i>q</i></sub>文档集合，即<i>Q</i>(<i>loc</i><sub><i>q</i></sub>, <i>text</i><sub><i>q</i></sub>, <i>radius</i>) =<img file="201210346215X100001DEST_PATH_IMAGE002.GIF" wi="357" he="30" />，其中<i>dist</i>(<i>loc</i><sub><i>q</i></sub>, <i>loc</i><sub><i>i</i></sub>)表示<i>loc</i><sub><i>q</i></sub>和<i>loc</i><sub><i>i</i></sub>之间的直线距离；（4）移动终端访问协议：（a）移动终端下载索引的第一层，即网格划分索引；通过网格索引，用户首先计算与查询区域有交叉的网格；（b）基于阶段（a）的结果，客户端将所有交叉的网格按下一次广播时间排序，然后等待第一个交叉的网格被广播，在等待过程中保持休眠状态；当第一个交叉的网格被广播时，用户进入信道，获取该网格的倒排表，通过倒排表，获得该网格内包含查询关键字的文档（以下称这些文档为候选文档）的下一次广播时间，进而获取该网格内的所有获选文档（在等待候选文档时同样保持休眠状态）；接着，重复以上过程，直至获取所有交叉的网格的候选文档；（c）在获取所有候选文档之后，客户端在本地进行确认，即对于每个候选文档，计算该文档到查询点的距离，进而获取最终精确结果。 |
