Collaborative Research: Support Efficient Similarity Searches for Multidimen= sional Non-ordered Discrete Data Spaces

Supported by the National Science Foundation= Research Grants
=

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)

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)

Graduate Students

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

Undergraduate Students

Chad Klochko
Rachel Radziszewski

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 multid= imensional Non-ordered Discrete Data Spaces (NDDS). Similarity searches in N= DDSs are becoming increasingly important for application areas such as genom= e 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 intro= duce a set of essential geometric concepts for an NDDS based on some similar= concepts for a traditional (ordered) Continuous Data Spaces (CDS). Using th= em, 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. W= e also study other related issues including supporting various types of quer= ies, 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 i= n 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 Infor= mation 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 Disc= rete Data Spaces", Proc. of the 12th International Conference on Exte= nding 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, "Delet= ion 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 Indexin= g Strategies for Hybrid Data Spaces", Proc. of the 11th International= Conference on Enterprise Information Systems (ICEIS'09), pp 149-159, Mi= lan, Italy, May 2009.

Gang Qian, Hyun-Jeong Seok, Qiang Zhu and Sakti Pramanik, "S= pace-Partitioning-Based Bulk-Loading for the NSP-Tree in Non-ordered Discret= e Data Spaces", Proc. of the 19th International Conference on Databas= e and Expert Systems Applications (DEXA'08), pp 404-418, Turin, Italy, S= ept. 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 Applicat= ions (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 Comp= uter Journal, Vol. 51, No. 6, pp 662-676, 2008.

Dashiell Kolbe, Qiang Zhu and Sakti Pramanik, "On k-Nearest Neighbor Searching in N= on-Ordered Discrete Data Spaces", Proc. of the 23rd IEEE Internationa= l 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-Partition= ing=20 Approach", ACM Transactions on Database Systems (TODS), Vol. 31, No. 2, pp 439-4= 84, 2006

Gang Qian, Qiang Zhu, Qiang Xue and Sakti Pramanik, "A Space-Partitioning-Based Indexing Method for Multidimentional Non-ordered Discrete Data Spaces",= =20 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. 16-18, 2006.

Gang Qian, Qiang Zhu, Qiang Xue and Sakti Pramanik, "The ND-Tree: A Dynamic Inde= xing Technique for Multidimensional Non-ordered Discrete Data Spaces",= =20 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 sit= e at UM-D

--=_2byo1chufy6p--