Article: Slot index spatial join

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleSlot index spatial join
AuthorsMamoulis, N1
Papadias, D2
KeywordsBuffer management
Database index
Join processing
Query processing
Spatial databases
Spatial index
Issue Date2003
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
CitationIeee Transactions On Knowledge And Data Engineering, 2003, v. 15 n. 1, p. 211-231 [How to Cite?]
DOI: http://dx.doi.org/10.1109/TKDE.2003.1161591
AbstractEfficient processing of spatial joins is very important due to their high cost and frequent application in spatial databases and other areas involving multidimensional data. This paper proposes slot index spatial join (SISJ), an algorithm that joins a nonindexed data set with one indexed by an R-tree. We explore two optimization techniques that reduce the space requirements and the computational cost of SISJ and we compare it, analytically and experimentally, with other spatial join methods for two cases: 1) when the nonindexed input is read from disk and 2) when it is an intermediate result of a preceding database operator in a complex query plan. The importance of buffer splitting between consecutive join operators is also demonstrated through a two-join case study and a method that estimates the optimal splitting is proposed. Our evaluation shows that SISJ outperforms alternative methods in most cases and is suitable for limited memory conditions.
ISSN1041-4347
2011 Impact Factor: 1.657
2011 SCImago Journal Rankings: 0.081
DOIhttp://dx.doi.org/10.1109/TKDE.2003.1161591
ISI Accession Number IDWOS:000180230300014
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorMamoulis, N
dc.contributor.authorPapadias, D
dc.date.accessioned2007-03-23T04:51:32Z
dc.date.available2007-03-23T04:51:32Z
dc.date.issued2003
dc.description.abstractEfficient processing of spatial joins is very important due to their high cost and frequent application in spatial databases and other areas involving multidimensional data. This paper proposes slot index spatial join (SISJ), an algorithm that joins a nonindexed data set with one indexed by an R-tree. We explore two optimization techniques that reduce the space requirements and the computational cost of SISJ and we compare it, analytically and experimentally, with other spatial join methods for two cases: 1) when the nonindexed input is read from disk and 2) when it is an intermediate result of a preceding database operator in a complex query plan. The importance of buffer splitting between consecutive join operators is also demonstrated through a two-join case study and a method that estimates the optimal splitting is proposed. Our evaluation shows that SISJ outperforms alternative methods in most cases and is suitable for limited memory conditions.
dc.description.naturepublished_or_final_version
dc.format.extent3237099 bytes
dc.format.extent26624 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/msword
dc.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2003, v. 15 n. 1, p. 211-231 [How to Cite?]
DOI: http://dx.doi.org/10.1109/TKDE.2003.1161591
dc.identifier.doihttp://dx.doi.org/10.1109/TKDE.2003.1161591
dc.identifier.epage231
dc.identifier.hkuros81185
dc.identifier.isiWOS:000180230300014
dc.identifier.issn1041-4347
2011 Impact Factor: 1.657
2011 SCImago Journal Rankings: 0.081
dc.identifier.issue1
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-0037246488
dc.identifier.spage211
dc.identifier.urihttp://hdl.handle.net/10722/43664
dc.identifier.volume15
dc.languageeng
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
dc.publisher.placeUnited States
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering
dc.relation.referencesReferences in Scopus
dc.rights©2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.subjectBuffer management
dc.subjectDatabase index
dc.subjectJoin processing
dc.subjectQuery processing
dc.subjectSpatial databases
dc.subjectSpatial index
dc.titleSlot index spatial join
dc.typeArticle
Author Affiliations
  1. The University of Hong Kong
  2. Hong Kong University of Science and Technology