Skip to content

Tutorial notebook DAMP #920

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
NimaSarajpoor wants to merge 20 commits into
base: main
Choose a base branch
from
Open

Tutorial notebook DAMP #920

Changes from 1 commit
Commits
Show all changes
20 commits
Select commit Hold shift + click to select a range
b311533
Add tutorial notebook DAMP
NimaSarajpoor Oct 3, 2023
4ef1f5d
add function to compute range
NimaSarajpoor Oct 8, 2023
efeb68a
Clean code
NimaSarajpoor Oct 13, 2023
f3c7f30
enhance readability
NimaSarajpoor Oct 13, 2023
01bb14c
improve docstring
NimaSarajpoor Oct 14, 2023
f871b42
minor fix for finding dhunks for function
NimaSarajpoor Nov 6, 2023
d7d1314
improve docstring
NimaSarajpoor Nov 19, 2023
80f214e
minor fix in code and docstring
NimaSarajpoor Nov 19, 2023
d130159
add functions to complete DAMP
NimaSarajpoor Nov 19, 2023
d3d7e7d
minor enhancements
NimaSarajpoor Nov 19, 2023
50c6709
enhance code readability
NimaSarajpoor Nov 19, 2023
633cce8
Revise comments
NimaSarajpoor Nov 19, 2023
c112477
add performant func and minor enhancements
NimaSarajpoor Nov 26, 2023
585fc4c
add new example
NimaSarajpoor Nov 26, 2023
53f7346
minor fixes
NimaSarajpoor Nov 27, 2023
99593e0
minor fix to make sure chunks get updated in each iter
NimaSarajpoor Nov 29, 2023
5c110a1
use JIT compiled functions with fastmath flag where possible
NimaSarajpoor Dec 8, 2023
830bb27
Merge branch 'main' into DAMP
NimaSarajpoor Aug 18, 2025
4d87d99
fix code so that it becomes compatible with numpy>=2.0
NimaSarajpoor Aug 20, 2025
6b6e30f
Add new notebook to explore pyFFTW in DAMP
NimaSarajpoor Aug 20, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
minor fix for finding dhunks for function
  • Loading branch information
@NimaSarajpoor
NimaSarajpoor committed Nov 6, 2023
commit f871b4266d256835c676f9fe83d88aa6b1393440
136 changes: 29 additions & 107 deletions docs/Tutorial_DAMP.ipynb
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -101,9 +101,6 @@
" \n",
" discord_idx : int\n",
" The start index of the top discord\n",
" \n",
" Note\n",
" ----\n",
" \n",
" \"\"\"\n",
" mp = stumpy.stump(T, m)\n",
Expand Down Expand Up @@ -159,109 +156,35 @@
},
{
"cell_type": "code",
"execution_count": 5,
"id": "387ca010",
"execution_count": 1,
"id": "dd1f7b3d",
"metadata": {},
"outputs": [],
"source": [
"def naive_get_range_damp(i, m, chunksize_init=None):\n",
" if chunksize_init is None:\n",
" chunksize_init = next_pow2(m)\n",
" \n",
" lst = []\n",
" chunksize = chunksize_init\n",
" stop = i\n",
" for _ in range(i):\n",
" start = stop - chunksize\n",
" start = max(0, start)\n",
" \n",
" lst.append([start, stop])\n",
" if start > 0:\n",
" stop = start\n",
" chunksize = 2 * chunksize\n",
" else:\n",
" break\n",
" \n",
" return np.array(lst)\n",
"\n",
"\n",
"def _get_range_damp(i, m, chunksize_init=None):\n",
"def naive_get_range_damp(stop, m, chunksize=None, start=0):\n",
" \"\"\"\n",
" For the given index `i`, segmentize the array `np.arange(i)` into \n",
" chunks such that the last chunk has size `chunksize_init`, and \n",
" the one before that has size `2 * chunksize_init` and so on. The\n",
" output contains the (start, stop) indices of chunks.\n",
" \n",
" Parameters\n",
" ----------\n",
" i : int\n",
" The stop index\n",
" \n",
" m : int\n",
" The window size\n",
" \n",
" chunksize_init : int\n",
" The initial chunksize, which is the size of the last chunk\n",
" \n",
" Returns\n",
" -------\n",
" out : np.ndarray\n",
" A 2D numpy array, where each row has (start, stop) index. \n",
" `out[0]` is the first chunk just before `i`. `out[-1]` is\n",
" the left-most chunk in the time series, with start index 0. \n",
" \n",
" For the given indices range `(start, stop)`, returns the\n",
" (start, stop) of chunks, each with a length that is power\n",
" of two.\n",
" \"\"\"\n",
" if chunksize_init is None:\n",
" chunksize_init = next_pow2(m)\n",
" \n",
" # The array [0, 1, 2, ..., i-1] is chunked as follows:\n",
" # `s` is the initial chunksize\n",
" \n",
" # chunks are:\n",
" # 1st chunk: [i - s: i],\n",
" # 2nd chunk: [i - s - (2s): i - s],\n",
" # 3rd chunk: [i - 3s - (4s) : i - 3s]\n",
" # 4th chunk: [i - 7s - (8s) : i - 7s]\n",
" # ...\n",
" \n",
" # The first index of the n-th chunk will be `i - (2^n - 1)s`. \n",
" # So, if we have `n` chunks in total, `n` is the minimum int\n",
" # that satisfies `(2**n - 1) * s >= i`\n",
" \n",
" n_chunks = int(math.ceil(math.log2((i / chunksize_init) + 1)))\n",
" chunks_ticks = i - (np.power(2, np.arange(n_chunks + 1)) - 1) * chunksize_init\n",
" start_indices = chunks_ticks[1:]\n",
" stop_indices = chunks_ticks[:-1]\n",
" if chunksize is None:\n",
" chunksize = next_pow2(m)\n",
" \n",
" out = np.empty((n_chunks, 2), dtype=np.int64)\n",
" out[:, 0] = start_indices\n",
" out[:, 1] = stop_indices\n",
" out[-1, 0] = 0 # the most-left chunk starts at 0.\n",
" \n",
" return out\n",
"\n",
"\n",
"# test \n",
"for i in range(8, 65):\n",
" for m in range(3, 8):\n",
" ref = naive_get_range_damp(i, m)\n",
" cmp = _get_range_damp(i, m)\n",
" np.testing.assert_almost_equal(ref, cmp)\n",
" \n",
" chunksize_init = next_pow2(2 * m)\n",
" ref = naive_get_range_damp(i, m, chunksize_init)\n",
" cmp = _get_range_damp(i, m, chunksize_init)\n",
" np.testing.assert_almost_equal(ref, cmp)\n",
" lst = []\n",
" chunk_stop = stop\n",
" while start < chunk_stop:\n",
" chunk_start = max(chunk_stop - chunksize, start)\n",
" lst.append([chunk_start, chunk_stop])\n",
" \n",
" chunksize_init = 1\n",
" ref = naive_get_range_damp(i, m, chunksize_init)\n",
" cmp = _get_range_damp(i, m, chunksize_init)\n",
" np.testing.assert_almost_equal(ref, cmp)"
" chunk_stop = chunk_start + m\n",
" chunksize = 2 * chunksize\n",
" \n",
" return np.array(lst)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"execution_count": 2,
"id": "79663447",
"metadata": {},
"outputs": [],
Expand All @@ -274,6 +197,7 @@
" Σ_T, \n",
" T_subseq_isconstant, \n",
" bsf,\n",
" chunks_indices=None,\n",
"):\n",
" \"\"\"\n",
" Compute the (approximate) left matrix profile value that corresponds to the subsequence \n",
Expand Down Expand Up @@ -312,35 +236,33 @@
" bsf : float\n",
" The best-so-far discord distance \n",
" \"\"\"\n",
" excl_zone = int(math.ceil(m / stumpy.core.config.STUMPY_EXCL_ZONE_DENOM))\n",
" chunksize = next_pow2(m) \n",
" if chunks_indices is None:\n",
" excl_zone = int(math.ceil(m / stumpy.core.config.STUMPY_EXCL_ZONE_DENOM))\n",
" chunks_indices = naive_get_range_damp(stop=idx + m - excl_zone, start=0)\n",
" \n",
" nn_distance = np.inf\n",
" for (start, stop) in _get_range_damp(query_idx - excl_zone, m, chunksize):\n",
" # (start, stop) contains the \"start\" index of subsequences that should \n",
" # be compared against the query `Q = T[query_idx : query_idx + m]`.\n",
" for (start, stop) in chunks_indices:\n",
" QT = core.sliding_dot_product(\n",
" T[query_idx : query_idx + m], \n",
" T[start : stop - 1 + m],\n",
" T[start : stop],\n",
" )\n",
" D = core._mass(\n",
" T[query_idx : query_idx + m],\n",
" T[start : stop - 1 + m],\n",
" T[start : stop],\n",
" QT=QT,\n",
" μ_Q=M_T[query_idx],\n",
" σ_Q=Σ_T[query_idx],\n",
" M_T=M_T[start : stop],\n",
" Σ_T=Σ_T[start : stop],\n",
" M_T=M_T[start : stop - m + 1],\n",
" Σ_T=Σ_T[start : stop - m + 1],\n",
" Q_subseq_isconstant=T_subseq_isconstant[query_idx],\n",
" T_subseq_isconstant=T_subseq_isconstant[start : stop],\n",
" T_subseq_isconstant=T_subseq_isconstant[start : stop - m + 1],\n",
" )\n",
" \n",
" nn_distance = min(nn_distance, np.min(D))\n",
" if nn_distance < bsf:\n",
" break\n",
" \n",
" else:\n",
" bsf = nn_distance\n",
" bsf = max(bsf, nn_distance)\n",
" \n",
" return nn_distance, bsf"
]
Expand Down