Challenges in Finding an Appropriate Multi-Dimensional Index Structure with Respect to Specific Use Cases Alexander Grebhahn David Broneske Martin Schäler Institute of Technical and Institute of Technical and Institute of Technical and Business Information Systems Business Information Systems Business Information Systems University of Magdeburg University of Magdeburg University of Magdeburg grebhahn@st.ovgu.de dbronesk@st.ovgu.de schaeler@ovgu.de Reimar Schröter Veit Köppen Gunter Saake Institute of Technical and Center for Digital Engineering Institute of Technical and Business Information Systems University of Magdeburg Business Information Systems University of Magdeburg vkoeppen@ovgu.de University of Magdeburg rschroet@st.ovgu.de saake@ovgu.de ABSTRACT It is possible to extract feature vectors from an item to man- In recent years, index structures for managing multi-dimen- age the data in a compressed and meaningful way. For man- sional data became increasingly important. Due to hetero- aging these feature vectors, multi-dimensional index struc- geneous systems and specific use cases, it is a complex chal- tures can be used. In general, the question arises, which lenge to find an appropriate index structure for specific prob- index structure supports managing data best. Throughout lems, such as finding similar fingerprints or micro traces in a this paper, index structure performance describes suitability database. One aspect that should be considered in general is with respect to a specific use case. However, we analyze core the dimensionality and the related curse of dimensionality. aspects that have to be considered, if trying to answer this However, dimensionality of data is just one component for a specific use case. In order to achieve a reconstructible that have to be considered. To address the challenges of and valid comparison, we present the idea of a framework finding the appropriate index, we motivate the necessity of that allows the comparison of different index structures in a a framework to evaluate indexes for specific use cases. Fur- homogeneous test environment. thermore, we discuss core components of a framework that This paper is organized as follows: In Section 2, we give supports users in finding the most appropriate index struc- a short overview of basic components that have to be con- ture for their use case. sidered for evaluating the performance of index structures. Within Section 3, we give an overview of additional chal- lenges, which have to be handled by using index structures Keywords in a specific use case. Finally, in Section 4, we present core index structures, evaluation, multi-dimensional data components that a framework needs for quantitatively eval- uation of multi-dimensional index structures with respect to different use cases. 1. INTRODUCTION In the last years, data storage and management in com- 2. BASIC CHALLENGES puter-aided systems became more advanced, because of an increasing amount of unstructured data being stored. For Querying multi-dimensional data in an efficient way is example, in multimedia databases images or videos are stored a complex challenge. Within the last decades, new index and analyzed to find similar data items. A special use case structures are proposed and existing once are improved to is the Digi-Dak Database Project1 , where multi-dimensional solve this challenge. Regarding a specific use case, it is not feature vectors of fingerprints and micro traces are stored in suitable to consider an index structure in isolation. Addi- a database. To manage these data items, methods are re- tionally data properties, used query types, and underlying quired to handle unstructured data in an appropriate way. distance metrics have to be taken into account. In this sec- tion, we give a short overview of these four basic challenges. 1 https://omen.cs.uni-magdeburg.de/digi-dak 2.1 Data Properties Characteristics of data cause main challenges of querying data within a database system. For instance, data dimen- sionality has to be considered, because existing index struc- tures are generally effected by the curse of dimensionality [7, 23]. As a result, index structures, that are suitable for a small number of dimensions are not necessarily suitable for a larger amount of dimensions. An additional important 24th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. property is the data distribution, because some index struc- Copyright is held by the author/owner(s). tures are more practicable for clustered data than others. Furthermore, value domain and the type of the data has to R1 R4 be considered. R7 2.2 Query Types R5 R6 R2 Based on the work of Böhm et al. [8], query types can be R8 categorized into two groups: -similarity queries and Nearest- R3 Neighbor-similarity (NN-similarity) queries. The former de- R10 A R9 B scribes a query, resulting in a set of data points being situ- R11 C ated in a defined -distance to the query point, whereas the latter results in a data point being the nearest item to the R12 query point. Describing these two groups, the -similarity and NN-similarity has to be defined. Figure 1: R-Tree with overlapping MBRs. Definition: -similarity Query. Two data points p1 and p2 are -similar if and only if d(p1 , p2 ) ≤ . The function d defines a similarity measure 2.4 Index Structures for two points. In literature, similarity measures are of- Since we aim at providing a comprehensive set of indexes, ten replaced by distance metrics, which we review in Sec- we want to consider different types of index structures. Thus, tion 2.3. For finding all points in the data base being - we use the classification of Weber et al. [23] to address a similar, an -similarity query is executed. A special case of broad variety of different approaches. Thus, index struc- the -similarity is represented for  = 0, because this implies tures are classified by partitioning of the data space. Index two identical points and an exact match is executed [8]. structures that partition the whole space are called space partitioning methods, whereas data partitioning methods Definition: NN-similarity Query. partition the necessary space according to the location of The data point p1 is NN-similar to p2 with respect to a data points [8, 23]. Consequently, there are regions that data base of points DB if and only if ∀p ∈ DB, p 6= p1 : are not taken into account by performing a query on data d(p2 , p1 ) ≤ d(p2 , p). For NN-similarity queries, all points partitioning methods. in a database are retrieved that are NN-similar to the query Alternatively, Andoni and Indyk [2] classify index struc- point. An extension to the NN-similarity query is presented, tures by query results. There are exact index structures that when instead of a nearest neighbor, k nearest neighbors have guarantee to retrieve the exact result of a query. Although, to be retrieved. In this paper, we call the resulting query this behavior is usually preferred, there are approximation- k-NN query. based index structures, guaranteeing to retrieve points that are similar to the correct result of a query. For instance for k- Apart from the mentioned similarity range query, window NN queries, approximation-based index structures provide k queries are common queries and often called range queries in near neighbors to the query point instead of all exact nearest literature [24]. These window queries are defined by intervals neighbors. Hereby, the quality of the retrieved results, called for every queried dimension. precision, can differ significantly, because approximate in- 2.3 Distance Metrics dex structures aim at improving the query performance by decreasing the precision. Nevertheless, an approximation- To execute similarity queries, we require a function com- based index should hold a threshold, because resulting data puting the similarity of two data items. To this end, similar- would not be useful. In the following sections, we present ity for equal points is 1 whereas the maximum dissimilarity some representatives of index structures. First, exact index is expressed by 0. Equivalent information is delivered from structures, such as R-Tree [11], Pyramid Technique [5], and distance metrics, whereupon two data items are more simi- VA-File [22] are introduced. Subsequently, p-stable Local- lar, the smaller their distance is. ity Sensitive Hashing [12] as an approximation-based index The most common distance metrics are Minkowsky class structure is presented. metrics, also called Lp distance metrics. The distance of two data items x and y is computed by: 2.4.1 Exact Index Structures d X 1/p Giving an overview of existing index structures, we intro- Lp (x, y) = (xi − yi )p . duce promising exact index structures in this section. Fur- i=1 thermore, the difference between space partitioning and data By choosing different values for p, different representatives partitioning methods is stated by presenting at least one in- of this class are produced. For p = 2, the Euclidean distance dex structure for each category. metric is generated, which dominates common database sys- tems according to Bugatti et al. [9]. R-Tree. Beneath these distance metrics, there are many other met- One of the most important multi-dimensional index struc- rics, such as Canberra [9] or Dynamical-Partial [16] dis- tures is the R-Tree [11], introduced by Guttmann in 1984. tance function. In contrast to Minkowsky distance func- Since this time, many new index structures are proposed tions, Dynamical-Partial distance metric dm uses only the based on the ideas used in the R-Tree. For instance R+ - m smallest distances for the computation of the distance of Tree [21], R∗ -Tree [4], X-Tree [6], A-Tree [19], and SR- data items [16]. As a result, in some specific use cases, it Tree [13]. Beside these structures, there are many more can be a great benefit using the Dynamical-Partial distance index structures which are not mentioned here. For fur- metric, because the influence of particular dimensions can ther informations, see Samet [20], giving a comprehensive deteriorate the distance of data items. overview of existing index structures. (0; 1) (0; 1) Approximation File A 00 11 N 11 01 A D B B 01 11 O 11 01 11 J (0,5; 0,5) C C 01 11 P 11 00 K (0,5; 0,5) D 10 11 Q 10 01 E L H E 01 10 R 11 00 F M 10 G F 01 10 S 10 00 I W G 01 10 T 01 00 N H 00 10 U 10 00 01 X I 00 10 V 10 01 Y V Q O J 10 11 W 10 10 Z U P K 11 11 X 00 01 00 L 11 10 Y 01 01 (0; 0) (1; 0) (0; 0) (1; 0) T S R M 11 10 Z 00 00 (a) (b) 00 01 10 11 Figure 2: Space partition of a 2-d space by Berchtold Figure 3: Partitioning of the VA-File. et al. [5] (a) and Lee and Kim [15] (b). However, the basic idea of these index structures is to ad- degeneration of most index structures to a sequential scan, if ministrate points hierarchically in a tree. The R-Tree par- the dimensionality of data points exceeds a certain limit [23]. titions the data space using minimum bounding rectangles Hence, the authors propose to accelerate the sequential scan (MBR). A minimum bounding rectangle can be described by using vector approximation. by two points, being the end of the diagonal of the rectan- The VA-File divides each dimension of the space into 2b gle. Stepwise, the space is partitioned by MBRs, so that the equally filled cells, where b is an user defined amount of bits superordinate MBR encloses all of its subordinate MBRs, as per dimension. Each cell is labeled with a unique bit string, we visualize in Figure 1. being the concatenation of the corresponding bit strings for With increasing dimensionality, R-Trees face the challenge every dimension. For every point, the bit string of the cell is of overlapping MBRs. A query rectangle, situated in a re- stored, which the point is inserted into. Thus, the VA-File gion, where two or more MBRs overlap (like the MBR R2 uses two lists: an approximation file that stores the bit string and R3 in Figure 1), forces the R-Tree to follow up two or of the cells for every point and a vector file with the vector more different routes in the tree. Thus, the query perfor- data for each point. An exemplary space partitioning and mance decreases [6]. To overcome this disadvantage other the corresponding approximation file can be seen in Figure 3. index structures that we mentioned before, are developed. Generally, the query algorithm of the VA-File traverses the whole approximation file to collect suitable candidates for the query result at first. After that, exact comparisons Pyramid Technique. between the vector data of the candidates and the query are An example for an exact space partitioning index struc- performed. ture is the Pyramid Technique, which was introduced by The approximation technique of the VA-File helps to re- Berchtold et al. [5]. The Pyramid Technique divides an n- duce hard-disk accesses, because small bit strings can be dimensional space into 2d pyramids [5]. A d dimensional kept in main memory. Even if the whole approximation normalized point x is inserted into a pyramid according to file does not fit into the main memory, the sequential ex- the dimension jmax with its maximum distance to the center amination of the approximations reduces disk access costs of the data space. Thus, the pyramid number pi is computed compared to random accesses to many data items [22]. An- as follows:  other advantage is, in contrast to the Pyramid Technique, jmax if xjmax < 0, 5 the availability of different algorithms to efficiently support i= (jmax + d) if xjmax ≥ 0, 5 all query types being executable on a sequential scan with- Second, for managing the space enclosed by a pyramid, out adaption of the space partitioning of the VA-File. the pyramids are divided in pyramid slices. According to the 2.4.2 Approximation-based Index Structures query types supported by the index structure, the partition of pyramids can be done in different ways. In Figure 2, Typical representatives for an approximation-based index we present two different possible methods for partitioning a structure are based on hash schemes. Apart from common pyramid, for a two dimensional normalized space. hashing algorithms, scattering inserted data points over the In particular, the partition of Figure 2 (a) is proposed amount of buckets is not applicable for similarity queries. by Berchtold et al. [5] to support range queries. The other Consequently, there is a need for hash functions, causing partition, shown in Figure 2 (b), is used by the approach of collisions when hashing locally near situated points. This Lee and Kim [15] to support k-NN queries. It is possible to challenge is handled by Locality Sensitive Hashing (LSH). use the partitioning from Berchtold et al. for k-NN queries as The aim of LSH is to map the key to a one dimensional well, but not in an efficient way. Anyway, a point is inserted hash value. Thus, all comparisons are made on the hash into the slice depending on its distance to the center of the value instead of a high dimensional key. Supporting nearest space. To sum up, for supporting different query types in neighbor queries, LSH uses (P 1, P 2, r, cr)-sensitive functions an efficient way, different pyramid partitions are required. h to compute the hash value. These functions h have to fulfill the following constraints [12]: VA-File. For every dataset in a d-dimensional space p, q ∈ Rd : In 1997, Weber and Blott [22] introduce the VA-File to overcome the curse of dimensionality. The VA-File is an 1. if ||p − q|| ≤ r, then P r[h(p) = h(q)] > P 1 improved sequential scan, because Weber et al. noticed a 2. if ||p − q|| ≥ cr, then P r[h(p) = h(q)] < P 2 The first constraint demands that the probability for two the approximation-based index structure p-stable LSH pre- points to be hashed into the same bucket has to be larger sented in Section 2.4 are number of hash functions and width than P 1 if their distance is smaller than r. Whereas, if their of hash buckets. distance is bigger than cr, the probability should be smaller Thus, we have to assume, that these parameters have an than P 2. In order to be an useful locality sensitive function, impact on the performance of index structures. Therefore, P 1 should be much bigger than P 2. it is necessary to analyze suitable parameter values when Improving the precision of the index structure, usually trying to identify an appropriate index structure for a given several hash tables with different hash functions are used. use case. However, there are some problems considering an Consequently, the need for (P 1, P 2, r, cr)-sensitive functions appropriate value of some parameters. For example, the is obvious. A promising family of hash functions is used in vectors used for p-stable LSH are randomly chosen from p- p-stable LSH. stable distributions. As a result of this random component it is possible that the performance and precision results of p-stable LSH. the same index structure created with different seeds of the The approach of p-stable LSH is based on p-stable distri- random component can differ very much, within the same butions. A distribution D is p-stable for p ≥ 0 if for any n the use case. This is problematic when trying to quantitatively real numbers v1 , ..., vn and i.i.d. random variables X1 , ..., Xn evaluate the index structure. with distribution D, the following constraint is fulfilled: 3.2 Workload and used Queries n X n X 1/p Although, two different applications can deal with the (vi Xi ) ∼ (kvi kp ) X, same data, they can have a different workload. For that i=1 i=1 reason, they can differ in requirements of index structures. The workload of an application depends on the used query ∼ means the operands have the same distribution and X is types. Yet, it is obvious, not to use the Pyramid Technique a random variable from the distribution D [18]. presented from Berchtold et al. [5] for performing a k-NN Using d random variables from D to form a d-dimensional query, but the version presented by Lee and Kim [15], be- Vector ~a, the scalar of vector ~a and the data point ~v result in P d 1/p cause it is optimized for this query type. a random variable with distribution (kvi kp ) X [12]. For defining the workload of a database system we use i=1 a definition inspired by Ahmad et al. [1]. As a result, the Several of these scalar products with different vectors can workload is defined by the percentage of the query types be used to estimate k~v kp (the Lp distance metric). The used and the amount of concurrent requests performed. corresponding distributions are: • The Cauchy Distribution DC (0, 1), defined by the den- 3.3 DBMS Environment 1 sity function c(x) = (π(1+x 2 )) is 1-stable and can be In addition to use cases and workload, the test environ- used to estimate the Manhattan distance metric. ment has an impact on the performance of each index struc- • The Gaussian (Normal) Distribution DG (0, 1), defined ture. As already mentioned, the VA-File is optimized for 2 by the density function g(x) = √12π e−x /2 is 2-stable database systems, storing data items on a disk and not in and can be used to estimate the Euclidean distance main memory. Evaluations of VA-File and sequential scan, metric. result in different conclusions according to an evaluation Instead of estimating a distance metric, the scalar prod- with an in-memory database or a database storing items uct with vectors from p-stable distributions can be used to on the disk. Consequently, it is necessary to consider the compute hash values of the data points, because the scalar underlying storage management of the database system as product maps the vectors to a one dimensional space. Fur- well. thermore, the result of the scalar product has the same dis- Beside the storage management of a database, the amount tribution as the Lp distance metric, which guarantees the of main memory and the CPU performance are other impact (P 1, P 2, r, cr)-sensitiveness. factors to the performance. 3. ADVANCED CHALLENGES 4. TOWARDS A FRAMEWORK After giving a short introduction to general challenges of Since we aim at providing a comprehensive library of use indexing multi-dimensional data, in this section we provide cases and suitable indexes, we motivate a framework to give existing challenges of evaluating the performance of index users the possibility to evaluate own use cases with different structures for a specific use case. For giving an overview index structures. In this paper, we summarize key aspects of possible challenges when evaluating index structures, we of a framework that supports four groups. In Figure 4, we group the challenges into three groups. give an overview of these four groups. 3.1 Parameter of the Index Structures 4.1 Extensibility Some index structures have specific parameters for tuning First, the framework has to be extensible w.r.t. four key their performance. Thus, when evaluating the performance aspect, we present in Section 2. In other words, for an user, of index structures, these parameter have to be considered it has to be possible to implement, integrate, and evaluate as well. For index structures given in Section 2.4, these pa- own index structures. Furthermore, it has to be possible rameter are: the minimum and the maximum number of to extend the framework and existing index structures with points within a MBR for the R-Tree, the number of slices a additional distance metrics and also other query types. Fi- pyramid is divided in, for the Pyramid Technique, and the nally, it has to be possible to integrate existing data in the length of the bit vector for the VA-File. The parameters of framework and to create data with specific properties like a USER or pit-falls of the chosen index structure. For instance, the user is able to follow the split of MBRs in the R-Tree and can easily identify overlapping regions while the tree is be- ing constructed. Another aspect, being worth to visualize, test environment workload visualization extensibility is a statistic on query performance. These statistics help to simulator analyze the performance of different index structures for a given workload or an index structure under different work- FRAMEWORK loads. Apart form the query performance, other interesting values may be worth visualizing. The time spent on con- structing the index structure is important for systems with Figure 4: Structure of the Framework. many delete and update queries, because a reconstruction of the index is sometimes necessary when a certain threshold of changed data is reached. Furthermore, when using an ap- specific data distribution. Thus, creating data distributions proximate index structure, the precision of executed queries is not trivial, an interface has to be created for importing and the overall precision of the index structure is worth vi- existing data sets and communicating with systems like R, sualizing, because it has an impact on the suitability of an see for instance [14]. index structure for a special use case. 4.2 Adaptability to Different Workload 4.5 Working with the Framework In real world applications, the workload differs quite much. Finally, our framework shall help finding the most suit- On the one hand, there are use cases that use only read able index structures for a given use case. For this, the transactions. On the other hand, the workload can consist expected workload has to be known. These parameters in- of read and write transactions. Thus, the performance re- clude supported query types, exact or approximate results, sults of workloads can differ very much. Hence, an interface data dimensionality and distribution, amount of data, the is needed for importing workloads from existing systems. A delay of the data access, and the environment. By finding further requirement, is to support standardized benchmarks, suitable index structures for the given parameters, there are e.g. the TPC-H Benchmark2 . index structures that do not have to be taken into account, Beside the queries used, the desired precision of the query because they do not support certain query types or work results have to be defined by the user. Thus, if approximate approximately although the result is restricted to be exact. results are allowed, the user has to define the accuracy of After excluding unsuitable index structures, the remaining the results. Nevertheless, the precision depends on the data index structures are evaluated under the given workload. By properties, the given distance metric, the used queries and reviewing the performance results, the user can choose the the parameters of the index structure as well. suitable index structure for her use case. 4.3 Test Environment Simulator Existing index structures are created with respect to dif- 5. RELATED WORK ferent optimization criteria. As already mentioned, the VA- In the last decades, many new index structures are cre- File is optimized for reducing disk accesses. Consequently, ated [5, 10, 22]. In addition, existing index structures are another criteria our framework has to consider is the envi- improved for supporting new query types [15] or to increase ronment the tests are located in. Thus, within the frame- performance [6]. However, within the presented evaluation work a parameter has to exist, for setting whether the test of these index structures only a small set of existing in- is for an in-memory database or if a disk access is needed for dex structures is considered. For example, within Berchtold accessing the data. Due to an assumption, that the access et al. [5], the Pyramid Technique is evaluated against X- time of data differs very much considering Hard-Disk-Drives Tree, Hilbert R-Tree, and sequential scan. Therefore, it is and Solid-State-Disks, the framework should have a compo- problematic to identify, which is the most appropriate in- nent for virtualizing the disk access. With this component dex structure for a given problem. Additionally, different it is possible to perform tests on one system while simulat- performance evaluations are done in different environments ing an access delay of another system. In addition to this with different data characteristics. So, it is problematic to storage device simulator, a simulator for all hardware com- generalize the results of an evaluation. ponents is required to give an useful hint about the best For giving a comparison of the performance of multi-di- performing index structure. mensional index structures, there already exists some frame- Additionally, within the framework a parameter has to works, like the GiST 3 framework or the MESSIF [3] frame- exist for defining the values of some index structure param- work. In contrast to the framework we present here, these eters such as the maximum number of data items of leaves frameworks have some additional constraints. For example, of the R-Tree. the GiST framework only focuses on trees, hence no other multi-dimensional index structures such as the VA-File or the Pyramid Technique are considered, while the MESSIF 4.4 Visualization framework only focuses on metric data. Another framework In case the index structure has to struggle with a specific limiting the available index structures is introduced by Muja data distribution or query type, it can be useful to visualize et al. [17]. The aim of this framework is to optimize param- the space partitioning of the index structure. With this vi- eters of approximate index structures in order to match the sualization, further hypothesis can be drawn on the benefits required precision under given data distributions. 2 3 http://www.tpc.org/tpch/ http://gist.cs.berkeley.edu/ 6. CONCLUSION IEEE Trans. on Pattern Analysis and Machine In this paper, we provide an overview of existing chal- Intelligence (TPAMI), 30(9):1647–1658, 2008. lenges in finding an appropriate index for multi-dimensional [11] A. Guttman. R-Trees: A dynamic index structure for data for a specific use case. First, we explain distance met- spatial searching. In SIGMOD’84, Proc. of Annual rics and common query types that have to be considered. Meeting, pages 47–57, 1984. Second, the parameters of the index structures can have an [12] P. Indyk and R. Motwani. Approximate nearest impact on the performance of an index structure. Third, for neighbors: Towards removing the curse of users, it has to be possible to define own workload pattern dimensionality. In Proc. Symp. on Theory of Compu. and the environment, the application is located in. (STOC). ACM, 1998. For supporting these characteristics of real-world use cases [13] N. Katayama and S. Satoh. The SR-tree: An Index we present requirements of a framework we intend to de- Structure for High-Dimensional Nearest Neighbor velope. Our framework has to support four key aspects. Queries. In Proc. Int’l. Conf. on Mgmt. of Data Namely, it has to be extensible, support different workload (SIGMOD), pages 369–380. ACM, 1997. patterns, virtualize different use case environments, and con- [14] V. Köppen. Improving the Quality of Indicator tain a visualization component for improving user experi- Systems by MoSi – Methodology and Evaluation. PhD ences. thesis, Freie Universität Berlin, 2008. [15] D.-H. Lee and H.-J. Kim. An efficient technique for 7. ACKNOWLEDGMENTS nearest-neighbor query processing on the SPY-TEC. The work in this paper has been funded in part by the Trans. on Knowl. and Data Eng. (TKDE), German Federal Ministry of Education and Science (BMBF) 15:1472–1486, 2003. through the Research Programme under Contract No. [16] B. Li, E. Chang, and Y. Wu. Discovery of a perceptual FKZ:13N10817 and FKZ:13N10818. Additionally we want distance function for measuring image similarity. to thank Sandro Schulze for giving us useful comments. Multimedia Systems, 8(6):512–522, Apr. 2003. [17] M. Muja and D. G. Lowe. Fast approximate nearest 8. REFERENCES neighbors with automatic algorithm configuration. In [1] M. Ahmad, A. Aboulnaga, and S. Babu. Query Proc. Int’l. Conf. on Computer Vision Theory and interactions in database workloads. In Proc. Int’l. Applications (VISAPP), pages 331–340, 2009. Workshop on Testing Database Systems, DBTest, [18] J. P. Nolan. Stable distributions: Models for heavy pages 11:1–11:6. ACM, 2009. tailed data. Springer-Verlag, 2009. [2] A. Andoni and P. Indyk. Near-optimal hashing [19] Y. Sakurai, M. Yoshikawa, S. Uemura, and H. Kojima. algorithms for approximate nearest neighbor in high The A-tree: An index structure for high-dimensional dimensions. Commun. ACM, 51(1):117–122, 2008. spaces using relative approximation. In Proc. Int’l. [3] M. Batko, D. Novak, and P. Zezula. Messif: Metric Conf. on Very Large Data Bases (VLDB), pages similarity search implementation framework. In Proc. 516–526. Morgan Kaufmann Publishers Inc., 2000. Conf. on Digital Libraries (DELOS), 2007. [20] H. Samet. Foundations of Multidimensional and [4] N. Beckmann, H.-P. Kriegel, R. Schneider, and Metric Data Structures. Morgan Kaufmann Publishers B. Seeger. The R*-Tree: An efficient and robust access Inc., 2005. method for points and rectangles. In Proc. Int’l. Conf. [21] T. K. Sellis, N. Roussopoulos, and C. Faloutsos. The on Mgmt. of Data (SIGMOD), pages 322–331. ACM, R+-Tree: A dynamic index for multi-dimensional 1990. objects. In Proc. Int’l. Conf. on Very Large Data [5] S. Berchtold, C. Böhm, and H.-P. Kriegel. The Bases (VLDB), pages 507–518. Morgan Kaufmann Pyramid-Technique: Towards breaking the curse of Publishers Inc., 1987. dimensionality. SIGMOD Rec., 27:142–153, 1998. [22] R. Weber and S. Blott. An approximation-based data [6] S. Berchtold, D. A. Keim, and H.-P. Kriegel. The structure for similarity search. Technical Report X-Tree: An index structure for high-dimensional data. ESPRIT project, no. 9141, 1997. In Proc. Int’l. Conf. on Very Large Data Bases [23] R. Weber, H.-J. Schek, and S. Blott. A quantitative (VLDB), pages 28–39. Morgan Kaufmann Publishers analysis and performance study for similarity-search Inc., 1996. methods in high-dimensional spaces. In Proc. Int’l. [7] C. Böhm. Efficiently Indexing High-Dimensional Data Conf. on Very Large Data Bases (VLDB), pages Spaces. PhD thesis, Ludwig-Maximilians-Universität 194–205. Morgan Kaufmann Publishers Inc., 1998. München, 1998. [24] R. Zhang, B. C. Ooi, and K.-L. Tan. Making the [8] C. Böhm, S. Berchtold, and D. A. Keim. Searching in pyramid technique robust to query types and high-dimensional spaces: Index structures for workloads. In Proc. Int’l. Conf. on Data Engineering improving the performance of multimedia databases. (ICDE), pages 313–324. IEEE Computer Society, ACM Comput. Surv., 33:322–373, 2001. 2004. [9] P. H. Bugatti, A. J. M. Traina, and C. Traina, Jr. Assessing the best integration between distance-function and image-feature to answer similarity queries. In Proc. ACM Symp. on Applied Computing (SAC), pages 1225–1230. ACM, 2008. [10] E. Chavez Gonzalez, K. Figueroa, and G. Navarro. Effective proximity retrieval by ordering permutations.