增量精炼的GI交互查询的空间连接技术.doc

摘要： 越来越多的新兴网络数据库应用程序处理大型地标数据集。然而,通过空间查询探索这些大型数据集十分耗费时间和资源。互动空间查询的需要出现在多项领域上,例如地理信息系统 GIS 进行有效的决策支持。在本文中,我们提出一个新的GIS互动空间查询处理技术。我们提出一系列的增量精炼空间连接算法，到目前为止可以用来报告增量精炼运行集合查询同时显示元数据集采样的实际查询结果。我们的目标是最小化时间直到通过置信区间（congfidence interval）衡量查询结果对于用户来说是可接受的精确的估计。我们的方法能够让更多的交互式数据探索和分析。在关系数据库中相似的已做了工作，据我们所知，这是第一次在GIS中使用这个方法。我们通过大量的实验性能比较，调查和评估不同的抽样方法。基于真实和综合数据的实验显示当使用完全R—树连接时，一个数量级（order of magnitude）响应时间改善和最后获取的结果有关。我们也显示了不同索引结构对我们算法的性能影响通过使用三种有名的抽样方法。 关键字： 交互式查询，抽样，估计，置信区间，空间连接，窗口查询，R-树，人口比例，GIS 1.介绍 在很多领域和应用程序中使用GIS来探索大型地标数据集，为了获取直觉知识和洞察存储的信息。在GIS中为了不同的目的经常使用数据分析，比如，科学有哪些信誉好的足球投注网站和决策支持。这个数据分析与集合查询有直接关系比如空间连接。集合查询要求存取大容量的数据集并且经常计算精确的数字查询结果。然而，计算精确的大数据集的查询结果会耗费很多时间由于完整的数据集大小和空间的地理相关数据比例。GIS和空间数据集提供了一些算法用来计算精确的空间数据的查询结果，其中一些算法对于探索大型空间数据集在时间上是不允许。 在一些GIS应用程序中查询响应时间是挑剔的，因此，在合理的短时间内获取近似的查询结果远远比花费很长时间评估精确的结果要重要的多。比如，预先警告系统如洪水和火灾探测系统需要尽快的获取查询结果。这些系统将对是否疏散危险中的人们做出及时的决定。因为，它们需要在在查询数据处理的早期阶段检测出异常情况。在合理的错误范围内获取一个快速的查询结果比花费很长时间得到精确的结果更好。 图表1的例子显示了我们实验中使用的部分真实数据集的，这个实验是美国的煤矿资源，其参杂了地球化学松散的沉淀物（geochemical unconsolidated sediments）。这个查询结果对分析如湖泊和河流这些沉淀物如何影响煤矿资源如盐石是很有帮助的。假设一些数据集需要相互关联，获取二个数据集的交集的准确数量要花费数天。一个近似的结果是足够的并且避免浪费计算时间，因此允许更有效率的数据挖掘。我们的目标就是加速GIS数据的挖掘处理同时提供一个估计结果的统计置信（statistical confidence）。 在这篇文章中，对于GIS的空间连接我们提出一个新的交互查询处理技术，它将返回有界置信区间内的最终结果的增量精细运行估计 ，同时展示相连接的数据集的部分结果，一个近似的结果，界于say bounded by 5% of the exact answer with 95% probability confidence level 。这个近似结果通过使用数据集的子集计算所用时间是计算精确结果所用时间的十分之一。同时，目前用户能够看到真实的连接索引。 为了使系统更加具有交互性，用户可以停止查询结果是当结果是足够好或者指定想得到的精度。在传统的GIS中，空间查询以模块化的形式生成，用户必须控制查询处理（query processing）。用户只能提交他们的查询，等待很长时间看不到任何结果直到最后一个结果返回。交互式查询处理（Interactive query processing）方式能够为更有效率的数据挖掘和更有效率的决策支持提供灵活的方法。这个方法允许快速的获取查询结果是否有用的消息，因此能够更改查询处理或者相应的停止它。由于GIS查询主要用来获取大型数据集和他们之间的联系，这个交互式查询处理技术对GIS最终用户（GIS end users）更加具有吸引力。用户经常希望形象化查询结果，在交互模式下实现将大大增加了GIS的实用性。 有时仅仅一个集合查询结果（aggregate query result）价值是足够的，我们的目的是最小化需求的时间提供部分结果以及任一想得到的集合价值的一个有界置信区间估计。如果获取一个精确的结果的查询仅仅需要30s相比较而言使用我们方法获取一个估计值需要5s，这个方法是无意义的。另一方面，如果我们花费15min计算一个置信区间的有界估计与花费3h计算一个精确结果相对比，我们的方法是很有吸引力的。当我们处理的GIS数据是字节或者系统大小时这种情景是可能的。因此，一些GIS应用程序会从我们的方法中获