Benchmarking spatial joins a la carte

Citation
O. Gunther et al., Benchmarking spatial joins a la carte, INT J GEO I, 13(7), 1999, pp. 639-655
Citations number
23
Categorie Soggetti
EnvirnmentalStudies Geografy & Development
Journal title
INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
ISSN journal
13658816 → ACNP
Volume
13
Issue
7
Year of publication
1999
Pages
639 - 655
Database
ISI
SICI code
1365-8816(199910/11)13:7<639:BSJALC>2.0.ZU;2-S
Abstract
Spatial joins are join operations that involve spatial data types and opera tors. Spatial access methods are often used to speed up the computation of spatial joins. This paper addresses the issue of benchmarking spatial join operations. For this purpose, we first present a WWW-based benchmark genera tor to produce sets of rectangles. Using a Web browser, experimenters can s pecify the number of rectangles in a sample, as well as the statistical dis tributions of their sizes, shapes, and locations. Second, using the generat or and a well-defined set of statistical models we define several tests to compare the performance of three spatial join algorithms: nested loop, scan -and-index, and synchronized tree traversal. We also added two real-life da ta sets from the Sequoia 2000 storage benchmark. Our results show that the relative performance of the different techniques mainly depends on the sele ctivity factor of the join predicate. All of the statistical models and alg orithms are available on the Web, which allows for easy verification and mo dification of our experiments.