User:Jadrian Miles/Streamline clustering - Revision history

Jadrian Miles: /* Notes */

2009-03-31T06:28:26Z

Notes

@@ Line 44: / Line 44: @@
 * No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain).  These are loose bounds on our clustering threshold.  Near-infinite distances also don't need to be stored in the priority queue.
 * About 35% of the distances computed are infinite.
 == References ==
 * Corouge, et al. Towards a shape model of white matter fiber bundles using diffusion tensor MRI.
 * Moberts, et al. Evaluation of fiber clustering methods for diffusion tensor imaging.

Jadrian Miles: /* Notes */

2009-03-29T09:41:50Z

Notes

← Older revision		Revision as of 09:41, 29 March 2009
Line 43:		Line 43:
	* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).		* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).
	* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.		* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.
	* About ~~half~~ the distances computed are infinite.		* About 35% of the distances computed are infinite.

	=== Parallel Computation of the Priority Queue ===		=== Parallel Computation of the Priority Queue ===

Jadrian Miles at 14:52, 28 March 2009

2009-03-28T14:52:06Z

← Older revision		Revision as of 14:52, 28 March 2009
Line 75:		Line 75:

	When "marking" the index file, each process can just seek to the end and read and delete the last line. That way the merges are always working from smaller to bigger, and there's no search time for unmarked indices.		When "marking" the index file, each process can just seek to the end and read and delete the last line. That way the merges are always working from smaller to bigger, and there's no search time for unmarked indices.

			== References ==
			* Corouge, et al. Towards a shape model of white matter fiber bundles using diffusion tensor MRI.
			* Moberts, et al. Evaluation of fiber clustering methods for diffusion tensor imaging.

Jadrian Miles: /* Parallel Computation of the Priority Queue */

2009-03-27T18:05:49Z

Parallel Computation of the Priority Queue

← Older revision		Revision as of 18:05, 27 March 2009
Line 73:		Line 73:
	\| \| \| \| release the lock		\| \| \| \| release the lock
	\| \| write q[k] to a file "results.i.k"		\| \| write q[k] to a file "results.i.k"

			When "marking" the index file, each process can just seek to the end and read and delete the last line. That way the merges are always working from smaller to bigger, and there's no search time for unmarked indices.

Jadrian Miles: /* Notes */

2009-03-27T18:02:21Z

Notes

← Older revision		Revision as of 18:02, 27 March 2009
Line 43:		Line 43:
	* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).		* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).
	* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.		* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.
			* About half the distances computed are infinite.

	=== Parallel Computation of the Priority Queue ===		=== Parallel Computation of the Priority Queue ===

Jadrian Miles: /* Files */

2009-03-27T18:01:30Z

Files

← Older revision		Revision as of 18:01, 27 March 2009
Line 18:		Line 18:
	=== Files ===		=== Files ===
	* <tt>tube_12.nocr</tt> (757MB) --- the full list of all the curves generated by <tt>tubegen</tt>.		* <tt>tube_12.nocr</tt> (757MB) --- the full list of all the curves generated by <tt>tubegen</tt>.
	* <tt>~~lines.mat~~</tt> ~~(261MB)~~ --- a Matlab workspace ~~file~~ with the ~~variable~~ <tt>~~lines~~</tt> ~~in it, which is just a parsing of~~ <tt>~~tube_12.nocr~~</tt>.		* <tt>matfiles</tt> --- a directory full of Matlab workspace files with random subsets of the full set of curves from <tt>tube_12.nocr</tt> stored as the variable <tt>lines</tt>.
	* <tt>hostlist</tt> --- a list of hosts I can run remote jobs on.		* <tt>hostlist</tt> --- a list of hosts I can run remote jobs on.

	~~If we stored the full distance matrix as single-precision floats, it would be about 400GB. Obviously something else needs to happen.~~

	=== Distance Measurements ===		=== Distance Measurements ===

Jadrian Miles: /* Parallel Computation of the Priority Queue */

2009-03-27T17:58:52Z

Parallel Computation of the Priority Queue

← Older revision		Revision as of 17:58, 27 March 2009
Line 59:		Line 59:
	\|		\|
	\| create empty priority queue q		\| create empty priority queue q
	\| for j=(i+1):n		\| for j=(i+1:n-1)
	\| \| d = dcc(i,j)		\| \| d = dcc(i,j)
	\| \| if !isinf(d)		\| \| if !isinf(d)

Jadrian Miles: /* Distance Measurements */

2009-03-27T17:47:07Z

Distance Measurements

← Older revision		Revision as of 17:47, 27 March 2009
Line 34:		Line 34:
	** <tt>drawpdcc.m</tt> plots two curves and the point-to-point matches found on them by <tt>pdcc.m</tt>.		** <tt>drawpdcc.m</tt> plots two curves and the point-to-point matches found on them by <tt>pdcc.m</tt>.
	** <tt>drawpdccset.m</tt> plots all four variations of the asymmetric distance for two curves.		** <tt>drawpdccset.m</tt> plots all four variations of the asymmetric distance for two curves.

			=== Distributed Distance Matrix ===
			Here "priority queue" actually means a list of distances and corresponding curve indices that is sorted by increasing distance.
			* <tt>distanceMatrixRows.m</tt> computes several lines of the matrix and returns the corresponding priority queue
			* <tt>mergeSorted.m</tt> merges two priority queues together

	== Notes ==		== Notes ==

Jadrian Miles: /* Notes */

2009-03-27T17:43:43Z

Notes

← Older revision		Revision as of 17:43, 27 March 2009
Line 40:		Line 40:
	* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).		* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).
	* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.		* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.

			=== Parallel Computation of the Priority Queue ===
			First, the server writes a file containing the indices of all the rows. In parallel, each machine does the following:
			read all the curves 0--(n-1) into memory
			while(true)
			\| wait for a lock on the index file
			\| search for an unmarked index i
			\| if no unmarked index
			\| \| release the index file lock
			\| \| return
			\| mark index i
			\| release the index file lock
			\|
			\| create empty priority queue q
			\| for j=(i+1):n
			\| \| d = dcc(i,j)
			\| \| if !isinf(d)
			\| \| \| q.insert((d,i,j))
			\|
			\| divide q into lists q[k] where <math>\scriptstyle \forall\,d\,\in\,q[k],\;k^2\epsilon\,<\,d\,<\,(k+1)^2\epsilon</math> for some constant <math>\scriptstyle\epsilon</math>
			\|
			\| foreach k
			\| \| if a file "results.*.k" exists
			\| \| \| try to get a lock on it
			\| \| \| \| read in the file
			\| \| \| \| merge the contents with q[k]
			\| \| \| \| delete the file
			\| \| \| \| release the lock
			\| \| write q[k] to a file "results.i.k"

Jadrian Miles: /* Notes */

2009-03-27T01:34:05Z

Notes

← Older revision		Revision as of 01:34, 27 March 2009
Line 39:		Line 39:
	* We only need to store the upper half of the distance matrix. A manageable subset of curves is 30000 (9.3%). (30000^2)/2 * 4bytes = 1.7GB.		* We only need to store the upper half of the distance matrix. A manageable subset of curves is 30000 (9.3%). (30000^2)/2 * 4bytes = 1.7GB.
	* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).		* Brain is ~100mm wide (X=LR), ~145mm long (Y=AP), ~100mm high (Z=IS).
	* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold.		* No two curves should be closer than 0.5, and anything more than 50 away is basically infinitely far away (on the other side of the brain). These are loose bounds on our clustering threshold. Near-infinite distances also don't need to be stored in the priority queue.