SGER: Fractals for Spatial and Temporal Databases

这个项目的目标是使用分形的概念来解决查询优化，空间数据库和时态数据库中长期存在的数据库问题。此外，它还介绍了分形，混沌和非线性系统的强大工具，用于其他应用程序，如预测，时间序列数据挖掘，缓冲和预取，大型数据库应用程序。典型的问题可以是多种多样的：在GIS（地理信息系统）设置中的“在一组真实的点中，如世界上的城市，估计距离纽约市10英里内的邻居的平均数量”，以及在磁盘调度设置中的“给定过去的磁盘页面请求的历史，我们可以预测未来的请求是什么”。由于真实的数据集表现出的非均匀性，要得出这些问题的估计答案是非常困难的。虽然不切实际，但一致性和独立性假设在过去的研究中一直被传统地使用，主要是因为它们在数学上的易处理性，也因为缺乏更好的假设。目前的项目建议用自相似性的假设来代替它们，从而得到更准确的估计。目前使用均匀性假设进行的估计会导致高达179%的误差;使用分形，我们预计误差将下降到10%或更低。这将允许更准确的选择性估计，为查询提供更真实的答案，更成功的查询优化，以及更好的磁盘调度，提高数据库和磁盘的性能systems.http://www.cs.cmu.edu/~christos

The goal of this project is to use concepts from fractals to solve long-standing database problems in query optimization, spatial databases, and temporal databases. Moreover, it introduces the powerful tools of fractals, chaos and non-linear systems for additional applications, like forecasting, time-sequence data mining, buffering and prefetching, for large database applications. Typical questions can be as diverse as: "In a real set of points, like cities of the world, estimate the average number of neighbors within 10 miles from New York city" in a GIS (Geographic Information System) setting, and "Given the history of past disk page requests, what can we forecast for future requests" in a disk scheduling setting. Deriving estimated answers to such questions is notoriously hard, because of the non-uniformities that real datasets exhibit. Although unrealistic, the uniformity and independence assumptions have been traditionally used in past efforts, mainly because of their mathematical tractability and because of the lack of anything better. The current project proposes to replace them with the assumption of self-similarity, leading to much more accurate estimates. Current estimates with the uniformity assumption lead to up to 179 per cent error; with fractals, we expect the error to go down to 10 per cent or less. This will allow for more accurate selectivity estimations, yielding more realistic answers to queries and more successful query optimization, and better disk scheduling, improving the performance of database and disk systems.http://www.cs.cmu.edu/~christos