Implementing KDB-trees to support high-dimensional data

The problem of retrieving large volumes of high dimensional data is an important and timely issue in the area of database management. The guiding idea of this paper is to develop a general-purpose point access method that attacks the limitations of KDB-trees in high-dimensional spaces, while preserving their relatively good performance in low-dimensional situations. The proposed structure, called high-dimensional KDB-tree, eliminates downward propagation of splits associated with the original KDB-tree structure, which results in low storage utilization and rapid deterioration of the retrieval performance. Additional improvements in the storage and retrieval performance are achieved by removing certain redundant information from the interior nodes. Experimental results show that, in high-dimensional spaces, the proposed structure outperforms the original KDB-trees by a significant margin, while incurring no loss of performance in low-dimensional spaces. The structure also outperforms two other variants of KDB-trees investigated in the paper.