Foundations of multidimensional and metric data structures

By Hanan Samet. 2006

1,623 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

OctNetFusion: Learning Depth Fusion from Data (2017, methodology): “A notable exception is the OctNet approach of Riegler et al. [34] which takes advantage of the sparsity of 3D volumetric models using an octree representation [35], enabling deep learning at resolutions of 256 3 voxels and beyond.”
Practical and Optimal LSH for Angular Distance (2015, methodology): “There is a wide range of algorithms for nearest neighbor search based on techniques such as space partitioning with indexing, as well as dimension reduction or sketching [5].”
Recognition and retrieval of mathematical expressions (2011, methodology): “Spatial data structures used by these three decomposition approaches, respectively , include k-d trees, R-trees, and M-trees [126].”
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation (2011, methodology): “For example, tree-based methods [36] can compute accurate re-sults eﬃciently on low dimensional datasets only.”
A public turbulence database cluster and applications to study Lagrangian evolution of velocity increments in turbulence (2008, methodology): “In our system, the data are indexed according to the Z-order (also known as Morton order) [32], for it maintains fairly good locality and is simple to implement and calculate.”
Near neighbor searching with K nearest references (2015, background): “This issue is well documented in the literature, for example by Pestov [43–46], Volnyansky and Pestov [55], Shaft and Ramakrishnan [48], Indyk [30], Samet [47], Hjaltason and Samet [28], Chavez et al.”
Navigating K-Nearest Neighbor Graphs to Solve Nearest Neighbor Searches (2010, methodology): “A nearest neighbor query is deﬁned as NN ( q ) = arg min x ∈ S d ( x, q ), and can be solved by successive applications of range query ( q, r ) d = { x ∈ S | d ( q, x ) ≤ r } in a hierarchical index with the algorithm described in [2].”
Differentially Private Spatial Decompositions (2011, background): “Let D1,D2 be two neighboring datasets, i.e., D1 and D2 differ in only one tuple t, written as ‖D1−D2‖ = 1.”
The Algorithm Design Manual (2020, background): “Samet [Sam06] is the best reference on kd-trees and other spatial data structures.”
A neural algorithm for a fundamental computing problem (2017, methodology): “If the Web contained many images, but each image was represented by a low-dimensional vector (e.g., 10 or 20 features), then space partitioning methods, such as kd -trees ( 20 ), would similarly sufﬁce.”
Voronoi grids conforming to 3D structural features (2014, methodology): “The algorithm can be decomposed in three steps: – The bounding box of the fine cell is computed and the closer seed for each corner of the box is retrieved through a kd-tree algorithm [19].”
Learning to Prune in Metric and Non-Metric Spaces (2013, background): “As dimensionality increases, the filtering efficiency of space-partitioning methods decreases rapidly, which is known as the “curse of dimensionality” [30].”
Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, background): “, the triangle inequality [35, 45] or its generalization for non-metric spaces [21].”
Isogeometric Collocation: Cost Comparison with Galerkin Methods and Extension to Adaptive Hierarchical NURBS Discretizations (2013, background): “Efficient implementation of hierarchical refinement A considerable advantage of hierarchical refinement in the present form is its straightforward and efficient implementation through quadtrees and octrees [75], which provide a natural way to decompose and organize spatial data according to differen”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “Recently neighborhood graph search has been attracting a lot of interests [1, 2, 5, 15, 31, 32, 38] because of its simplicity and good search performance.”