The partition value is then chosen to be the median value along the partition dimension. On the other hand, a derived basis might be calculated from principal components, which may well pay off in subsequent searches. This type of approach would provide an additional tool for serendipitous searches, since strange objects would reside away from the bulk of the data. We are also investigating more generalized methods of partitioning. 3.3 Geometric Querying Geometric searches, such as nearest neighbor or all objects within a metric distance from a given object, can be visualized as finding all points within the search ellipsoid or polyhedron.
Simple queries are Boolean combinations of cuts within the attribute space of the data.
Further geometric queries can be constructed through linear combinations of the attributes, proximity cuts, and K-nearest neighbor searches. Curved decision surfaces, separating various classes of objects, can be approximated by multidimensional polyhedra. These geometric queries use the nodal boundaries to find the cells that intersect the query volume and must be searched in more detail. One of the basic operations required is a quick rejection test of the rectangular cells to eliminate those that do not intersect the query volume. For those cells that are not rejected, the volume fraction of the intersection between the cell and the query volume must be estimated.