Data value storage for compressed semi-structured data

Growing user expectations of anywhere, anytime access to information require new types of data transfer to be considered. While semi-structured data is a common data exchange format, its verbose nature makes les of this type too large to be transferred quickly, especially where only a small part of that data is required by the user. There is consequently a need to develop new models of data storage to support the sharing of small segments of semi-structured data as existing XML compressors require the transfer of the entire compressed structure as a whole. This thesis examines the potential for bisimilarity-based partitioning (i.e. the grouping of items with similar structural patterns) to be combined with dictionary compression methods to produce a data storage model that remains directly accessible for query processing whilst facilitating the sharing of individual data segments. The use of dictionary compression is shown to compare favourably against Hu mantype compression, especially with regard to real world data sets, while a study of the e ects of di ering types of bisimilarity upon the storage of data values identi ed the use of both forwards and backwards bisimilarity as the most promising basis for a dictionary-compressed structure. Having employed the above in a combined storage model, a query strategy is detailed which takes advantage of the compressed structure to reduce the number of data segments that must be accessed (and therefore transferred) to answer a query. A method to remove redundancy within the data dictionaries is also described and shown to have a positive e ect in terms of disk space usage.Growing user expectations of anywhere, anytime access to information require new types of data transfer to be considered. While semi-structured data is a common data exchange format, its verbose nature makes les of this type too large to be transferred quickly, especially where only a small part of that data is required by the user. There is consequently a need to develop new models of data storage to support the sharing of small segments of semi-structured data as existing XML compressors require the transfer of the entire compressed structure as a whole. This thesis examines the potential for bisimilarity-based partitioning (i.e. the grouping of items with similar structural patterns) to be combined with dictionary compression methods to produce a data storage model that remains directly accessible for query processing whilst facilitating the sharing of individual data segments. The use of dictionary compression is shown to compare favourably against Hu mantype compression, especially with regard to real world data sets, while a study of the e ects of di ering types of bisimilarity upon the storage of data values identi ed the use of both forwards and backwards bisimilarity as the most promising basis for a dictionary-compressed structure. Having employed the above in a combined storage model, a query strategy is detailed which takes advantage of the compressed structure to reduce the number of data segments that must be accessed (and therefore transferred) to answer a query. A method to remove redundancy within the data dictionaries is also described and shown to have a positive e ect in terms of disk space usage