Efficient Geometry-based Similarity Search of 3D Spatial Databases Daniel A. Keim University of Halle-Wittenberg, Kurt-Mothes-Str. 1, D-06120 Halle, Germany [email protected] Abstract Searching a database of 3D-volume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications - for example, in Medicine and CAD. In this paper, we present a new geometry- based solution to the problem of searching for similar 3D-vol- ume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D ob- jects to speed up the search process. We formally show the cor- rectness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approxi- mations. We finally provide a performance evaluation of our new index structure revealing significant performance improve- ments over existing approaches. 1 Introduction Searching a database of 3D objects for objects which are similar to a given 3D search object is an important prob- lem. The problem arises in a number of applications such as CAD and Medicine. Since our motivation for the work presented in this paper comes from a cooperation with a radiological clinic, in the following we briefly describe the background. The specific medical application of our part- ners in medicine is epilepsy of children. The current med- ical theory of epilepsy of children assumes that an irregu- lar development of a specific portion of the brain called the hippocampus is the reason for epilepsy. In several studies, it has been observed that epilepsy only occurs with children whose hippocampi are significantly larger than the average hippocampus of healthy children. On the other hand, it has been found that there also exists a signif- icant number of children which have large hippocampi but do not develop epilepsy. The current medical practice is to use the available mag- netic resonance imaging (-1) and computer tomography (CT) data to determine the volume of the patient’s hippoc- Permission to make digital or hard copies of all or part of this work f01 personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that topics hear this notice and the full citation on the tirst page. TO COpy othcrwisc, to republish, to post on swvers or to rcdisrributc to lists. requires prior specific permission and/or a fee. SIGMOD ‘99 Philadelphia PA Copyright ACM 1999 l-58113-084-8/99/05...$5.00 ampus. The data resulting from MRI or CT scanning of the patient are multiple layers of images (cf. Figure la) which can be segmented (cf. Figure lb) and then combined into a voxel-based 3D representation (cf. Figure 2). Note that the position of the patient is fixed in taking the MRI or CT images and therefore, no significant translation or rotation may occur. Depending on the determined volume, the hip- pocampus is then completely removed by brain surgery. Although this procedure is the best medical doctors are able to provide for the time being, there is a serious need for a more thorough analysis of the hippocampus and the volume defects that cause epilepsy. The observation of children with a large hippocampus but no epilepsy leads to the hypothesis that the shape of the deformation may indi- cate the defect. In first studies, initial support for this hy- pothesis has been collected. For a thorough analysis, how- ever, a large number of hippocampi has to be examined and their shapes have to be compared. Using a database of hippocampi, the deformations that lead to epilepsy can be better understood and the surgery can hopefully be im- proved, e.g., by only removing the affected portions of the hippocampus. A more immediate goal, however, is to use the database to search for similar cases and make the sur- gery decision based on the outcome of this search. This al- ready would largely improve the decision process and help to avoid unnecessary surgeries. Although our work is motivated by a rather specific medical application, the problem of finding all objects from a database of 3D ob- jects which are similar to a given 3D object is a general problem which arises in many application areas such as CAD, pattern recognition, and others. It is widely recognized that 3D similarity search is a diffi- cult problem-by far more difficult than the 2D similarity search. Database technology does no yet support geome- try-based similarity search of 3D-objects. In comparison to the available systems that support 2D spatial data, the 3D data is much more complex. The currently most widely used techniques for accessing database of complex objects are feature-based approaches (e.g., [Fal94, MG 951) which are mainly used as a simple filter to restrict the search space. In case of our application, a useful feature would be, for example, the volume of the objects or a fea- ture vector containing the volumes of a pattern spectrum of the objects [Kor 961. Although filtering approaches can be very effective, in our application they do not provide good 419neighborhood relation -N , and the light grey voxels are in neighborhood relation -k . In Figure 3b, the dark grey squares are in neighborhood relation -N0 of the black mid- dle square. Figure 3b also shows two example objects - the upper fulfills definition 2 using the neighborhood rela- tion -N, while the lower object would not be allowed using the degree zero neighborhood relation. Due to the volume properties of our medical volume objects, in our applica- tion, it is appropriate to use a -N0 neighborhood relation. To define the similarity search task on 3D-volume objects, we first need to define a similarity measure 8: vol x Vol+ 31 which determines the volume