Join Strategies on Multi-Dimensional C1ustered Relations

スポンサーリンク

概要

• 論文の詳細を見る

• For the last years we have developed relational database systems like GRACE and FDS-R(Functional Disk with Relational database engine)in which the relational algebraic operations were based on dynamic clustering algorithms. Performance evaluations of FDS-R and other works showed that the dynamic clustering algorithm was a good solution for very large unstructured relations. Concerning the relational algebraic operations on structured relations, recent researches exemplified by the Predicate-tree, the Superjoin Algorithm and the DYOP are based on multidimensional clustered relations. The first two are based on hashing, and the last, on a grid-partitioned relation. Anyway, all them are based on structures that partition the relation based on the relation space, not the attribute values. These kind of partitioning are obviously easy to be handled for join operations because the generated partitions are naturally disjoint concerning the discriminate attributes. However they are not conceivable in real applications since the methods based on hashing are not order-preserving and the ones based on grid-partitions show low load-factor for reasonable number of discriminate attributes. Here we present some join strategies for KD-tree indexed relations. As a multidimensional clustering method, KD-tree presents the desired characteristics of order preserving and high load-factor. However, the KD-tree generates partitions that are not disjoint concerning the value of discriminate attributes, which makes the operations on them difficult. In what follows we recall some strategies we have proposed to deal with this difficulty and previously introduced in. Some analysis and evaluations demonstrate the effectiveness of the join strategies for KD-tree indexed relations.

• 一般社団法人情報処理学会の論文
• 1988-09-12

著者

• Takagi Mikio

  University Of Tokyo

• Kitsuregawa M

  Institute Of Industrial Science The University Of Tokyo

• Kitsuregawa Masaru

  University Of Tokyo

• Harada Lilian

  University of Tokyo

• Harada L

  Fujitsu Lab.

関連論文

• 5ZN-9 A Topical Study on the Web Spam
• Mining Communities on the Web Using a Max-Flow and a Site-Oriented Framework(Data Mining)
• Relational Algebra Machine GRACE
• Compact Encoding of the Web Graph Exploiting Various Power Distributions(Discrete Mathematics and Its Applications)
• Finding Neighbor Communities in the Web Using an Inter-Site Graph(Database)
• Join Strategies on Grid-Files
• Join Strategies on Multi-Dimensional C1ustered Relations
• Detecting Hijacked Sites by Web Spammer Using Link-Based Algorithms
• On Parallel Hash-Join Processing with Skewed Data
• Pipeline Stage Based Dynamic Load Balancing for Right-Deep Multi-Joins

スポンサーリンク