Multiattribute indexing using multidimensional data structures

Abstract

Many applications involve searches using values of several of their attributes. Indexes are well-known data structures utilized to improve the performance of searches for data. A multiattribute index has advantages over several single-attribute indexes. First, the clustering of index terms reduces the number of I/O access needed for the search. Second, multiattribute index requires single update when new record is inserted.Several data structures have been used for multiattribute key index. B+-tree is commonly used as multiattribute key index, but has the disadvantage that it does not allow search on some of the attributes from the multiattribute key. Grid File allows search on all the attributes from the multiattribute key while restricting the keys in the index to only contain uniform values. Insertion and deletion can also be difficult on grid files. There has been previous work that uses R-trees for indexing purposes where the emphasis was on spatial data. The research in this thesis focuses on the relational data which exploits relational databases and the use of multidimensional data structures to perform multiattribute key indexing. It examines how to employ R-trees to perform multiattribute indexing such that the order of attributes is no more important for queries. Data records with multiattribute keys are modeled as multidimensional data to be indexed by means of a multidimensional data structure, specifically an R-tree. This will enable a relational database system to perform queries using any one of the attributes or any of their combination. It is hereby shown how a multiattribute key index implemented by an R-tree facilitates retrieval of records from database in response to search conditions based on any of the attributes forming the key or any combination thereof. An improvement on R-tree is then presented where regions do not overlap and n-dimensional signatures are incorporated into nodes of the tree for effective filtration of irrelevant tree nodes during searches. Algorithms for search (point, range and similarity), insertion, and deletion operations are also provided.

Many applications involve searches using values of several of their attributes. Indexes are well-known data structures utilized to improve the performance of searches for data. A multiattribute index has advantages over several single-attribute indexes. First, the clustering of index terms reduces the number of I/O access needed for the search. Second, multiattribute index requires single update when new record is inserted.Several data structures have been used for multiattribute key index. B+-tree is commonly used as multiattribute key index, but has the disadvantage that it does not allow search on some of the attributes from the multiattribute key. Grid File allows search on all the attributes from the multiattribute key while restricting the keys in the index to only contain uniform values. Insertion and deletion can also be difficult on grid files. There has been previous work that uses R-trees for indexing purposes where the emphasis was on spatial data. The research in this thesis focuses on the relational data which exploits relational databases and the use of multidimensional data structures to perform multiattribute key indexing. It examines how to employ R-trees to perform multiattribute indexing such that the order of attributes is no more important for queries. Data records with multiattribute keys are modeled as multidimensional data to be indexed by means of a multidimensional data structure, specifically an R-tree. This will enable a relational database system to perform queries using any one of the attributes or any of their combination. It is hereby shown how a multiattribute key index implemented by an R-tree facilitates retrieval of records from database in response to search conditions based on any of the attributes forming the key or any combination thereof. An improvement on R-tree is then presented where regions do not overlap and n-dimensional signatures are incorporated into nodes of the tree for effective filtration of irrelevant tree nodes during searches. Algorithms for search (point, range and similarity), insertion, and deletion operations are also provided.