K-Nearest Neighbors Problem for Moderately High Dimensional Spaces

**Background:**

HEEDS is Siemens software which does “design space exploration” for engineering-design problems. The problem has a design space, which is defined by the design parameters that can be varied. The number of design parameters is usually less than 10, sometimes it can be much more than that.

HEEDS search algorithms vary the design parameters to create trial designs and then simulate their performance with appropriate analysis tools. A common goal is optimizing the dimensions or material properties of a structure to get the best tradeoff between strength and cost. The number of trial designs can be anywhere from a few dozen to 10’s of thousands. As the search accumulates trial designs, HEEDS identify interesting designs and then finds nearby designs from among those that it has already analyzed.

This is a k-nearest neighbors problem. As HEEDS users take on higher-dimensional problems and create larger design sets, the search starts to encounter performance issues. The execution time of a naïve implementation increases exponentially with problem size. There are more sophisticated algorithms available for 2D and 3D spaces and there is some work in very high dimensional problems (text, image recognition) but not as much in the range of our problems.

**About Project: **

The goal of this project is to collect and evaluate KNN search implementations to determine which, if any, offer lower complexity compared to simple approaches. R-tree and X-tree are possible techniques to test, for example.

The problem size of interest is roughly 25-50 dimensions, 50,000-100,000 points, and 10 < k < 500. Example data sets can be provided.

Review available algorithms from the open-source community, select those that seem appropriate for this size problem, and test them to determine how their speed increases as the problem size increases. Compare to a naïve approach.

**Deliverables: **

- Report outlining the testing process, techniques tested, and measured performance.
- Recommendations on most promising techniques to explore further.
- Code that was written for the project to execute the testing.

- About the Program
- Admission Requirements
- Industrial Projects and Partners
- Graduate Placements Statistics
- MSIM Testimonials
- MSIM Student Handbook
- Frequently Asked Questions for MSIM Applicants

For any additional questions regarding the program curriculum and/or the extension deadline for the application to the MSIM program, contact us at msim@math.msu.edu

Department of Mathematics

Michigan State University

619 Red Cedar Road

C212 Wells Hall

East Lansing, MI 48824

Phone: (517) 353-0844

Fax: (517) 432-1562

- People
- All
- Regular Faculty
- Postdocs
- Fixed Term/Visiting Faculty
- Specialists and Instructors
- Adjunct Faculty
- Emeriti
- Graduate Students
- Teaching Assistants
- Staff
- Administration
- Diversity, Equity, Inclusiveness
- Faculty Honors

- Research
- Faculty Research Interests
- Seminars
- Seminars by Week
- Topology RTG
- MCIAM
- MathSciNet
- Institute of Mathematical Physics
- Math Library
- Phillips Lecture

- Undergraduate
- Undergraduate Program
- Class Pages
- Student Portal
- Webwork
- Math Learning Center
- Actuarial Science
- Advising Information
- Override Request
- Math Placement Service
- Herzog Competition
- Scholarships
- Exchange Program
- Sample Finals
- Multicultural Center Feasibility