HECURA: Colaborative: Multidimensional and String Indexes for Streaming Data

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