Cbcb:Pop-Lab:Mohammad-Report: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Bounds for embedding Levenstein distance into metric spaces | Bounds for embedding Levenstein distance into metric spaces | ||
*[http://portal.acm.org/citation.cfm?id=1109557.1109669 Lower bound of <math>\Omega(\log n)</math> where n is number of points | *[http://portal.acm.org/citation.cfm?id=1109557.1109669 Lower bound of <math>\Omega(\log n)</math> where n is number of points] | ||
*[http://portal.acm.org/citation.cfm?id=1284322 Upper bound of <math>2^{O(\sqrt(log d log log d))}</math> where d is dimension (i.e. length) | *[http://portal.acm.org/citation.cfm?id=1284322 Upper bound of <math>2^{O(\sqrt(log d log log d))}</math> where d is dimension (i.e. length)] | ||
FFT and random projections | FFT and random projections | ||
*[https://wiki.umiacs.umd.edu/cbcb/images/f/f6/Projection.pdf Presentation] | *[https://wiki.umiacs.umd.edu/cbcb/images/f/f6/Projection.pdf Presentation] | ||
*[https://wiki.umiacs.umd.edu/cbcb/images/1/13/Fft2.pdf Writeup] | *[https://wiki.umiacs.umd.edu/cbcb/images/1/13/Fft2.pdf Writeup] | ||
Revision as of 17:39, 11 March 2009
Bounds for embedding Levenstein distance into metric spaces
- Lower bound of <math>\Omega(\log n)</math> where n is number of points
- Upper bound of <math>2^{O(\sqrt(log d log log d))}</math> where d is dimension (i.e. length)
FFT and random projections