Vincenzo C Liberatore

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:

6438593, Aug 20, 2002

Filed:

May 21, 1998

Appl. No.:

09/082786

Inventors:

Sanjeev Khanna - Highland Park NJ
Vincenzo Liberatore - Somerset NJ

Assignee:

Lucent Technologies Inc. - Murray Hill NJ

International Classification:

G06F 1300

US Classification:

709224, 709203

Abstract:

A paging method for information retrieval from broadcast disk systems is described. In response to a page request (e. g. , a request for an item of data), the method selectively stores and evicts, in and from a fast memory, pages of data broadcasted by the broadcast disk system. The methods proceeds using a three-âcolorâ labelling scheme, wherein the label assigned to a broadcasted page is based on how recently a given page was last requested. If a requested page is stored in fast memory, then the request is immediately served. If the requested page is not stored in fast memory, the request cannot be served until the requested page is broadcasted. While waiting for the requested page to be broadcasted, certain âsomewhat-recentlyâ requested pages are âprefetched,â wherein they are stored in fast memory even though there is no pending request for such pages. Since the size of the fast memory is very small compared to the amount of information being broadcasted, only a small amount of the available information can be stored and there will be significant turnover in the particular stored pages as a function of the page requests. Pages are selected for eviction based upon the âcostâ (to the competitive performance of the method) to replace the evicted page, wherein the least costly page to replace is evicted.

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.