移动计算环境下非确定数据的索引与查询方法研究

摘要

在移动对象数据库的研究中，如何建模、索引并查询移动对象的位置信息是一个很重要的问题，学者们对此进行了大量研究，并提出了许多空间对象和时空对象的索引方法。但是传统的方法并不能支持此类数据的一个重要应用特性——非确定性，如何对非确定性数据进行查询处理成了数据库研究人员关注的焦点。在移动计算环境中，受限于测量设备误差，数据更新延迟，取样失真等因素，中心数据库很难全程记录移动对象的准确位置信息，鉴于传统的移动对象索引方法和查询处理技术均假设数据库中的数据是精确的，因此这些技术不能直接应用到非确定数据的索引和查询，或者效率极低，这就给研究者提出了新的问题和挑战。
　　 U 树是具有代表性的一种非确定对象空间索引方法，它是在R*树基础之上融合了数据非确定性的变种。U 树固有的良好动态结构，这使它不仅可以支持非确定数据对象以任何次序更新或插入，而且其提出的域查询处理算法不局限于非确定数据本身的概率密度分布函数。但U 树本身只是针对非确定静止对象的索引，并不能支持非确定移动对象的索引或执行效率甚微。
　　 基于移动计算环境，针对如何支持频繁位置更新的非确定移动对象当前及未来位置索引的问题，在基本U 树结构上增加了记录移动对象非确定状态特征的数据结构，通过利用概率密度分布函数描述移动对象在非确定区域的位置分布，在保留原有位置记录的情况下加入时间特性，这样就可以预测移动对象在未来时间段内的大概位置信息，从而为当前及未来非确定位置信息检索提供可靠保证。在TPU 树索引基础上，一种改进的基于p-bound的域查询处理算法MP_BBRQ，利用索引中记录的概率限定性区域和启发式判定准则，能高效的处理概率性域查询问题；一种基于分支定界思想的概率skyline 查询处理算法B 2 CPS，利用最近邻的最好优先遍历思想，能使查询处理的磁盘开销达到最优。
　　 相对于传统的空间查询概念，非确定数据库中常用的查询——概率空间查询，由于其结果集中增加了结果正确性的保证系数，从而使得基于非确定数据的查询更具有可信性。鉴于概率空间查询具有很高的计算代价，需要进一步提高概率空间查询效率，尤其是旨在减少CPU计算时间和磁盘I/O 次数的概率k 最近邻查询算法，国内外目前尚无相关研究。概率k 最近邻查询k-PNN 就是返回k个非确定对象，而且这k个非确定对象分别作为查询对象Q的第k个最近邻居的概率，相对于其它非确定对象是最大的。与传统的k 最近邻查询相比，计算非确定对象的k 最近邻概率值需要原始的积分运算或Monte-Carlo方法，在这种情况下，概率k 最近邻查询的计算代价是非常高的。因此，必须尽量缩小查询所需搜索的空间范围，从而在不影响返回正确结果集的情况下，进一步减少所要考虑的非确定对象，在很大程度上避免利用原始计算公式来返回结果集。高效处理k-PNN 查询框架包含四个步骤：R 树索引的建立，空间裁剪，概率裁剪和精炼阶段。利用安全可靠的空间裁剪以及概率裁剪方法，把这些方法与R 树索引进行完美的结合以减少查询的搜索空间，从而提高k-PNN 查询的处理效率。实验结果表明，空间裁剪和概率裁剪方法具有非常高的裁剪效率，整个k-PNN 查询处理过程是可靠高效的。
　　 非确定数据库需要研究的问题还很多，在许多查询问题上欠缺高效的处理算法，例如概率连接问题，概率Top-k 查询，概率反最近邻查询，以及概率反轮廓查询等等，因此，针对不同方面的概率空间和时空查询问题，将相应解决方法融入到数据库管理系统中以支持非确定数据的有效管理，将是研究人员面临的新问题。此外，将已有的研究成果应用于多维空间，并进一步考虑非欧式距离环境下的索引及查询处理方法可作为未来的研究方向。在非确定数据流环境下，如何利用有效的内存索引机制，提出各种高效的数据流查询算法也将是非常有潜力的研究课题。