Martin L Farach-Colton

US Patent:

8185551, May 22, 2012

Filed:

Jun 8, 2007

Appl. No.:

11/760379

Inventors:

Bradley C. Kuszmaul - Lexington MA, US
Michael A. Bender - East Northport NY, US
Martin Farach-Colton - New York NY, US

Assignee:

Massachusetts Institute of Technology - Cambridge MA
Rutgers University - New Brunswick NJ
Research Foundation of State University of NY - Stony Brook NY

International Classification:

G06F 7/00
G06F 17/30

US Classification:

707790, 707705

Abstract:

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.

US Patent:

8489638, Jul 16, 2013

Filed:

May 21, 2012

Appl. No.:

13/476826

Inventors:

Bradley C. Kuszmaul - Lexington MA, US
Michael A. Bender - East Northport NY, US
Martin Farach-Colton - New York NY, US

Assignee:

Massachusetts Institute of Technology - MA
Research Foundation of State University of New York - NY

International Classification:

G06F 7/00
G06F 17/30

US Classification:

707790, 707705

Abstract:

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.

US Patent:

8495483, Jul 23, 2013

Filed:

Mar 12, 2003

Appl. No.:

10/386110

Inventors:

Jeffrey A. Dean - Menlo Park CA, US
Martin Farach-Colton - New York NY, US
Sanjay Ghemawat - Mountain View CA, US
Benedict Gomes - Mountain View CA, US
Georges R. Hank - Mountain View CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 17/00
G06F 17/30

US Classification:

715205, 715209

Abstract:

Web quotes are gathered from web pages that link to a web page of interest. The web quote may include text from the paragraphs that contain the hypertext links to the page of interest as well as text from other portions of the linked web page, such as text from a nearby header. The obtained web quotes may be ranked based on quality or relevance and may then be incorporated into a search engine's document index or into summary information returned to users in response to a search query.

US Patent:

20110246503, Oct 6, 2011

Filed:

Apr 6, 2010

Appl. No.:

12/755391

Inventors:

Michael A. Bender - Syosset NY, US
Martin Farach-Colton - New York NY, US
Yonatan R. Fogel - Port Jefferson NY, US
Zardosht Kasheff - New York NY, US
Bradley C. Kuszmaul - Lexington MA, US
Vincenzo Liberatore - University Heights OH, US
Barry Perlman - Cambridge MA, US
Rich Prohaska - Westford MA, US
David S. Wells - Waterville VT, US

International Classification:

G06F 17/30

US Classification:

707769, 707797, 707E17012

Abstract:

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.

US Patent:

7296016, Nov 13, 2007

Filed:

Mar 12, 2003

Appl. No.:

10/385752

Inventors:

Martin Farach-Colton - New York NY, US
Monika H. Henzinger - Menlo Park CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 7/00
G06F 17/30

US Classification:

707 5, 707 2, 707 3, 707 4

Abstract:

A system provides search results relating to a point-of-view (POV). The system obtains a search query and POV data. The system generates a list of documents based on the search query and filters the list of documents based on the POV data. Alternatively, the system may perform a search based on the search query and the POV data to generate the list of documents. In either case, the system then presents the list of documents as the result of the search.

US Patent:

20190114324, Apr 18, 2019

Filed:

Oct 11, 2018

Appl. No.:

16/158136

Inventors:

- Hopkinton MA, US
Martin Losada Farach-Colton - New York NY, US
Philip Shilane - Newtown PA, US

International Classification:

G06F 17/30

Abstract:

One example method includes receiving a hash, inserting the hash into an array of an on-disk hash table that has one or more levels that each include a bundle of one or more arrays, and each of the arrays includes a plurality of hashes, and when the array into which the hash was inserted is full, merging the full array down to the next lower level of the on-disk hash table by appending the full array to a group of one or more arrays residing at the next lower level.

US Patent:

20150370860, Dec 24, 2015

Filed:

Feb 24, 2015

Appl. No.:

14/630579

Inventors:

- Durham NC, US
Martin Farach-Colton - New York NY, US
Yonatan R. Fogel - Port Jefferson NY, US
Zardosht Kasheff - New York NY, US
Bradley C. Kuszmaul - Lexington MA, US
Vincenzo Liberatore - University Heights OH, US
Barry Perlman - Cambridge MA, US
Rich Prohaska - Westford MA, US
David S. Wells - Waterville VT, US

Assignee:

Percona, LLC - Durham NC

International Classification:

G06F 17/30
G06F 9/54

Abstract:

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.

US Patent:

20150347477, Dec 3, 2015

Filed:

May 30, 2014

Appl. No.:

14/292600

Inventors:

John Esmet - Brooklyn NY, US
Michael A. Bender - Syosset NY, US
Martin L. Farach-Colton - New York NY, US
Bradley C. Kuszmaul - Lexington MA, US

International Classification:

G06F 17/30

Abstract:

An indexing system and method for a filesystem, such as a database using the POSIX application programming interface, uses two fractal tree indices, a metadata index mapping the full pathname of files to file metadata, preferably data such as returned with a struct stat call, and a data index mapping pathname and block number to a datablock of a predetermined size, optionally a fixed size. The data index has keys ordered lexicographically, and the system and method allows for modifying existing keys, and creating new keys if there is no existing key, for writes smaller than the predetermined block size and for unaligned writes. The invention provides at least about an order of magnitude improvement in microdata operations (such as creating and scanning files smaller than a predetermined size, such as 512-byte files), and has write times comparable with existing file systems.