Amazon.com, Inc.
Compact storage of non-sparse high-dimensionality data

Abstract:

Methods, systems, and computer-readable media for compact storage of non-sparse high-dimensionality data are disclosed. A data store comprises a plurality of records, and the plurality of records represent a space having n dimensions of ordered input values. The space is partitioned into a plurality of non-overlapping segments having the n dimensions. Individual ones of the records correspond to individual ones of the segments. A query is received that comprises one or more input values for at least some of the n dimensions of the space. At least one record is retrieved from the data store based at least in part on the query. The record corresponds to one of the segments in the space, and the record comprises content responsive to the query.