Efficient Processing of Large Spatial Queries Using Interior Approximations
Efficient Processing of Large Spatial Queries Using Interior Approximations
复制标题
使用内部近似有效处理大型空间查询
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
S. Ravada
中科院分区：
文献类型：
--
作者：
K. Kanth;S. Ravada
CAD/CAM和地理信息系统中的空间数据涉及任意形状的二维和三维几何形状。对此类复杂几何数据的查询涉及识别与指定查询几何交互的数据几何。由于数据几何尺寸较大，几何之间的比较代价高昂，空间引擎通过首先比较mbr并过滤掉不相关的几何来避免不必要的比较。如果查询几何形状比数据几何形状大，那么这种过滤技术可能无法有效地提高性能。在本文中，我们描述了如何通过首先使用几何形状的内部近似进行滤波（除了比较外部，即mbr）来减少几何形状的比较。我们将此技术作为Oracle Spatial中R-tree索引的一部分实现，并观察到，对于实际空间数据集的大多数查询，查询性能提高了50%以上（或2倍）。
Spatial data in CAD/CAM and geographic information systems involve arbitrarily-shaped 2- and 3-dimensional geometries. Queries on such complex geometry data involve identification of data geometries that interact with a specified query geometry. Since geometry-geometry comparisons are expensive due to the large sizes of the data geometries, spatial engines avoid unnecessary comparisons by first comparing the MBRs and filtering out irrelevant geometries. If the query geometry is large compared to the data geometries, this filtering technique may not be effective in improving the performance. In this paper, we describe how to reduce geometry-geometry comparisons by first filtering using the interior approximations of geometries (in addition to and after comparing the exteriors, i.e., the MBRs). We implemented this technique as part of the R-tree indexes in Oracle Spatial and observed that the query performance improves by more than 50% (or a factor of 2) for most queries on real spatial datasets.