Harvard College

Stratos Idreos

Niv Dayan

Michael H Kester

Subarna Chatterjee

Meena Jagadeesan

Wilson Qin

Brian Hentschel

Manoussos Gavriil Athanassoulis

Wasay Abdul

Embodiments of the invention utilize an improved LSM-tree-based key-value approach to strike the optimal balance between the costs of updates and lookups and storage space. The improved approach involves use of a new merge policy that removes merge operations from all but the largest levels of LSM-tree. In addition, the improved approach may include an improved LSM-tree that allows separate control over the frequency of merge operations for the largest level and for all other levels. By adjusting various parameters, such as the storage capacity of the largest level, the storage capacity of the other smaller levels, and/or the size ratio between adjacent levels in the improved LSM-tree, the improved LSM-tree-based key-value approach may maximize throughput for a particular workload.

Key-value stores with optimized merge policies and optimized LSM-tree structures

Embodiments of the invention utilize a 'data canopy' that breaks statistical measures down to basic primitives for various data portions and stores the basic aggregates in a library within an in-memory data structure. When a queried statistical measure involves a basic aggregate stored in the library over a data portion that at least partially overlaps the data portion associated with the basic aggregate, the basic aggregate may be reused in the statistical computation of the queried measure.

Systems and methods for accelerating exploratory statistical analysis

Embodiments of the invention utilize an optimized key-value storage engine to strike the optimal balance between cloud-cost and performance and supports queries, including updates, lookups, range queries, inserts, and read-modify-writes. Cloud cost is manifested in purchasing both storage and processing resources. The improved approach has the ability to self-design and instantiate holistic configurations given a workload, a cloud budget, and optionally performance goals and a set of Service Level Agreement (SLA) specifications. A configuration reflects an optimized storage engine design in terms of, for example, the individual data structures design (in-memory and on-disk) in the engine as well as their algorithms and interactions, a cloud provider, and the exact virtual machines to be used.

Optimized self-designing key-value storage engine

Various approaches for accelerating data access to a computer memory and predicate evaluation includes storing, in the computer memory, (i) base data as multiple base columns, (ii) multiple sketched columns each corresponding to a base column in the base data and having smaller code values compared thereto, and (iii) a compression map for mapping one or more base columns to the corresponding sketched column; applying the compression map to a query having a predicate; determining data on the sketched column that satisfies the predicate; and evaluating the predicate based at least in part on the determined data on the sketched column without accessing the base column in the base data.

Rapid and robust predicate evaluation

Embodiments of the invention utilize an improved LSM-tree-based key-value approach to strike the optimal balance between the costs of updates and lookups with any given main memory budget. The improved approach involves allocating memory to Bloom filters differently across different levels so as to minimize the sum of the false positive rates associated with the Bloom filters. In addition, the improved approach may predict the impact of the system design parameter(s) and/or environmental parameter(s) on the lookup performance. Subsequently, the improved approach may 'self-tune' the system design parameter(s) and/or environment parameter(s) to maximize the throughput.

Optimized navigable key-value store

Embodiments of the present invention provide a new multi-level data structure, log-structured merge bush (LSM-bush), to alleviate the performance compromise between LSH-table and LSM-tree data structures. Similar to LSM-tree, LSM-bush may buffer writes in memory, merge the writes as sorted runs across multiple levels in storage, and use in-memory fence pointers and Bloom filters to facilitate lookups. LSM-bush differs from LSM-tree in that it allows newer data to be merged more 'lazily' than LSM-tree. This can be achieved by allowing larger numbers of runs to be collected at the smaller levels before merging them.

Growing community of inventors

Cambridge, MA, United States of America

Stratos Idreos