9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Fast similarity join for multi-dimensional data

ARTICLE IN PRESS

Information Systems 32 (2007) 160–177 www.elsevier.com/locate/infosys

Fast similarity join for multi-dimensional data$, $$

Dmitri V. Kalashnikova,?, Sunil Prabhakarb

a b

Department of Computer Science, University of California, Irvine, 4300 Calit2 Building, Irvine, CA 92697, USA Department of Computer Sciences, Purdue University, 250 N. University Street, West Lafayette, IN 47907, USA Received 15 January 2003; received in revised form 20 July 2005; accepted 22 July 2005

Abstract The ef?cient processing of multidimensional similarity joins is important for a large class of applications. The dimensionality of the data for these applications ranges from low to high. Most existing methods have focused on the execution of high-dimensional joins over large amounts of disk-based data. The increasing sizes of main memory available on current computers, and the need for ef?cient processing of spatial joins suggest that spatial joins for a large class of problems can be processed in main memory. In this paper, we develop two new in-memory spatial join algorithms, the Grid-join and EGO*-join, and study their performance. Through evaluation, we explore the domain of applicability of each approach and provide recommendations for the choice of a join algorithm depending upon the dimensionality of the data as well as the expected selectivity of the join. We show that the two new proposed join techniques substantially outperform the state-of-the-art join algorithm, the EGO-join. r 2005 Elsevier B.V. All rights reserved.

Keywords: Similarity join; Grid-based joins

1. Introduction Similarity (spatial) joins are an important database operation for several applications including GIS, multimedia databases, data mining, locationbased applications, and time-series analysis. Spatial joins are natural for geographic information systems and moving object environments where pairs of objects located close to each other are to be

Recommended by Y. Ioannidis. This work was supported by NSF Grants IIS-9985019, 0010044-CCR, 9972883, and an Intel Ph.D. Fellowship. A preliminary version of this work appeared in [1]. ?Corresponding author. Tel.: +949 824 1396; fax: +949 824 8831. E-mail addresses: dvk@ics.uci.edu (D.V. Kalashnikov), sunil@cs.purdue.edu (S. Prabhakar).

$$ $

identi?ed [2,3]. Many algorithms for several basic data mining operations such as clustering [4], outlier detection [5], and association rule mining [6] require the processing of all pairs of points within a certain distance to each other [7]. Thus, a similarity join can serve as the ?rst step for many of these operations [8]. The problem of ef?cient computation of similarity joins of multidimensional data has been studied extensively in the literature. Most researchers have focused their attention on disk-based joins for high-dimensional data. Current high-end workstations have enough memory to handle joins even for large amounts of data. For example, a selfjoin of 1 million 32-dimensional data points, using an algorithm similar to that of [7] (assuming ?oat data type for coordinate and int for point

0306-4379/$ - see front matter r 2005 Elsevier B.V. All rights reserved. doi:10.1016/j.is.2005.07.002

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 161

identities) requires roughly 132 MB of memory (i.e. ?32 ? 4 ? 4? ? 106 % 132 MB, plus memory for stack etc.). Furthermore, there are situations when it is necessary to join intermediate results situated in main memory or sensor data, which is to be kept in main memory. With the availability of a large main memory cache, disk-based algorithms may not necessarily be the best choice. Moreover, for certain applications (e.g. moving object environments) near real-time computation may be critical and require main memory evaluation. In this paper, we consider the problem of main memory processing of similarity joins, also known as -joins. Given two datasets A and B of d-dimensional points and value 2 R, the goal of a join operation is to identify all pairs of points, R, one from each dataset, that are within distance from each other, i.e. R ? J?A; B; ? ? f?a; b? : ka ? bko; a 2 A; b 2 Bg. While several research efforts have concentrated on designing ef?cient high-dimensional join algorithms, the question which method should be used when joining low-dimensional (e.g. 2–6 dimensions) data remains open. This paper addresses this question and investigates the choice of a join algorithm for low- and high-dimensional data. We propose and evaluate two new join algorithms: the Grid-join and EGO*-join. We compare them with the state-of-the-art algorithm— EGO-join [7], and with a method which serves as a benchmark in many similar publications, the R-tree spatial join (RSJ) [9]. These techniques are compared empirically using synthetic and real data. The experimental evaluation shows that the Grid-join approach is the best method for low-dimensional data. When using the Grid-join, the join of two datasets A and B is computed using an index nested loop approach: an index (i.e. speci?cally constructed two-dimensional grid) is built on circles with radius centered at the ?rst two coordinates of points from dataset B. The ?rst two coordinates of points from dataset A are used as point-queries to the grid-index in order to compute the join. Although several choices are available for constructing this index, only the grid is considered in this paper. The choice of the grid index is not accidental, it is based upon our earlier results for main memory evaluation of range queries. In [10], we have shown that for range

queries over moving objects, using a grid index results in an order of magnitude better performance than memory optimized R-tree, CR-tree, R*-tree, or Quad-tree. The results for high-dimensional data show that the EGO*-join is the best join technique, unless is very small. The EGO*-join that we propose in this paper is based upon the EGO-join algorithm. Bohm ¨ et al. in [7] have shown that the epsilon grid order (EGO) join algorithm outperforms other spatial join techniques for high-dimensional data. The new EGO*-join algorithm signi?cantly outperforms EGO-join for all cases considered. The improvement is especially notable when the number of dimensions is not very high, or the value of is not large. The RSJ algorithm is signi?cantly less effective than all other tested algorithms. To join two datasets using RSJ, two R-tree indexes are built or maintained on these datasets. But unlike the case of some approaches, these indexes need not be rebuilt when the join is recomputed with different . Although not often addressed in related research, the choice of the parameter for the join is critical for producing meaningful results. We have discovered that often in similar research the choice of values of yields very small selectivity, i.e. almost no point from one dataset joins with a point from the other dataset. Section 3.1 discusses how to choose the appropriate values of to achieve meaningful selectivity of the result set. The contributions of this paper are as follows:

Two join algorithms that achieve better performance (by a factor of 2–10) than the state-of-theart EGO-join algorithm. Recommendations for the choice of a join algorithm based upon data dimensionality d, and . Highlight the importance of the choice of and the corresponding selectivity for experimental evaluation.

The rest of this paper is organized as follows. The new Grid-join and EGO*-join algorithms are presented in Section 2. The proposed join algorithms are evaluated in Section 3. Related work is discussed in Section 4. Finally, Section 5 concludes the paper. A sketch of the algorithm for selecting grid size, and cost estimator functions for Grid-join, are presented in the Appendix.

ARTICLE IN PRESS

162 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

2. Similarity join algorithms In this section, we introduce two new algorithms: the Grid-join and EGO*-join. The Grid-join is based upon a uniform grid and builds upon the approach proposed in [10] for evaluating continuous range queries over moving objects. The EGO*join is based upon EGO-join proposed in [7]. In Section 2.1, we ?rst present the Grid-join algorithm followed by an important optimization for improving the cache hit-rate. An analysis of the appropriate grid size as well as cost prediction functions for the Grid-join is presented in the Appendix. The EGO*-join method is discussed in Section 2.2. 2.1. Grid-join Let us ?rst assume the case of joining twodimensional data, the general case of d dimensions will be discussed shortly. The spatial join of two datasets, A and B, can be computed using the standard index nested loop approach as follows. We treat one of the point datasets as a collection of circles of radius centered at each point of one of the two datasets (say B). This collection of circles is then indexed using some spatial index structure. The join is computed by taking each point from the other dataset (A) and querying the index on the circles to ?nd those circles that contain the query point. Each point (from B) corresponding to each such circle joins with the query point (from A). An advantage of this approach (as opposed to the alternative of building an index on the points of one dataset and processing a circle region query for each point from the other dataset) is that point-queries are much simpler than region-queries and thus tend to be faster. For example, a region-query on a quadtree index might need to evaluate several paths while a point-query is guaranteed to be a single path query. An important question is the choice of index structure for the circles. In earlier work [10], we have investigated the execution of large numbers of range queries over point data in the context of evaluating multiple concurrent continuous range queries on moving objects. The approach can also be employed for spatial join if we compute the join using the index nested loops technique mentioned above. The two approaches differ only in the shape of the queries, which are circles for the spatial join problem and rectangles for the range queries.

Fig. 1. An example of the grid index, I G .

In [10], the choice of a good main-memory index has been investigated. Several key index structures, including R-tree, R*-tree, CR-tree [11], quad-tree, and 32-tree [10], were considered. All trees were optimized for main memory. The conclusion of the study was that a simple one-level Grid-index outperformed all other indexes by almost an order of magnitude for uniform as well as skewed data. Due to its superior performance, in this study, we use the Grid-index for indexing the -circles. Grid index: While many variations exist, we have designed our own implementation of the Gridindex, which we denote as I G . I G is built on circles with -radius.1 The similarity join algorithm which utilizes I G is called the Grid-join, or J G for short. Case of two dimensions: Let us now consider the two-dimensional case more formally. We will consider the problem of joining two twodimensional datasets, A ? fa0 ; a1 ; . . . ; ajAj?1 g and B ? fb0 ; b1 ; . . . ; bjBj?1 g, using an index nested loop approach, where the grid index is built on dataset B. The grid index I G is a two-dimensional array of cells. Each cell represents a region of space generated by partitioning the domain using a regular grid. Fig. 1 illustrates an example of I G . Throughout the paper, we assume that the domain is normalized to the unit d-dimensional hyper-cube ?0; 1?d . In this example, the domain is divided into a 10 ? 10 grid of 100 cells, each of size 0:1 ? 0:1. Since the grid is uniform, it is easy to calculate the cell-coordinates corresponding to a point in O?1? time. Each cell in the grid contains two lists called the full and part lists, as illustrated in Fig. 1. Let circle?p; r? denote a circle with center at point p and radius r. The full list of each cell C in I G

Note, however, that it is not necessary to generate a new dataset consisting of these circles. Since each circle has the same radius (), the dataset of the points representing the centers of these circles is suf?cient.

1

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 163

contains pointers to each point bi from B such that circle?bi ; ? fully covers the cell: C:full ? fbi : C & circle?bi ; ?; bi 2 Bg. The part list of each cell C contains pointers to each point bi from B such that circle?bi ; ? partially covers the cell: C:part ? fbi : Cgcircle?bi ; ? and C \ circle a;; bi 2 Bg. To ?nd all points within -distance from a given point ai 2 A, ?rst the cell corresponding to ai is retrieved. All points in the full list of that cell are guaranteed to be within -distance from ai . The points bj in the cell’s part list need to be processed further to check if kai ? bj ko.2 Outline of the algorithm: The basic steps of J G to join two datasets A and B are outlined in Fig. 2. In Steps 2 and 3, a spatial sort, called z-sort, is applied to the two datasets. The need for z-sort is explained later. A grid index I G is initialized in Step 4. In the loop in Step 5, all points bi 2 B are added to I G one by one as follows. First bi , a two-dimensional point constructed from the ?rst two coordinates of bi , is considered.3 Then pointer to bi is added to the part lists of each cell C in I G that satis?es C \ circle?bi ; ?a;.4 The loop in Step 6 performs a nested loop join. For each point ai 2 A all points from B that are within distance are determined using I G . To achieve this, point ai is constructed from the ?rst two coordinates of ai and the cell corresponding to ai in I G , C, is determined in Steps 6(a) and 6(b). Then, in Step 6(c), the algorithm iterates through points in the part list of cell C and ?nds all points that are within distance from ai . Step 6(d0 ) is analogous to Step 6(c) but for full lists and valid only for the two-dimensional case. Case of d dimensions: In the general d-dimensional case, J G still employs a two-dimensional grid. Only the ?rst two coordinates of points in A and B are utilized for all operations, exactly as in two2 The choice of data structures for the full and part lists is critical for performance. We implemented these lists as dynamicarrays rather than lists, which improves performance by roughly 40% due to the resulting clustering in memory (and thereby reduced cache misses). A dynamic array is a standard data structure for arrays whose size adjusts dynamically. 3 Note, for two-dimensional case bi is equivalent to bi , the difference exists only for more than two dimensions, as explained shortly. 4 This step is valid for the general d-dimensional case, where dX2. However, for better performance in the two-dimensional case, pointer to bi is added to the full lists of each cell C in I G that satis?es the condition fC & circle?bi ; ?g and it is added to the part lists of each cell C in I G that satis?es the condition fCgcircle?bi ; ? and C \ circle?bi ; ?a;g.

Fig. 2. Grid-join procedure, J G .

dimensional case, except when processing part lists, in which case all d coordinates are utilized to determine if ka ? bko. While in the two-dimensional case each cell has two lists, in the d-dimensional case where d42 each cell has only one list. The reason for having two separate lists (full and part) per cell for twodimensional points is as follows. When processing a point ai 2 A, points bj in the full list do not need kai ? bj ko checks since those points are guaranteed to be within -distance from ai , whereas points from the part list do need these checks. For more than two dimensions, keeping a separate full list per each cell of a two-dimensional grid is of little value because now points from the full list do need kai ? bj ko checks as well. Therefore, for the d-dimensional case each cell has only one list, called the part list: C:part ? fb : C \ circle?b; ?a;; b 2 Bg. Choice of grid size: The performance of J G depends on the choice of grid size, therefore it must be selected carefully. Intuitively, the ?ner the grid, the faster the processing, but the greater the time needed to initialize the index and load the data into it. We now present a sketch of a solution for selecting appropriate grid size. The ?rst step is to develop a set of estimator functions that predict the cost (i.e. the execution time, in our context) of the join given a grid size. The cost is composed of three components, the

ARTICLE IN PRESS

164 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

costs of: (a) initializing the empty grid; (b) loading the dataset B into the index; and (c) processing each point of dataset A through this index. The Appendix presents details of how each of these costs is estimated. These functions are able to achieve very accurate prediction. With the help of these functions, it is possible to estimate which grid size is optimal. Such functions can also be used by a query optimizer to evaluate if it is more ef?cient to use J G for the given parameters or another join approach. Improving the cache hit-rate: The performance of main-memory algorithms is greatly affected by cache hit-rate. In this section, we describe an important optimization that improves cache hit-rate and, consequently, the overall performance of J G . In J G , for each point in A its cell is computed, and the full and part lists (or just part list) of this cell are accessed, as illustrated in Fig. 2. The algorithm simply processes points in sequential order in the array corresponding to dataset A. Cache hit-rate can be improved by altering the order in which points are processed. In particular, points in the array should be ordered such that points that are close to each other according to their ?rst two coordinates in the two-dimensional domain are also tend to be close to each other in the array. In this situation, data structures for a given cell (e.g., its part list) are likely to be reused from the cache during the processing of subsequent points from the array. The speedup is achieved because such points are more likely to be covered by the same circles than points that are far apart, thus the relevant information is more likely to be retrieved from the cache rather than from main memory. Sorting the points to ensure that points that are close to each other in two-dimensional domain are also tend to be close in the array can easily be achieved by various methods. We choose to use a sorting based on the Z-order. We sort not only dataset A but also dataset B, which reduces the time needed to add circles to I G . In Section 3, we will show that the gain achieved by z-sort can be quite signi?cant. For example, approximately 2.5 times speedup is achieved by utilizing Z-sort in Fig. 13 in that section. 2.2. EGO*-join In this section, we present our second algorithm called EGO*-join, which is based on EGO-join approach [7]. In [7], Bohm et al. have shown that ¨ EGO-join substantially outperforms other methods

Fig. 3. EGO-join procedure, J EGO .

for joining massive, high-dimensional data. We will use the notation J EGO to denote the EGO-join approach and J EGO? for the EGO*-join approach. Before introducing J EGO? , we begin by brie?y describing J EGO as presented in [7]. The epsilon grid order: J EGO is based on the socalled Epsilon Grid Ordering (EGO) [7]. To impose an EGO on dataset A, a regular grid with the cell size of is laid over the data space. The grid is imaginary, and never materialized. For each point in A, its cell-coordinates can be determined in O?1? time. A lexicographical order is imposed on each cell by choosing an order for the dimensions. The EGO of two points is determined by the lexicographical order of the corresponding cells that the points belong to. EGO-sort: To join datasets A and B with a certain using J EGO , ?rst the points in these datasets are sorted in accordance with the EGO for the given (Fig. 3). Note, if a subsequent J EGO operation is needed but with a different , datasets A and B must be sorted again since EGO depends on . Recursive join: The procedure for joining two sequences is recursive. Each sequence is further subdivided into two roughly equal subsequences and each subsequence is joined recursively with both its counterparts. The partitioning is carried out until the length of both subsequences is smaller than a threshold value, at which point a simple-join is performed. In order to avoid excessive computation, the algorithm avoids joining sequences that are guaranteed not to have any points within distance of each other. We refer to such sequences as nonjoinable. EGO-heuristic: A key element of J EGO is the heuristic to identify non-joinable sequences. To understand the heuristic, let us consider a simple example. In a short EGO-sorted sequence its ?rst and last points are likely to have the same values in the ?rst few dimensions of their cellcoordinates. For example, points with cell-coordinates ?2; 7; 4; 1? and ?2; 7; 6; 1? have the same values in the two ?rst dimensions ?2; 7; ?; ??. The

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 165

Fig. 4. Two sequences with (a) 0 inactive dimensions and (b) 1 inactive dimension. The EGO-heuristic fails in both cases. In both cases EGO*-heuristic correctly determines the sequences are non-joinable.

Fig. 5. J EGO? : procedure for obtaining a bounding rectangle of a sequence.

values in the third dimension are different. The third dimensions is called the active dimension, the ?rst two dimensions are called inactive. Because the sequence is EGO-sorted, in this sequence all points have ‘2’ and ‘7’ in their ?rst and second dimensions of their cell-coordinates. Given two EGO-sorted sequences, the EGOheuristic ?rst computes two values: the number of inactive dimensions for each of the two sequences. Then it computes another value min, corresponding to the minimum of the two values. It is easy to prove [7] that if there is a dimension no greater than min such that the cell-coordinates of the ?rst points of the two sequences differ by at least two in that dimension, then the sequences are non-joinable. This is based upon the fact that the length of each cell is . New EGO*-heuristic: The proposed J EGO? (EGO*-join) algorithm is J EGO (EGO-join) with a different heuristic for determining that two sequences are non-joinable. Section 3 will demonstrate that the use of the EGO*-heuristic signi?cantly improves performance of the join. We now present our heuristic with the help of an example for which J EGO is unable to determine that the sequences are non-joinable. Fig. 4(a) demonstrates the case when two sequences are located in two separate slabs, both of which have the size of at least two in each dimension. There are no inactive dimensions for this case thus EGO-heuristic will fail to determine that they are non-joinable. In Fig. 4(b), assume each sequence has many points. One sequence starts in cell (0,1,3) and ends in cell (0,2,2). The second sequence starts in cell (0,5,6) and ends in (0,6,3). Both sequences have one inactive dimension (dimension number zero), and in dimension number zero they both have the same value of 0. Thus, the

EGO-heuristic will fail again to determine that they are non-joinable. The new heuristic being proposed is able to correctly determine that for the two cases of Figs. 4(a) and (b) the two sequences are nonjoinable. To do that, the EGO*-heuristic utilizes not only inactive dimensions as EGO-heuristic, but also the active dimension. The EGO*-heuristic uses the notion of a bounding rectangle (BR) for each sequence. Notice, in general, given only the ?rst and last cells of a sequence, it is impossible to compute the minimum bounding rectangle (MBR) for that sequence. However, it is possible to compute a BR. Fig. 5 sketches an algorithm for computing a BR. The procedure takes as its input the coordinates of the ?rst and last cells of an EGO-sorted sequence and outputs a BR for that sequence. To understand the getBR?? algorithm, note that if the ?rst and the last points of the sequence have the same values in the ?rst n dimensions of their cellcoordinates (e.g. ?1; 2; 3; 4? and ?1; 2; 9; 4? are equal in their ?rst two dimensions—?1; 2; ?; ??) then all points in the sequence have the same values in the ?rst n dimensions (e.g. ?1; 2; ?; ?? for our example). This means that the ?rst n dimensions of the sequence can be bounded by those values. Furthermore, the active dimension of the sequence can be bounded by the values of ?rst and last points of that sequence in that dimension. Continuing with our example, the lower bound is now ?1; 2; 3; ?? and the upper bound is ?1; 2; 9; ??. In general, by observing only the ?rst and the last points of the sequence, the rest of the dimensions cannot be bounded precisely, however the lower bound can always be set to 0 and upper bound to MAX_CELL.

ARTICLE IN PRESS

166 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Fig. 6. Beginning of J EGO? : EGO*-heuristic.

Once the BRs for both sequences being joined are known, it is easy to see that if one BR, expanded by one in all directions, does not intersect with the other BR, then no point from the ?rst sequence will join a point from the second sequence. The basic steps of the EGO*-heuristic are outlined in Fig. 6. As we shall see in Section 3, J EGO? signi?cantly outperforms J EGO in all instances. This improvement is a direct result of the large reduction of the number of sequences needed to be compared based upon the above criterion. This result is predictable since if EGO-heuristic can determine that two sequences are non-joinable then EGO*-heuristic will always do the same, but the reverse is not true. The difference in CPU time needed to compute the EGO- and EGO*-heuristics, given the same two sequences, is insigni?cant. Thus, EGO*-heuristic is more powerful. Unlike J G , both J EGO? and J EGO are disk-based joins, even though in this paper we evaluate them only in main memory. Since J EGO? is identical to J EGO except for the heuristic, the performance of a diskbased implementation of J EGO? is expected to be better than that of J EGO . J G has been designed for main memory only and an ef?cient disk-based implementation of J G is outside the scope of this paper. 3. Experimental results In this section, we experimentally study J RSJ (RSJ), J G , J EGO [7], and J EGO? approaches. In all our experiments, we have used a 1 GHz Pentium III machine with 2 GB of memory. All multidimensional points have been distributed on the unit d-dimensional box ?0; 1?d . The number of points has been varied from 68,000 to 10,000,000. We have considered the following distributions of points: (1) Uniform: Points are uniformly distributed. (2) Skewed: The points are distributed among ?ve clusters. Within each cluster points are distributed normally with a standard deviation of 0.05.

(3) Real data: We test data from ColorHistogram and ColorMoments ?les representing image features. The ?les are available at the UC Irvine repository. ColorMoments stores nine-dimensional data, which we normalized to ?0; 1?9 domain, ColorHistogram—32-dimensional data. For experiments with low-dimensional real data, a subset of the leading dimensions from these datasets is used. Unlike uniform and skewed cases, for real data a self-join is performed. Often, in similar research, the costs of sorting the data, building or maintaining the index or costs of other operations needed for a particular implementation of a join are ignored. No cost is ignored in our experiments for J G , J EGO , and J EGO? . One could argue that for J RSJ the two indexes, once built, need not be rebuilt for different . While there are many other situations where the two indexes need to be built from scratch for J RSJ , we ignore the cost of building and maintaining indexes for J RSJ , thus giving it an advantage. 3.1. Correlation between selectivity and The choice of the parameter is critical when performing an -join. Little justi?cation for the choice of this parameter has been presented in related research. In fact, we present this section because we have discovered that selected values of are often too small in similar research.5 The choice of has a signi?cant effect on the selectivity depending upon the dimensionality of the data. The -join is a common operation for similarity matching. Typically, for each multidimensional point from dataset A a few points (i.e. from 0 to 10, possibly from 0 to 100, but unlikely more than 100) from dataset B need to be identi?ed on average. The average number of points from dataset B that joins with a point from dataset A is called selectivity.

There is some evidence that the mistake may happen because researchers often test a self-join of dataset A, which is simpler than a join of two distinct datasets A and B. In a self-join, each point joins at least with itself. Thus, for the result set R of a selfjoin, it holds that jRjXjAj. By increasing the dimensionality d the space needed to store each data point increases. Consequently, the space occupied by R (e.g. in bytes) also increases as d increases, for any ?xed positive , however small. Such an increase of the space occupied by R might be mistaken for an increase of the selectivity of the join.

5

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 167

In our experiments, selectivity motivated the range of values chosen for . The value of is typically lower for smaller number of dimensions and higher for high-dimensional data. For example, a 0:1 ? 0:1 square6 query ( ? 0:1) is 1% of a twodimensional domain, however it is only 10?6 % of an eight-dimensional domain, leading to small selectivity. Let us estimate what values for should be considered for joining high-dimensional uniformly distributed data such that a point from dataset A will join with a few (close to 1) points from dataset B. Assume that the cardinality of both datasets is m. We need to answer the question: what should the value of be such that m hyper-squares of side completely ?ll the unit d-dimensional cube? It is easy to see that the solution is ? 1=m1=d . Fig. 7 plots this function ?d? for two different values of m: 105 and 106 . Our experimental results for various numbers of dimensions corroborate the results presented in the ?gure. For example, the ?gure predicts that in order to get a selectivity comparable to one for 32-dimensional data, the value of should be close to 0.65, or 0.7. If one chooses values smaller than say 0.3 instead, this will lead to zero selectivity (or close to zero) which is of little value.7 This is in close agreement to the experimental results. If the domain is not normalized to the unit square, the values of should be scaled accordingly. For example, of 0.1 for ??1; 1?d domain corresponds to of 0.05 for our ?0; 1?d domain. Fig. 8 demonstrates the pitfall of using an improper selectivity. The value of is set such that the selectivity plunges sharply as the number of dimensions d increases: the selectivity is high for d ? 4, it becomes very small for d ? 8, and it is zero when dX10. Fig. 8 presumably shows that J G is better than J EGO and J EGO? even for high-dimensional cases. However, the contrary is true for meaningful selectivity as will be demonstrated in Section 3.3. Due to the importance of the selectivity, we plot its values in each experiment on the y-axis at the right end of each graph. The parameter is plotted on the x-axis, and the time taken by each join method is plotted on the left y-axis in seconds.

A square query was chosen to demonstrate the idea, ideally one should consider a circle. 7 For self-join selectivity is always at least 1, thus selectivity 2–100 is desirable.

6

0.7 0.6 0.5 epsilon 0.4 0.3 0.2 0.1 0 2 6 10 14 18 22 26 d - num of dimensions 30

|A|=|B|=100,000 |A|=|B|=1,000,000

Fig. 7. Choosing for selectivity close to one for 105 (and 106 ) points uniformly distributed on ?0; 1?d .

30 25 Time (secs) 20 15 10 5 0 4 8

Time to ε-join (A,B) ε = 0.05; |A| = |B|= 100,000

3.5 3

Grid EGO*

EGO Selectivity

2 1.5 1 0.5

12

16

20

24

0 28

#dimensions

Fig. 8. Pitfall of using improper selectivity.

3.2. Low-dimensional data In this section, we study J RSJ , J EGO , J EGO? , and J G approaches for low-dimensional data. For the experiments in this section, the value of is varied so as to achieve meaningful selectivity. When the right y-axis is present in a ?gure, it plots the selectivity values for each value of in the experiments, in actual number of matching points. As expected, the selectivity, shown by the line with the ‘?’, increases as increases in each graph. In all ?gures in this section, the execution time of all join techniques monotonically increases as the selectivity increases, except for the low- selectivity case of J EGO . The reason why J EGO is an exception is explained in the subsequent subsection. J RSJ technique: In all experiments, the results of J RSJ are substantially worse than the results of the other methods. Consequently, J RSJ is not shown in most of the ?gures except for Figs. 9 and 10 which

Selectivity

2.5

ARTICLE IN PRESS

168 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Time to ε-join(A,B) 4D, uniform, |A| = |B| = 100,000 200 150 100 50 5 0 0.01 0.03 0.05 ε 0.07 0 0.09

Grid EGO* Selectivity EGO RSJ

30 25 Selectivity 20 15 10

Fig. 9. Join four-dimensional uniform data, with J RSJ .

Relative to RSJ performance of ε-join(A,B) 4D, uniform, |A| = |B| = 100,000 50 times better than RSJ 40 30 20 10 0 0.01

Grid EGO* Selectivity EGO RSJ

30 25 Selectivity 20 15 10 5 0.03 0.05 ε 0.07 0 0.09

Fig. 10. Join four-dimensional uniform data, performance relative to J RSJ .

have been included for the purpose of demonstrating J RSJ ’s poor performance. Figs. 9 and 10 study the effect of varying on the ef?ciency of the join techniques for four-dimensional uniformly distributed data where cardinality of both datasets being joined, A and B, is 100; 000. Fig. 13 is for the same experiment but with J RSJ removed. J EGO technique: J EGO achieves 3.5–6.5 times better results than those of J RSJ . This asserts J EGO is a good technique for joining low-dimensional data. However, the two new techniques proposed in this paper, J G and J EGO? , are even better than J EGO . J EGO? technique: J EGO? ’s performance is always better than that of J EGO in all experiments. This demonstrates the strength of J EGO? . Because of the selectivity, the values of are likely to be small for low-dimensional data and large for high-dimensional data. The EGO-heuristic is not well-suited for small values of . The smaller the epsilon, the less likely a sequence will have an inactive dimension. In

Fig. 10, the performance of J EGO? is 13.5–24 times better than the performance of J RSJ . Fig. 14 illustrates another trend: J EGO? can be better than J G for low-dimensional data when the selectivity is high. In Fig. 14, J EGO? becomes a better choice than J G for values of greater than approximately 0.07. This choice of corresponds to a high selectivity of approximately 43. J G technique: For low-dimensional data, J G consistently demonstrates the best results among all the tested join techniques. The results of J G are 15.5–46 times better than the results of J RSJ . They are several times better than the results of J EGO? , except for high-selectivity cases as in Fig. 14. Recall that the grid has been established in [10] as the best choice of index for the index nested loop approach among the main memory optimized versions of the grid, R-tree, R*-tree, CR-tree, and quad-tree indexes. Thus, the good results of J G for lowdimensional data are not very surprising. Figs. 11 and 12 studies a self-join of real threedimensional data taken from the ColorMoments ?le. The cardinality of the dataset is 68,000. Fig. 11 plots the three best schemes, whereas Fig. 12 omits J EGO scheme due to its much poorer performance. In these ?gures, J G is almost two times better than J EGO? for small values of . Figs. 13 and 14 study a case of joining four-dimensional uniform data. The graph on the left is for datasets of cardinality 100,000, and that on the right is for datasets with cardinality 200,000. Figs. 15 and 16 demonstrate the results for four-dimensional skewed and real data. The trends in these ?gures are consistent with the trends exhibited by the join techniques for the uniform distribution.

Time (secs)

Time to ε-join (A,A) 3D, real data (ColorMom), |A| = 68,000 30 25

Time (secs)

Grid EGO* EGO Selectivity

40 35 30 25 20 15 10 5 0.004

ε

Fig. 11. Join three-dimensional real data.

15 10 5 0 0.001 0.007

0 0.01

Selectivity

20

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 169

Time to ε-join (A,A) 3D, real data (ColorMom), |A| = 68,000 3 2.5

Time (secs)

Grid EGO* Selectivity

Time to ε-join (A,B) 4D, skewed, |A| = |B| = 100,000 40 35 30 Time (secs) Selectivity 25 20 15 10 5 20 15 10 5 0 0.005 0.01

ε

Fig. 15. Join four-dimensional skewed data.

Grid EGO* EGO Selectivity

30 25

1.5 1 0.5 0 0.001 0.004

ε

0.007

0 0.01

0.015

Fig. 12. Join three-dimensional real data without J EGO (for clarity).

Time to ε-join (A,A) Time to ε-join (A,B) 4D, uniform, |A| = |B| = 100,000 35 30 Time (secs) 25 20 15 10 5 0 0.01 0.03 0.05 ε 0.07

Grid Grid, no Z-sort EGO EGO* Selectivity

10 30 8 Time (secs) 25 Selectivity 20 15 10 5 0 0.09 6 4 2

4D, real data (ColorMom), |A| = 68,000

Grid EGO* Selectivity

80 70 60 50 40 30 20 10 0 0.03 Selectivity

0 0.001

0.01

ε

0.02

Fig. 16. Join four-dimensional real data. Fig. 13. Four-dimensional, uniform, 100,000 points.

Time to ε-join (A,B) 4D, uniform, |A| = |B| = 200,000 80 60 Time (secs) 40

Grid EGO* EGO Selectivity

140 120 100 80 60 40 20 Selectivity

20 0 0.01

0.03

0.05 ε

0.07

0 0.09

Fig. 14. Four-dimensional, uniform, 200,000 points.

mately 2.5 times. J G ’s performance without Z-sort, in general, is better than J EGO but worse than that of J EGO? . Comparing the number of sequence tests for J EGO? and J EGO : As discussed in Section 2.2, J EGO? ’s better performance over J EGO is a direct result of the large reduction in the number of sequences needed to be compared. Figs. 17(a) and (b) corroborate this assertion by showing the number of such comparisons (in millions) as a function of . For both EGO- and EGO*- heuristics, the number of tests increase as increases (starting from greater than approximately 0.5). This is because as increases the bounds on sequences the two methods produce get courser. Since the size of each cell is equal to , the bounds of the sequences are more likely to be within distance from each other.8

To illustrate this point consider EGO*-heuristic, ?0; 1?2 domain and two points a?0:05; 0:05? and b?0:55; 0:55?. The

8

Using spatial sorts: Fig. 13 emphasizes the importance of performing Z-sort on data being joined: the performance improvement is approxi-

Selectivity

2

18 16 14 12 10 8 6 4 2 0 0.02

ARTICLE IN PRESS

170 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Number of sequence tests 4D, uniform, |A| = |B| = 100,000 25 number of tests Millions 20 15 10 5 0 0 (a) 0.02 0.04 ε 0.06 0.08 EGO EGO*

25 number of testsMillions 20 15 10 5 0

Number of sequence tests 4D, uniform, |A| = |B| = 100,000

EGO EGO*

sequences with at least one inactive dimension (the EGO heuristic utilizes inactive dimensions). Fig. 17(b) show that as soon as becomes smaller than a certain value the curve stabilizes since almost no sequence with an inactive dimension is found. The J EGO? does not suffer from this drawback since it utilizes both inactive and active dimensions. Separating costs of join phases: The join procedures of J EGO , J EGO? , and J G consist of several phases. All the methods ?rst sort the points in the two arrays: J EGO and J EGO? use EGO-sort while J G uses Z-sort. Thus, we will refer to the ?rst phase of each algorithm as the sort phase. The next two phases of J G are the init phase where the grid is initialized and the add phase where the grid index is built on top of the -radius circles. Finally, the last phase of all methods is the join phase. It is interesting to study the contribution of each phase to the overall cost for each method. Figs. 18 and 19 plot the time spent in different phases of the join procedures for a join of four-dimensional uniform data and for a self-join of nine-dimensional real

80 70 60 time (secs) join add init sort

0 (b)

0.00025

0.0005 ε

0.00075

0.001

50 40

join

Fig. 17. The number of sequence comparisons by J EGO? and J EGO : (a) 2 ?0; 0:09?; (b) 2 ?0; 0:001?.

join

join

30

join

join

20

join

join

10 0

add

The number of sequence tests performed by J EGO increases as approaches zero. This is because it becomes more and more challenging to ?nd

0.01 0.05 0.09 EGO*

0.01 0.05 0.09 EGO

0.01 0.05 0.09 Grid

Fig. 18. Cost of join phases, four-dimensional, uniform data, jAj ? jBj ? 200; 000.

only one point a and sequence Sb consists of only b. If is 0.2 then the corresponding cells for a and b are C a ?0; 0? and C b ?2; 2?. Because the cell size is , S a is bounded by a rectangle Ra ? ?0; 0:2? ? ?0; 0:2? and Sb by Rb ? ?0:4; 0:6? ? ?0:4; 0:6?. These rectangles are not within distance from each other and thus the heuristic will successfully return that the sequences are nonjoinable. On the other hand, if is say 0.5, then the cells are C a ?0; 0? and C b ?1; 1?, the corresponding rectangles are much courser (larger): Ra ? ?0; 0:5? ? ?0; 0:5? and Rb ? ?0:5; 1? ? ?0:5; 1?. Now, Ra and Rb are within distance from each other and thus the heuristic will fail to correctly determine that S a and Sb are non-joinable.

time (secs)

(footnote continued) q?????????????????????????????????????????????????????????????? distance d?a; b? is equal to ?0:55 ? 0:05?2 ? ?0:55 ? 0:05?2 which q?? is 1 or approximately 0.707. Assume sequence Sa consists of 2

180 160 140 120 100

join

join add init sort

80 60

join

40 20 0

join

0.02 0.06 0.1 EGO*

Fig. 19. Cost of join phases, nine-dimensional, real data (ColorMom), jAj ? 68; 000, self-join.

join Join join

join

0.02 0.06 0.1 EGOG

0.02 0.06 0.1 rid

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 171

data. The cost of the join phase is dominant in most of the cases. The contribution of the sort phase is signi?cant only for the low-dimensional case of four-dimensional data. Note that if we ignore the sort cost, the relative stand of the methods will not change. The cost of the init phase is almost nonexistent. Finally, the cost of the add phase of J G , while is not negligible, is still dominated by the cost of the join phase.

data. Figs. 24 and 25 show the results for the nineand 16-dimensional real data, respectively. As in the low-dimensional data case, for all tested cases J RSJ has demonstrated substantially worse

Time to ε -join(A,B) 9D, skewed, |A| = |B| = 100,000 90

EGO

12

EGO* Selectivity

75 Time (secs) 60 45 30 15 0 0.04

10 8 6 4 2 Selectivity Selectivity Selectivity

3.3. High-dimensional data We now study the performance of the join techniques for high-dimensional data. The results for nine-dimensional uniformly distributed data are illustrated in Figs. 20 and 21. Fig. 22 studies a case of joining nine-dimensional skewed data, and Fig. 23 plots the results for nine-dimensional real

Time to ε -join(A,B) 9D, uniform, |A| = |B| = 100,000 40 1500 Time (secs) 35 30

0.05

ε

0.06

0 0.07

Fig. 22. Join nine-dimensional skewed data.

Time to ε -join(A,A) 9D, real data (ColorMom), |A| = 68,000 150 Selectivity 125 Time (secs) 100 75 50 25 0 0.02 0.04 0.06 ε 0.08 60

Grid EGO EGO* Selectivity

50 40 30 20 10 0 0.1

1000

Grid EGO* Selectivity EGO RSJ

25 20 15 10 5

500

0 0.10

0.2

ε

0.3

0 0.4

Fig. 20. Join nine-dimensional uniform data.

Fig. 23. Join nine-dimensional real data.

Time to ε -join(A,B) 9D, uniform, |A| = |B| = 100,000 250

EGO EGO* Selectivity

Time to ε -join(A,A) 16D, real data (ColorHist), |A| = 68,000 40 35 Time (secs) 30 25 20 15 10 5 15 0 0.0005 0 0.4 Selectivity 90 75 60 45 30

Grid EGO EGO* Selectivity

200 Time (secs) 150 100 50 0 0.1

0.2

ε

0.3

0.005

ε

0.01

18 16 14 12 10 8 6 4 2 0 0.015

Fig. 21. Best two techniques of Fig. 20.

Fig. 24. Join 16D real data.

ARTICLE IN PRESS

172 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Time to ε -join(A,A) 32D, real data (ColorHist), |A| = 68,000 140 120 Time (secs) 100 80 60 40 20 0 0.01 0.04

ε

Fig. 25. Join 32D real data.

EGO EGO* Selectivity

join(A,B), 8D, uniform, |A|=|B|, = 0.1 30,000

0.07

18 16 14 12 10 8 6 4 2 0 0.1

25,000 Time (secs) 20,000 15,000 10,000 5,000 0 0

EGO EGO*

Selectivity

2,500,000 5,000,000 7,500,000 10,000,000 the number of points in A and B

Fig. 26. Join 8D uniform, large datasets.

results. Therefore, the results of J RSJ are omitted from most of the graphs, except for Fig. 20. Unlike the case of the low-dimensional data, J EGO and J EGO? are now better than J G . J G is not a good choice for the high-dimensional data, hence its results are often omitted for clarity of comparisons of the results of J EGO and J EGO? . A consistent trend in all experiments is that the performance of J EGO? is always better than the performance of J EGO . The difference is especially notable for low-selectivity cases. This is a general trend: J EGO does not work well for smaller epsilons, because in this case a sequence is less likely to have an inactive dimension. J EGO? does not suffer from this limitation. The behavior of the J EGO curve is different from that of the low-dimensional case, except for Fig. 24. For the low-dimensional case the performance of J EGO would increase ?rst with increasing and then decrease, whereas for the high-dimensional case it typically monotonically decreases. This is because with the increased dimensionality larger values of should be used to get reasonable selectivity. Consequently, the effect where the performance of J EGO would improve ?rst for small values of , is no longer present. Datasets with large cardinality: Fig. 26 studies the performance of J EGO and J EGO? for large volumes of eight-dimensional data uniformly distributed in ?0; 1?8 . In this experiment, the cardinality of each distinct dataset A and B is not ?xed as before, but varied from 100,000 points to 10,000,000 points per each dataset. The setup of this experiment is similar to that of Fig. 10(left) in [7], except in [7] the maximum number of points is 40,000,000. Also, it is not very clear whether [7] studies a self-join, or a join of two distinct datasets. In the experiment

illustrated in Fig. 26, J EGO? outperforms J EGO by a factor of approximately 2.15. Choosing to-be-indexed dataset: When a join of two datasets is to be computed using Grid-join, an index is built on one of the two datasets. Naturally, the question of which dataset to build the index on arises. We ran experiments to study this issue. The results indicate that building the index on the smaller dataset gives better results. 4. Related work The problem of the similarity join of two datasets is to identify pairs of objects, one from each dataset, such that they satisfy a certain constraint. If both datasets are the same, this corresponds to a selfjoin. The most common join constraint is that of proximity: i.e. the two objects should be within a certain distance of each other. This corresponds to the -join where is the threshold distance beyond which objects are no longer considered close enough to be joined. Below, we discuss some of the most prominent solutions for ef?cient computation of similarity joins. Shim et al. [14] propose to use -KDB-tree for performing high-dimensional similarity joins of massive data. The main-memory based -KDB-tree and the corresponding algorithm for similarity join are modi?ed to produce a disk-based solution that can scale to larger datasets. Whenever the number of points in a leaf node exceeds a certain threshold, it is split into b1=c stripes,9 each of width equal to or slightly greater than in the i-th dimension. If the leaf node is at level i, then the i-th dimension is used

Note that for high-dimensional data can easily exceed 0.5 rendering this approach into a brute force method.

9

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 173

for splitting. The join is performed by traversing the index structures for each of the datasets. Each leaf node can join only with its two adjacent siblings. The points are ?rst sorted with the ?rst splitting dimension and stored in an external ?le. The RSJ algorithm [9] works with an R-tree index built on the two datasets being joined. The algorithm is recursively applied to corresponding children if their MBRs are within distance of each other. Several optimizations of this basic algorithm have been proposed [15]. A cost model for spatial joins was introduced in [16]. The Multipage Index (MuX) was also introduced that optimizes for I/O and CPU cost at the same time. In [2] a plane sweeping technique is modi?ed to create a diskbased similarity join for two-dimensional data. The new procedure is called the partition-based spatial merge join, or PBSM-join. A partition-based merge join is also presented in [3]. Shafer et al. in [17] present a method of parallelizing high-dimensional proximity joins. The -KDB-tree is parallelized and compared with the approach of space partitioning. Koudas et al. [18] have proposed a generalization of the size separation spatial join algorithm, named multidimensional spatial join (MSJ). Recently, Bohm et al. [7] proposed the EGO-join. ¨ Both datasets of points being joined are ?rst sorted in accordance with the EGO. The EGO-join procedure is recursive. A heuristic is utilized for determining non-joinable sequences. More details about EGO-join are covered in Section 2.2. The EGO-join was shown to outperform other join methods in [7]. An excellent overview of multidimensional index structures including grid-like and quad-tree based structures can be found in [19]. Main-memory optimization of disk-based index structures has been explored recently for B?-trees [20] and multidimensional indexes [11–13]. Both studies investigate the redesign of the nodes in order to improve cache performance. Another problem that is related to the problem of similarity joins is the problem of similarity searching. This problem has been well studied by several researchers [21–27]. Many of those solutions utilize nearest-neighbor queries. 5. Conclusions This paper develops two novel in-memory methods for fast similarity join of multidimensional data. It demonstrates the advantage of the proposed

Table 1 Choosing a join algorithm Small Low-dimensional High-dimensional JG J G or J EGO? Average JG J EGO? Large J G or J EGO? J EGO?

methods, called Grid-join and EGO*-join, over the state-of-the-art technique by evaluating them on low- and high-dimensional data. The novel Gridjoin approach shows the best results for lowdimensional case, or when the value of is very small. The EGO*-join technique shows the best results for high-dimensional data or when the value of is large. The empirical and analytical evaluation demonstrates that the proposed EGO*-join technique signi?cantly outperforms the state-of-the-art EGO-join method. Based upon the experimental results, the recommendations for choosing a join algorithm are summarized in Table 1. The paper also studies the effect of the parameter on the resulting selectivity of the join and provides recommendations for choosing to achieve meaningful selectivity. The paper demonstrates that improper selectivity can lead to the wrong conclusions. Finally, the paper develops a cost-estimation function for Grid-join. Such a function can be employed for choosing the size of the grid, or by a query optimizer for selecting a query execution plan. As future work, we plan to look into the problem of similarity join for datasets of very high dimensionality, such as 100 dimensions or more. This is an interesting challenge since many existing methods rely on the fact that is likely to be (much) less than 1 for ?0; 1?d domain. However, for data with very high dimensionality, one can expect to encounter the values of which are greater than (or comparable to) 1.

Appendix A. Choice of grid size In this section, we develop cost estimator functions for Grid-join. These functions can be used to determine the appropriate choice of grid size for computing the -join for a speci?c problem. The discussion focuses on the case of two dimensions, but can be generalized to any number of dimensions in a straightforward manner.

ARTICLE IN PRESS

174 Table A.1 Parameters used for -join Parameter A B k ? jAj m ? jBj c n ? 1=c eps; Meaning First dataset for join Second dataset (on which the index is built) Cardinality of A Cardinality of B Length of side of a cell Grid size: n ? n grid Epsilon parameter for the join D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Table A.1 lists parameters needed for our analysis. All the parameters are known before the join, except for grid size n, which needs to be determined. We are interested in ?nding n such that the time needed for the join is minimized. Furthermore, if there are several values of n that yield minimal or close to minimal join cost, then we are interested in the smallest such n. This is because the memory requirements for the grid increase with the number of cells in the grid. In order to determine the relationship between the join cost and the various parameters of the problem, we develop what we call estimator (or predictor) functions for the various phases of Gridjoin. Once the predictor functions are constructed, a suitable choice for n can be found by identifying a minimal value of the cost. For the value of n selected, the predictor functions are also useful in providing an estimated cost to the query optimizer which can use this information to decide whether or not Grid-join should be used for the problem. In our analysis, we assume uniform distribution of points in datasets A and B. The Grid-join procedure can be divided into three phases: (1) init phase: initialization of the grid pointers and lists. (2) add phase: loading the data into the grid. (3) proc phase: processing the point-queries using the grid. Init and add phases collectively are called the build index phase. There is a tradeoff between the build and proc phases with respect to the grid size n. With fewer cells, each circle is likely to intersect fewer cells and thus be added to fewer full and part lists. On the other hand, with fewer cells the average length of the part lists is likely to be larger and each query may take longer to process. In other words, the coarser the grid (i.e. the smaller the value

of n), the faster the build phase, but the slower the proc phase. Due to this fact, the total time needed for join is likely to be a concave downwards function of n. This has been the case in all our experiments. Upper bound: While the general trend is that a ?ner grid would imply shorter query processing time (since the part lists would be shorter or empty), beyond a certain point, a ?ner grid may not noticeably improve performance. For our implementation, the difference in time needed to process a cell when its part list is empty, versus when its part list has size one, is very small. It is enough to choose grid size such that the size of part list is one and further partitioning does not noticeably improve query processing time. Thus, we can estimate an upper-bound nupper for the optimal value of n, and search for the optimal value of n only among the values in the interval ?1; nupper ?. For the two-dimensional case, if the grid is built on squares instead of circles, it can be shown that an upper bound is given by [10]: 8 1 > d4qme > if q4 p???? ; > > 2 m > >2 > 3 < nupper ? 6 1 7 >6 7 otherwise: > >6 7 > >6 1 > p???? ? q7 > :6 m 7 In this formula, q is the size of a side of each square. Since for -join the index is built on circles, the formula is reused by approximating the circle by a p??? square with the same area, that is q % p. The corresponding formula for nupper is therefore 8 1 > d4p???me > p if 4 p??????? ; > > 2 pm > >2 > 3 < nupper ? 6 7 1 > 7 >6 >6 > 1 p???7 otherwise: > > 6p???? ? p7 >6 : 7 m A ?ner grid than that speci?ed by the above formula will give very minor performance improvement while incurring a large memory penalty. Thus, the formula establishes the upper bound for the grid size. However, if the value returned by the formula is too large, the grid might not ?t in memory. In that case, n is further limited by the memory space availability. In our experiments, the optimal value for grid size tended to be closer to 1 rather than to nupper , as will

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 175

be demonstrated later in this section in Figs. A.4 and A.5. Analysis: For each of the phases of the Grid-join, the analysis is conducted as follows. (1) First, the parameters on which a phase depends on are determined. (2) Then, the nature of the dependence on each distinct parameter is predicted based on the algorithm and implementation of the grid. Since the grid is a simple data structure, the nature of the dependence on a parameter, as a rule, is not complicated. (3) Next, the dependence on the combination of the parameters is predicted, based on the dependence on each parameter. (4) Finally, an explanation is given on how to calibrate the predictor functions for a speci?c machine. Estimating the init phase: The time to initialize the index depends only on the grid size n. The process of index initialization can be viewed as O?1? operations, followed by the initialization of n2 cells. Thus, the index initialization time is expected to be a polynomial such that the degree of n is 2: Pinit ?n? ? an2 ? bn ? c, for some coef?cients a, b, and c. The values of the coef?cients depend upon the particular machine on which the initialization is performed. They can be determined through a calibration step. To validate the correctness of this estimator, we calibrated it for a given machine. The corresponding estimator function was then used to predict the performance for other values of n not used for the calibration. The result is illustrated in Figs. A.1 and A.2 (a ? 8:26 ? 10?7 , b ? 0, and c ? 0). These two ?gures are for different ranges of n, that is, n varies from 10 to 100 in Fig. A.1 and it varies from 100 to 1000 in Fig. A.2. The ?gures plot the actual grid initialization time, measured for different values of n, and the initialization time predicted by the estimator function. Let us observe that the estimator function computes very accurate approximations of the actual values, especially for larger values of n. Figs. A.1 and A.2 show that the time needed for index initialization phase can be approximated well with a simple polynomial. Any numerical method can be used for calibrating the coef?cients a, b, and c for a particular machine. Estimating the add phase: This phase is more complicated than the init phase because it depends on three parameters: n—the grid size, m—the cardinality of the indexed dataset B, and . By analyzing the dependence on each parameter separately, we estimate that the overall function can be represented as a polynomial Padd ?n; m; ? ?

Time to create index 0.01 0.008 Time (secs) 0.006 0.004 0.002 0 0.01 0.008 0.006 0.004 0.002 0 10 20 30 40 50 60 70 80 90 100 n - grid size

Estimated values Experemental Data

Fig. A.1. Time to initialize index n 2 ?10; 100?.

Time to create index 0.8 Time (secs) 0.6 0.4 0.2 Experemental Data Estimated values 0.8 0.6 0.4 0.2

0 0 100 200 300 400 500 600 700 800 900 1000 n - grid size

Fig. A.2. Time to initialize index n 2 ?100; 1000?.

a17 n2 2 m ? ? ? ? ? a1 m ? a0 such that the degree of n and is 2 and the degree of m is 1. The next step is to calibrate the coef?cients ai ’s. This can be done by solving a system of 18 linear equations. These equations can be obtained by choosing three different values of n, three values of , and two values of m ?3 ? 3 ? 2 ? 18?. The combinations of the following calibration points have been examined in order to get the coef?cients: n0 ? 10, n1 ? 100, n2 ? 200; 0 ? 0:001, 1 ? 0:01, 2 ? 0:02; m0 ? 50 and m1 ? 100. The choice of values implies we assume that typically n 2 ?10; 200?, 2 ?0:001; 0:02?, and m 2 ?50; 100?. The linear system was solved using the Gaussian elimination with pivoting method. Fig. A.3 demonstrates the time needed for the add phase for various values of when n ? 150 and m ? 75 and the other curve represents our interpolation polynomial. Again, we observe that the estimator function is highly accurate. In fact, we never

ARTICLE IN PRESS

176 D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177

Time to add circles 150x150grid, m=|B|=75,000, Calibration 1.6 1.4 1.2 Time (secs) 1 0.8 0.6 0.4 0.2 0 0.001 0.005 0.009 ε 0.013 0.017 Interpolated values Experimental results 1.6

Time (secs)

0.4

Total time ε=0.001, k=|A|=10,000, m=|B|=20,000 Experimental results Estimated values

0.4

1.4 1.2 1 0.8 0.6 0.4

0.3

0.3

0.2

0.2

0.1

0.1

110

130

150

170

0

n - grid size

Fig. A.4. Estimation of total join time, n 2 ?10; 190?.

Fig. A.3. Estimation with polynomial for add phase.

encountered more than a 3% relative error in our experiments. Estimating the proc phase: The processing phase depends on all parameters: n—grid size, k ? jAj, m ? jBj, and . Thankfully, the dependence on k is linear since each point is processed independently of other points. Thus, once the solution for some ?xed k0 is known, the solution for an arbitrary k can be computed by scaling. However, there is a small complication: the average lengths of the full and part lists are given by different formulae depending p??? upon whether cell size c is greater than p or not (see p??? [10], in our case query side size q is replaced by p). Consequently, the proc phase cost can be estimated pby two polynomials (depending on ??? whether pXc or not), which we denote as Pproc;p??Xc ?c; ; m; k0 ? and Pproc;p??oc ?c; ; m; k0 ?. p p Each of them has the type P?c; ; m; k0 ? a17 c2 2 m ? ? ? ? ? a1 m ? a0 such that the degree of c and is 2 and the degree of m is 1. Once again, the calibration can be done by solving a system of 18 linear equations for each of the two cases. Estimating the total time: The estimated total time needed for Grid-join is the sum of estimated time needed for each phase. Figs. A.4 and A.5 demonstrate estimation of time needed for Grid-join when ? 0:001, m ? 20; 000, k ? 10; 000 as a function of grid size n. The estimator functions of each phase were calibrated using different values than those shown in the graph. A simple bisection method was employed to get the estimated optimal value of n, as computed by the estimator function f est ?n? for the total execution time. This method assumes that it is given a concave downwards function f est ?n?, de?ned on ?a; b?. The

Total time ε=0.001, k=|A|=10,000, m=|B|=20,000 0.046 Time (secs) 0.045 0.044 0.043 0.042

Experimental results Estimated values

0.046 0.045 0.044 0.043 0.042 70 71 72 73 74 75 76 77 78 79 80 n - grid size

Fig. A.5. Estimation of total join time, n 2 ?70; 80?.

function f est ?n? has been concave downwards in all our experiments, however in future work we plan to prove that the estimator function is always concave downwards for various combinations of parameters. The objective of the bisection method is to ?nd the leftmost minimum of f est ?n? on the interval ?a; b?. The method ?rst computes c ? ?a ? b?=2. If f ?c ? 1?pf ?c ? 1?, then it makes the new b equal c and repeats the procedure, otherwise it makes the new a equal c and repeat the procedure. The process is repeated until ?b ? a?o2. The bisection method for the example in Figs. A.4 and A.5 returns ‘74’ as an estimated optimal value for n. Experimentally, we found that the actual optimal value for n was 73. The difference in execution time for the Grid-join with 73 ? 73 grid and with 74 ? 74 grid is just 2 ms for the given settings. This illustrates the high accuracy of the estimator functions. Let us observe that the results of interpolation look even better if they are rounded to the closest millisecond values.

190

10

30

50

70

90

0.2

0

0

ARTICLE IN PRESS

D.V. Kalashnikov, S. Prabhakar / Information Systems 32 (2007) 160–177 177

References

[1] D.V. Kalashnikov, S. Prabhakar, Similarity join for lowand high-dimensional data, in: Proceedings of the Eighth International Conference on Database Systems for Advanced Applications (DASFAA 2003), IEEE Computer Society Press, Kyoto, Japan, 2003. [2] J.M. Patel, D.J. DeWitt, Partition based spatial-merge join, in: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Que., Canada, June 4–6, 1996, ACM Press, New York, 1996, pp. 259–270. [3] M.-L. Lo, C.V. Ravishankar, Spatial hash-joins, in: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4–6, 1996, ACM Press, New York, 1996, pp. 247–258. [4] S. Guha, R. Rastogi, K. Shim, CURE: an ef?cient clustering algorithm for large databases, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1998. [5] E.M. Knorr, R.T. Ng, Algorithms for mining distance-based outliers in large datasets, in: Proceedings of the International Conference on Very Large Data Bases, 1998. [6] K. Koperski, J. Han, Discovery of spatial association rules in geographic information databases, in: International Symposium on Large Spatial Databases, 1995. [7] C. Bohm, B. Braunmuller, F. Krebs, H.-P. Kriegel, ¨ ¨ Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data, in: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, ACM Press, New York, 2001, pp. 379–388. [8] C. Bohm, B. Braunmuller, M. Breunig, H.-P. Kriegel, Fast ¨ ¨ clustering based on high-dimensional similarity joins, in: International Conference on Information and Knowledge Management, 2000. [9] T. Brinkhoff, H.-P. Kriegel, B. Seeger, Ef?cient processing of spatial joins using R-trees, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1993. [10] D.V. Kalashnikov, S. Prabhakar, S. Hambrusch, W. Aref, Ef?cient evaluation of continuous range queries on moving objects, in: Proceedings of the 13th International Conference on Database and Expert Systems Applications (DEXA 2002), Aix en Provence, France, 2002. [11] K. Kim, S. Cha, K. Kwon, Optimizing mutidimensional index trees for main memory access, in: Proceedings of ACM SIGMOD Conference, Santa Barbara, CA, 2001. [12] S. Prabhakar, Y. Xia, D. Kalashnikov, W. Aref, S. Hambrusch, Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects, IEEE Trans. Comput. 51 (10) (2002) 1124–1140. [13] D.V. Kalashnikov, S. Prabhakar, S. Hambrusch, Main memory evaluation of monitoring queries over moving objects, Distributed Parallel Databases, Int. J. (DAPD) 15 (2) (2004) 117–135. [14] K. Shim, R. Srikant, R. Agrawal, High-dimensional similarity joins, in: Proceedings of the 13th International Conference on Data Engineering, April 7–11, 1997, [15]

[16]

[17]

[18]

[19] [20]

[21]

[22]

[23]

[24] [25]

[26]

[27]

Birmingham, UK, IEEE Computer Society, Silver Spring, MD, 1997, pp. 301–311. Y.-W. Huang, N. Jing, E.A. Rundensteiner, Spatial joins using r-trees: breadth-?rst traversal with global optimizations, in: M. Jarke, M.J. Carey, K.R. Dittrich, F.H. Lochovsky, P. Loucopoulos, M.A. Jeusfeld (Eds.), VLDB’97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25–29, 1997, Athens, Greece, Morgan Kaufmann, Los Altos, CA, 1997, pp. 396–405. C. Bohm, H.-P. Kriegel, A cost model and index architecture ¨ for the similarity join, in: Proceedings of the International Conference on Data Engineering, 2001. J.C. Shafer, R. Agrawal, Parallel algorithms for highdimensional similarity joins for data mining applications, in: VLDB’97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25–29, 1997, Athens, Greece, Morgan Kaufmann, Los Altos, CA, 1997, pp. 176–185. N. Koudas, K.C. Sevcik, High-dimensional similarity joins: algorithms and performance evaluation, in: Proceedings of the 14th International Conference on Data Engineering, IEEE Computer Society, Silver Spring, MD, 1998, pp. 466–475. ¨ J. Tayeb, O. Ulusoy, O. Wolfson, A quadtree-based dynamic attribute indexing method, Comput. J. 41(3). J. Rao, K.A. Ross, Making B? -trees cache conscious in main memory, in: Proceedings of ACM SIGMOD Conference, Dallas, TX, 2000. W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, The QBIC project: querying images by content using color, texture and shape, in: Proceedings of the SPIE Conference on 1908 on Storage and Retrieval for Image and Video Databases, vol. 1908, 1993, pp. 173–187. F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, Z. Protopapas, Fast nearest neighbor search in medical image databases, in: Proceedings of the International Conference on Very Large Data Bases, Mumbai, India, 1996, pp. 215–226. S. Mehrotra, Y. Rui, M. Ortega, T.S. Huang, Supporting content-based queries over images in mars, in: Proceedings of the Fourth IEEE International Conference on Multimedia Computing and Systems, Ottawa, Ont., Canada, 1997, pp. 632–633. S. Mehrotra, et al., MARS project, UC Irvine, ohttp:// www-db.ics.uci.edu/pages/research/mars.shtml4. A. Gionis, P. Indyk, R. Motwani, Similarity search in high dimensions via hashing, in: Proceedings of the International Conference on Very Large Data Bases (VLDB), 1999. H.-P. Kriegel, S. Brecheisen, P. Kroger, M. Pfei?e, M. Schubert, Using sets of feature vectors for similarity search on voxelized cad objects, in: Proceedings of ACM SIGMOD International Conference on Management of Data, 2003, pp. 587–598. R. Agrawal, C. Faloutsos, A. Swami, Ef?cient similarity search in sequence databases, in: Proceedings of the Fourth International Conference on Foundations of Data Organization and Algorithms (FODO), 1993.

赞助商链接

更多相关文章：
**
lect5.ppt.Convertor
**

*quickly* *Multi-dimensional* dynamic programming (Murata...*joining* methods 3) Align the sequences sequentially...*similarity* CLUSTAL W (1.82) *multiple* sequence ...**
计算机视觉、机器学习相关领域论文和源代码大集合
**

*Similarity* Descriptors [Project] *Fast* Sparse ...[Project] THE MNIST *DATA*BASE of handwritten ...*Multi-Dimensional* Boosting Regression[Paper][Code] ...
更多相关标签：