Accelerated clustering through locality-sensitive hashing
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.B.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/77534 |
| _version_ | 1811079092943978496 |
|---|---|
| author | Kishore, Shaunak |
| author2 | Jonathan A. Kelner. |
| author_facet | Jonathan A. Kelner. Kishore, Shaunak |
| author_sort | Kishore, Shaunak |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.B.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012. |
| first_indexed | 2024-09-23T11:09:55Z |
| format | Thesis |
| id | mit-1721.1/77534 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:09:55Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/775342019-04-10T21:54:36Z Accelerated clustering through locality-sensitive hashing Kishore, Shaunak Jonathan A. Kelner. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Mathematics. Electrical Engineering and Computer Science. Mathematics. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.B.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012. Cataloged from PDF version of thesis. Includes bibliographical references (p. 18). We obtain improved running times for two algorithms for clustering data: the expectation-maximization (EM) algorithm and Lloyd's algorithm. The EM algorithm is a heuristic for finding a mixture of k normal distributions in Rd that maximizes the probability of drawing n given data points. Lloyd's algorithm is a special case of this algorithm in which the covariance matrix of each normally-distributed component is required to be the identity. We consider versions of these algorithms where the number of mixture components is inferred by assuming a Dirichlet process as a generative model. The separation probability of this process, [alpha], is typically a small constant. We speed up each iteration of the EM algorithm from O(nd2k) to O(ndk log 3(k/a))+nd 2 ) time and each iteration of Lloyd's algorithm from O(ndk) to O(nd(k/a). 39) time. by Shaunak Kishore. S.B. M.Eng. 2013-03-01T15:27:03Z 2013-03-01T15:27:03Z 2012 2012 Thesis http://hdl.handle.net/1721.1/77534 826515141 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 18 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Mathematics. Kishore, Shaunak Accelerated clustering through locality-sensitive hashing |
| title | Accelerated clustering through locality-sensitive hashing |
| title_full | Accelerated clustering through locality-sensitive hashing |
| title_fullStr | Accelerated clustering through locality-sensitive hashing |
| title_full_unstemmed | Accelerated clustering through locality-sensitive hashing |
| title_short | Accelerated clustering through locality-sensitive hashing |
| title_sort | accelerated clustering through locality sensitive hashing |
| topic | Electrical Engineering and Computer Science. Mathematics. |
| url | http://hdl.handle.net/1721.1/77534 |
| work_keys_str_mv | AT kishoreshaunak acceleratedclusteringthroughlocalitysensitivehashing |