Massachusetts Institute of Technology

The State University of New York

Rutgers, the State University of New Jersey

Sandia Corporation

Tokutek, Inc.

Michael A Bender

Bradley C Kuszmaul

Martin Farach-Colton

David S Wells

Zardosht Kasheff

Cynthia A Phillips

Barry Perlman

Vitus J Leung

Yonatan R Fogel

David P Bunde

Vincenzo Liberatore

Rich Prohaska

A method, apparatus and computer program product for storing data in a disk storage system is presented. A high-performance dictionary data structure is defined. The dictionary data structure is stored on a disk storage system. Key-value pairs can be inserted and deleted into the dictionary data structure. Updates run faster than one insertion per disk-head movement. The structure can also be stored on any system with two or more levels of memory. The dictionary is high performance and supports with full transactional semantics, concurrent access from multiple transactions, and logging and recovery. Keys can be looked up with only a logarithmic number of transfers, even for keys that have been recently inserted or deleted. Queries can be performed on ranges of key-value pairs, including recently inserted or deleted pairs, at a constant fraction of the bandwidth of the disk.

High-performance streaming dictionary

A method, apparatus and computer program product for storing data in a disk storage system is presented. A dictionary data structure is defined and stored on the disk storage system. Key-value pairs can be inserted and deleted into the dictionary data structure, with full transactional semantics, at a rate that is faster than one insertion per disk-head movement. Keys can be looked up with only a logarithmic number of transfers, even for keys that have been recently inserted or deleted. Queries can be performed on ranges of key-value pairs, including recently inserted or deleted pairs, at a constant fraction of the bandwidth of the disk. The dictionary employs indirect logging for physical block logging.

Disk-resident streaming dictionary

In a multiple processor computing apparatus, directional routing restrictions and a logical channel construct permit fault tolerant, deadlock-free routing. Processor allocation can be performed by creating a linear ordering of the processors based on routing rules used for routing communications between the processors. The linear ordering can assume a loop configuration, and bin-packing is applied to this loop configuration. The interconnection of the processors can be conceptualized as a generally rectangular 3-dimensional grid, and the MC allocation algorithm is applied with respect to the 3-dimensional grid.

Allocating application to group of consecutive processors in fault-tolerant deadlock-free routing path defined by routers obeying same rules for path selection

Growing community of inventors

East Northport, NY, United States of America

Michael A Bender