HECURA: Colaborative: Multidimensional and String Indexes for Streaming Data

HECURA：协作：流数据的多维和字符串索引

• 批准号: 0937860
• 负责人: Charles Leiserson
• 金额: $ 60万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0937860&HistoricalAwards=false
• 关键词: HECURA; Colaborative; Multidimensional; String; 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

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