Symbolic Intersect Detection: A Method for Improving Spatial Intersect Joins
dc.contributor.author | Huang, Yun-Wu | en_US |
dc.contributor.author | Jones, Matthew | en_US |
dc.contributor.author | Rundensteiner, Elke A. | en_US |
dc.date.accessioned | 2006-09-11T16:15:04Z | |
dc.date.available | 2006-09-11T16:15:04Z | |
dc.date.issued | 1998-06 | en_US |
dc.identifier.citation | Huang, Yun-Wu; Jones, Matthew; Rundensteiner, Elke A.; (1998). "Symbolic Intersect Detection: A Method for Improving Spatial Intersect Joins." GeoInformatica 2(2): 149-174. <http://hdl.handle.net/2027.42/45600> | en_US |
dc.identifier.issn | 1384-6175 | en_US |
dc.identifier.issn | 1573-7624 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/45600 | |
dc.description.abstract | Due to the increasing popularity of spatial databases, researchers have focused their efforts on improving the query processing performance of the most expensive spatial database operation: the spatial join. While most previous work focused on optimizing the filter step, it has been discovered recently that, for typical GIS data sets, the refinement step of spatial join processing actually requires a longer processing time than the filter step. Furthermore, two-thirds of the time in processing the refinement step is devoted to the computation of polygon intersections. To address this issue, we therefore introduce a novel approach to spatial join optimization that drastically reduces the time of the refinement step. We propose a new approach called Symbolic Intersect Detection (SID) for early detection of true hits. Our SID optimization eliminates most of the expensive polygon intersect computations required by a spatial join by exploiting the symbolic topological relationships between the two candidate polygons and their overlapping minimum bounding rectangle. One important feature of our SID optimization is that it is complementary to the state-of-the-art methods in spatial join processing and therefore can be utilized by these techniques to further optimize their performance. In this paper, we also develop an analytical cost model that characterizes SID’s effectiveness under various conditions. Based on real map data, we furthermore conduct an experimental evaluation comparing the performance of the spatial joins with SID against the state-of-the-art approach. Our experimental results show that SID can effectively identify more than 80% of the true hits with negligible overhead. Consequently, with SID, the time needed for resolving polygon intersect in the refinement step is improved by over 50% over known techniques, as predicted by our analytical model. | en_US |
dc.format.extent | 247584 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Kluwer Academic Publishers; Springer Science+Business Media | en_US |
dc.subject.other | Geography | en_US |
dc.subject.other | Computer Science, General | en_US |
dc.subject.other | Data Structures, Cryptology and Information Theory | en_US |
dc.subject.other | Information Storage and Retrieval | en_US |
dc.subject.other | Multimedia Information Systems | en_US |
dc.subject.other | True Hit Detection | en_US |
dc.subject.other | Spatial Joins | en_US |
dc.subject.other | Spatial Databases | en_US |
dc.subject.other | Spatial Query Processing | en_US |
dc.title | Symbolic Intersect Detection: A Method for Improving Spatial Intersect Joins | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Atmospheric, Oceanic and Space Sciences | en_US |
dc.subject.hlbsecondlevel | Natural Resources and Environment | en_US |
dc.subject.hlbsecondlevel | Geography and Maps | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Civil and Environmental Engineering | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.subject.hlbtoplevel | Social Sciences | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Electrical Eng. and Computer Science Dept, University of Michigan, Ann Arbor, MI, 48109 | en_US |
dc.contributor.affiliationother | IBM T.J. Watson Research Center, Hawthorne, NY, 10532 | en_US |
dc.contributor.affiliationother | Department of Computer Science, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA, 01609 | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/45600/1/10707_2004_Article_167261.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1023/A:1009708015126 | en_US |
dc.identifier.source | GeoInformatica | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.