Abstract: kNN-Join is an important but costly primitive operation of high-dimensional databases. As RAM gets cheaper and larger,more and more datasets can fit into the main memory,how to realize the kNN-Join efficiently brings people's interests. 4-trecR and 4-trecS were designed especially for main-memory kNN-Join according to the properties of it.The core algorithms and relevant certificates of building them were presented combining with coding and node center coincidence technologies. Experiments show that the algorithrr}p-tree-kNN-Join based on p-tree-R and p-tree-S is superior to the existing kNN-Join algorithm of Gorder that can be used in main memory.

Key words: kNN-Join,High-dimensional space, Main-memory, Index structure, kNN search