中文摘要：

无线数据广播是移动数据管理领域的重要研究分支，具有极大的市场潜力。传统的无线数据广播研究专注于"平坦数据（flat data）"，对于带结构信息的XML数据和查询，已有技术无法支持。把XML引入数据广播领域引出一批亟待解决的新问题，我们从索引和调度这两个基本方面开展研究，包括 (1) 提出并研究一套全新的XML空中索引解决方案。以在广播信道中实现高效的结构信息查询为目标，从索引基本结构的设计和优化开始，研究新的索引组织和索引分布技术，以及高效的索引生成方法。 (2) 拓展传统广播调度的研究范围，突破传统广播调度中的数据项原子性假设，以消除广播文档中的冗余信息、提高调度性能为目标，分析冗余信息，提出并研究文档剪枝、分割与合并等新的调度优化技术。

结论摘要：

无线数据广播是移动数据管理领域的重要研究分支，具有极大的市场潜力。随着技术发展和应用推动，无线数据广播信道中的数据从最初的关系型数据，扩展到以XML为代表的树数据和以道路网络为代表的图数据等新型的非结构化数据，引出一批亟待研究解决的新问题。本项目以XML格式数据为重点，研究树数据和图数据的数据广播及相关技术，取得的主要成果如下（1）以XML格式数据为代表，提出一套全新的树数据的空中索引解决方案。从索引基本结构的设计和优化开始，研究新的索引组织和索引分布技术。提出了一套全新的On-demand模式下的索引分布策略，采用两层索引结构和部分复制策略，降低访问时间和调谐时间的综合代价，适用于一般的多数据项广播场合，是继著名的(1, m)索引分布策略后广播索引技术领域的一个重要突破。首次提出把查询（而不是数据）作为索引，并且根据数据广播信道的特点，对XPath查询中的“*”和“//”操作做预处理为一个普通的DFA节点，兼具了DFA查询时无分支和NFA尺寸小的特点。（2）突破传统数据广播调度中的数据项原子性假设，拓展了数据广播调度的研究范围。传统上，数据项是最小调度单位，广播调度的核心工作是优化数据项的出现频率和顺序，使得平均访问时间最小。在XML查询语义下查询结果可能是文档分支而非完整文档。如直接广播这些XML文档，从用户查询角度就含有冗余信息。我们把冗余信息按照语义归纳为三类无匹配分支冗余、部分匹配分支冗余和文档间结构信息冗余。突破数据项原子性假设，以消除广播文档中的冗余信息从而提高调度性能为目标，提出并实现了文档剪枝、分割与合并三种新的调度优化技术。这些技术可以叠加使用，也可以和已有数据广播调度算法结合。（3）图数据广播及其相关技术研究。图数据广播的核心是，如何把图数据转变为适合广播特点的流数据形式。我们围绕路网上的基础空间查询问题开展研究，在无线数据广播信道下分别支持最短路查询和邻近查询。采用树分解方法结合Hilbert曲线优化支持最短路查询，在调谐时间和CPU开销上均优于已有工作。采用划分区域分治的索引支持邻近查询，访问时间和调谐时间均优于已有工作，并且可以根据数据集的特点选择不同的区域划分方法。同时我们对相关的空间数据库技术进行研究，在一些方面取得了领先同行的研究成果，如目前性能最好的路网轨迹压缩算法、精度最高的地图匹配算法、速度最快的ANN算法。