计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
22期
123-126
,共4页
Z曲线%网格划分%最近邻查询%查询层
Z麯線%網格劃分%最近鄰查詢%查詢層
Z곡선%망격화분%최근린사순%사순층
Z curve%grid partition%nearest neighbor%query layer
为了解决高维空间最近邻查询问题，在网格划分的基础上，利用Z曲线对网格排序并将二维空间中的点映射到一维空间中。考虑到点的分布和网格形状对查询的影响，提出最小查询层和方向变换的概念。只要给出查询点与任意点之间的方向变换，即可求出该点所在的网格Z值，从而求出任意查询层的所有网格Z值。证明了最近邻查询只需访问至最小查询层后再访问两层。基于此提出了最近邻查询算法，它适用于数据点任意分布的情况，该算法能够得到精确解。
為瞭解決高維空間最近鄰查詢問題，在網格劃分的基礎上，利用Z麯線對網格排序併將二維空間中的點映射到一維空間中。攷慮到點的分佈和網格形狀對查詢的影響，提齣最小查詢層和方嚮變換的概唸。隻要給齣查詢點與任意點之間的方嚮變換，即可求齣該點所在的網格Z值，從而求齣任意查詢層的所有網格Z值。證明瞭最近鄰查詢隻需訪問至最小查詢層後再訪問兩層。基于此提齣瞭最近鄰查詢算法，它適用于數據點任意分佈的情況，該算法能夠得到精確解。
위료해결고유공간최근린사순문제，재망격화분적기출상，이용Z곡선대망격배서병장이유공간중적점영사도일유공간중。고필도점적분포화망격형상대사순적영향，제출최소사순층화방향변환적개념。지요급출사순점여임의점지간적방향변환，즉가구출해점소재적망격Z치，종이구출임의사순층적소유망격Z치。증명료최근린사순지수방문지최소사순층후재방문량층。기우차제출료최근린사순산법，타괄용우수거점임의분포적정황，해산법능구득도정학해。
In order to solve Nearest Neighbor(NN)query in high-dimensional space, the grids are ordered and points on two-dimensional space are mapped into 1D space with Z curve based on grid partition. Considering the influence of the distribution of points and the shape of grids on queries, the definitions of minimum query layer and direction transformation are proposed. The Z value of any point could be computed if only the direction transformation between it and query point is given, and moreover all Z values of any query layer can be computed. It is proved that the layer, two more layers than the minimum query layer are needed to be queried to accomplish the NN query. The grid shape is tend to square would make efficient and the NN only needs visit the minimum and then two layers are proved. Based on these, the NN algorithm is presented, which is suitable to points of any distribution. And the accurate solution can be obtained.
