SGER: Fractals for Spatial and Temporal Databases

该项目的目标是使用分形学中的概念来解决查询优化、空间数据库和时态数据库中长期存在的数据库问题。此外，它还介绍了用于大型数据库应用程序的其他应用程序的强大工具，如预测、时间序列数据挖掘、缓冲和预取。典型的问题可以是多种多样的：在一个真实的点集合中，就像世界上的城市一样，在一个地理信息系统(GIS)设置中，估计离纽约市10英里范围内的平均邻居数量，以及在一个磁盘调度设置中，“给出过去的磁盘页面请求的历史记录，我们可以对未来的请求做出什么预测”。由于真实数据集表现出的不一致性，得出这类问题的估计答案是出了名的困难。虽然不切实际，但一致性和独立性假设在过去的工作中传统上一直被使用，主要是因为它们在数学上容易处理，而且因为缺乏更好的东西。目前的项目建议用自相似假设取代它们，从而产生更准确的估计。采用一致性假设的当前估计误差高达179%；采用分形法，我们预计误差将降至10%或更低。这将允许更准确的选择性估计，产生更现实的查询答案和更成功的查询优化，以及更好的磁盘调度，提高数据库和磁盘系统的性能。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