Spatial hash-joins

DOI Web Site Web Site 被引用文献2件
  • Ming-Ling Lo
    Department of EECS, University of Michigan-Ann Arbor, 1301 Beal Avenue, Ann Arbor, MI
  • Chinya V. Ravishankar
    Department of EECS, University of Michigan-Ann Arbor, 1301 Beal Avenue, Ann Arbor, MI

書誌事項

公開日
1996-06
権利情報
  • https://www.acm.org/publications/policies/copyright_policy#Background
DOI
  • 10.1145/235968.233337
公開者
Association for Computing Machinery (ACM)

この論文をさがす

説明

<jats:p>We examine how to apply the hash-join paradigm to spatial joins, and define a new framework for spatial hash-joins. Our spatial partition functions have two components: a set of bucket extents and an assignment function, which may map a data item into multiple buckets. Furthermore, the partition functions for the two input datasets may be different.We have designed and tested a spatial hash-join method based on this framework. The partition function for the inner dataset is initialized by sampling the dataset, and evolves as data are inserted. The partition function for the outer dataset is immutable, but may replicate a data item from the outer dataset into multiple buckets. The method mirrors relational hash-joins in other aspects. Our method needs no pre-computed indices. It is therefore applicable to a wide range of spatial joins.Our experiments show that our method outperforms current spatial join algorithms based on tree matching by a wide margin. Further, its performance is superior even when the tree-based methods have pre-computed indices. This makes the spatial hash-join method highly competitive both when the input datasets are dynamically generated and when the datasets have pre-computed indices.</jats:p>

収録刊行物

  • ACM SIGMOD Record

    ACM SIGMOD Record 25 (2), 247-258, 1996-06

    Association for Computing Machinery (ACM)

被引用文献 (2)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ