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.