Apparatus and method for performing transformation-based indexing of high-dimensional data

Abstract

A method and apparatus for implementation in a database management system transforms high-dimensional data points to a single-dimensional space so that single-dimensional values can be used as representative index keys for high-dimensional data points and a single-dimensional index structure can be employed to index the transformed values. Upon achieving transformed values, known single-dimensional indexing structures can be employed. To achieve transformation from high-dimensions to a single-dimension, attribute values of a data item, each representing a different dimension, are mapped into a range and an integer value is assigned to each dimension. Either the minimum or maximum dimension value for the multi-dimensional data item is selected, and the minimum or maximum dimensional value is added to the integer value. As a result of this transformation, data points are mapped over a range in a single dimension and associated single-dimension values are used as a representative index key for subsequent search queries.