The C-ND tree: a multidimensional index for hybrid continuous and non-ordered discrete data spaces

ABSTRACT

Contemporary database applications often perform queries in hybrid data spaces (HDS) where vectors can have a mix of continuous valued and non-ordered discrete valued dimensions. To support efficient query processing for an HDS, a robust indexing method is required. Existing indexing techniques to process queries efficiently either apply to continuous data spaces (e.g., the R-tree) or non-ordered discrete data spaces (e.g., the ND-tree). No techniques directly indexing vectors in HDSs have been reported in the literature. In this paper, we propose a new multidimensional indexing technique, called the C-ND tree, to directly index vectors in an HDS. To build such an index, we first introduce some essential geometric concepts (e.g., hybrid bounding rectangle) in HDSs. The C-ND tree structure and the relevant tree building and query processing algorithms based on these geometric concepts in HDSs are then presented. Strategies have been suggested to make the values in continuous dimensions and non-ordered discrete dimensions comparable and controllable. Novel node splitting heuristics which exploit characteristics of both continuous and discrete dimensions are proposed. Performance of the C-ND tree is compared with that of linear scan, R*-tree and ND-tree using range queries on hybrid data. Experimental results demonstrate that the C-ND tree is quite promising in supporting range queries in HDSs.

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: Jason Catlett, On Changing Continuous Attributes into Ordered Discrete Attributes, Proceedings of the European Working Session on Machine Learning, p.164-178, March 06-08, 1991
• 5: 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
• 6: J. Clement, P. Flajolet, and B. Vallee. Dynamic sources in information theory: a general analysis of trie structures. In Algorithmica, 29(1/2), pages 307--369, 2001.
• 7: 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]
• 8: Alex A. Freitas, A survey of evolutionary algorithms for data mining and knowledge discovery, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
• 9: 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
• 10: 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
• 11: 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
• 12: Sofus A. Macskassy , Haym Hirsh , Arunava Banerjee , Aynur A. Dayanik, Converting numerical classification into text classification, Artificial Intelligence, v.143 n.1, p.51-77, January 2003 [doi>10.1016/S0004-3702(02)00359-4]
• 13: Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, The ND-tree: a dynamic indexing technique for multidimensional non-ordered discrete data spaces, Proceedings of the 29th international conference on Very large data bases, p.620-631, September 09-12, 2003, Berlin, Germany
• 14: Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach, ACM Transactions on Database Systems (TODS), v.31 n.2, p.439-484, June 2006 [doi>10.1145/1138394.1138395]
• 15: 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]
• 16: 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]
• 17: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 18: H. Shen, X. Zhou, and B. Cui. Indexing text and visual features for WWW images. Springer Berlin / Heidelberg, 2005.
• 19: Heng Tao Shen , Xiaofang Zhou , Bin Cui, Indexing and Integrating Multiple Features for WWW Images, World Wide Web, v.9 n.3, p.343-364, October 2006 [doi>10.1007/s11280-006-8560-4]
• 20: J. Smith, S. Basu, C. Lin, M. Naphade, and B. Tseng. Integrating features, models, and semantics for content-based retrieval. the 10th Text REtrieval Conference (TREC10), 2001.
• 21: J. Smith and S.-f. Chang. Searching for images and videos on the world-wide-web. Technical Report 459-96-25, Columbia University, 1996.
• 22: 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