论文标题
一种新的数据结构，用于有效地搜索Isovists
A new data structure for efficient search on isovists
论文作者
论文摘要
空间数据结构允许对地理信息系统（GIS）进行有效的查询。空间查询涉及数据的几何形状，例如点，线或多边形。例如，空间查询可以从给定位置对最近的餐馆进行轮询。可以通过浏览整个数据来详尽地求解空间查询，随着数据点的数量增加，这是过于敏感的。在本文中，我们有兴趣对无限长的几何形状进行有效的查询。例如，定义为两个半空间的交点的角扇区无限长。但是，常规的空间数据结构不适合这些几何形状。我们提出了一种新方法，允许在角扇区上进行有效的空间查询（即，一个点是否在角扇区内）。它通过角扇区的双重空间构建了一个R-Tree。广泛的评估表明，我们的方法比使用常规的R-Tree要快。
Spatial data structures allow to make efficient queries on Geographical Information Systems (GIS). Spatial queries involve the geometry of the data, such as points, lines, or polygons. For instance, a spatial query could poll for the nearest restaurants from a given location. Spatial queries can be solved exhaustively by going through the entire data, which is prohibitive as the number of data points increases. In this article, we are interested in making efficient queries on infinitely long geometrical shapes. For instance, angular sectors, defined as the intersection of two half-spaces, are infinitely long. However, regular spatial data structures are not adapted to these geometrical shapes. We propose a new method allowing to make efficient spatial queries on angular sectors (i.e. whether a point is inside an angular sector). It builds a R-tree from the dual space of angular sectors. An extensive evaluation shows our method is faster than using a regular R-tree.
