This paper presents KDT-MOEA, a framework that takes advantage of a special kind of binary search tree, named K-D tree, to solve multiobjective optimization problems (MOPs). Our main goal is to ...explore the capabilities of this data structure to define neighborhood structures either in decision variables space or in objective space, as well as by switching between them at any time. The KDT-MOEA framework performance is compared with five state-of-the-art algorithms on the DTLZ, WFG and LZ09 benchmarking problems with up to 15 objectives. Statistical tests demonstrate that KDT-MOEA was able to outperform the compared methods on most problems. In addition, in order to evaluate the flexibility and the potential of the proposed operators, extended versions of the compared algorithms are also presented. Empirical results pointed out that the new versions were superior to all five original MOEAs, indicating that the proposed operators can also be easily incorporated into existing MOEAs with different strategies to achieve better results.
Executing convex polytope queries on nD point clouds Liu, Haicheng; Thompson, Rodney; van Oosterom, Peter ...
International journal of applied earth observation and geoinformation,
12/2021, Letnik:
105
Journal Article
Recenzirano
Odprti dostop
•Efficient intersection algorithms for polytope querying on nD point clouds.•Easy-to-use polytope formulation for querying.•Illustrated by nD-simplex and nD-prism model for querying tests from 2D to ...10D.•Solve perspective view selection and flood risk query efficiently using the polytope.
Efficient spatial queries are frequently needed to extract useful information from massive nD point clouds. Most previous studies focus on developing solutions for orthogonal window queries, while rarely considering the polytope query. The latter query, which includes the widely adopted polygonal query in 2D, also plays a critical role in many nD spatial applications such as the perspective view selection. Aiming for an nD solution, this paper first formulates a convex nD-polytope for querying. Then, the paper integrates three approximate geometric algorithms – SWEEP, SPHERE, VERTEX, and a linear programming method CPLEX, developing a solution based on an Index-Organized Table (IOT) approach. IOT is applied with space filling curve based clustering and advanced querying mechanism which recursively refines hypercubic nD spaces to approach the query geometry for primary filtering. Results from experiments based on both synthetic and real data have confirmed the superior performance of SWEEP. However, the algorithm may lag behind CPLEX due to pessimistic intersection computation in high dimensional spaces. In a real application, by properly transforming a perspective view selection into a polytope query, the solution achieves a sub-second querying performance using SWEEP. In another flood risk query, SWEEP also leads the others. In general, the robust and efficient solution can be immediately used to address different polytope queries, including those abstract ones whose constraints on combinations of different dimensions are formed into a polytope model. Besides, the knowledge of high-dimensional computations acquired also provides significant guidance for handling more nD GIS issues.
We note that a recently described data structure, the Neighborhood Grid, is equivalent to a data structure developed in the mid-1980s called the Monotonic Lagrangian Grid (MLG). The MLG was ...originally developed to support high-performance molecular and fluid dynamics simulations on both supercomputer and vector processing architectures and still finds use in those and other areas. In this paper we emphasize that the rediscovery of the MLG offers benefits to users of the Neighborhood Grid in the form of an existing literature with results relevant to its efficient implementation in various contexts while users of the MLG similarly benefit from new theoretical results obtained for the Neighborhood grid.
•The paper notes that the recently introduced Neighborhood Grid is a rediscovery of a known data structure called the Monotonic Lagrangian Grid (MLG).•Background on the MLG and its literature are discussed, and a previously-unpublished result relating to its theoretical properties is provided.•It is argued that the Neighborhood Grid has motivated new theoretical analyses that has proven new results not previously known about the MLG.
Hexagonal discrete global grid systems (DGGSs) with integer spatial indexes are a promising new approach to designing geospatial data structures and location reference systems. Central place indexing ...(CPI) is a class of multi-precision hierarchical linear spatial indexing systems for pure and mixed-aperture hexagonal DGGSs. Definitions for CPI systems are given both on the plane and on the polyhedral surfaces of geodesic DGGSs, and examples of real-world DGGSs indexed using CPI are described. The semantic advantages of CPI systems are discussed, including their ability to exactly represent their own geometries.
Geodesic Discrete Global Grid Systems Sahr, Kevin; White, Denis; Kimerling, A. Jon
Cartography and geographic information science,
04/2003, Letnik:
30, Številka:
2
Journal Article
Recenzirano
In recent years, a number of data structures for global geo-referenced data sets have been proposed based on regular, multi-resolution partitions of polyhedra. We present a survey of the most ...promising of such systems, which we call Geodesic Discrete Global Grid Systems (Geodesic DGGSs). We show that Geodesic DGGS alternatives can be constructed by specifying five substantially independent design choices: a base regular polyhedron, a fixed orientation of the base regular polyhedron relative to the Earth, a hierarchical spatial partitioning method defined symmetrically on a face (or set of faces) of the base regular polyhedron, a method for transforming that planar partition to the corresponding spherical/ellipsoidal surface, and a method for assigning point representations to grid cells. The majority of systems surveyed are based on the icosahedron, use an aperture 4 triangle or hexagon partition, and are either created directly on the surface of the sphere or by using an equal-area transformation. An examination of the design choice options leads us to the construction of the Icosahedral Snyder Equal Area aperture 3 Hexagon (ISEA3H) Geodesic DGGS.
Efficient manipulation of Pareto fronts and Pareto archives involves non-trivial data structures and algorithms. Because of this complexity, researchers and programmers might recur to naive ...strategies based on linear lists, where most operations require expensive pairwise comparisons between all elements. The lack of a functional container type for Pareto fronts and archives reduces their usefulness in multi-objective optimization, simulations in economics, decision making, data analysis, or any application that caches objects based on multiple criteria. Despite the existence of some frameworks for multi-objective optimization, there is no user-oriented solution focused exclusively on efficient implementations of dynamic fronts and archives as abstract data types with their fundamental operations for insertion, removal, searching, reference points, hyperbox queries, nearest points, and indicators. This paper describes such a library based on spatial data structures for Pareto fronts and archives with specialized algorithms to perform all of these operations with low asymptotic complexity. At a negligible integration cost, the results confirm this implementation achieves notable performance gains over naive methods for fronts of all sizes and dimensions.
In-Path Oracles for Road Networks Ghosh, Debajyoti; Sankaranarayanan, Jagan; Khatter, Kiran ...
ISPRS international journal of geo-information,
07/2023, Letnik:
12, Številka:
7
Journal Article
Recenzirano
Odprti dostop
Many spatial applications benefit from the fast answering to a seemingly simple spatial query: “Is a point of interest (POI) ‘in-path’ to the shortest path between a source and a destination?” In ...this context, an in-path POI is one that is either on the shortest path or can be reached within a bounded yet small detour from the shortest path. The fast answering of the in-path queries is contingent on being able to determine without having to actually compute the shortest paths during runtime. Thus, this requires a precomputation solution. The key contribution of the paper is the development of an in-path oracle that is based on precomputation of which pairs of sources and destinations are in-path with respect to the given POI. For a given road network with n nodes and m POIs, an O(m×n)-sized oracle is envisioned based on the reduction of the well-separated pairs (WSP) decomposition of the road network. Furthermore, an oracle can be indexed in a database using a B-tree that can answer queries at very high throughput. Experimental results on the real road network POI dataset illustrate the superiority of this technique compared to a baseline algorithm. The proposed approach can answer ≈ 1.5 million in-path queries per second compared to a few hundred per second using a suitable baseline approach.
This paper presents a survey of georeferenced point clouds. Concentration is, on the one hand, put on features, which originate in the measurement process themselves, and features derived by ...processing the point cloud. On the other hand, approaches for the processing of georeferenced point clouds are reviewed. This includes the data structures, but also spatial processing concepts. We suggest a categorization of features into levels that reflect the amount of processing. Point clouds are found across many disciplines, which is reflected in the versatility of the literature suggesting specific features.
Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the
bounding-box quality of space-filling curves that express ...how effective different space-filling curves are for this purpose. We give general lower bounds on the bounding-box quality measures and on locality according to Gotsman and Lindenbaum for a large class of space-filling curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and the bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with relatively bad locality by Gotsman and Lindenbaum's measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.
PDF
