Histogram-based Query Estimation for Datasets with different Modalities

从传统的数据库查询优化到OLAP应用程序，再到大型数据集的探索，数据汇总和估计都可以作为一种有用的工具用于各种应用程序。在该项目的过程中，将为具有不同形态的数据集开发数据估计和汇总技术：点数据集、包含具有空间范围的对象的数据集以及流数据集。该方法具体基于在不同环境中使用直方图。在数据库管理系统中应用估计技术的主要问题之一是将填充到给定数据库管理系统中的数据的分布的未知特征。事实上，为了使这种技术有用，估计技术应该对不同类型的数据分布和查询模式有效。这是因为DBMS用于各种应用程序，导致填充数据库的数据范围很广。一种名为黄金估计器的新估计技术已经被确定，它使用累积概率分布来创建直方图并捕获潜在的数据分布。该技术还可用于适应查询模式的变化。对于具有空间范围的对象，该项目将产生源自欧拉图形公式的直方图。对于流数据集，将探索能够动态维护直方图的各种方法。将结合亚历山大市数字图书馆和南加州大学商学院的数字校园项目对研究结果进行评估。

Data summarization and estimation can serve as a useful tool for a diverse set of applications ranging from traditional database query optimization to OLAP applications and the exploration of large data sets. During the course of this project, data estimation and summarization techniques will be developed for datasets with different modalities: point datasets, datasets containing objects with spatial extents, and stream datsets. The approach is specifically based on the use of histograms in different contexts. One of the main problems of applying estimation techniques in a database management system is the unknown characteristic of the distribution of the data that will populate a given DBMS. In fact, in order for such a technique to be useful, the estimation technique should be effective for different kinds of data distributions and query patterns. This is because a DBMS is used for a variety of applications resulting in a wide spectrum of data that populates the database. A new estimation technique called the golden estimator has been identified that employs cumulative probability distributions for creating histograms and captures the underlying data distribution. This technique can also be used to adapt to changes in the query patterns. For objects with spatial extents, this project will lead to histograms derived from Euler's formulation for graphs. For stream datasets, a variety of approaches will be explored that are amenable to maintain histograms dynamically. The research results will be evaluated in the context of the Alexandria Digital Library and the Digital Campus projects at UCSB.