Method for computing near neighbors of a query point in a database
作者： Nimrod Megiddo , Uri Shaft
DOI:
关键词:
摘要: A method for determining k nearest-neighbors to a query point in database which an ordering is defined data set P of database, the being based on l one-dimensional codes C1, . , C1. single relation R created has attributes index-id, point-id and value. An entry (j,i,C.sub.ej (pi)) included each pi EP, where index-id equals j, i, value C.sub.ej (pi). B-tree index combination attribute attribute. received Q having One tuple generated j=1, l, j (q). distance d selected. The compared point. candidate selected when comparison less than d. Lower bounds are calculated cube plurality cubes that represent minimum between any Lastly, points as
google.co.uk参考文章(24)
John Christopher Shafer, Rakesh Agrawal, Method and system for performing proximity joins on high-dimensional data points in parallel ,(1997)
Surajit Chaudhuri, Method and apparatus for optimizing queries having group-by operators ,(1996)
Shabtai Aldersberg, Fast search method for vector quantizer communication and pattern recognition systems ,(1988)
A. Prasad Sistla, Clement T. Yu, Chengwen Liu, King Liu, Similarity based Retrieval of Pictures Using Indices on Spatial Relationships very large data bases. pp. 619- 629 ,(1995)
William Robinson Equitz, Peter Cornelius Yanker, Myron Dale Flickner, Carlton Wayne Niblack, Dragutin Petkovic, Ronald Jason Barber, Bradley James Beitel, Thomas Randolph Work, Image query system and method ,(1994)
Robert W. Schwanke, Two-neighborhood method for computing similarity between two groups of objects ,(1994)
Arthur R. Butz, Convergence with Hilbert's space filling curve Journal of Computer and System Sciences. ,vol. 3, pp. 128- 146 ,(1969) , 10.1016/S0022-0000(69)80010-3
King-Ip Lin, H. V. Jagadish, Christos Faloutsos, The TV-tree: an index structure for high-dimensional data very large data bases. ,vol. 3, pp. 517- 542 ,(1994) , 10.1007/BF01231606
R. J. Stevens, A. F. Lehar, F. H. Preston, Manipulation and Presentation of Multidimensional Image Data Using the Peano Scan IEEE Transactions on Pattern Analysis and Machine Intelligence. ,vol. PAMI-5, pp. 520- 526 ,(1983) , 10.1109/TPAMI.1983.4767431
Arthur R. Butz, Space filling curves and mathematical programming Information & Computation. ,vol. 12, pp. 314- 330 ,(1968) , 10.1016/S0019-9958(68)90367-7