|
 ABSTRACT
Two new spatial join operations, distance join and distance semi-join, are introduced where the join output is ordered by the distance between the spatial attribute values of the joined tuples. Incremental algorithms are presented for computing these operations, which can be used in a pipelined fashion, thereby obviating the need to wait for their completion when only a few tuples are needed. The algorithms can be used with a large class of hierarchical spatial data structures and arbitrary spatial data types in any dimensions. In addition, any distance metric may be employed. A performance study using R-trees shows that the incremental algorithms outperform non-incremental approaches by an order of magnitude if only a small part of the result is needed, while the penalty, if any, for the incremental processing is modest if the entire join result is required.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
W. G. Aref and H. Samet. The spatial filter revisited. Proc. of 6th international Symposium on Spatial Data Handling, pp. 190-208, Edinburgh, Scotland, September 1994.
|
| |
2
|
|
 |
3
|
Roberto J. Bayardo, Jr. , Daniel P. Miranker, Processing queries for first-few answers, Proceedings of the fifth international conference on Information and knowledge management, p.45-52, November 12-16, 1996, Rockville, Maryland, United States
[doi> 10.1145/238355.238372]
|
| |
4
|
|
| |
5
|
Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
|
| |
6
|
|
| |
7
|
Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
|
| |
8
|
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
|
| |
9
|
Bureau of the Census. Tiger~Line precensusfiles. Washington, DC, 1989.
|
| |
10
|
|
| |
11
|
K. L. Clarkson. Fast algorithm for the all nearest neighbors problem. Proc. of 24th IEEE Syrup. on the Foundations of Computer Science, pp. 226-232, Tucson, November 1983.
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
|
| |
17
|
A. Henrich. A distance-scan algorithm for spatial access structures. Proc. of 2nd ACM Workshop on GIS, pp. 136-143, Gaithersburg, MD, December 1994.
|
| |
18
|
|
| |
19
|
E. Hoel and H. Samct. Data-parallel spatial join algorithms, Proc. of 23rd Int. Conf on Parallel Processing, pp. 227-234, St. Charles, IL, August 1994.
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
|
| |
24
|
|
| |
25
|
|
| |
26
|
Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
|
| |
27
|
|
| |
28
|
|
| |
29
|
|
| |
30
|
|
| |
31
|
H. W. Six and D. Wood. Counting and reporting intersections of d-ranges. IEEE Transactions on Computers, 31 (3):!81- 187, March 1982.
|
| |
32
|
|
| |
33
|
|
| |
34
|
|
CITED BY 45
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hanan Samet , Houman Alborzi , František Brabec , Claudio Esperança , Gísli R. Hjaltason , Frank Morgan , Egemen Tanin, Use of the SAND spatial browser for digital government applications, Communications of the ACM, v.46 n.1, January 2003
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jeremy Kubica , Andrew Moore , Andrew Connolly , Robert Jedicke, A multiple tree algorithm for the efficient association of asteroid observations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
|
|
|
|
|
|
|
|
|
|
|
|
Panfeng Zhou , Donghui Zhang , Betty Salzberg , Gene Cooperman , George Kollios, Close pair queries in moving object databases, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zhen Zhang , Seung-won Hwang , Kevin Chen-Chuan Chang , Min Wang , Christian A. Lang , Yuan-chi Chang, Boolean + ranking: querying a database by k-constrained optimization, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
|
|
|
|
|
|
Xiaobin Ma , Shashi Shekhar , Hui Xiong , Pusheng Zhang, Exploiting a page-level upper bound for multi-type nearest neighbor queries, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chenyi Xia , Hongjun Lu , Beng Chin Ooi , Jing Hu, Gorder: an efficient method for KNN join processing, Proceedings of the Thirtieth international conference on Very large data bases, p.756-767, August 31-September 03, 2004, Toronto, Canada
|
|
|
Yun-Jun Gao , Chun Li , Gen-Cai Chen , Ling Chen , Xian-Ta Jiang , Chun Chen, Efficient k-nearest-neighbor search algorthims for historical moving object trajectories, Journal of Computer Science and Technology, v.22 n.2, p.232-244, March 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2