Voronoi trees and clustering problems
References (10)
- et al.
Clustering analysis
Clustering methodologies in exploratory data analysis
- et al.
A data structure and an algorithm for the nearest point problem
IEEE Trans. Software Engng
(1983) An O(n4) algorithm to construct all Voronoi diagrams for K nearest neighbor searching in the euclidean plane
- et al.
Closest point problems
Cited by (43)
Supermetric search
2019, Information SystemsCitation Excerpt :The simplest such index structure is the Generalised Hyperplane Tree (GHT) [9]. Others include Bisector trees [10] and variants on them (e.g. Monotonous Bisector Trees [11] and Voronoi Trees [12]), the Metric Index [13], and the Spatial Approximation Tree [14]. This last has various derivatives, notably including the Dynamic SAT [15] and the Distal SAT (DiSAT) [3].
A heuristic approach to effective and efficient clustering on uncertain objects
2014, Knowledge-Based SystemsFully dynamic metric access methods based on hyperplane partitioning
2011, Information SystemsCitation Excerpt :The result is shown experimentally to be superior to the M-tree in various scenarios, thanks to the intrinsic advantage given by the nonoverlapping areas. To illustrate the generality of the technique, we apply it to another rigid structure, the Voronoi tree [3]. The result is competitive with the EGNAT in main memory.
Solving similarity joins and range queries in metric spaces with the list of twin clusters
2009, Journal of Discrete AlgorithmsCitation Excerpt :Each zone has a center c and stores both its radius rp and the bucket I of internal objects, that is, the objects inside the zone. In metric spaces, a natural approach to solve this problem consists in indexing one or both sets independently (by using any from the plethora of metric indices [3,4,7,8,10–12,14,15,17,21,27,36–38,40,41,44,47–50], most of them compiled in [13,26,46,51]), and then solving range queries for all the involved elements over the indexed sets. In fact, this is the strategy proposed in [19], where the authors use the D-index [18] in order to solve similarity self joins.
Indexing Metric Spaces for Exact Similarity Search
2022, ACM Computing Surveys