https://nmsl.cs.sfu.ca/api.php?action=feedcontributions&feedformat=atom&user=Tdameh 2026-06-03T21:08:54Z User contributions MediaWiki 1.35.1 https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4766 2012-01-27T01:19:08Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 and Spring 2012 (RA) =<br /> <br /> <br /> === Jan 27 ===<br /> * Implementing my method on cluster, report to be sent soon.<br /> <br /> <br /> === Dec 23 ===<br /> * Finished the study of different methods, the analysis and the implementation on a single machine.<br /> <br /> <br /> === Nov 9 ===<br /> * Scaled the Spectral Hashing.<br /> * Working on the US Census Data (1990) [number of features (dimensions) = 69 ]<br /> * run experiments on small DataSet (4k) using the 3 methods LSH Random Projection, LSH Spectral Hashing and Hilbert Curve<br /> * now running on large DataSet (1M) using LSH only (as H-curve doesn't work on large Scale)<br /> * experiment results to be added to the report<br /> <br /> <br /> === Oct 26 ===<br /> * I am facing problems working on very high dimensional data (d~100000) [curse of dimensionality]<br /> ** I can't use small dataSets (1k points) to compare different methods (Hilbert curve fails for high dimensional but LSH still works)<br /> ** The concept of distance becomes less precise as the number of dimensions grows.<br /> ** There are other techniques to cluster the high-dimensional data (no usage of gram matrix) such as Subspace Clustering, Projected Clustering and Correlation Clustering. <br /> * I start working on different real DataSets with low dimension (~100)<br /> * Working on Scaling the Spectral Hashing by scaling the Principle Component Analysis function on matlab<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4681 2011-11-11T00:13:31Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Nov 9 ===<br /> * Scaled the Spectral Hashing.<br /> * Working on the US Census Data (1990) [number of features (dimensions) = 69 ]<br /> * run experiments on small DataSet (4k) using the 3 methods LSH Random Projection, LSH Spectral Hashing and Hilbert Curve<br /> * now running on large DataSet (1M) using LSH only (as H-curve doesn't work on large Scale)<br /> * experiment results to be added to the report<br /> <br /> <br /> === Oct 26 ===<br /> * I am facing problems working on very high dimensional data (d~100000) [curse of dimensionality]<br /> ** I can't use small dataSets (1k points) to compare different methods (Hilbert curve fails for high dimensional but LSH still works)<br /> ** The concept of distance becomes less precise as the number of dimensions grows.<br /> ** There are other techniques to cluster the high-dimensional data (no usage of gram matrix) such as Subspace Clustering, Projected Clustering and Correlation Clustering. <br /> * I start working on different real DataSets with low dimension (~100)<br /> * Working on Scaling the Spectral Hashing by scaling the Principle Component Analysis function on matlab<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4679 2011-11-01T23:29:55Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 26 ===<br /> * I am facing problems working on very high dimensional data (d~100000) [curse of dimensionality]<br /> ** I can't use small dataSets (1k points) to compare different methods (Hilbert curve fails for high dimensional but LSH still works)<br /> ** The concept of distance becomes less precise as the number of dimensions grows.<br /> ** There are other techniques to cluster the high-dimensional data (no usage of gram matrix) such as Subspace Clustering, Projected Clustering and Correlation Clustering. <br /> * I start working on different real DataSets with low dimension (~100)<br /> * Working on Scaling the Spectral Hashing by scaling the Principle Component Analysis function on matlab<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4677 2011-10-26T06:02:34Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 26 ===<br /> * I am facing problems working on very high dimensional data (d~100000) [curse of dimensionality]<br /> ** I can't use small dataSets (1k points) to compare different methods (Hilbert curve fails for high dimensional but LSH still works)<br /> ** The concept of distance becomes less precise as the number of dimensions grows.<br /> ** There are other techniques to cluster the high-dimensional data (no usage of gram matrix) such as Subspace Clustering, Projected Clustering and Correlation Clustering. <br /> * I am looking for other real DataSets with low dimension (~100)<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4676 2011-10-26T05:58:06Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 26 ===<br /> * I am facing problems working on very high dimensional (and sparse) data (d~100000) [curse of dimensionality]<br /> ** I can't use small data sets (1k points) to compare different methods (Hilbert curve fails for high dimensional but LSH still works)<br /> ** The concept of distance becomes less precise as the number of dimensions grows<br /> ** There are other techniques to cluster the high-dimensional data (no usage of gram matrix) such as Subspace Clustering, Projected Clustering and Correlation Clustering. <br /> * I am looking for other real DataSets with low dimension (~100)<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4664 2011-10-12T09:40:53Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I use document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4663 2011-10-12T09:24:50Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I chose document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i. Keywords correspond to the words that remain after the pre-processing of stop-words removal and words stemming. Below N is the total number of documents.<br /> * DataSets: source: http://archive.ics.uci.edu/ml/datasets/Bag+of+Words:<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> ** PubMed abstracts: (PubMed comprises more than 21 million citations for biomedical literature from MEDLINE, life science journals, and online books)<br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> * Currently I process 1M documents from PubMed with the dimesion 141043, total size of this DataSet on HD is about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4662 2011-10-12T09:20:16Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I chose document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i , below N is the total number of documents.<br /> * DataSets (http://archive.ics.uci.edu/ml/datasets/Bag+of+Words):<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> <br /> ** PubMed abstracts: <br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> <br /> * currently I process 1M documents from PubMEd with the dimesion 141043, total size of this DataSet on HD about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4661 2011-10-12T09:20:01Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I chose document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i , below N is the total number of documents.<br /> * DataSets (http://archive.ics.uci.edu/ml/datasets/Bag+of+Words):<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> <br /> ** PubMed abstracts: <br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> <br /> * currently I process 1M documents from PubMEd with the dimesion 141043, total size of this DataSet on HD about 250GB. <br /> * To Do: compare the performance using two different LSH families.<br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4660 2011-10-12T09:18:54Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Oct 12 ===<br /> * Process Very-High dimensional and Very-Large Scale real DataSets<br /> ** I chose document clustering, where each document i is commonly represented by a term-frequency vector xi = [x1i, x2i, ..., xDi], where D is the total number of keywords in the given document corpus, and xji is the number of occurrences of keyword j in document i , below N is the total number of documents.<br /> * DataSets (http://archive.ics.uci.edu/ml/datasets/Bag+of+Words):<br /> ** NYTimes news articles: <br /> *** orig source: ldc.upenn.edu<br /> *** N=300000 <br /> *** D=102660 <br /> <br /> ** PubMed abstracts: <br /> *** orig source: www.pubmed.gov <br /> *** N=8200000 <br /> *** D=141043 <br /> <br /> * currently I process 1M documents from PubMEd with the dimesion 141043, total size of this DataSet on HD about 250GB. <br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4634 2011-09-28T08:56:56Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here:<br /> ** /nsl/students/dameh/reports/doc/main.pdf <br /> * updated sections : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4633 2011-09-28T08:56:01Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> <br /> === Spet 28 ===<br /> * Updated report is here /nsl/students/dameh/reports/doc/main.pdf <br /> * section updated : <br /> ** IV. PERFORMANCE METRICS<br /> ** VI. RESULTS<br /> <br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4588 2011-09-12T10:09:59Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at these addresses :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4587 2011-09-12T10:07:29Z

<p>Tdameh: </p> <hr /> <div>= Fall 2011 (RA) =<br /> <br /> === Sept 12 ===<br /> * Comparison Results for H-curve, LSH-Spectral hashing and LSH-Random Projection:<br /> * Metrics used for comparison:<br /> ** FN.SpaceReduction product Metric : Gram matrix level comparison which takes in account both the FN and the space reduction for the approximated gram matrix (as FN decreases space reduction increases)<br /> *** to unify the comparison we set H-curve window_width = DataSets_size/2^k. where k is the number of the LSH hash bits (number of buckets 2^k), in this case we get same matrix size for both H-curve and LSH.<br /> *** this metric gives us the optimal value of k (maximum).<br /> *** LSH-Spectral hashing over performs LSH-Random projection. H-curve over performs both.<br /> *** Graph results can be found at this addresses (DataSet of size 4k points and a dimension of 65) :<br /> **** FN for different values of k: dameh/reports/dameh/fall11/FN.pdf<br /> **** gram matrix size for different values of k: dameh/reports/dameh/fall11/Size.pdf<br /> **** FN.SpaceReduction : dameh/reports/dameh/fall11/FSprod.pdf<br /> ** Average distance between each point and its Exemplar: which is clustering error metric <br /> *** to unify the comparison we are comparing Avg distance against the number of Exemplars, (we change a parameter in the affinity propagation to control number of Exemplars, or its an initialization parameter for k-means clustering)<br /> *** again, LSH-Spectral hashing over performs LSH-Random projection, and LSH-Spectral hashing over performs H-curve only for smaller number of clusters<br /> *** Graph result can be found at this address: dameh/reports/dameh/fall11/ClusteringError.pdf<br /> ** over all, the advantage of LSH over H-cuve is the parallel property of LSH, where we can get a speedup up to 2^k for the LSH (each node takes care of each bucket)<br /> <br /> <br /> = Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4571 2011-08-22T08:33:02Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the Hilbert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4570 2011-08-22T08:27:28Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Aug 22 ===<br /> *fixing bugs in the hibert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4569 2011-08-22T08:26:59Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 22 ===<br /> *fixing bugs in the hibert curve and the affinity propagation codes (still working on them)<br /> *revised the metric to be FN.SpaceRedcution product (Inspired from the Energy.Delay product used in the Energy-Efficient Computing )<br /> *cmpt300 Final grading<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4555 2011-08-09T21:41:43Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y-axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4554 2011-08-09T21:40:48Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow width for H-curve that gives us same approximated matrix size, using the formula (winWidth=DataSize/2^k) <br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4553 2011-08-09T08:35:26Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow size for H-curve that gives us same approximated matrix size.<br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I came back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4552 2011-08-09T00:00:57Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Space filling Curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow size for H-curve that gives us same approximated matrix size.<br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I got back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4551 2011-08-08T23:59:48Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Aug 8 ===<br /> *working on comparing LSH methods with Hilbert curve methods.<br /> ** for the low level comparing (matrix level using average FN): we get almost same average FN for both spectral hashing and H-curve.<br /> ** comparing in the high level (clustering error): <br /> *** I am picking the optimal value of k for spectral hashing and choosing a widow size for H-curve that gives us same approximated matrix size.<br /> *** In the affinity propagation, using small value of self similarity (s(i,i)) we get small numbers of clusters and vise verse , so I am changing self similarity values between max and min to get same number of clusters for both methods, which will be the x-axis, on the other hand, the y axis will be the average distance between each point and its Exemplar.<br /> * PS: I was sick for a week after I got back form China and then busy in setting up and grading assignments for cmpt300. <br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4532 2011-07-17T18:04:20Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4531 2011-07-17T18:03:59Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> ===July 10 - July 24 ===<br /> * Attending workshop on [http://www.nudt.edu.cn/summerschool/eng/lessoninfo.html High Performance Computing] at National University of Defense Technology, China.<br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4525 2011-07-07T00:09:02Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method using the &quot;Locality Sensitive Hashing&quot; to the method using &quot;Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4523 2011-07-06T06:02:18Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === July 8 ===<br /> * Comparing our method to previous method &quot;Methods using Hilbert Space filling Curve&quot;<br /> * Initial results can be found at this address students/dameh/reports/dameh/summer11/H-CurveVSlsh.pdf<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4503 2011-06-18T02:46:35Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4502 2011-06-18T02:46:23Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === Jun 17 ===<br /> * Report should be available [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/main.pdf here]<br /> <br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=group_meeting&diff=4492 2011-06-07T21:11:28Z

<p>Tdameh: </p> <hr /> <div>We hold regular meetings for discussion and for every student to update the group on his/her progress. In some of the meetings, graduate students present talks summarizing their research progress so far. <br /> <br /> The meetings are good opportunities for students to practice their presentation skills and to get constructive feedback from the group on their research. The meetings keep the group members informed about different research problems being addressed in the group. They are also very helpful in finding research topics specially for new students. <br /> <br /> Everybody is welcome to attend. Meeting time: Every Tuesday, 10:00 AM -12:00 PM, room SUR 4010. <br /> <br /> <br /> == Spring 2011==<br /> <br /> * 1 Feb: Ahmed Bu-khamsin, Top Ten Computationally-Complex Problems in Oil and Gas Exploration Filed<br /> <br /> * 25 Jan: Naghmeh, [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/khodabakhshi/talks/3DVideoCopyDetection.pptx 3D Video Copy Detection]<br /> <br /> * 18 Jan: Cameron, [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/harvey/talks/Copy%20Detection%20Using%20Optical%20Flow.pptx Video Copy Detection using Optical Flow]<br /> <br /> * 11 Jan: Mathieu, [[media:3D_VideosOverview.pptx | 3D Media - An Overview]]<br /> <br /> <br /> <br /> Group meetings were held biweekly up to Dec 2010. <br /> <br /> == Fall 2010==<br /> <br /> * 21 Dec 10: Group discussion.<br /> <br /> * 9 Dec 10: Mohammad, [[media:Botnet-Detection-2.0.pptx | Detection of SIP Botnets Based on C&amp;C Communication]]<br /> <br /> * 23 Nov 10: Taher, [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/talks/AppAlgo2.ppt Approximation algorithms for Large-Scale Kernel Methods]<br /> <br /> * 19 Oct 10: Jeff, [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/gao/talks/LSH_Cluster.pdf Gram Matrix Approximation Using Locality Sensitive Hashing on Cluster]<br /> <br /> * 7 Oct 10: Dr. Rocky Chang (Hong Kong Polytechnic University),&lt;br/&gt; [[media:Rocky-SFU-7-Oct-2010.pdf | Active Measurement of Data-Path Quality in a Non-cooperative Internet]]<br /> <br /> * 28 Sep 10: Ahmed, [[media:DRS.pdf | Energy-Efficient Gaming on Mobile Devices using Dead Reckoning-based Power Management]]<br /> <br /> <br /> == Spring/Summer 2010==<br /> <br /> * 31 Aug 10: Hamed, [[media:Predicting_Click_Through_Rate_for_new_ads.pdf | Predicting Click Through Rate for New Ads with Semantically Similarity Measurement]]<br /> <br /> * 9 Aug 10: Yuanbin, [[media:mutisendP2Pstream.pdf | Efficient Algorithms for Multi-Sender Data Transmission in Swarm-based P2P Streaming Systems]]<br /> <br /> * 3 Aug 10: Azin, [[media:CognitiveRadio.ppt | Cognitive Radio Networks]]<br /> <br /> * 20 July 10: Farid, [[media:movid10.pdf | Optimal Scalable Video Multiplexing in Mobile Broadcast Networks]]<br /> <br /> * 17 May 10: Cameron, Reducing Energy Consumption in Online Network Games on Mobile Devices<br /> <br /> * 10 May 10: Cong, Latency Reduction in Online Network Games<br /> <br /> * 19 April 10: Shabnam, [[media:Svc-nc.ppt | Live P2P Streaming with Scalable Video Coding and Network Coding]]<br /> <br /> * 29 March 10: Jeff and Taher, [[media:AppAlgo.ppt | Approximation algorithms for Kernel Methods on Multi-core CPUs and GPUs]]<br /> <br /> * 15 March 10: Som, [http://www.cs.sfu.ca/~ssa121/personal/wimaxSVC.pdf Video Streaming over WiMAX]<br /> <br /> * 1 March 10: Farid, [[media:scalable_video_streaming_for_mobiletv.pptx | Scalable Video Streaming for MobileTV]]<br /> <br /> * 1 Feb 10: Ahmed, [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/hamza/talks/pCDN_SVC/pCDN_SVC.pdf Design of pCDN with Scalable Video Coding]<br /> <br /> * 18 Jan 10: Shabnam, P2P Streaming with Newtork Coding and Scalable Video Coding<br /> <br /> <br /> == Fall 2009==<br /> <br /> * 8 December 09: Yi, Video Streaming over Cooperative Wireless Networks<br /> <br /> * 10 Nov 09: Cheng, [[media:testbed.ppt | Design of a Mobile TV Testbed]]<br /> <br /> * 27 October 09: Yuanbin, Segment Scheduling in P2P Streaming Systems<br /> <br /> * 13 October 09: Ahmed, [[media:LTE.pdf | Long Term Evolution (LTE) - A Tutorial]]<br /> <br /> * 6 October 09: Cheng, [[media:Mm09.ppt | Statistical Multiplexing of VBR Video Streams]] (ACM MM 09 talk)<br /> <br /> * 22 September 09: Som, Video Streaming over WiMAX Networks<br /> <br /> * 8 September 09: Cong, Minimizing Round-Trip Time in Online Games<br /> <br /> <br /> == Summer 2009==<br /> <br /> * 18 August 09: Mohammad and Cong: 30 min each. Present their Directed Reading projects. <br /> <br /> * 14 July 09: Cheng, [[media:wimaxTV.pptx | Broadcasting Variable-Bit-Rate Videos in 802.16e-Like Mobile Networks]] <br /> <br /> * 7 July 09: Yi<br /> <br /> * 26 June 09: Ahmed <br /> <br /> * 5 June 09: '''Canceled''' (Mohamed attending NOSSDAV'09)<br /> <br /> * 29 May 09: Kianoosh, End-to-End Secure Delivery of Scalable Video Streams <br /> <br /> * 22 May 09: Cong, [[media:wimax.pptx| Multimedia Streaming over WiMAX Networks]]<br /> <br /> * 8 May 09: Kianoosh, Analysis of Authentication Schemes for Nonscalable Video Streams<br /> <br /> <br /> == Spring 2009 ==<br /> <br /> * 17 Apr 09: [[media:infocom09.pptx|Cheng (practice your infocom presentation)]]<br /> <br /> * 27 March 09: Andreas Berger, [[media:Nsl_vancouver.odp | Network-based Detection of SIP Bots]]<br /> <br /> * 27 Feb 09: Shabnam and Yuanbin<br /> <br /> * 23 Jan 09: Cheng (rehearse your PhD proposal) and Kianoosh</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4483 2011-06-03T03:40:26Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4482 2011-06-03T03:39:43Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be sent soon<br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4481 2011-06-03T03:31:16Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === Jun 03 ===<br /> * Proposed new metric to be used instead of the FN ratio (more powerful to compare different families and to pick the optimal value of k)<br /> * More analysis on the spectral hashing<br /> * Writing up the report with the results to be send soon<br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4463 2011-05-20T03:46:49Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> <br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this [https://cs-nsl-svn.cs.surrey.sfu.ca/cssvn/nsl-members/dameh/summer11/doc/RandomVsSpectral.pdf comparison examples] in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4462 2011-05-20T03:41:12Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and more powerful than the random projection, see this comparison examples in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4461 2011-05-20T03:36:06Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 19 ===<br /> * Spectral Hashing is Data dependent hashing and powerful than the random projection, see this comparison examples in the 2D.<br /> * Random Projection Hashing<br /> ** Method:<br /> *** Take random projections of data.<br /> *** Quantize the projections to hash value’s bits.<br /> ** Disadvantage:<br /> *** Data Independent Hashing.<br /> ** Advantage:<br /> *** Strong theoretical guarantees.<br /> *** Simple and fast to compute (linear time).<br /> ** Types:<br /> *** Euclidean distance: two parameters to vary that have the opposite affect (number of random vectors k and quantization width w).<br /> *** L1 distance: uncontrolled, as k increase error increase.<br /> *** Cosine distance: more controlled than L1 as k increase.<br /> * Data-Dependent Hashing<br /> **Advantage:<br /> *** Data-distribution dependent; powerful than Random Projection.<br /> ** Disadvantage:<br /> *** More complex to compute than Random Projection.<br /> ** Types:<br /> *** Spectral hashing:<br /> **** Compute PCA.<br /> **** Calculate the k smallest single-dimension analytical EigenFunctions.<br /> **** Threshold the analytical EigenFnction of zero to obtain hash value's bits.<br /> *** KernelLSH:<br /> **** The key idea is first embed the data into a lower space using the kernel G and then do LSH in the lower dimensional space.<br /> <br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4423 2011-05-09T00:36:58Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4422 2011-05-06T20:48:05Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:<br /> ****** Spectral Hashing: overcomes previous families problems<br /> ****** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4421 2011-05-06T20:44:56Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigenDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem: They assume data uniformly distributed solution:<br /> ******* Spectral Hashing: overcomes previous families problems<br /> ******* General Problem for random projection, it doesn’t take in account if data are in a kernel space, Solution:<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4420 2011-05-06T20:44:08Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigemDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection:<br /> ******* Hamming distance, Euclidean Distance, Cosine Distance<br /> ******* Problem: They assume data uniformly distributed solution:<br /> ******* Spectral Hashing: overcomes previous families problems<br /> ******* General Problem for random projection, it doesn’t take in account if data are in a kernel space, Solution:<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4419 2011-05-06T20:40:38Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigemDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> ****** Problem: They assume data uniformly distributed solution:<br /> ****** Spectral Hashing: overcomes previous families problmes<br /> ****** General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4418 2011-05-06T20:39:39Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods' gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigneDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> ****** Problem: They assume data uniformly distributed solution:<br /> ****** Spectral Hashing: overcomes previous families problmes<br /> ****** General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4417 2011-05-06T20:39:07Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigneDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> ****** Problem: They assume data uniformly distributed solution:<br /> ****** Spectral Hashing: overcomes previous families problmes<br /> ****** General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4416 2011-05-06T20:38:36Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigneDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> Problem: They assume data uniformly distributed solution:<br /> ****** Spectral Hashing: overcomes previous families problmes<br /> ****** General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4415 2011-05-06T20:37:29Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> ** Problem: kernel methods gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> ** Previous Work:<br /> *** Low rank matrix approximation:<br /> **** using EigneDecomposition: Optimal solution<br /> ***** Problem: requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> <br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> <br /> *** Efficient implementation for computing the kernel matrix:<br /> **** Using Spatial Indexing:<br /> ***** using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ***** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> ***** Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> <br /> **** Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.<br /> ***** LSH families :<br /> ****** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> Problem: They assume data uniformly distributed solution:<br /> ****** Spectral Hashing: overcomes previous families problmes<br /> ****** General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> <br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4414 2011-05-06T20:32:57Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> === May 5 ===<br /> * Recap <br /> * Problem: kernel methods gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> * Previous Work:<br /> ** Low rank matrix approximation:<br /> *** using EigneDecomposition: Optimal solution<br /> **** Problem: requires O(N^3) computation to construct the low rank matrix<br /> **** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> <br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> <br /> ** Efficient implementation for computing the kernel matrix:<br /> *** Using Spatial Indexing:<br /> using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> **** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> **** Problems: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> <br /> *** Using Spatial Hashing or Locality sensitive hashing:<br /> where the kernel function and the cluster methods works on the buckets individually.<br /> **** LSH families :<br /> ***** Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> Problem: They assume data uniformly distributed solution:<br /> ***** Spectral Hashing: overcomes previous families problmes<br /> <br /> General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ***** Kernelized LSH : Problem: more complex to compute<br /> <br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4413 2011-05-06T20:25:45Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> ** Recap:<br /> *** Problem: kernel methods gram matrix is O(N^2), which is computational and memory usage infeasible for large-scale datasets<br /> *** Previous Work:<br /> **** Low rank matrix approximation:<br /> ***** using EigneDecomposition: Optimal solution but requires O(N^3) computation to construct the low rank matrix<br /> ***** Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m &lt;&lt; N.<br /> <br /> ***** Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.<br /> <br /> **** Efficient implementation for computing the kernel matrix:<br /> ***** Using Spatial Indexing:<br /> using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.<br /> ****** Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel<br /> So we proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:<br /> ***** Using Spatial Hashing or Locality sensitive hashing:<br /> where the kernel function and the cluster methods works on the buckets individually.<br /> ****** LSH families :<br /> ******* Random projection: Hamming distance, Euclidean Distance, Cosine Distance<br /> Problem: They assume data uniformly distributed solution:<br /> ******* Spectral Hashing: overcomes previous families problmes<br /> <br /> General Problem for random projection, it' doesn’t take in account if data are in a kernel space, Solution<br /> ******* Kernelized LSH : Problem: more complex to compute<br /> <br /> ** In progress: Comparing different LSH families<br /> <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4412 2011-05-06T20:12:07Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> ** Recap:<br /> *** Problem: kerenl methods gram matrix is $O(N^2)$, which is computational and memory usage infiseable for large-scale datasets<br /> *** Prevoius Work:<br /> **** Low rank matrix approximation:<br /> ***** using EginDecomposition: Optimal solution but reqiures &lt;math&gt;O(N^3)&lt;/math&gt; computation to constuct the low rank matix<br /> ***** Solution: use Nysrom therorem to approximate the eigen decomposition of the matrix which reqiures &lt;math&gt;O(m^2N)&lt;/math&gt; where m &lt;&lt; N.<br /> <br /> ***** Problem: In this methods in despite of reduce the computation complexity still we need &lt;math&gt;O(N^2)&lt;/math&gt; to store the matrix, so the next method reduce both computation and memory.<br /> <br /> **** Efficient implementation for computing the kernel matrix:<br /> ***** Using Spatial Indexing:<br /> using Z-order, H-order, Td-tress and other spatial indexing techniques to order the points in the space and then use sliding window where the kernel function computed only between points in that wiondow.<br /> ****** Problems: reqiures &lt;math&gt;O(NlogN)&lt;/math&gt; as preprocessing to order the points, fails for very hight dimentional Data and hard to parallel<br /> So we proposed a method that works fine foy large-scale and highly dimentinla data, overcome or pervoius work drwobbacks, easy to parallel, reqiures linear time preprocessing and reduce the computation and memory usae down form quadratic to subquadratic:<br /> ***** Using Spatial Hashing or Locality sensitive hashing:<br /> where the kerenl function and the cluster methods works on the buckets indicusally.<br /> ****** LSH families :<br /> ******* Random projection<br /> ******** Hamming distance<br /> ******** Eclidean Distance<br /> ******** Cosine Distance<br /> ********* Problem: assumes data uniforly distubuted solution:<br /> ******** Spectral Hasing<br /> <br /> General Problem for random projection, it' doesnt take care of data comes in a kerenel space, Solution<br /> ******* Kerenalized LSH<br /> <br /> ** Recap: Comparing differnt LSH families<br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4411 2011-05-06T20:00:40Z

<p>Tdameh: </p> <hr /> <div>= Summer 2011 (TA) =<br /> * Research: Gram Matrix approximation<br /> ** Recap:<br /> *** Problem: kerenl methods gram matrix is &lt;math&gt;O(N^2)&lt;/math&gt;, which is computational and memory usage infiseable for large-scale datasets<br /> *** Prevoius Work:<br /> **** Low rank matrix approximation:<br /> ***** using EginDecomposition: Optimal solution but reqiures &lt;math&gt;O(N^3)&lt;/math&gt; computation to constuct the low rank matix<br /> ***** Solution: use Nysrom therorem to approximate the eigen decomposition of the matrix which reqiures &lt;math&gt;O(m^2N)&lt;/math&gt; where m &lt;&lt; N.<br /> <br /> ***** Problem: In this methods in despite of reduce the computation complexity still we need &lt;math&gt;O(N^2)&lt;/math&gt; to store the matrix, so the next method reduce both computation and memory.<br /> <br /> **** Efficient implementation for computing the kernel matrix:<br /> ***** Using Spatial Indexing:<br /> using Z-order, H-order, Td-tress and other spatial indexing techniques to order the points in the space and then use sliding window where the kernel function computed only between points in that wiondow.<br /> ****** Problems: reqiures &lt;math&gt;O(NlogN)&lt;/math&gt; as preprocessing to order the points, fails for very hight dimentional Data and hard to parallel<br /> So we proposed a method that works fine foy large-scale and highly dimentinla data, overcome or pervoius work drwobbacks, easy to parallel, reqiures linear time preprocessing and reduce the computation and memory usae down form quadratic to subquadratic:<br /> ***** Using Spatial Hashing or Locality sensitive hashing:<br /> where the kerenl function and the cluster methods works on the buckets indicusally.<br /> ****** LSH families :<br /> ******* Random projection<br /> ******** Hamming distance<br /> ******** Eclidean Distance<br /> ******** Cosine Distance<br /> ********* Problem: assumes data uniforly distubuted <br /> <br /> = Spring 2011 (TA/RA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4371 2011-04-15T20:11:59Z

<p>Tdameh: </p> <hr /> <div>= Spring 2011 (TA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> *research:<br /> **Gram matrix approximation<br /> **...<br /> <br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh https://nmsl.cs.sfu.ca/index.php?title=Private:progress-dameh&diff=4110 2011-01-25T10:00:07Z

<p>Tdameh: </p> <hr /> <div>= Spring 2011 (TA) =<br /> * Courses:<br /> **CMPT 885: Special Topics in Computer Architecture<br /> **CMPT 886: Special Topics in Operating Systems<br /> <br /> *research:<br /> **Gram matrix approximation<br /> **...<br /> <br /> === Jan 24 ===<br /> *reading and understanding previous work on Gram matrix approximation:<br /> ** Nyström Method [http://portal.acm.org/ft_gateway.cfm?id=1194916&amp;type=pdf&amp;CFID=5834693&amp;CFTOKEN=95499878] [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D118367961D24D13CCF1ACBC18F9BBDF?doi=10.1.1.18.7519&amp;rep=rep1&amp;type=pdf]<br /> <br /> <br /> <br /> = Fall 2010 (FAS-GF/RA) =<br /> * Courses:<br /> **CMPT 705: Design/Analysis Algorithms<br /> **CMPT 820: Multimedia Systems<br /> <br /> * Worked on Gram matrix approximation, High Performance/large scale application case studies<br /> <br /> <br /> = Summer 2010 (TA) =<br /> * Worked on large Scale Kernel methods<br /> <br /> <br /> = Spring 2010 (RA) =<br /> * Courses:<br /> **CMPT 768: Sound Synthesis<br /> <br /> * Worked on Locality sensitive hashing families and their applications and implementations</div>

Tdameh