Parallel processing of nearest neighbor queries in declustered spatial data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel processing of nearest neighbor queries in declustered spatial data

Full text

Pdf (908 KB)

Source

Geographic Information Systems archive
Proceedings of the 4th ACM international workshop on Advances in geographic information systems table of contents

Rockville, Maryland, United States

Pages: 35 - 43

Year of Publication: 1996

ISBN:0-89791-874-6

Authors

Apostolos Papadopoulos	Department of Informatics, Aristotle University, 54006 Thessaloniki, Greece
Yanis Manolopoulos	Department of Informatics, Aristotle University, 54006 Thessaloniki, Greece

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGIR: ACM Special Interest Group on Information Retrieval
SIGLINK: Hypertext, Hypermedia, and Web

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 44, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258319.258330 What is a DOI?

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.

	Aref93	W. Aref: 'Query processing and optimization in spatial dat,~bases", Technical Report CS-TIt- 3097, Department of Computer $cie~ce, UniYe::sity of Maryland at College Park, MD, 1993.
	Beck90	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
	Belu95	Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
	Brin93	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
	Ciac96	Paolo Ciaccia , Arianna Veronesi, Dynamic Declustering Methods for Parallel Grid Files, Proceedings of the Third International ACPC Conference with Special Emphasis on Parallel Databases and Parallel I/O: Parallel Computation, p.110-123, September 23-25, 1996
	DeWi92	David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
	Egen94	M. J. Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.86-95, February 1994 [doi>10.1109/69.273029]
	Fal91	Christos Faloutsos , Dimitris Metaxas, Disk Allocation Methods Using Error Correcting Codes, IEEE Transactions on Computers, v.40 n.8, p.907-914, August 1991 [doi>10.1109/12.83636]
	Fal93	Christos Faloutsos , Pravin Bhagwat, Declustering using fractals, Proceedings of the second international conference on Parallel and distributed information systems, p.18-25, January 1993, San Diego, California, United States
	Fal94	Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
	Guen89	Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
	Guti94	Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
	Gutt84	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	Henr89	A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
	Kame92	Ibrahim Kamel , Christos Faloutsos, Parallel R-trees, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.195-204, June 02-05, 1992, San Diego, California, United States
	Kame93	Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
	Kame94	Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
	Koud96	Nick Koudas , Christos Faloutsos , Ibrahim Kamel, Declustering Spatial Databases on a Multi-Computer Architecture, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.592-614, March 25-29, 1996
	Laur92	IL Laurini aad D. Thompson: "Fundamentals of spatial information systems", AcaAemic Press, London, 1992.
	LoRa94	Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
	Page93	Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
	Papa96a	A. Papadopoulos and Y. Manolopoulos: "Multiple range query optimization ht spatial databases", submitted.
	Papa96b	Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
	Rous85	Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
	Rous95	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
	Same90	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	Seeg93	Bernhard Seeger , Per-Åke Larson , Ron McFayden, Reading a Set of Disk Pages, Proceedings of the 19th International Conference on Very Large Data Bases, p.592-603, August 24-27, 1993
	Sell87	Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
	Ston93	Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.2-11, May 25-28, 1993, Washington, D.C., United States
	Theo96	Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
	Tiger94	TIGER/Line Files, 1994 Technical Documentation / prepared by the Bureau of the Census, Washington, DC, 1994.
	Vald91	M. Tamer Ozsu , P. Valduriez, Principles of distributed database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	Zhou	Yvonne Zhou , Shashi Shekhar , Mark Coyle, Disk Allocation Methods for Parallelizing Grid Files, Proceedings of the Tenth International Conference on Data Engineering, p.243-252, February 14-18, 1994

CITED BY 5

	Marina L. Gavrilova, On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets, The Journal of Supercomputing, v.22 n.1, p.87-98, May 2002
	Thomas Schwarz , Markus Iofcea , Matthias Grossmann , Nicola Hönle , Daniela Nicklas , Bernhard Mitschang, On efficiently processing nearest neighbor queries in a loosely coupled set of data sources, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
	Apostolos N. Papadopoulos , Yannis Manolopoulos, Distributed Processing of Similarity Queries, Distributed and Parallel Databases, v.9 n.1, p.67-92, January 1, 2001
	Erion Plaku , Lydia E. Kavraki, Distributed computation of the knn graph for large high-dimensional point sets, Journal of Parallel and Distributed Computing, v.67 n.3, p.346-359, March, 2007
	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