Publications related to K-d tree

Cluster-and-Conquer: When Randomness Meets Graph Locality

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Ola Nils Anders Svensson, Adam Teodor Polak, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Xinrui Jia

We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data point ...

2021

Smaller, Faster & Lighter KNN Graph Constructions

Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas

We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard’s index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and s ...

2020

Memory of Motion for Warm-Starting Trajectory Optimization

Sylvain Calinon, Emmanuel Pignat, Antonio Paolillo, Teguh Santoso Lembono

Trajectory optimization for motion planning requires good initial guesses to obtain good performance. In our proposed approach, we build a memory of motion based on a database of robot paths to provide good initial guesses. The memory of motion relies on f ...

2020

A memory of motion for visual predictive control tasks

Sylvain Calinon, Antonio Paolillo, Teguh Santoso Lembono

This paper addresses the problem of efficiently achieving visual predictive control tasks. To this end, a memory of motion, containing a set of trajectories built off-line, is used for leveraging precomputation and dealing with difficult visual tasks. Stan ...

2020

Fingerprinting Big Data: The Case of KNN Graph Construction

Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas

We propose fingerprinting, a new technique that consists in constructing compact, fast-to-compute and privacy-preserving binary representations of datasets. We illustrate the effectiveness of our approach on the emblematic big data problem of K-Nearest-Nei ...

2019

Taster: Self-Tuning, Elastic and Online Approximate Query Processing

Anastasia Ailamaki, Raja Appuswamy, Matthaios Alexandros Olma, Odysseas Papapetrou

Current Approximate Query Processing (AQP) engines are far from silver-bullet solutions, as they adopt several static design decisions that target specific workloads and deployment scenarios. Offline AQP engines target deployments with large storage budget ...

IEEE2019

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Akhil Arora, Arnab Bhattacharya, Piyush Kumar

Nearest neighbor searching of large databases in high-dimensional spaces is inherently difficult due to the curse of dimensionality. A flavor of approximation is, therefore, necessary to practically solve the problem of nearest neighbor search. In this pap ...

ASSOC COMPUTING MACHINERY2018

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Anastasia Ailamaki, Darius Sidlauskas, Eleni Tzirita Zacharatou

The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests ...

IEEE2018

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

K-d tree

Cluster-and-Conquer: When Randomness Meets Graph Locality

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Smaller, Faster & Lighter KNN Graph Constructions

Memory of Motion for Warm-Starting Trajectory Optimization

A memory of motion for visual predictive control tasks

Fingerprinting Big Data: The Case of KNN Graph Construction

Taster: Self-Tuning, Elastic and Online Approximate Query Processing

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Graph Chatbot

Chat with Graph Search

Cluster-and-Conquer: When Randomness Meets Graph Locality

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Taster: Self-Tuning, Elastic and Online Approximate Query Processing

Memory of Motion for Warm-Starting Trajectory Optimization

A memory of motion for visual predictive control tasks

Fingerprinting Big Data: The Case of KNN Graph Construction

Smaller, Faster & Lighter KNN Graph Constructions

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes