Histogram-based Query Estimation for Datasets with different Modalities

不同模态数据集的基于直方图的查询估计

• 批准号: 0209112
• 负责人: Divyakant Agrawal
• 金额: $ 28.71万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-15 至 2005-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0209112&HistoricalAwards=false
• 关键词: Histogram; based; Query; Estimation; Datasets

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.

数据汇总和估计可以作为一个有用的工具，用于各种各样的应用程序，从传统的数据库查询优化到OLAP应用程序和大型数据集的探索。 在这个项目的过程中，数据估计和总结技术将开发不同形式的数据集：点数据集，数据集包含对象的空间范围，和流数据集。 该方法特别基于在不同上下文中使用直方图。 在数据库管理系统中应用估计技术的主要问题之一是填充给定DBMS的数据的分布的未知特性。 事实上，为了使这种技术有用，估计技术应该对不同类型的数据分布和查询模式有效。 这是因为DBMS用于各种应用程序，从而导致填充数据库的数据范围很广。 一种新的估计技术称为黄金估计器已被确定，采用累积概率分布创建直方图，并捕捉底层数据分布。这种技术也可以用来适应查询模式的变化。 对于具有空间范围的对象，该项目将导致从欧拉的图形公式导出的直方图。对于流数据集，将探索各种方法，这些方法可以动态维护直方图。研究结果将在亚历山大数字图书馆和UCSB数字校园项目的背景下进行评估。