Efficient k nearest neighbor queries on remote spatial databases using range estimation
Proceedings 14th International Conference on Scientific and Statistical Database Management - Trang 121-130
Tóm tắt
We propose a k-NN query processing algorithm that uses one or more window queries to retrieve the nearest neighbors of a given query point. We also propose two different methods to estimate the ranges to be used by the window queries. Each range estimation method requires different statistical knowledge about the spatial databases. Our experiments on the TIGER data allow us to study the behavior of the proposed algorithm using different range estimation methods. Apart from not requiring direct access to the spatial indices, the window queries used in the proposed algorithm can be easily supported by non-spatial database systems containing spatial objects.
Từ khóa
#Nearest neighbor searches #Spatial databases #Neural networks #Geographic Information Systems #Application software #Query processing #Database systems #Information systems #Data engineering #Computer aided manufacturingTài liệu tham khảo
10.1145/379437.379504
0, U.S. Bureau of the Census, Tiger/Line Files
10.1109/ICDE.2000.839417
10.1137/0217052
0, The Federal Geographic Data Committee The Clearinghouse
10.1007/3-540-47724-1_14
10.1109/ICDE.2001.914864
10.1145/280277.280279
10.1145/276304.276326
10.1145/320248.320255
10.1109/ICDE.2000.839451
10.1109/SSDM.1999.787640
stanoi, 2000, Reverse nearest neighbor queries for dynamic databases, ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 44
10.1145/93597.98741
10.1109/69.755614
10.1145/293347.293348
10.1109/ICDE.1998.655779
10.1145/237661.237705
10.1145/263661.263671
10.1145/290593.290596
10.1109/69.842249
arya, 1995, Nearest Neighbor Searching and Applications
ciaccia, 1999, A query-sensitive cost model for similarity queries with M-tree, Proceedings of the 10th Australasian Database Conference (ADC '99), 65
10.1145/304182.304184
10.1145/342009.335415
ooi, 2001, Indexing the distance: an efficient method to KNN processing, Proc Int Conf On Very Large Data Bases
lang, 2001, Technical Report TRCS01-04
papadopoulos, 1997, Nearest neighbor queries in shared-nothing environments, Geo-Informatica, 369
10.1109/ICDE.2000.839457
10.1145/223784.223794
papadopoulos, 1997, Performance of nearest neighbor queries in R-trees, Proc of the Int Conf Database Theory, 394