Proximity search is an important type of database query which is essential to many practical applications involving various types of metric data, including multivariate data with distance function. Point spatial data is a popular subset of metric data in which each data record corresponds to a point in a multidimensional space, and the proximity is represented as a distance function, such as the Euclidean distance, defined on the multidimensional space. Numerous hierarchical data structures, under the name of point spatial data structures, have been developed for implementing efficient spatial proximity searches. Much less work has been done on developing general hierarchical metric data structures for general metric data, such as non-spatial multivariate data. This paper presents an innovative approach for deriving a new class of hierarchical metric data structures from existing point spatial data structures. Instead of performing direct decomposition on metric data as is done for previous hierarchical data structures such as metric trees and vp-trees, we define a class of simple proximity-preserving mappings from metric data to multidimensional spaces, which we call multipolar mappings. By applying multipolar mappings to metric data, hierarchical decompositions can be done in multidimensional space, and various point spatial data structures, such as quadtree, octree, or k-d tree, can be utilized for storing and accessing metric data based on proximity.

Databases are an important part of many Computer Assisted Design (CAD) applications. Real world knowledge is often defined by a database which is managed by a database system. Unlike most traditional database applications, the CAD process involves significant amounts of scientific and engineering computation on database contents to produce a result. Existing standalone language database systems often cannot meet this computational need. Users can either forego the use of a database system and its conveniences or interface conventional Procedure Oriented Language (POL) programs to database systems for the computational work. This paper describes EXTRAS, a relational algebra query language with extensions for numerical computation. This language has the advantages of a unified approach to computation and database query capabilities and of offering a high level language for numerical computation based on relations.