{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T20:10:17Z","timestamp":1737231017638,"version":"3.33.0"},"reference-count":36,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":4827,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1994,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a new join processing algorithm for the KD\u2010tree indexed relations. The processing is evaluated by a simulation and the effectiveness is demonstrated. The KD\u2010tree index is one of the typical multidimensional clustering data structures. A flexible database can be constructed which provides uniform access characteristics in regard to the multiple attributes. On the other hand, the data structure is made complex, and the traditional join processing technique for the ordinary one\u2010dimensional clustering relation, which maintains the physical order, cannot be applied. Also, there has not been proposed a join technique for the KD\u2010tree indexed relations.<\/jats:p><jats:p>This paper introduces anew the concepts called \u201cwave\u201d and \u201cjoin range,\u201d and proposes an efficient join algorithm for the KD\u2010tree indexed relations. Then an extended algorithm is proposed by introducing the garbage collection function into the forementioned basic algorithm, where the unnecessary tuples on the main memory can be eliminated dynamically. Each of those algorithms is evaluated by a simulation, and the effectiveness is verified.<\/jats:p><jats:p>When the order of the join attribute is not preserved, the join processing by the hash\u2010based algorithm, which at present is considered the fastest, requires two read scannings and one write scanning, while the best algorithm proposed in this paper can execute the processing by almost one read scanning. Thus, a drastic improvement of the performance can be expected for the join processing by the proposed algorithm.<\/jats:p>","DOI":"10.1002\/scj.4690250307","type":"journal-article","created":{"date-parts":[[2007,7,8]],"date-time":"2007-07-08T02:18:29Z","timestamp":1183861109000},"page":"78-90","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms and performance evaluation of join processing on KD\u2010tree indexed relations"],"prefix":"10.1002","volume":"25","author":[{"given":"Masaru","family":"Kitsuregawa","sequence":"first","affiliation":[]},{"given":"Mikio","family":"Takagi","sequence":"additional","affiliation":[]},{"given":"Lilian","family":"Harada","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"J.Aoe.Key Search Strategies. IEEE Comp. Society Technology Series (1991)."},{"issue":"9","key":"e_1_2_1_3_2","first-page":"509","volume":"18","author":"Bentley J. L.","journal-title":"Multidimensional binary search trees used for associative searching. Commun. ACM"},{"issue":"4","key":"e_1_2_1_4_2","first-page":"333","volume":"5","author":"Bentley J. L.","year":"1970","journal-title":"Multidimensional binary search trees in database applications. IEEE Trans. Software Eng."},{"volume-title":"Object Data Management: Object\u2010Oriented and Extended Relational Database Systems","year":"1991","author":"Cattell R. G. G.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"J. M.ChangandK. S.Fu. A dynamical clustering technique for physical database design. Proc. of SIGMOND pp.188\u2013199(1980).","DOI":"10.1145\/582250.582280"},{"key":"e_1_2_1_7_2","unstructured":"J. P.Cheiney P.Faudemay R.MichelandJ. M.Thevenin. A reliable parallel backend using multiattribute clustering and select\u2010join operator. Proc. of Very Large Data Bases pp.220\u2013227(1986)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"D. J.DeWitt R. H.KatzandF.Olken. Implementation techniques for main memory database systems. Proc. of SIGMOND pp.1\u20138(1984).","DOI":"10.1145\/971697.602261"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"M.Freeston.The BANG File: A New Kind of Grid File. Proc. of SIGMOND pp.260\u2013269(1987).","DOI":"10.1145\/38714.38743"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"S.Fushimi M.Kitsuregawa M.Nakayama H.TanakaandT.Moto\u2010oka.Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. Proc. of SIGMOND pp.308\u2013318(1985).","DOI":"10.1145\/971699.318928"},{"key":"e_1_2_1_11_2","unstructured":"R.Gerber.Dataflow Query Processing using Multiprocessor Hash\u2010Partitioned Algorithms. PhD. Thesis and Computer Science Technical Report #672 University of Wisconsin\u2010Madison (1986)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"A.Guttman.R\u2010Trees: A Dynamic Index Structure for Spatial Searching. Proc. SIGMOND pp.47\u201357(1984).","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_13_2","unstructured":"L.Harada.Query Processing on Multidimensionally Clustered Relations. Doctoral Thesis University of Tokyo (1989)."},{"key":"e_1_2_1_14_2","article-title":"Design and Implementation of Join Algorithms for KD\u2010Tree Indexed Relations","volume":"90","author":"Harada L.","year":"1990","journal-title":"Info\u2010Japan'"},{"key":"e_1_2_1_15_2","unstructured":"L.Harada M.Nakano M.KitsuregawaandM.Takagi.Query processing method for multiattribute clustered relations. Proc. of Very Large Data Bases pp.59\u201370(1990)."},{"key":"e_1_2_1_16_2","first-page":"45","volume-title":"The LSD\u2010Tree: Spatial Access to Multidimensional Point and Non Point Objects","author":"Henrich A.","year":"1989"},{"key":"e_1_2_1_17_2","first-page":"183","volume-title":"Twin Grid Files: Space Optimizing Access Schemes","author":"Hutflesz A.","year":"1989"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"K. L.KelleyandRusinkiewicz: Implementation of Multi\u2010Key Extendable Hashing as an Access Method for a Relational DBMS. Proc. of IEEE Int. Conf. on Data Engineering pp.124\u2013131(1986).","DOI":"10.1109\/ICDE.1986.7266214"},{"issue":"1","key":"e_1_2_1_19_2","first-page":"62","volume":"1","author":"Kitsuregawa M.","year":"1983","journal-title":"Its Application of Hash to Data Base Machine and Its Architecture. New Generation Computing"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"M.Kitsuregawa L.HaradaandM.Takagi.Join strategies on KD\u2010tree indexed relations. Proc. of IEEE Int. Conf. on Data Engineering pp.85\u201393(1989).","DOI":"10.1109\/ICDE.1989.47203"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"H. P.KriegelandB.Seeger. Multidimensional dynamic quantile hashing is very efficient for nonuniform record distributions. Proc. of IEEE Int. Conf. on Data Engineering pp.10\u201317(1987).","DOI":"10.1109\/ICDE.1987.7272349"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"H. P.KriegelandB.Seeger.PLOP\u2010hashing: A grid file without directory. Proc. of IEEE Int. Conf. on Data Engineering pp.369\u2013376(1988).","DOI":"10.1109\/ICDE.1988.105439"},{"key":"e_1_2_1_23_2","unstructured":"R.KrishnamurthyandK. Y.Wang.Multilevel Grid Files. IBM Research Report Yorktown Heights (1985)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"D. B.LometandB.Salzberg.A robust multi\u2010attribute search structure. Proc. of IEEE Int. Conf. on Data Engineering pp.296\u2013304(1989).","DOI":"10.1109\/ICDE.1989.47229"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/128762.128764"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_2_1_27_2","first-page":"493","volume-title":"A mapping function for the directory of a multidimensional extendable hashing","author":"Otoo E. J.","year":"1984"},{"key":"e_1_2_1_28_2","doi-asserted-by":"crossref","unstructured":"E. J.Otoo. A multidimensional digital hashing scheme for files with composite keys. Proc. of SIGMOND pp.214\u201322991985).","DOI":"10.1145\/971699.318918"},{"key":"e_1_2_1_29_2","unstructured":"E. A.OzkarahanandM.Ouksel.Dynamic order preserving data partitioning for database machines. Proc. of Very Large Data Bases pp.358\u2013368(1985)."},{"issue":"1","key":"e_1_2_1_30_2","first-page":"18","volume":"6","author":"Ozharahan E. A.","year":"1988","journal-title":"Join strategies using data space partitioning. New Generation Computing"},{"key":"e_1_2_1_31_2","doi-asserted-by":"crossref","unstructured":"J. T.Robinson.The KDB\u2010Tree: A Search Structure for Large Multidimensional Dynamic Indexes. Proc. of SIGMOND pp.10\u201318(1981).","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"P. G.Selingeret al.Access Path Selection in a Relational Database Management System. Proc. of SIGMOND pp.23\u201334(1979).","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/6314.6315"},{"issue":"2","key":"e_1_2_1_34_2","first-page":"15","volume":"2","author":"Tanaka T.","year":"1985","journal-title":"Optimal and adaptive file decomposition of the file with multiple attributes Comp. Software"},{"key":"e_1_2_1_35_2","first-page":"189","volume-title":"A Superjoin Algorithm for Deductive Databases","author":"Thorn J. A.","year":"1986"},{"key":"e_1_2_1_36_2","unstructured":"M.Toyama.A fluent algorithm in multidimensional linear hash file database. 34th Nat. Conv. Inf. Proc. pp.407\u2013408(1987)."},{"key":"e_1_2_1_37_2","first-page":"107","volume-title":"A Multikey Hashing Scheme using Predicate Trees","author":"Valduriez P.","year":"1984"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690250307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690250307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T19:36:34Z","timestamp":1737228994000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690250307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1002\/scj.4690250307"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690250307","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"type":"print","value":"0882-1666"},{"type":"electronic","value":"1520-684X"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}