Patent · US Expired

High-dimensional index structure

US6154746A · kind A · utility

58Cited by

2References

12Claims

0Family size

Assignee

AT&T CORP. · US

Inventors

Stefan Berchtold · Augsburg, DE
Christian Boehm · Huntington, US
Hans-Peter Kriegel · Bobingen, DE

Key dates

Filing date	Apr 22, 1998
Grant date	Nov 28, 2000
Priority date	—
Expiry date	Apr 22, 2018

Classification

Technology area (CPC Y)Emerging Cross-Sectional Technologies
CPC primaryY10S707/99943
WIPO fieldComputer technology
WIPO sectorElectrical engineering

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.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.