A space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces

ABSTRACT

There is an increasing demand for similarity searches in a multidimensional non-ordered discrete data space (NDDS) from application areas such as bioinformatics and data mining. The non-ordered and discrete nature of an NDDS raises new challenges for developing efficient indexing methods for similarity searches. In this article, we propose a new indexing technique, called the NSP-tree, to support efficient similarity searches in an NDDS. As we know, overlap causes a performance degradation for indexing methods (e.g., the R-tree) for a continuous data space. In an NDDS, this problem is even worse due to the limited number of elements available on each dimension of an NDDS. The key idea of the NSP-tree is to use a novel discrete space-partitioning (SP) scheme to ensure no overlap at each level in the tree. A number of heuristics and strategies are incorporated into the tree construction algorithms to deal with the challenges for developing an SP-based index tree for an NDDS. Our experiments demonstrate that the NSP-tree is quite promising in supporting efficient similarity searches in NDDSs. We have compared the NSP-tree with the ND-tree, a data-partitioning-based indexing technique for NDDSs that was proposed recently, and the linear scan using different NDDSs. It was found that the search performance of the NSP-tree was better than those of both methods.

REFERENCES

• 1: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 2: Bruno Becker , Paolo Giulio Franciosa , Stephan Gschwind , Thomas Ohler , Gerald Thiemt , Peter Widmayer, An Optimal Algorithm for Approximating a Set of Rectangles by Two Minimum Area Rectangles, Proceedings of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, p.13-25, March 21-22, 1991
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 5: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
• 6: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 7: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 8: Clement, J., Flajolet, P., and Vallee, B. 2001. Dynamic sources in information theory: A general analysis of trie structures. Algorithm 29, 1/2, 307--369.
• 9: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 10: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: Andreas Henrich, Improving the Performance of Multi-Dimensional Access Structures Based on k-d-Trees, Proceedings of the Twelfth International Conference on Data Engineering, p.68-75, February 26-March 01, 1996
• 12: Andreas Henrich, The LSDh-Tree: An Access Structure for Feature Vectors, Proceedings of the Fourteenth International Conference on Data Engineering, p.362-369, February 23-27, 1998
• 13: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 14: Kent, W. J. 2002. BLAT---the BLAST-like aligment tool. Genome Res. 12, 656--664.
• 15: Knuth, D. E. 1973. The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA.
• 16: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 17: Gang Qian , Sakti Pramanik, Principles and applications for supporting similarity queries in non-ordered-discrete and continuous data spaces, 2004
• 18: Qian, G., Zhu, Q., Xue, Q., and Pramanik, S. 2003. The ND-tree: A dynamic indexing technique for multidimensional non-ordered discrete data spaces. In Proceedings of VLDB. 620--631.
• 19: Qian, G., Zhu, Q., Xue, Q., and Pramanik, S. 2006. Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach. ACM Trans. Datab. Syst. 31, 2. To appear.
• 20: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 21: Skopal, T., Pokorny, J., and Snasel, V. 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases. In Proceedings of Dateso 2004 Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO'04). 27--37.
• 22: C. Traina, Jr. , A. Traina , C. Faloutsos , B. Seeger, Fast Indexing and Visualization of Metric Data Sets using Slim-Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.244-260, March 2002 [doi>10.1109/69.991715]
• 23: Uhlmann, J. K. 1991. Satisfying general proximity/similarity queries with metric trees. Inf. Proc. Lett. 40, 4, 175--179.
• 24: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 25: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996
• 26: Xiangmin Zhou , Guoren Wang , Jeffrey Xu Yu , Ge Yu, M⁺-tree: a new dynamical multidimensional index for metric spaces, Proceedings of the fourteenth Australasian database conference, p.161-168, February 01, 2003, Adelaide, Australia
• 27: Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley, Reading, MA.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Performance

Keywords:
Hamming distance, Non-ordered discrete data spaces, multidimensional index tree, similarity search