Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach

ABSTRACT

Similarity searches in multidimensional Non-ordered Discrete Data Spaces (NDDS) are becoming increasingly important for application areas such as bioinformatics, biometrics, data mining and E-commerce. Efficient similarity searches require robust indexing techniques. Unfortunately, existing indexing methods developed for multidimensional (ordered) Continuous Data Spaces (CDS) such as the R-tree cannot be directly 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. Other indexing methods based on metric spaces such as the M-tree and the Slim-trees are too general to effectively utilize the special characteristics of NDDSs, resulting in nonoptimized performance. In this article, we propose a new dynamic data-partitioning-based indexing technique, called the ND-tree, to support efficient similarity searches in an NDDS. The key idea is to extend the relevant geometric concepts as well as some indexing strategies used in CDSs to NDDSs. Efficient algorithms for ND-tree construction and techniques to solve relevant issues such as handling dimensions with different alphabets in an NDDS are presented. Our experimental results on synthetic data and real genome sequence data demonstrate that the ND-tree outperforms the linear scan, the M-tree and the Slim-trees for similarity searches in multidimensional NDDSs. A theoretical model is also developed to predict the performance of the ND-tree for random data.

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: 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
• 3: 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
• 4: 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
• 5: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 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: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 8: Tzi-cker Chiueh, Content-Based Image Indexing, Proceedings of the 20th International Conference on Very Large Data Bases, p.582-593, September 12-15, 1994
• 9: 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
• 10: 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.
• 11: Vlastislav Dohnal , Claudio Gennaro , Pasquale Savino , Pavel Zezula, D-Index: Distance Searching Index for Metric Data Sets, Multimedia Tools and Applications, v.21 n.1, p.9-33, September 2003 [doi>10.1023/A:1025026030880]
• 12: 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]
• 13: 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
• 14: 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
• 15: 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
• 16: Kent, W. J. 2002. BLAT--The BLAST-like aligment tool. Gen. Res. 12, 656--664.
• 17: Knuth, D. E. 1973. The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA.
• 18: Jinhua Li , Sakti Pramanik, Efficient similarity search based on data distribution properties in high dimensions, 2001
• 19: Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, A space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.79-110, January 2006 [doi>10.1145/1125857.1125860]
• 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: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 22: 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 Internation Workshop on DAtabases, TExts, Specifications and Objects (DATESO'04). 27--37.
• 23: 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]
• 24: Uhlmann, J. K. 1991. Satisfying general proximity/similarity queries with metric trees. Inf. Proc. Lett. 40, 4, 175--179.
• 25: 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
• 26: 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
• 27: Xue, Q., Qian, G., Cole, J. R., and Pramanik, S. 2004. Investigation on approximate q-gram matching in genome sequence databases. Tech. Report, Michigan State Univ.
• 28: Xiangmin Zhou , Guoren Wang , Jeffrey Xu Yu , Ge Yu, M⁺-tree: a new dynamical multidimensional index for metric spaces, Proceedings of the 14th Australasian database conference, p.161-168, February 01, 2003, Adelaide, Australia

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Performance, Theory

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