CAREER: Generalized Search Technique for Indexing Complex Data

该项目解决了两个主要挑战。第一个是创建一个软件开发环境，用于容易地为具有大量数据库工作负荷的新的复杂数据，例如地图、图像、声音、视频、序列、文档等生成索引技术。这是通过(1)在对象关系数据库管理系统的上下文中实现称为通用搜索树(GIST)的数据结构，以及(2)开发图形GIST可视化和调试系统来实现的。第二个挑战是对如何以及何时能够开发有效的指数进行严格的数学调查；这被称为索引性理论。可指标性理论类似于复杂性理论，它指导软件开发人员理解如何以及何时可以开发高效的算法。主要区别在于，索引性侧重于索引的空间/时间权衡，以及数据库索引涉及的基本辅助存储挑战。这项研究议程的执行将产生一个框架，数据领域专家(如生物学家、化学家、地球科学家、计算机多媒体研究人员等)可以(1)确定其工作负载是否可索引，以及(2)如果是，则轻松地为其工作负载开发有效的索引，以最小的工作量将这些索引集成到对象关系数据库管理系统中。另一项努力是将开发环境纳入课程，教授索引和索引能力方面的基本和高级技术。这门课程包括软件本身，以及在伯克利大学由首席研究员教授的本科生和研究生课程中测试的作业。

This project addresses two main challenges. The first is to produce a software development environment for easily generating indexing techniques for new complex data, e.g., maps, images, sound, video, sequences, documents, etc., with large database workloads. This is being done by (1) implementing a data structure called a Generalized Search Tree (GiST) in the context of an Object-Relational database management system, and (2) developing a graphical GiST visualization and debugging system. The second challenge is to undertake a rigorous mathematical investigation of how and when one can develop efficient indexes; this is referred to as a Theory of Indexability. Indexability theory is akin to complexity theory, which has guided software developers in understanding how and when one can develop efficient algorithms. The main distinction is that indexability focuses on space/time tradeoffs for indexes, and on the fundamental secondary-storage challenges involved in database indexing. Execution of this research agenda will produce a framework in which data domain experts (e.g., biologists, chemists, earth scientists, computer multimedia researchers, etc.) can (1) identify whether their workloads are indexable, and (2) if so, easily develop efficient indexes for their workloads, integrating these indexes with minimal effort into Object-Relational database management systems. An additional effort is to integrate the development environment into a curriculum for teaching both basic and advanced techniques in indexing and indexability. This curriculum includes the software itself, along with assignments being tested in undergraduate and graduate courses at Berkeley taught by the principal investigator.