HECURA: Colaborative: Multidimensional and String Indexes for Streaming Data

该研究项目旨在理解和开发用于维护流数据超线性索引的系统。 超线性索引提供了对不易线性化（全序）的抽象空间的搜索能力。相比之下，以B树为代表的线性索引支持对全序数据的点和范围查询。超线性索引的例子包括多维索引，它可以是在一个几何域上，例如地理数据，也可以是在多个线性索引上；以及全文查询，其中可以包括搜索特定单词或子字符串。当今数据库中的超线性索引无法支持高插入率。 在传统的机械磁盘驱动器上，现有的超线性索引在最坏的情况下只能支持每秒大约一百次插入。 对于许多重要的应用程序来说，这太慢了，因此数据库用户通常会避免超线性索引。 即使是基于B树的传统线性索引也无法支持许多数据库所要求的高插入率。本研究研究流式超线性索引，即有效支持全文或多维查询的索引，并且可以以与磁盘带宽相关的速度而不是每秒寻道速度更新。其中重要的研究问题如下：（1）为流式超线性索引设计高效的文件结构； (2)研究流式超线性索引如何为改进文件系统铺平道路； (3)确定缓存忽略算法技术是否可以增强流式超线性索引； (4) 为事务和恢复编写复杂的数据结构。如果成功，这项研究将展示如何构建比当今基于 B 树的文件系统具有显着更好性能的文件系统，如何实时维护丰富的几何数据和多维非地理数据库，以及如何实时维护全文可搜索数据库。 例如，当今的一些文件系统尝试维护全文索引以快速查找文件中的字符串，但这些系统在高数据写入速率时通常会落后。 流式超线性索引将允许这样的文件系统跟上，并将提高高端存储系统和相对较小的消费存储系统的可用性，但这些系统太大而无法用当今的索引进行索引。研究人员正在开发关于流式索引技术的课程材料，这些材料将在麻省理工学院开放课程计划（http://ocw.mit.edu）下免费提供。有关该项目的更多信息可以在该项目网页上找到： http://supertech.csail.mit.edu/superlinear-indexes

This research project aims to understand and develop systems formaintaining superlinear indexes for streaming data. A superlinearindex provides search capability over an abstract space that cannoteasily be linearized (totally ordered). In contrast, a linear index,typified by a B-tree, supports point and range queries on totallyordered data.Examples of superlinear indexes include multidimensional indexes,which can be over a geometric domain, such as geographic data, orwhich can be over multiple linear indexes; and full text queries,which can include searching for a particular word or substring.The superlinear indexes found in today's databases cannot support highrates of insertion. On traditional mechanical disk drives, theexisting superlinear indexes can only support about one hundredinsertions per second in the worst case. For many importantapplications, that is too slow, and so database users often avoidsuperlinear indexing. Even traditional linear indexes based onB-trees cannot support the high insertion rates demanded by manydatabases.This research investigates streaming superlinear indexes, that is,indexes that efficiently support full text or multidimensionalqueries, and can be updated at speeds that are related to diskbandwidth rather than seeks per second.Among the significant research issues are the following: (1) designefficient files structures for streaming superlinear indexes; (2)investigate how streaming superlinear indexes might pave the way toimproved file systems; (3) determine whether cache-obliviousalgorithms technology can enhance streaming superlinear indexes; and(4) program complex data structures for transactions and recovery.If successful, this research will show how to build filesystems thatachieve dramatically better performance than today's B-tree-basedfilesystems, how to maintain rich geometrical data andmultidimensional nongeographical databases in real time, and how tomaintain full-text searchable databases in real time. For example,some of today's file systems try to maintain an full-text index tofind strings in files quickly, but these systems often fall behind athigh data write rates. A streaming superlinear index would allow sucha file system to keep up, and would improve the usability of bothhigh-end storage systems and relatively small consumer storage systemsthat are nonetheless too large to index with today's indexes.The researchers are developing course materials on streaming indexingtechnology which will be made freely available under the MITOpenCourseWare initiative (http://ocw.mit.edu).Further information on this project may be found at the projectweb page: http://supertech.csail.mit.edu/superlinear-indexes