High-dimensional index structure
AssigneeAT&T Corp.
InventorsStefan Berchtold, Christian Boehm, Hans-Peter Kriegel
Life of this patent
Estimating the term…
Abstract
A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure is disclosed. The data space is divided into a first plurality of pyramids each having a center point of the data space as a top and a (d-1) dimensional surface of the data space as a base, wherein the first plurality of pyramids is equal to twice the number of dimensions of the data space. Each pyramid is then divided into a second plurality of partitions. A Pyramid-value for each partition is then computed. Finally, each partition is stored in the index structure using the Pyramid-value as an index key.
Claims12
A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure, comprising the steps of:
- splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1 dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space;
- dividing each pyramid into a second plurality of partitions;
- computing a Pyramid-value for each partition;
- and
- storing each partition in said index structure using said Pyramid-value as an index key.
A method for storing and querying multidimensional data points, comprising the steps of:
- splitting data space into a first plurality of pyramids each having a center point of the data space as a top and a d-1dimensional surface, a number of dimensions equal to the number of dimensions of the data space minus 1, of the data space as a base, wherein said first plurality of pyramids is equal to twice the number of dimensions of the data space;
- dividing each pyramid into a second plurality of partitions;
- computing a Pyramid-value for each partition;
- storing each partition in a 1-dimensional index structure using said Pyramid-value as an index key;
- computing the range of Pyramid-values affected by the query;
- querying the index using said range to produce a candidate set of partitions;
- outputting all candidate partitions that are inside the query range.
Dependencies are inferred from the claim text.