SYSTEM AND METHODS FOR MAPPING AND SEARCHING OBJECTS IN MULTIDIMENSIONAL SPACE

摘要

This invention relates to a system and methods for determining the placement of an object in a distributed key-value store by mapping the object to nodes in multidimensional hyperspace. A search function supports efficient object retrieval, even when the search query requests multiple objects and specifies them through non-primary keys. In response to a search query, the search is translated into hyperregions in the hyperspace to determine the set of nodes that hold the queried data object. The number of contacted nodes and the number of scanned objects are significantly reduced in comparison to prior art techniques.

主权项

1. A distributed key-value store within a distributed computing environment, comprising:
a hyperspace divided into a plurality of hyperspace regions; a plurality of data objects, each data object having coordinates computed from one or more attribute values of the data object, a plurality of data storage nodes, wherein each hyperspace region is assigned to one or more data storage nodes and each data storage node is mapped to one or more data objects whose coordinates are encapsulated by the hyperspace region.