The Performance of Object Decomposition Techniques for Spatial Query Processing
The Performance of Object Decomposition Techniques for Spatial Query Processing
复制标题
空间查询处理的对象分解技术的性能
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Michael Schiwietz
中科院分区：
文献类型：
--
作者：
H. Kriegel;Holger Horn;Michael Schiwietz
在图形和图像处理、地理学以及计算机辅助设计（CAD）等应用中的空间数据管理对空间数据库系统提出了严格的新要求，特别是对复杂空间对象的高效查询处理。在本文中，我们提出了一个两级，多表示查询处理技术，它包括一个过滤器和一个细化级别。空间查询处理的效率大大提高使用以下两个设计范例：第一，分而治之，即复杂的空间对象分解成更简单的空间组件，如凸多边形，三角形或椭球形，第二，应用程序的有效和强大的空间访问方法，简单的空间对象。我们的方法中最强大的成分是对象分解的概念。应用于空间查询处理的精化层，它用简单快速的算法代替复杂的计算几何算法。在本文中，我们提出了四种不同的多边形物体的分解技术。论文的第二部分包括使用真实的和合成数据集的这些技术的实证性能比较。四种类型的分解技术进行了比较，彼此和传统的方法方面的空间查询处理的性能。这种比较指出，我们的方法使用对象分解是上级传统的查询处理策略。
The management of spatial data in applications such as graphics and image processing, geography as well as computer aided design (CAD) imposes stringent new requirements on spatial database systems, in particular on efficient query processing of complex spatial objects. In this paper, we propose a two-level, multi-representation query processing technique which consists of a filter and a refinement level. The efficiency of spatial query processing is improved considerably using the following two design paradigms: first, divide and conquer, i.e. decomposition of complex spatial objects into more simple spatial components such as convex polygons, triangles or trapezoids, and second, application of efficient and robust spatial access methods for simple spatial objects. The most powerful ingredient in our approach is the concept of object decomposition. Applied to the refinement level of spatial query processing, it substitutes complex computational geometry algorithms by simple and fast algorithms for simple components. In this paper, we present four different decomposition techniques for polygonal shaped objects. The second part of the paper consists of an empirical performance comparison of those techniques using real and synthetic data sets. The four types of decomposition techniques are compared to each other and to the traditional approach with respect to the performance of spatial query processing. This comparison points out that our approach using object decomposition is superior to traditional query processing strategies.