Pattern matching on GPU #718

Activity

1. pavlexander commented on Nov 12, 2022

   

   pavlexander

   on Nov 12, 2022

   Last edited by pavlexander

   Author

   More actions

   "Complimentary", but not "replacery" to original post: I have made some attempts to improve computation time using custom made functionality.

   Code

   import stumpy
   from stumpy import config
   from scipy import stats
   import math
   import numpy as np
   import time
   
   repeating_data = [219.14, 219.25, 219.15, 219.07, 219.28]
   
   older_data = [218.24, 218.79, 218.69, 218.84, 219.21, 219.0, 218.93, 219.01, 219.0,
                 218.31, 218.89, 218.21, 218.47, 218.7, 218.52, 218.24, 218.03, 218.03, 218.04, 218.04, 218.21, 218.25,
                 218.54, 218.44, 218.29]
   
   newer_data = [218.29, 218.42, 218.29, 218.51, 218.87, 218.56, 218.67, 218.58, 218.58, 218.79, 218.81, 218.81,
                 218.78, 218.84, 218.82, 218.82, 218.69, 218.75, 218.73, 218.98]
   
   data = []
   data += older_data
   data += repeating_data
   data += newer_data
   data += repeating_data
   m = 5
   
   data_to_find = np.array(repeating_data)
   data = np.array(data)
   print('data_to_find length ', len(data_to_find))
   print('data length ', len(data))
   
   
   def start_timer():
       return time.time()
   
   
   def stop_timer(start_time, adder=''):
       print(adder, "--- %s seconds ---" % (time.time() - start_time))
       return start_timer()
   
   
   def z_norm(a, axis=0):
       std = np.std(a, axis, keepdims=True)
       std[std == 0] = 1
   
       return (a - np.mean(a, axis, keepdims=True)) / std
   
   
   def rolling_window(a, window):
       a = np.asarray(a)
       shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
       strides = a.strides + (a.strides[-1],)
   
       return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
   
   timer2 = start_timer()
   
   distance_profile = stumpy.mass(data_to_find, data)
   timer2 = stop_timer(timer2, '\nstumpy.mass ')
   idx = np.argmin(distance_profile)
   print(f"\tThe nearest neighbor to `Q_df` is located at index {idx} in `T_df`")
   
   distances = np.linalg.norm(z_norm(rolling_window(data, m), 1) - z_norm(data_to_find), axis=1)
   timer2 = stop_timer(timer2, '\nCustom ')
   idx = np.argmin(distances)
   print(f"\tThe nearest neighbor to `Q_df` is located at index {idx} in `T_df`")
   
   print('\nComparing stumpy.mass and custom generated distances')
   for i in range(len(distances)):
       print('\tMass: ', distance_profile[i], ', Custom: ', distances[i], ', Diff: ', (distance_profile[i] - distances[i]))
   
   print('Done')

   Output

   stumpy.mass --- 0.9259753227233887 seconds ---
   The nearest neighbor to Q_df is located at index 25 in T_df

   Custom --- 0 seconds ---
   The nearest neighbor to Q_df is located at index 25 in T_df

   Comparing stumpy.mass and custom generated distances
   Mass: 2.2105205844573215 , Custom: 2.210520585039989 , Diff: -5.826676918729845e-10
   Mass: 3.8282502748376936 , Custom: 3.828250275047967 , Diff: -2.1027357632874555e-10
   Mass: 3.4533746719581417 , Custom: 3.4533746718142164 , Diff: 1.4392531610951664e-10
   Mass: 1.9113193715052448 , Custom: 1.9113193732141167 , Diff: -1.7088719328484103e-09
   Mass: 3.458043570843686 , Custom: 3.458043571020999 , Diff: -1.7731283108446405e-10
   Mass: 4.154752748228278 , Custom: 4.154752748523079 , Diff: -2.9480151653160647e-10
   Mass: 1.8414238802224574 , Custom: 1.8414238819074986 , Diff: -1.6850412176694363e-09
   Mass: 3.701514742892828 , Custom: 3.701514743304959 , Diff: -4.121307739524127e-10
   Mass: 3.357192640386953 , Custom: 3.357192640174392 , Diff: 2.1256107984868322e-10
   Mass: 1.7340022421510477 , Custom: 1.7340022425813102 , Diff: -4.302624923013809e-10
   Mass: 4.025896930746229 , Custom: 4.025896931101078 , Diff: -3.5484948313069253e-10
   Mass: 3.6908006445288866 , Custom: 3.6908006451267976 , Diff: -5.979110540010879e-10
   Mass: 3.247382093375601 , Custom: 3.2473820937951627 , Diff: -4.195617187008338e-10
   Mass: 3.101020367895569 , Custom: 3.101020368198151 , Diff: -3.025824035773894e-10
   Mass: 3.2151523541440556 , Custom: 3.21515235502738 , Diff: -8.83324524636464e-10
   Mass: 3.542604830177246 , Custom: 3.54260483306828 , Diff: -2.891034078800203e-09
   Mass: 1.9202249779012381 , Custom: 1.9202249837287837 , Diff: -5.827545557224312e-09
   Mass: 3.0104809717644745 , Custom: 3.010480971920461 , Diff: -1.559863349598345e-10
   Mass: 2.5794214522067587 , Custom: 2.5794214531544806 , Diff: -9.477219009568216e-10
   Mass: 3.3182572646681816 , Custom: 3.3182572649903617 , Diff: -3.221800604080727e-10
   Mass: 3.850433587331335 , Custom: 3.8504335883242375 , Diff: -9.929026489885473e-10
   Mass: 1.3154870358066373 , Custom: 1.315487036488339 , Diff: -6.817018061155977e-10
   Mass: 3.0824902985267824 , Custom: 3.082490298938153 , Diff: -4.113704932251494e-10
   Mass: 3.5960444037723738 , Custom: 3.5960444041766886 , Diff: -4.043148038590516e-10
   Mass: 2.904488555396711 , Custom: 2.904488556126461 , Diff: -7.297500381753252e-10
   Mass: 0.00010079352952945846 , Custom: 0.0 , Diff: 0.00010079352952945846
   Mass: 4.16416120131542 , Custom: 4.164161201588881 , Diff: -2.7346036546305186e-10
   Mass: 3.069263551540473 , Custom: 3.0692635513875994 , Diff: 1.528737136879954e-10
   Mass: 2.8791877762763187 , Custom: 2.87918777661224 , Diff: -3.359210687392533e-10
   Mass: 3.3649871025910105 , Custom: 3.364987102578873 , Diff: 1.2137402194412061e-11
   Mass: 2.1328441196088974 , Custom: 2.1328441188015987 , Diff: 8.072986723561826e-10
   Mass: 4.028530575737881 , Custom: 4.028530575299188 , Diff: 4.3869352595038436e-10
   Mass: 2.956792368133736 , Custom: 2.956792367984455 , Diff: 1.492810319803084e-10
   Mass: 2.655451909828746 , Custom: 2.6554519099073945 , Diff: -7.864864315365594e-11
   Mass: 3.6576912140403177 , Custom: 3.6576912156040735 , Diff: -1.5637557915226807e-09
   Mass: 1.1457593089109914 , Custom: 1.1457593076787576 , Diff: 1.2322338704962021e-09
   Mass: 3.2703485305235573 , Custom: 3.2703485303642403 , Diff: 1.5931700403370996e-10
   Mass: 3.4241058351283016 , Custom: 3.4241058365722243 , Diff: -1.4439227591367398e-09
   Mass: 2.9566489570340115 , Custom: 2.9566489587835862 , Diff: -1.7495747073326129e-09
   Mass: 1.0341935968089795 , Custom: 1.0341936093022772 , Diff: -1.2493297729676556e-08
   Mass: 3.44291838472567 , Custom: 3.4429183952948716 , Diff: -1.0569201513987991e-08
   Mass: 3.7506410276983564 , Custom: 3.7506410263700323 , Diff: 1.3283241173667193e-09
   Mass: 3.8728677730397068 , Custom: 3.8728677713513258 , Diff: 1.6883809905721137e-09
   Mass: 2.6735389665990144 , Custom: 2.6735389665005984 , Diff: 9.841594206250193e-11
   Mass: 2.99521481673855 , Custom: 2.995214817101798 , Diff: -3.632480982673769e-10
   Mass: 2.2901261143524523 , Custom: 2.290126113750003 , Diff: 6.024492016365457e-10
   Mass: 2.7078183471280237 , Custom: 2.7078183479412936 , Diff: -8.132698958718265e-10
   Mass: 3.1422797563859666 , Custom: 3.1422797575820334 , Diff: -1.1960668011568032e-09
   Mass: 3.3126752260590555 , Custom: 3.3126752261699 , Diff: -1.1084466677857563e-10
   Mass: 3.393349891753226 , Custom: 3.3933498928226915 , Diff: -1.0694654051235375e-09
   Mass: 0.0001010852974836315 , Custom: 0.0 , Diff: 0.0001010852974836315
   Done

   Surprisingly, the distances are very very similar between the two results.. But we are still able to tell exactly where the match is, based on the distance... Pattern occurrence indices match perfectly.

   On another the positive side - the computation time is so neglectable, that I see the 0 second computation time! (it's about 0.0001 seconds or something similar) - a huge improvement over 1 second default time.

   Now, given the essentially same results, and a LOT smaller execution time - would this function not be of some use? I do not understand completely what I have done, but it looks like I have skipped some post-processing step from the original stumpy.mass function, that makes the distances slightly different, and execution time many times slower. Please correct me if I am wrong.

   I would still like to see the GPU based function for pattern matching, but, in addition to that - maybe you could make use of this code above to create some kind of "less strict" version of the distance calculation function, that runs many times faster than the original function, even on CPU

   p.s. I ended up reusing most of the code from unit tests here https://github.com/TDAmeritrade/stumpy/blob/e8a7dd4566eb662fc1c49a2a3b692035f64f18c3/tests/test_core.py#L400

   p.p.s I understand that most of the functions are based on research papers from other people..
2. stumpy-dev

   locked and limited conversation to collaborators on Nov 13, 2022
3. seanlaw

   converted this issue into a discussion #719 on Nov 13, 2022