Related Experiment Video
Updated: Jun 13, 2026
05:12
ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
Published on: January 16, 2019
Fast construction of k-nearest neighbor graphs for point clouds
1Department of Computer Science, Florida State University, Tallahassee, FL 32306, USA. miconnor@cs.fsu.edu
Summary
This study introduces a faster parallel algorithm for k-nearest neighbor graph construction using Morton ordering. The method improves efficiency, reduces space usage, and handles large datasets effectively on multicore machines.
Area of Science:
- Computer Science
- Data Science
- Algorithm Design
Background:
- K-nearest neighbor (KNN) graph construction is fundamental in machine learning and data analysis.
- Existing parallel algorithms face challenges with efficiency, scalability, and resource utilization.
Purpose of the Study:
- To develop a novel parallel algorithm for efficient k-nearest neighbor graph construction.
- To leverage Morton ordering for improved performance on multicore architectures.
Main Methods:
- Implementation of a parallel algorithm utilizing Morton ordering for point set representation.
- Experimental evaluation on multicore machines comparing performance against existing methods.
Main Results:
- Demonstrated faster k-nearest neighbor graph construction compared to existing approaches.
- Achieved reduced space usage and enhanced cache efficiency.
- Showcased scalability for large datasets and ease of parallel implementation.
Conclusions:
- The proposed Morton ordering-based parallel algorithm offers significant advantages for k-nearest neighbor graph construction.
- This method provides a practical and efficient solution for handling large-scale data on modern multicore systems.
Related Concept Videos
01:10Design Example: Measuring Distance Between Two Points with Obstructions
When measuring distances in areas with physical obstructions, such as a lake in a field, surveyors must employ techniques to calculate accurate lengths without direct line measurements. One effective method is the offset technique, which allows for precise distance estimation over inaccessible stretches.In this scenario, a surveyor must measure a side of an area that crosses a lake. Since the measuring tape cannot span the lake, the surveyor begins by establishing a baseline that aligns with...
01:10Vector Algebra: Graphical Method
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
01:20Cluster Sampling Method
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
01:29Distance Problem
When an object's velocity changes over time, the total distance traveled can be determined by summing small displacement intervals over short increments. This approach approximates the true distance through numerical summation and the use of integral calculus. An estimate of the total displacement can be obtained by measuring velocity at regular intervals and multiplying each value by the corresponding time step.If a runner accelerates over the first three seconds of a race, speed measurements...
01:27Graphs of Two-Variable Functions
A weather map provides a practical example of a function of two variables. Across a wide region such as the United States, temperatures vary from one location to another. Each location can be identified by two geographic coordinates: longitude and latitude. Since a single temperature value is assigned to each coordinate pair, the situation can be represented mathematically as a function with two inputs and one output.In mathematical notation, longitude and latitude can be labeled as x and y,...
01:29Vectors in 2D: Problem Solving
A plane traveling due north at 180 km/h in still air was found to be 80 km off-course after 30 minutes, deviating approximately 5 degrees east of north. This deviation means the influence of a crosswind alters the plane’s intended trajectory. The actual ground path formed a diagonal, suggesting that the aircraft’s effective ground speed was reduced to 160 km/h and directed slightly to the east due to the wind.By analyzing the displacement from the intended path, the velocity contributed by the...