Collaborative Research: Support Efficient Similarity Searches for Multidimensional Non-ordered Discrete Data Spaces

Supported by the National Science Foundation Research Grants
and The University of Michigan Research Grants (OVPR and UMD)

Principal Investigator at UM-D

Dr. Qiang Zhu
Department of Computer and Information Science,
The University of Michigan, Dearborn, MI, USA
qzhu@umich.edu
(NSF Grant for UM-D: IIS-0414594)

Principal Investigator at MSU

Dr. Sakti Pramanik
Department of Computer Science and Engineering,
Michigan State University, East Lansing, MI, USA
pramanik@msu.edu
(NSF Grant for MSU: IIS-0414576)

Graduate Students

Changqing Chen
Dashiell Matthews Kolbe
Hyun-Jeong Seok
Alok Watve
Qiang Xue

Undergraduate Students

Chad Klochko
Rachel Radziszewski

High School Student

David Kong

Alumni

Gang Qian

Project Overview

This collaborative research project conducted jointly by the Michigan State University and the University of Michigan at Dearborn is to investigate the issues and techniques for supporting efficient similarity searches in multidimensional Non-ordered Discrete Data Spaces (NDDS). Similarity searches in NDDSs are becoming increasingly important for application areas such as genome sequence databases. Efficient similarity searches require robust indexing techniques. Unfortunately, existing indexing methods are either not suitable for an NDDS (e.g., the R*-tree) or too generic to provide good performance for an NDDS (e.g., metric trees). The main goal of this project is to study the fundamental properties of NDDSs and develop indexing methods exploiting these properties to support efficient similarity searches in NDDSs. We introduce a set of essential geometric concepts for an NDDS based on some similar concepts for a traditional (ordered) Continuous Data Spaces (CDS). Using them, we explore and compare promising data-partitioning (DP) based and space-partitioning (SP) based indexing techniques for NDDSs, including index tree structures, building strategies, search algorithms and performance models. We also study other related issues including supporting various types of queries, adopting different distance measures, indexing hybrid data spaces with mixed ordered and non-ordered dimensions, developing efficient bulk loading techniques, and utilizing effective compression schemes. This research will provide contemporary database indexing techniques to solve relevant issues in the emerging fields such as bioinformatics, biometrics and E-commerce.

Project References

Dashiell Kolbe, Qiang Zhu and Sakti Pramanik, "Efficient k-Nearest Neighbor Searching in Non-ordered Discrete Data Spaces", ACM Transactions on Information Systems (TOIS), 2009 (to appear).

Changqing Chen, Sakti Pramanik, Qiang Zhu, Alok Watve and Gang Qian, "The C-ND Tree: A Multidimensional Index for Hybrid Continuous and Non-ordered Discrete Data Spaces", Proc. of the 12th International Conference on Extending Database Technology (EDBT'09), pp 462-471, St. Petersburg, Russia, March 2009.

Hyun-Jeong Seok, Qiang Zhu, Gang Qian, Sakti Pramanik and Wen-Chi Hou, "Deletion Techniques for the ND-tree in Non-ordered Discrete Data Spaces", Proc. of the 18th International Conference on Software Engineering and Data Engineering (SEDE'09), pp 1-6, Las Vegas, Nevada, June 2009.

Changqing Chen, Sakti Pramanik, Qiang Zhu and Gang Qian, "A Study of Indexing Strategies for Hybrid Data Spaces", Proc. of the 11th International Conference on Enterprise Information Systems (ICEIS'09), pp 149-159, Milan, Italy, May 2009.

Gang Qian, Hyun-Jeong Seok, Qiang Zhu and Sakti Pramanik, "Space-Partitioning-Based Bulk-Loading for the NSP-Tree in Non-ordered Discrete Data Spaces", Proc. of the 19th International Conference on Database and Expert Systems Applications (DEXA'08), pp 404-418, Turin, Italy, Sept. 2008.

Hyun-Jeong Seok, Gang Qian, Qiang Zhu, Alexander Oswald and Sakti Pramanik, "Bulk-Loading the ND-Tree in Non-ordered Discrete Data Spaces", Proc. of 13th International Conference on Database Systems for Advanced Applications (DASFAA'08), pp 156-171, New Delhi, India, March 19 - 22, 2008.

Qiang Zhu, Brahim Medjahed, Anshuman Sharma and Henry Huang, "The Collective Index: A Technique for Efficient Processing of Progressive Queries", The Computer Journal, Vol. 51, No. 6, pp 662-676, 2008.

Dashiell Kolbe, Qiang Zhu and Sakti Pramanik, "On k-Nearest Neighbor Searching in Non-Ordered Discrete Data Spaces", Proc. of the 23rd IEEE International Conference on Data Engineering (ICDE'2007), pp 426-435, Turkey, April 2007.

Gang Qian, Qiang Zhu, Qiang Xue and Sakti Pramanik, "Dynamic Indexing for Multidimensional Non-ordered Discrete Data Spaces Using a Data-Partitioning Approach", ACM Transactions on Database Systems (TODS), Vol. 31, No. 2, pp 439-484, 2006

Gang Qian, Qiang Zhu, Qiang Xue and Sakti Pramanik, "A Space-Partitioning-Based Indexing Method for Multidimentional Non-ordered Discrete Data Spaces", ACM Transactions on Information Systems (TOIS), Vol. 23, No. 1, pp 79-110, 2006

Qiang Xue, James Cole and Sakti Pramanik, "Sequence Homology Search Based on Database Indexing Using the Profile Hidden Markov Model", Proc. of IEEE International Conference on Bioinformatics and Bioengineering (BIBE'06), pp 135-140, Washington, DC, Oct. 2006.

Gang Qian, Qiang Zhu, Qiang Xue and Sakti Pramanik, "The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces", Proc. of 29th International Conference on Very Large Data Bases (VLDB'03), pp 620-631, Berlin, Germany, Sept. 9 - 12, 2003

Project Web Sites

Web site at MSU

Web site at UM-D