High Throughput I/O for Large Scale Data Repositories

包括地理信息系统、科学可视化和高维数据库在内的许多应用都包括大到TB大小的大型数据仓库。尽管现在可以实现数TB的存储空间，但有效的检索是一个具有挑战性的问题。该研究涉及数据在并行磁盘间分布以实现高效检索的新方案，包括使用复制的方案、高效的检索算法以及适应磁盘故障、磁盘增加和查询模式变化的自组织方案。在过去的几年中，分散引起了人们的极大兴趣，并在高维数据管理、地理信息系统和科学可视化等领域得到了应用。大多数去聚类研究都集中在空间范围查询和具有低最坏情况加性误差的搜索方案上。这项研究从多个方面研究了去聚类法，包括新的去聚类法、复制型去聚类法、异构型去聚类法、自适应去聚类法和使用多个数据库的去聚类法。调查人员从理论和实践两方面探讨每一个问题，研究理论上可能的，实践中可以实现的，并试图缩小两者之间的差距。研究人员研究了具有坚实理论基础的新颖的分选方案，包括数论分选和设计理论分选。研究了各种类型查询的复制策略，包括空间范围查询和任意查询。基于设计论复制的检索算法具有线性复杂度，保证了最坏情况下的检索代价。研究人员研究了检索在复杂性和检索成本之间的权衡，并开发了一套检索协议。这项研究涉及自适应去集群方案，该方案通过在空闲期间在磁盘之间移动存储桶来适应磁盘故障、磁盘添加和改变查询类型。

Many applications including geographical information systems, scientific visualization and igh-dimensional databases include large data repositories up to terabytes in size. Although terabytes of storage space is now achievable, efficient retrieval is a challenging problem. This research involves novel schemes to distribute data among parallel disks for efficient retrieval including schemes using replication, efficient retrieval algorithms and self-organizing schemes that adapt to disk failures, disk additions and changing query patterns.Declustering has attracted a lot of interest over the last few years and has applications in many areas including high-dimensional data management, geographical information systems and scientific visualization. Most of the declustering research have focused on spatial range queries and finding schemes with low worst-case additive error. This research investigates various aspects of declustering including novel declustering schemes, replicated declustering, heterogeneous declustering, adaptive declustering and declustering using multiple databases. The investigators approach every issue both theoretically and practically, study what is theoretically possible, what can be achieved in practice and try to close the gap between the two. The investigators study novel declustering schemes with solid theoretical foundations including number-theoretic declustering and design-theoretic declustering. Replication strategies for various types of queries including spatial range queries and arbitrary queries are studied. Retrieval algorithm for design-theoretic replication has linear complexity and guarantees worst-case retrieval cost. The investigators study tradeoffs in retrieval between complexity and retrieval cost and develop a suite of protocols for retrieval. This research involves adaptive declustering schemes that adapt to disk failures, disk additions and changing query types by moving buckets between disks during idle periods.