- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Graduate Research /
- Computational Geometry in High-Dimensional Spaces
Open Collections
UBC Graduate Research
Computational Geometry in High-Dimensional Spaces Liu, Paul
Abstract
In this project, we provide a review of efficient solutions to a few high-dimensional CG problems, with particular focus on the problem of nearest neighbour search. For the problems we examine, the general approach will be to either reduce the dimension (using the JL transform) or to preprocess the data and group together points that are close together (using locality sensitive hashing). Finally, we apply these techniques to a relaxed version of the unit disc cover problem, an NP-Hard facility location problem that has only been effectively approximated in the low-dimensional case.
Item Metadata
| Title |
Computational Geometry in High-Dimensional Spaces
|
| Creator | |
| Date Issued |
2015-09
|
| Description |
In this project, we provide a review of efficient solutions to a few high-dimensional CG problems, with particular focus on the problem of nearest neighbour search. For the problems we examine, the general approach will be to either reduce the dimension (using the JL transform) or to preprocess the data and group together points that are close together (using locality sensitive hashing). Finally, we apply these techniques to a relaxed version of the unit disc cover problem, an NP-Hard facility location problem that has only been effectively approximated in the low-dimensional case.
|
| Subject | |
| Genre | |
| Type | |
| Language |
eng
|
| Series | |
| Date Available |
2015-10-24
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution 2.5 Canada
|
| DOI |
10.14288/1.0103603
|
| URI | |
| Affiliation | |
| Campus | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Graduate
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution 2.5 Canada