Impact of Query Type on Multidimensional Indexing for Large Databases in Non-ordered Discrete Data Spaces

Impact of Query Type on Multidimensional Indexing for Large Databases in Non-ordered Discrete Data Spaces

时间： 地点：九龙湖校区计算机学院二楼会议室

报告简介：

There is an increasing demand to efficiently process various types of queries (e.g., similarity queries and box queries) on large databases in multidimensional Non-ordered Discrete Data Spaces (NDDS) from many application areas including bioinformatics, biometrics, network security, and E-commerce. Efficient query processing typically requires robust indexing techniques. Unfortunately, existing indexing methods developed for Continuous Data Spaces (CDS) such as the R*-tree cannot be directly applied to an NDDS due to lack of essential geometric concepts/properties in the NDDS. Other indexing methods based on metric spaces such as the M-tree are too general to effectively utilize the special characteristics of an NDDS. In this talk, I will first present a dynamic indexing technique, called the ND-tree, that we developed for processing similarity queries in an NDDS. This indexing technique adopts a set of essential geometric concepts that we extend from a CDS to an NDDS. The relevant index tree structure, constructing procedure, and search algorithm take the special characteristics of an NDDS into consideration. As a result, a set of unique indexing strategies suitable for an NDDS are employed. Our experimental results demonstrate that the ND-tree is very promising in supporting efficient similarity searches in an NDDS. However, I will then show that the ND-tree is not optimized for processing box queries, which are fundementally different from similarity queries. Based on theoretical analysis, we have identified the indexing strategies that are suitable for box queries and incorporated them into a new indexing technique, called the BoND-tree. Our experiments demonstrate that the BoND-tree is more efficient than the ND-tree when processing box queries. In the talk, I will also discuss how to process k-NN queries in an NDDS as well as our other studies on space-partition based indexing for an NDDS, bulk-loading for index trees in an NDDS, and indexing for a hybrid data space.

报告人简介：

Dr. Qiang Zhu is a Professor at The University of Michigan, Dearborn, USA. He is also an ACM Distinguished Scientist and an IBM CAS Faculty Fellow. Dr. Zhu received his Ph.D. from the University of Waterloo (Canada) in 1995. He also holds an M.Sc. from the McMaster University (Canada) as well as an M.Eng. and a B.Sc. from Southeast University (China). Dr. Zhu's research has been funded by highly competitive funding sources including US National Science Foundation and IBM Corporation. His work has been published in top journals and conferences in the database field including ACM Transactions on Database Systems, ACM Transactions on Information Systems, IEEE Transactions on Knowledge and Data Engineering, VLDB Journal, VLDB, ICDE, and CIKM. Some of his research results have been included in several well-known database text/research books. He received numerous distinguished research awards. He has served as an Editor-in-Chief, Associate Editor, and Editorial Board Member for a number of international journals including the Information Sciences (Elsevier). He also served as a program/organizing committee member for numerous international conferences. His main research interests include query optimization for advanced database systems, multidimensional indexes, self-managing databases, streaming data processing, spatio-temporal databases, information integration, and data mining. (http://www-personal.engin.umd.umich.edu/~qzhu)

计算机网络和信息集成教育部重点实验室（东南大学）