图 书 馆
精确的最近邻搜索的随机分配树Randomized partition trees for exact nearest neighbor search |
|
| 课程网址: | http://videolectures.net/colt2013_dasgupta_trees/ |
| 主讲教师: | Sanjoy Dasgupta |
| 开课单位: | 加州大学圣地亚哥分校 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | The k-d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and overlapping cells, have proved to be successful in practice. We analyze three such schemes. We show that the probability that they fail to find the nearest neighbor, for any data set and any query point, is directly related to a simple potential function that captures the difficulty of the point configuration. We then bound this potential function in two situations of interest: the first, when data come from a doubling measure, and the second, when the data are documents from a topic model. |
| 关 键 词: | 计算机科学; 机器学习; 最近邻搜索 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-12-17：lxf |
| 阅读次数: | 19 |