[1]骆炎民,陈维斌,廖明宏.无索引空间数据库的基于最优点的集合最近邻查找算法[J].华侨大学学报(自然科学版),2011,32(2):169-174.[doi:10.11830/ISSN.1000-5013.2011.02.0169]
　Luo Yan-min,CHEN Wei-bin,LIAO Min-hong.An Algorithm of Aggregate Nearest Neighbor Query for Non-Index Spatial Database[J].Journal of Huaqiao University(Natural Science),2011,32(2):169-174.[doi:10.11830/ISSN.1000-5013.2011.02.0169]
点击复制

无索引空间数据库的基于最优点的集合最近邻查找算法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第32卷
期数:
2011年第2期
页码:
169-174
栏目:
出版日期:
2011-03-20

文章信息/Info

Title:
An Algorithm of Aggregate Nearest Neighbor Query for Non-Index Spatial Database
文章编号:
1000-5013(2011)02-0169-06
作者:
骆炎民; 陈维斌; 廖明宏
华侨大学计算机科学与技术学院; 厦门大学信息科学与技术学院; 厦门大学软件学院
Author(s):
Luo Yan-min1; 2;  CHEN Wei-bin1;  LIAO Min-hong3
1.College of Computer Science and Technology, Huaqiao University, Quanzhou 362021, China; 2.School of Information Science and Technology, Xiamen University, Xiamen 361005, China; 3.School of Software, Xiamen University, Xiamen 361005, China
关键词:
空间数据库;  最近邻;  集合最近邻;  查询区域
Keywords:
spatial database;  nearest neighbor;  aggregate nearest neighbor;  search region
分类号:
TP311.13
DOI:
10.11830/ISSN.1000-5013.2011.02.0169
文献标志码:
A
摘要:
针对度量空间中的无索引空间数据库,提出一种基于最优点的集合最近邻查找算法及其改进算法.采用真实数据集与人工生成的数据集对算法进行测试,评估所提出算法的效率.实验结果表明,所提算法的效率优于组最近邻居查询算法,并且对于高维数据空间,所提出的算法有较高的稳定性.由于查询区域中数据点的数量比较少,改进的基于最优点的集合最近邻查找算法的效率总体上要比改进前高.
Abstract:
The vantage point-based aggregate nearest neighbor query algorithm and it′s improved algorithm are proposed for non-index spatial database in metric space.The algorithms are tested by using both real datasets and synthetic datasets to evaluate efficiencies of the proposed algorithms.The experimental results show that the efficiencies of proposed algorithms are better than that of multiple query method.Furthermore,the proposed algorithms have higher stabilization in high-dimensional data space.Since there are less data points in it′s search region,efficiency of the improved vantage point-based aggregate nearest neighbor query algorithm is generally higher than the vantage point-based aggregate nearest neighbor query algorithm.

参考文献/References:

[1] YIU Man-lung, MAMOULIS N, PAPADIAS D. Aggregate nearest neighbor queries in road networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2005(6):820-833.doi:10.1109/TKDE.2005.87.
[2] JENSEN C S, KOL(A)RVR J, PEDERSEN T B. Nearest neighbor queries in road networks [A]. New York:ACM, 2003.1-8.
[3] JAIN A K, M.MURTY N M, FLYNN P J. Data clustering:A review [J]. ACM Computing Surveys, 1999(3):264-323.
[4] AGGARWAL C C, YU P S. Outlier detection for high dimensional data [A]. New York:ACM, 2001.37-46.
[5] PAPADIAS D, TAO Yu-fei, MOURATIDIA K. Aggregate nearest neighbor queries in spatial databases [J]. ACM Transactions on Database Systems, 2005(2):529-576.doi:10.1145/1071610.1071616.
[6] PAPADIAS D, SHEN Qiong-mao, TAO Yu-fei. Group nearest neighbor queries [A]. Washington, DC:IEEE Computer Society, 2004.301-312.
[7] LI Hong-ga, LU Hua, HUANG Bo. Two ellipse-based pruning methods for group nearest neighbor queries [A]. Washington, DC:IEEE Computer Society, 2005.192-199.
[8] BEYER K, GOLDSEIN J, RAMAKRISHNAN R. When is "nearest neighbors" meaningful [A]. Lodon:Springer-Verlag, 1999.217-235.
[9] GUTTMAN A. R-trees:A dynamic index structure for spatial searching [A]. San Francisco:Morgan Kaufmann Publishers, 1984.47-57.
[10] BECKMANN N, KRIEGEL H P, SCHNEIDER R. The R* -tree:An efficient and robust access method for points and rectangles [A]. New York:ACM, 1990.322-331.
[11] PAPADOPOULOS A, MANOLOPOULOS Y. Performance of nearest neighbor queries in R-trees [A]. Lodon:Springer-Verlag, 1997.394-408.
[12] UHLMANN J K. Satisfying general proximity/similary queries with metric treea [J]. Information Processing Letters, 1991(4):175-179.doi:10.1016/0020-0190(91)90074-R.
[13] ROUSSOPOULOS N, KELLEY S, VINCENT F. Nearest neighbor queries [A]. New York:ACM, 1995.71-79.
[14] ISHIKAWA M, CHEN Han-xiong, FURUSE K. MB+tree:A dynamically updatable metric index for similarity searches [A]. Beilin:Springer-Verlag, 2000.356-373.
[15] BRIN S. Near neighbor search in large metric spaces [A]. San Francisco:Morgan Kaufmann Publishers, 1995.574-584.
[16] BOZKAYA T, OZSOYOGLU M. Distance-based indexing for high-dimensional metric spaces [A]. New York:ACM, 1997.357-368.

备注/Memo

备注/Memo:
福建省自然科学基金资助项目(2009J01288)
更新日期/Last Update: 2014-03-23