The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces Gang Qian, Qiang Zhu, Qiang Xue, and Sakti Pramanik   View Paper (PDF)   Return to Access Methods & Temporal Data (Session B7) Abstract Similarity searches in multidimensional Non- ordered Discrete Data Spaces (NDDS) are becoming increasingly important for applica- tion areas such as genome sequence databases. Existing indexing methods developed for multidimensional (ordered) Continuous Data Spaces (CDS) such as R-tree cannot be di- rectly applied to an NDDS. This is because some essential geometric concepts/properties such as the minimum bounding region and the area of a region in a CDS are no longer valid in an NDDS. On the other hand, indexing meth- ods based on metric spaces such as M-tree are too general to e ectively utilize the data dis- tribution characteristics in an NDDS. There- fore, their retrieval performance is not opti- mized. To support e cient similarity searches in an NDDS, we propose a new dynamic in- dexing technique, called the ND-tree. The key idea is to extend the relevant geometric con- cepts as well as some indexing strategies used in CDSs to NDDSs. Efficient algorithms for ND-tree construction are presented. Our ex- perimental results on synthetic and genomic sequence data demonstrate that the perfor- mance of the ND-tree is significantly better than that of the linear scan and M-tree in high dimensional NDDSs. ©2004 Association for Computing Machinery