基于压缩直方图的劣质数据库上相似连接结果大小估计

Compressed Histogram Based Similarity Join Size Estimation for Dirty Database

现代数据管理系统普遍存在劣质数据,影响了数据质量,给数据管理带来了新的挑战.已经有不少管理劣质数据的数据模型,实体关系数据模型就是其中一种,该模型允许劣质数据的存在,并给出衡量数据质量的方法,并且可根据对结果质量的需求给出查询结果.鉴于该模型的特点,传统的估计查询代价的优化方法很难再适用,需要新的代价估计技术.本文提出了一种新的估计连接结果大小的方法.使用加权的最小哈希函数获得某一属性的最小哈希签名,这使得属性具有相同维数,便于利用直方图进行快速估计;然后建立其直方图,最后使用改进的离散余弦变换压缩直方图信息,使用压缩信息直接进行代价估计,这使得即使对于高维数据也能保证低错误率和低存储代价.此外,此方法可以很好的支持动态数据更新,消除周期性重建直方图的时间开销.

Modern data management systems widespread of dirty data,which affects the quality of the data and brings new challenges for data management.Many methods for dirty data management have been proposed,and one of them is entity-based relational database in which one tuple represents an entity.The model allows the existence of poor quality data,and proposes the representation of data quality,data quality operators with the requirement of result data quality.In view of the characteristics of the model,the traditional query optimizations difficult to apply,we need new cost estimation techniques.This paper presents a new method to estimate the size of the join results.Using the weighted min-hash,we can get the min-hash signature of a property,which makes the property with the same dimensions and easy to use histogram to perform estimation,and then create its histogram,and finally use the improved discrete cosine transform to compress histogram information,which makes even for high dimensional data to ensure low error rate and low storage cost.We can use the compressed information directly to the cost estimation.In addition,this method can support dynamic data updates very well,which eliminate the need to periodically rebuild the histogram.