Search

Ray tracing is a rendering technique that is highly praised for its realism and image quality. Nonetheless, this is a computationally intensive task that is slow compared to other rendering techniques like rasterization. Bounding Volume Hierarchy (BVH) is a primitive subdivision acceleration mechanism that is the mainly used method for accelerating ray tracing in modern solutions. It is regarded as having better performance against other acceleration methods. Another well-known technique is Kd-Trees that uses binary space partitioning to adaptively subdivide space with planes. In this research, we made an up-to-date evaluation of both acceleration structures, using state-of-the-art BVH and Kd-Trees algorithms implemented in C, and found out that the Kd-Trees acceleration structure provided better performance in all defined scenarios on a modern x86 CPU architecture.

This paper considers the problem of exact accelerated algorithms for the K-means clustering of low-dimensional data on modern multi-core systems. A version of the filtering algorithm parallelized using the OpenMP (Open Multi-Processing) standard is proposed. The algorithm employs a kd-tree structure to skip some unnecessary calculations between cluster centroids and feature vectors. In our approach, both the kd-tree construction and the iterations of the K-means are parallelized using the OpenMP tasking mechanism. A new task is created for a recursive call performed during kd-tree construction and traversal. The tasks are executed in parallel by the cores of a shared-memory system. In computational experiments, we evaluated the parallel efficiency of our approach and compared its performance to the parallel Lloyd’s method, a GPU (Graphics Processing Unit) formulation of the K-means algorithm, and two parallel triangle inequality-based algorithms intended for low-dimensional data. The evaluation was performed on six synthetic datasets from two distributions and seven real-life datasets. The experiments, executed on a 24-core system, indicated that our version of the filtering algorithm had satisfactory or high parallel efficiency. Its runtime was much shorter than those of competing algorithms. However, the advantage of the parallel filtering algorithm decreased rapidly as the dimension of data increased.

Extracting useful information from astronomical observations represents one of the most challenging tasks of data exploration. This is largely due to the volume of the data acquired using advanced observational tools. While other challenges typical for the class of big data problems (like data variety) are also present, the size of datasets represents the most significant obstacle in visualization and subsequent analysis. This paper studies an efficient data condensation algorithm aimed at providing its compact representation. It is based on fast nearest neighbor calculation using tree structures and parallel processing. In addition to that, the possibility of using approximate identification of neighbors, to even further improve the algorithm time performance, is also evaluated. The properties of the proposed approach, both in terms of performance and condensation quality, are experimentally assessed on astronomical datasets related to the GAIA mission. It is concluded that the introduced technique might serve as a scalable method of alleviating the problem of the dataset size.

Bayesian inference using Gaussian processes on large datasets have been studied extensively over the past few years. However, little attention has been given on how to apply these on a high resolution input space. By approximating the set of test points (where we want to make predictions, not the set of training points in the dataset) by a kd-tree, a multi-resolution data structure arises that allows for considerable gains in performance and memory usage without a significant loss of accuracy. In this paper, we study the feasibility and efficiency of constructing and using such a kd-tree in Gaussian process regression. We propose a cut-off rule that is easy to interpret and to tune. We show our findings on generated toy data in a 3D point cloud and a simulated 2D vibrometry example. This survey is beneficial for researchers that are working on a high resolution input space. The kd-tree approximation outperforms the naïve Gaussian process implementation in all experiments.

Sample Entropy is the most popular definition of entropy and is widely used as a measure of the regularity/complexity of a time series. On the other hand, it is a computationally expensive method which may require a large amount of time when used in long series or with a large number of signals. The computationally intensive part is the similarity check between points in m dimensional space. In this paper, we propose new algorithms or extend already proposed ones, aiming to compute Sample Entropy quickly. All algorithms return exactly the same value for Sample Entropy, and no approximation techniques are used. We compare and evaluate them using cardiac inter-beat (RR) time series. We investigate three algorithms. The first one is an extension of the kd-trees algorithm, customized for Sample Entropy. The second one is an extension of an algorithm initially proposed for Approximate Entropy, again customized for Sample Entropy, but also improved to present even faster results. The last one is a completely new algorithm, presenting the fastest execution times for specific values of m, r, time series length, and signal characteristics. These algorithms are compared with the straightforward implementation, directly resulting from the definition of Sample Entropy, in order to give a clear image of the speedups achieved. All algorithms assume the classical approach to the metric, in which the maximum norm is used. The key idea of the two last suggested algorithms is to avoid unnecessary comparisons by detecting them early. We use the term unnecessary to refer to those comparisons for which we know a priori that they will fail at the similarity check. The number of avoided comparisons is proved to be very large, resulting in an analogous large reduction of execution time, making them the fastest algorithms available today for the computation of Sample Entropy. [ABSTRACT FROM AUTHOR]

Sample Entropy is the most popular definition of entropy and is widely used as a measure of the regularity/complexity of a time series. On the other hand, it is a computationally expensive method which may require a large amount of time when used in long series or with a large number of signals. The computationally intensive part is the similarity check between points in m dimensional space. In this paper, we propose new algorithms or extend already proposed ones, aiming to compute Sample Entropy quickly. All algorithms return exactly the same value for Sample Entropy, and no approximation techniques are used. We compare and evaluate them using cardiac inter-beat (RR) time series. We investigate three algorithms. The first one is an extension of the k d -trees algorithm, customized for Sample Entropy. The second one is an extension of an algorithm initially proposed for Approximate Entropy, again customized for Sample Entropy, but also improved to present even faster results. The last one is a completely new algorithm, presenting the fastest execution times for specific values of m, r, time series length, and signal characteristics. These algorithms are compared with the straightforward implementation, directly resulting from the definition of Sample Entropy, in order to give a clear image of the speedups achieved. All algorithms assume the classical approach to the metric, in which the maximum norm is used. The key idea of the two last suggested algorithms is to avoid unnecessary comparisons by detecting them early. We use the term unnecessary to refer to those comparisons for which we know a priori that they will fail at the similarity check. The number of avoided comparisons is proved to be very large, resulting in an analogous large reduction of execution time, making them the fastest algorithms available today for the computation of Sample Entropy.

We present the first parallel on-demand spatial hierarchy construction algorithm targeting ray tracing on many-core processors such as GPUs. The method performs simultaneous ray traversal and spatial hierarchy construction focused on the parts of the data structure being traversed. The method is based on a versatile framework built around a task pool and runs entirely on the GPU. We show that the on-demand construction can improve rendering times compared to full hierarchy construction. We evaluate our method on both object (BVH) and space (kd-tree) subdivision data structures and compare them mutually. The on-demand method is particularly beneficial for rendering large scenes with high occlusion. We also present SAH kd-tree builder that outperforms previous state-of-the-art builders running on the GPU. [ABSTRACT FROM PUBLISHER]

Ray-primitive intersection tests are the most important operations in ray tracing. The ray-box culling algorithm was presented to accelerate these intersection tests on grid structures, but this algorithm has not been widely used due to the poor ray traversal performance of the grid structures themselves. In this paper, we demonstrate how to apply this algorithm to tree structures and investigate its efficiency in terms of tree construction time and ray traversal performance. Experimental results show that our approach achieves up to 1.15x faster ray tracing performance and up to 1.22x faster total rendering performance, including tree construction and ray tracing. [ABSTRACT FROM AUTHOR]

Abstract: Estimating the disclosure risk of a Statistical Disclosure Control (SDC) protection method by means of (distance-based) record linkage techniques is a very popular approach to analyze the privacy level offered by such a method. When databases are very large, some particular record linkage techniques such as blocking or partitioning are usually applied to make this process reasonably efficient. However, in this case the record linkage process is not exact, which means that the disclosure risk of a SDC protection method may be underestimated. In this paper we propose the use of kd-trees techniques to apply exact yet very efficient record linkage when (protected) datasets are very large. We describe some experiments showing that this approach achieves better results, in terms of both accuracy and running time, than more classical approaches such as record linkage based on a sliding window. We also discuss and experiment on the use of these techniques not to link a whole protected record with its original one, but just to guess the value of some confidential attribute(s) of the record(s). This fact leads to concepts such as k-neighbor l-diversity or k-neighbor p-sensitivity, a generalization (to any SDC protection method) of l-diversity or p-sensitivity, which have been defined for SDC protection methods ensuring k-anonymity, such as microaggregation. [Copyright &y& Elsevier]

Abstract: A three-body potential function can account for interactions among triples of particles which are uncaptured by pairwise interaction functions such as Coulombic or Lennard-Jones potentials. Likewise, a multibody potential of order n can account for interactions among n-tuples of particles uncaptured by interaction functions of lower orders. To date, the computation of multibody potential functions for a large number of particles has not been possible due to its scaling cost. In this paper we describe a fast tree-code for efficiently approximating multibody potentials that can be factorized as products of functions of pairwise distances. For the first time, we show how to derive a Barnes–Hut type algorithm for handling interactions among more than two particles. Our algorithm uses two approximation schemes: (1) a deterministic series expansion-based method; (2) a Monte Carlo-based approximation based on the central limit theorem. Our approach guarantees a user-specified bound on the absolute or relative error in the computed potential with an asymptotic probability guarantee. We provide speedup results on a three-body dispersion potential, the Axilrod–Teller potential. [Copyright &y& Elsevier]

This paper presents a novel tabulation strategy for the adaptive numerical integration of chemical kinetics using the computational singular perturbation (CSP) method. The strategy stores and reuses CSP quantities required to filter out fast dissipative processes, resulting in a non-stiff chemical source term. In particular, non-parametric regression on low-dimensional slow invariant manifolds (SIMs) in the chemical state space is used to approximate the CSP vectors spanning the fast chemical subspace and the associated fast chemical time-scales. The relevant manifold and its dimension varies depending on the local number of exhausted modes at every location in the chemical state space. Multiple manifolds are therefore tabulated, corresponding to different numbers of exhausted modes (dimensions) and associated radical species. Non-parametric representations are inherently adaptive, and rely on efficient approximate-nearest-neighbor queries. As the CSP information is only a function of the non-radical species in the system and has relatively small gradients in the chemical state space, tabulation occurs in a lower-dimensional state space and at a relatively coarse level, thereby improving scalability to larger chemical mechanisms. The approach is demonstrated on the simulation of homogeneous constant pressure H2–air and CH4–air ignition, over a range of initial conditions. For CH4–air, results are shown that outperform direct implicit integration of the stiff chemical kinetics while maintaining good accuracy. [ABSTRACT FROM PUBLISHER]

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of n points in Rd. We show that a rank-based kd-tree, like an ordinary kd-tree, supports orthogonal range queries in O(n1-1/d + k) time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the kinetic data structure (KDS) processes O(n²) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log n) time, and each point is involved in O(1) certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees, for sets of points in R². Rank-based longest-side kd-trees can be kinetized efficiently as well, and like longest-side kd-trees, they support ϵ-approximate nearest-neighbor, ϵ-approximate farthest-neighbor, and ϵ-approximate range queries with convex ranges in O((1/ϵ) log² n) time. The KDS processes O(n³ log n) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log² n) time, and each point is involved in O(log n) certificates. [ABSTRACT FROM AUTHOR]

Similarity search has a growing usefulness in a range of applications like time series, image and multimedia databases, biological data, and so on. These searches are implemented by means of neighbour queries in the multidimensional spaces where the data resides. Faced with a large volume of data, it becomes imperative the use of indexing methods with specific algorithms capable of reducing the queries response time. The balanced indexing structures based on kd-trees generate a partition of multidimensional space in holey regions that complicate the underlying topology, hindering the calculation of distances between points and regions. In this paper, we introduce a nearest neighbour search algorithm that exploits this topology for efficiency. The experimental results that are included in this study support the usefulness of the proposed method. [ABSTRACT FROM PUBLISHER]

In this study, we explore the utility of data structures that facilitate efficient nearest neighbor searches for application in multi-source forest attribute prediction. Our trials suggest that the kd-tree in combination with exact search algorithms can greatly reduce nearest neighbor search time. Further, given our trial data, we found that enormous gain in search time efficiency, afforded by approximate nearest neighbor search algorithms, does not result in compromised kNN prediction. We conclude that by using the kd-tree, or similar data structure, and efficient exact or approximate search algorithms, the kNN method, and variants, are useful tools for mapping large geographic areas at a fine spatial resolution. [Copyright &y& Elsevier]

Clustering is central to many image processing and remote sensing applications. ISODATA is one of the most popular and widely used clustering methods in geoscience applications, but it can run slowly, particularly with large data sets. We present a more efficient approach to ISODATA clustering, which achieves better running times by storing the points in a kd-tree and through a modification of the way in which the algorithm estimates the dispersion of each cluster. We also present an approximate version of the algorithm which allows the user to further improve the running time, at the expense of lower fidelity in computing the nearest cluster center to each point. We provide both theoretical and empirical justification that our modified approach produces clusterings that are very similar to those produced by the standard ISODATA approach. We also provide empirical studies on both synthetic data and remotely sensed Landsat and MODIS images that show that our approach has significantly lower running times. [ABSTRACT FROM AUTHOR]

The cost of nearest-neighbor (NN) calls is one of the bottle-necks in the performance of sampling-based motion-planning algorithms. Therefore, it is crucial to develop efficient techniques for NN searching in configuration spaces arising in motion planning. In this paper, we present and implement an algorithm for performing NN queries in Cartesian products of R, S¹, and RP³, the most common topological spaces in the context of motion planning. Our approach extends the algorithm based on kd-trees, called ANN, developed by Arya and Mount for Euclidean spaces. We prove the correctness of the algorithm and illustrate substantial performance improvement over the brute-force approach and several existing NN pack- ages developed for general metric spaces. Our experimental results demonstrate a clear advantage of using the proposed method for both probabilistic roadmaps and rapidly exploring random trees. [ABSTRACT FROM AUTHOR]

Motivated by the poor performance (linear complexity) of the EM algorithm in clustering large data sets, and inspired by the successful accelerated versions of related algorithms like k-means, we derive an accelerated variant of the EM algorithm for Gaussian mixtures that: (1) offers speedups that are at least linear in the number of data points, (2) ensures convergence by strictly increasing a lower bound on the data log-likelihood in each learning step, and (3) allows ample freedom in the design of other accelerated variants. We also derive a similar accelerated algorithm for greedy mixture learning, where very satisfactory results are obtained. The core idea is to define a lower bound on the data log-likelihood based on a grouping of data points. The bound is maximized by computing in turn (i) optimal assignments of groups of data points to the mixture components, and (ii) optimal re-estimation of the model parameters based on average sufficient statistics computed over groups of data points. The proposed method naturally generalizes to mixtures of other members of the exponential family. Experimental results show the potential of the proposed method over other state-of-the-art acceleration techniques. [ABSTRACT FROM AUTHOR]

Due to growing concerns about the privacy of personal information, organizations that use their customers' records in data mining activities are forced to take actions to protect the privacy of the individuals. A frequently used disclosure protection method is data perturbation. When used for data mining, it is desirable that perturbation preserves statistical relationships between attributes, while providing adequate protection for individual confidential data. To achieve this goal, we propose a kd-tree based perturbation method, which recursively partitions a data set into smaller subsets such that data records within each subset are more homogeneous after each partition. The confidential data in each final subset are then perturbed using the subset average. An experimental study is conducted to show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Parti-game is a new algorithm for learning feasible trajectories to goal regions in high dimensional continuous state-spaces. In high dimensions it is essential that neither planning nor exploration occurs uniformly over a state-space. Parti-game maintains a decision-tree partitioning of state-space and applies techniques from game-theory and computational geometry to efficiently and adaptively concentrate high resolution only on critical areas. The current version of the algorithm is designed to find feasible paths or trajectories to goal regions in high dimensional spaces. Future versions will be designed to find a solution that optimizes a real-valued criterion. Many simulated problems have been tested, ranging from two-dimensional to nine-dimensional state-spaces, including mazes, path planning, non-linear dynamics, and planar snake robots in restricted spaces. In all cases, a good solution is found in less than ten trials and a few minutes. [ABSTRACT FROM AUTHOR]

Bayesian inference using Gaussian processes on large datasets have been studied extensively over the past few years. However, little attention has been given on how to apply these on a high resolution input space. By approximating the set of test points (where we want to make predictions, not the set of training points in the dataset) by a kd-tree, a multi-resolution data structure arises that allows for considerable gains in performance and memory usage without a significant loss of accuracy. In this paper, we study the feasibility and efficiency of constructing and using such a kd-tree in Gaussian process regression. We propose a cut-off rule that is easy to interpret and to tune. We show our findings on generated toy data in a 3D point cloud and a simulated 2D vibrometry example. This survey is beneficial for researchers that are working on a high resolution input space. The kd-tree approximation outperforms the naïve Gaussian process implementation in all experiments. [ABSTRACT FROM AUTHOR]

This study concerns the risks of privacy disclosure when sharing and releasing a dataset in which each individual may be associated with multiple records. Existing data privacy approaches and policies typically assume that each individual in a shared dataset corresponds to a single record, leading to an underestimation of the disclosure risks in multiple records per person scenarios. We propose two novel measures of privacy disclosure to arrive at a more appropriate assessment of disclosure risks. The first measure assesses individual-record disclosure risk based upon the frequency distribution of individuals' occurrences. The second measure assesses sensitive-attribute disclosure risk based upon the number of individuals affiliated with a sensitive value. We show that the two proposed disclosure measures generalize the well-known k -anonymity and l -diversity measures, respectively, and work for scenarios with either a single record or multiple records per person. We have developed an efficient computational procedure that integrates the two proposed measures and a data quality measure to anonymize the data with multiple records per person when sharing and releasing the data for research and analytics. The results of the experimental evaluation using real-world data demonstrate the advantage of the proposed approach over existing techniques for protecting privacy while preserving data quality.

Many example-based image-processing algorithms operate on image patches (small windows of pixels). Such algorithms are commonly used for texture synthesis, resolution enhancement, image denoising, colorization, and hole filling. One barrier to the widespread adoption and performance of these techniques is inaccessibility to a large, varied collection of image patches. The authors describe a database of one trillion image patches assembled from one million natural images downloaded from the Internet. They also describe and analyze two systems for performing nearest-neighbor searches over this database that use the parallel-programming frameworks Hadoop and MPI, respectively. To demonstrate this database's utility as a research tool, they used it to investigate the fundamental relationships between patch size, amount of training data, and expected accuracy of the closest matches. They report a closed-form analytic expression that relates these three quantities, letting them predict any one from the other two. The findings show that massive databases are necessary to achieve reliable performance for even moderate-size patches. These findings also offer important and heretofore absent guidelines for practitioners and researchers interested in working with and improving such data-driven systems. [ABSTRACT FROM PUBLISHER]