Cache-oblivious High-performance Similarity Join
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Perdacher, Martin
Plant,Claudia
Böhm, Christian
A similarity join combines vectors based on a distance condition. Typically, such algorithms apply a filter step (by indexing or sorting) and then refine pairs of candidate vectors. In this paper, we propose to refine the pairs in an order defined by a space-filling curve which dramatically improves data locality. Modern multi-core microprocessors are supported by a deep memory hierarchy including RAM, various levels of cache, and registers. The space-filling curve makes our proposed algorithm cache-oblivious to fully exploit the memory hierarchy and to reach the possible peak performance of a multi-core processor. Our novel space-filling curve called Fast General Form (FGF) Hilbert solves a number of limitations of well-known approaches: it is non-recursive, it is not restricted to traverse squares, and it has a constant time and space complexity. As we demonstrate the easy transformation from conventional into cache-oblivious loops we believe that many algorithms for complex joins and other database operators could be transformed systematically into cache-oblivious SIMD and MIMD parallel algorithms.
 The title of this paper is cache oblivious high performance similarity join. And if you're a quick introduction into the similarity join and the filter technique which is used is the epsilon grid order. And we are using space filling curves and we will show the improvement of cache data locality. And also two different experimental results. First of all performance gains of individual parts. So of the joint technique of the epsilon grid order and the space filling curve and additional each separate space filling curve on its own and also comparison to state of the art. So the similarity join problem is mostly typed. So there are so many different similarity join problems and they all differ in the type, in the data type they use. So they are set similarity joins. And they are for different environments. Here we are targeting the multi core environments. And for the similarity join we calculate for these points the epsilon region and how many points are in this epsilon region. And this is for example important for algorithms like DB scan where the epsilon is given. So the epsilon is given. And the motivation here is that existing solutions are not designed for main memory databases and we focus on multi core environments and we include including a complex cache hierarchy here depicted on the right. So you have the RAM, you have the shared level three cache which is up to 250 megabytes in recent architectures and you have shared level two and level one cache and registers within the core and this parallel technique. Yeah, we will show them optimal cache locality. The applications, as I mentioned clustering algorithm DB scan for example, but also data cleaning outlier detection classification of massive data or catalog metrics, sensor networks. So here is a two set join and the other hand is a self join. Both methods are implemented. If you consider the data and here I introduced here explain this epsilon grid order which has been already introduced by on the SIGMOD conference 2001. Here we order according to rainbow colors. So these epsilon grid cells and you of course you can within epsilon grid cell of the first dimension you can also order within the second dimension and so on. But for now we are considering only one dimension for explaining purpose. So the similarity matrix and if we consider it as a self join then we will exclude the lower triangle of this similarity matrix and if we then apply the epsilon grid order which is our filtering technique then this part is also excluded because for here you only need to consider the next epsilon grid and this is why you can filter these steps and this middle in between we call it the stripe and now let's see how you can traverse this stripe. So the traditional approach here depicted on the left is the canonical approach and canonical approach is I mean you have two loops the I and the J loop and you walk through line by line and of course you can also walk through it by a cache conscious approach where you choose a certain block size and which this block size is referred to your cache hierarchy in any case and but you can also walk through this stripe in a space feeling curve order for example the set order here depicted on the left and we propose to traverse this stripe in a Hilbert order here depicted on the right and how do we generate such a Hilbert curve? There is we use context free grammar and A and B are non-terminal symbols and minus plus and step forward are terminal symbols so these non-terminals expand to the next line here the B and here the A so this minus here this means turn left then this B is and this arrow here this triangle is step one forward and this one this plus is turn right and with this we can easily infer this matrix sizes for this one the blue one and this one for the green one green box here and for the red box here and this pie here in the end this means the process the object pair in this case of the similarity drawing it is like computer distance from these two points and of course we have a non-recursive formulation within our paper and this non-recursive formulation here we using a Hilbert value and this Hilbert value this tells us where we exactly are in this pattern of the Hilbert curve and we can infer every kind of property which is needed to decide where we are in this Hilbert curve yes that's basically it and we in order to in our non-recursive formulation we infer properties from this auxiliary variable the Hilbert value and our non-recursive formulation is also not restricted to traverse squares and has not has a constant time and space complexity per loop iteration and here again in this gray area here there is a stripe and outside this stripe we have red and green lines this red line is where we just check if we can prune or filter the space according to epsilon grid order or not and we can determine these boundaries here also in linear time and yeah we always filter some space for example so this green one here is eight boxes long and so we can filter eight by eight boxes and for the experimental evaluation we use the hardware inter-exeon phi and this inter-exeon phi has the decent cache memory hierarchy and with 16 megabytes of level 3 cache 1 megabyte of level 2 cache and 32 kilobytes of level 1 data cache and the results are also reproduced on a Skylake processor and for a selectivity measure we use the average of number of neighbors so it's the n selectivity so this is where you if you have a certain epsilon for the similarity join then all of the all of this the amount of the result set then divided by n so it's the average number of neighbors for all of the points and all plots have n selectivity between 1 and 100 and in the plots they are this n selectivity is on the right with and right vertical axis in our plots and dashed line so this n selectivity this is the FGF Hilbert is the complete including this Hilbert curve and this epsilon grid order this Kano Euclid is only a canonical version without this epsilon grid order and the Hilbert Euclid is a Hilbert version without the epsilon grid order and this Hilbert Kala also Hilbert without epsilon grid order but we use some refined technique where we apply this Kala product on the Euclidean distance to compute it faster and here is a Gaussian distributed data set for 1 million data objects and 8 dimensions and you can see that the impact of the Hilbert curve is like this here and the impact of the epsilon grid order is this one here and this one is the n selectivity here on the right axis this is the runtime and the epsilon region okay then we also have looked into the cache pattern so for level 1 cache we have and as in all of the levels of the cache levels for exactly the same data set we perform quite well and we have split this into parts to analyze which part takes the most time so the sorting includes this epsilon grid order sorting and planning is this determination of this upper bounds and the join is the regular join this epsilon join and yeah you can see most of the part is referred to the join algorithm and the sorting and the planning of this algorithm is not has not a huge impact and the comparison to the state of the art there is state of the art in multicore environments is super ego and which also relies on the epsilon grid order and blasts is optimized version for a reformulation of the similarity join problem as a matrix formulation and so we using d gem from Intel blasts to compute the similarity join and then the auto vectorization is a baseline to see how it well performs but yeah so the synthetic data sets we are using 64 dimensions and for uniform distributed data set depicted here on the left we are using our s fast as plus s plus and uniform distributed you can really prune the space and so our method is this plot shows that our method is kind of efficient and as you can see state of the art super ego the performance very badly on uniform distributed data sets but if we add eight selective dimensions then both this epsilon order grid order kicks in and you can see the impact of it so in real data experiments we compare to I mean there are some more in the paper the IOT botnet and the big cross data sets are here outlined here and always we choose this symbol and this between one and a hundred in average neighbors and yeah to conclude we our space feeling curves dramatically improves the efficient exploration of the memory hierarchy and our hillbett join inherits from the classical hillbett curve and integrates this idea to into a filter and refinement algorithm and then future work we will consider similarity joins on general matrix basis with canyons with neighbors predictions or multivay joints thank you.
 The title of this paper is cache oblivious high performance similarity join.  And if you're a quick introduction into the similarity join and the filter technique which  is used is the epsilon grid order.  And we are using space filling curves and we will show the improvement of cache data  locality.  And also two different experimental results.  First of all performance gains of individual parts.  So of the joint technique of the epsilon grid order and the space filling curve and additional  each separate space filling curve on its own and also comparison to state of the art.  So the similarity join problem is mostly typed.  So there are so many different similarity join problems and they all differ in the type,  in the data type they use.  So they are set similarity joins.  And they are for different environments.  Here we are targeting the multi core environments.  And for the similarity join we calculate for these points the epsilon region and how many  points are in this epsilon region.  And this is for example important for algorithms like DB scan where the epsilon is given.  So the epsilon is given.  And the motivation here is that existing solutions are not designed for main memory  databases and we focus on multi core environments and we include including a complex cache hierarchy  here depicted on the right.  So you have the RAM, you have the shared level three cache which is up to 250 megabytes in  recent architectures and you have shared level two and level one cache and registers within  the core and this parallel technique.  Yeah, we will show them optimal cache locality.  The applications, as I mentioned clustering algorithm DB scan for example, but also data  cleaning outlier detection classification of massive data or catalog metrics, sensor  networks.  So here is a two set join and the other hand is a self join.  Both methods are implemented.  If you consider the data and here I introduced here explain this epsilon grid order which  has been already introduced by on the SIGMOD conference 2001.  Here we order according to rainbow colors.  So these epsilon grid cells and you of course you can within epsilon grid cell of the first  dimension you can also order within the second dimension and so on.  But for now we are considering only one dimension for explaining purpose.  So the similarity matrix and if we consider it as a self join then we will exclude the  lower triangle of this similarity matrix and if we then apply the epsilon grid order which  is our filtering technique then this part is also excluded because for here you only  need to consider the next epsilon grid and this is why you can filter these steps and  this middle in between we call it the stripe and now let's see how you can traverse this  stripe.  So the traditional approach here depicted on the left is the canonical approach and canonical  approach is I mean you have two loops the I and the J loop and you walk through line  by line and of course you can also walk through it by a cache conscious approach where you  choose a certain block size and which this block size is referred to your cache hierarchy  in any case and but you can also walk through this stripe in a space feeling curve order  for example the set order here depicted on the left and we propose to traverse this stripe  in a Hilbert order here depicted on the right and how do we generate such a Hilbert curve?  There is we use context free grammar and A and B are non-terminal symbols and minus plus  and step forward are terminal symbols so these non-terminals expand to the next line here  the B and here the A so this minus here this means turn left then this B is and this arrow  here this triangle is step one forward and this one this plus is turn right and with  this we can easily infer this matrix sizes for this one the blue one and this one for  the green one green box here and for the red box here and this pie here in the end this  means the process the object pair in this case of the similarity drawing it is like computer  distance from these two points and of course we have a non-recursive formulation within  our paper and this non-recursive formulation here we using a Hilbert value and this Hilbert  value this tells us where we exactly are in this pattern of the Hilbert curve and we can  infer every kind of property which is needed to decide where we are in this Hilbert curve  yes that's basically it and we in order to in our non-recursive formulation we infer  properties from this auxiliary variable the Hilbert value and our non-recursive formulation  is also not restricted to traverse squares and has not has a constant time and space  complexity per loop iteration and here again in this gray area here there is a stripe and  outside this stripe we have red and green lines this red line is where we just check  if we can prune or filter the space according to epsilon grid order or not and we can determine  these boundaries here also in linear time and yeah we always filter some space for example  so this green one here is eight boxes long and so we can filter eight by eight boxes  and for the experimental evaluation we use the hardware inter-exeon phi and this inter-exeon  phi has the decent cache memory hierarchy and with 16 megabytes of level 3 cache 1 megabyte  of level 2 cache and 32 kilobytes of level 1 data cache and the results are also reproduced  on a Skylake processor and for a selectivity measure we use the average of number of neighbors  so it's the n selectivity so this is where you if you have a certain epsilon for the  similarity join then all of the all of this the amount of the result set then divided  by n so it's the average number of neighbors for all of the points and all plots have n  selectivity between 1 and 100 and in the plots they are this n selectivity is on the right  with and right vertical axis in our plots and dashed line so this n selectivity this  is the FGF Hilbert is the complete including this Hilbert curve and this epsilon grid order  this Kano Euclid is only a canonical version without this epsilon grid order and the Hilbert  Euclid is a Hilbert version without the epsilon grid order and this Hilbert Kala also Hilbert  without epsilon grid order but we use some refined technique where we apply this Kala  product on the Euclidean distance to compute it faster and here is a Gaussian distributed  data set for 1 million data objects and 8 dimensions and you can see that the impact  of the Hilbert curve is like this here and the impact of the epsilon grid order is this  one here and this one is the n selectivity here on the right axis this is the runtime  and the epsilon region okay then we also have looked into the cache pattern so for  level 1 cache we have and as in all of the levels of the cache levels for exactly the  same data set we perform quite well and we have split this into parts to analyze which  part takes the most time so the sorting includes this epsilon grid order sorting and planning  is this determination of this upper bounds and the join is the regular join this epsilon  join and yeah you can see most of the part is referred to the join algorithm and the  sorting and the planning of this algorithm is not has not a huge impact and the comparison  to the state of the art there is state of the art in multicore environments is super  ego and which also relies on the epsilon grid order and blasts is optimized version for  a reformulation of the similarity join problem as a matrix formulation and so we using d  gem from Intel blasts to compute the similarity join and then the auto vectorization is a  baseline to see how it well performs but yeah so the synthetic data sets we are using 64  dimensions and for uniform distributed data set depicted here on the left we are using  our s fast as plus s plus and uniform distributed you can really prune the space and so our  method is this plot shows that our method is kind of efficient and as you can see state  of the art super ego the performance very badly on uniform distributed data sets but  if we add eight selective dimensions then both this epsilon order grid order kicks in and  you can see the impact of it so in real data experiments we compare to I mean there are  some more in the paper the IOT botnet and the big cross data sets are here outlined  here and always we choose this symbol and this between one and a hundred in average  neighbors and yeah to conclude we our space feeling curves dramatically improves the efficient  exploration of the memory hierarchy and our hillbett join inherits from the classical  hillbett curve and integrates this idea to into a filter and refinement algorithm and  then future work we will consider similarity joins on general matrix basis with canyons  with neighbors predictions or multivay joints thank you.
Perdacher_Plant_Boehm_0_131.png Perdacher_Plant_Boehm_132_179.png Perdacher_Plant_Boehm_180_227.png Perdacher_Plant_Boehm_228_1403.png Perdacher_Plant_Boehm_1404_2435.png Perdacher_Plant_Boehm_2436_2939.png Perdacher_Plant_Boehm_2940_4091.png Perdacher_Plant_Boehm_4092_4463.png Perdacher_Plant_Boehm_4464_4715.png Perdacher_Plant_Boehm_4716_5015.png Perdacher_Plant_Boehm_5016_5687.png Perdacher_Plant_Boehm_5688_7235.png Perdacher_Plant_Boehm_7236_8339.png Perdacher_Plant_Boehm_8340_8807.png Perdacher_Plant_Boehm_8808_10883.png Perdacher_Plant_Boehm_10884_12635.png Perdacher_Plant_Boehm_12636_14099.png Perdacher_Plant_Boehm_14100_16019.png Perdacher_Plant_Boehm_16020_17255.png Perdacher_Plant_Boehm_17256_17603.png Perdacher_Plant_Boehm_17604_18179.png Perdacher_Plant_Boehm_18180_18635.png Perdacher_Plant_Boehm_18636_19247.png Perdacher_Plant_Boehm_19248_19727.png Perdacher_Plant_Boehm_19728_20951.png Perdacher_Plant_Boehm_20952_22211.png Perdacher_Plant_Boehm_22212_22967.png Perdacher_Plant_Boehm_22968_23831.png Perdacher_Plant_Boehm_23832_23969.png