A Selectivity Estimation Scheme for Spatial Topological Predicate Using Multi-Dimensional Histogram


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 4, pp. 841-850, Apr. 1999
10.3745/KIPSTE.1999.6.4.841,   PDF Download:

Abstract

Many commercial database systems maintain histograms to summarize the contents of relations, permit efficient estimation of query result sizes, and access lan costs. In spatial database systems, most query predicates consist of topological relationship between spatial objects, and it is very important to estimate the selectivity of those predicates for spatial query optimizer. In this paper, we propose a selectivity estimation scheme for spatial topological predicates based on the multi-dimensional histogram and the transformation scheme. Proposed scheme applies two partition strategies on transformed object space to generate spatial histogram, and estimates the selectivity of topological predicates based on the topological characteristic of transformed space. Proposed scheme provides a way for estimating the selectivity without too much memory space usage and additional I/Os in spatial query optimizer.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
B. H. Young and K. H. Yeon, "A Selectivity Estimation Scheme for Spatial Topological Predicate Using Multi-Dimensional Histogram," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 4, pp. 841-850, 1999. DOI: 10.3745/KIPSTE.1999.6.4.841.

[ACM Style]
Bae Hae Young and Kim Hong Yeon. 1999. A Selectivity Estimation Scheme for Spatial Topological Predicate Using Multi-Dimensional Histogram. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 4, (1999), 841-850. DOI: 10.3745/KIPSTE.1999.6.4.841.