Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

A Method of Multi-level Uniform Grids for Spatial Searching
Authors
	Davydov V.V.
Date of publication
	2018
DOI
	10.31114/2078-7707-2018-1-167-172
Abstract
	Fast geometry search techniques are of high importance in electronic design automation area (topological design, physical verification, data visualization and others). The evolution of the technology leads to the increase of the number of elements on a chip. Consequently, the require-ments to geometry indexing algorithms become stricter in terms of memory consumption and query performance. In practice, a simple uniform grid method [1] is often a good alternative to tree-based search structures such as R-tree, BSP-tree, quadtree. Despite of the decent query performance in comparison with tree-based structures it has such weak-ness as significant performance degradation with highly clustered data, higher memory consumption when geometries cover more than one grid cell, duplication of found geometries in the result (some geometries may cover several adjacent grid cells). To tackle some of the weakness of the classical grid method a new uniform grid-based method is presented in this article. The implementation of the method for the fixed set of 2D geometries demonstrates lower memory consumption with higher query performance in comparison with BOOST R-tree implementations. The implementation has been successfully applied in practice for restoring interconnectivity of power net shapes in analog and mixed designs. The idea of the method is to group all the geometries by its sizes (dimensions) and to create a separate spatial uniform grid for each size group. The uniform grid cells sizes are chosen to be greater than any geometry sizes of the group. Each geometry is assigned on a single grid cell only by its origin point (bounding box lower left point, center). The range search algorithm is applied independently to each spatial grid. Because the number of size groups can be high enough a reduction technique is proposed to decrease its number. The implementation was successfully tested on a real design with huge amount of geometries. About 109 device boundary boxes were used as the input. The test was to construct a search structure with rectangles and to perform a query in the areas corresponding to each input rectangle. The test demonstrates higher query rates in comparison with BOOST R-tree implementation - more than 3x faster with the lower amount of memory (2x lower). Considering that the real design has a significant empty area in the center of the layout (about 25% of full layout size) the method demonstrates de-cent performance on non-regular data. Despite of some limitations related to clustered data the method is applicable to the most tasks in electronic design automation area. The introduced implementation is applicable to the fixed set of 2D geometric data, but it can be enhanced to support dynamic sets of data with insert/delete operations and to support higher dimension spaces.
Keywords
	multi-level uniform grid, spatial search, geometry search
Library reference
	Davydov V.V. A Method of Multi-level Uniform Grids for Spatial Searching // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 1. P. 167-172. doi:10.31114/2078-7707-2018-1-167-172
URL of paper
	http://www.mes-conference.ru/data/year2018/pdf/D018.pdf