On efficiently processing nearest neighbor queries in a loosely coupled set of data sources

ABSTRACT

We propose a family of algorithms for processing nearest neighbor (NN) queries in an integration middleware that provides federated access to numerous loosely coupled, autonomous data sources connected through the internet. Previous approaches for parallel and distributed NN queries considered all data sources as relevant, or determined the relevant ones in a single step by exploiting additional knowledge on object counts per data source. We propose a different approach that does not require such detailed statistics about the distribution of the data. It iteratively enlarges and shrinks the set of relevant data sources. Our experiments show that this yields considerable performance benefits with regard to both response time and effort. Additionally, we propose to use only moderate parallelism instead of querying all relevant data sources at the same time. This allows us to trade a slightly increased response time for a lot less effort, hence maximizing the cost profit ratio, as we show in our experiments. Thus, the proposed algorithms clearly extend the set of NN algorithms known so far.

REFERENCES

• 1: Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996
• 2: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• 3: Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Fast Nearest Neighbor Search in High-Dimensional Space, Proceedings of the Fourteenth International Conference on Data Engineering, p.209-218, February 23-27, 1998
• 4: 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
• 5: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 6: P. Ciaccia, A. Nanni, M. Patella: A Query-sensitive Cost Model for Similarity Queries with M-tree, Proc. of the 10th Australasian Database Conference (ADC'99), Auckland, New Zealand, Jan 1999, pp. 65--76
• 7: H. Ferhatosmanoglu, Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching, Proceedings of the 15th International Conference on Data Engineering, p.608, March 23-26, 1999
• 8: Hakan Ferhatosmanoglu , Divyakant Agrawal , Amr El Abbadi, Optimal Partitioning for Efficient I/O in Spatial Databases, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.889-900, August 28-31, 2001
• 9: 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
• 10: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 11: The Federal Geographic Data Committee: The Clearinghouse, http://www.fgdc.gov/clearinghouse/clearinghouse.html
• 12: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 13: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 14: 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
• 15: Yu-long Lo , Kien A. Hua , Honesty C. Young, A General Multidimensional Data Allocation Method for Multicomputer Database Systems, Proceedings of the 8th International Conference on Database and Expert Systems Applications, p.357-366, September 01-05, 1997
• 16: Danzhou Liu , Ee-Peng Lim , Wee Keong Ng, Efficient k Nearest Neighbor Queries on Remote Spatial Databases Using Range Estimation, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.121-130, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029712]
• 17: Daniela Nicklas , Matthias Großmann , Thomas Schwarz , Steffen Volz , Bernhard Mitschang, A Model-Based, Open Architecture for Mobile, Spatially Aware Applications, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.117-135, July 12-15, 2001
• 18: Open GIS Consortium: OpenGIS Simple Features Specification for SQL, Revision 1.1, Open GIS Consortium (OGC), May 1999, http://www.opengis.org/docs/99--049.pdf
• 19: Open GIS Consortium: The OpenGIS Abstract Specification - Topic 13: Catalog Services, Open GIS Consortium (OGC), March 1999, http://www.opengis.org/docs/99--113.pdf
• 20: Open GIS Consortium: OpenGIS Catalog Services Specification, Open GIS Consortium (OGC), Dec. 2002, http://www.opengis.org/docs/02-087r3.pdf
• 21: Open GIS Consortium: OWS1.2 UDDI Experiment, Open GIS Consortium (OGC), Jan 2003, http://www.opengis.org/docs/03-028.pdf
• 22: Sunil Prabhakar , Khaled A. S. Abdel-Ghaffar , Divyakant Agrawal , Amr El Abbadi, Cyclic Allocation of Two-Dimensional Data, Proceedings of the Fourteenth International Conference on Data Engineering, p.94-101, February 23-27, 1998
• 23: Apostolos Papadopoulos , Yanis Manolopoulos, Parallel processing of nearest neighbor queries in declustered spatial data, Proceedings of the 4th ACM international workshop on Advances in geographic information systems, p.35-43, November 1996, Rockville, Maryland, United States [doi>10.1145/258319.258330]
• 24: Apostolos N. Papadopoulos , Yannis Manolopoulos, Similarity query processing using disk arrays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.225-236, June 01-04, 1998, Seattle, Washington, United States
• 25: Apostolos N. Papadopoulos , Yannis Manolopoulos, Distributed Processing of Similarity Queries, Distributed and Parallel Databases, v.9 n.1, p.67-92, January 1, 2001 [doi>10.1023/A:1026509108054]
• 26: H. Pinto, N. V. Boas, R. José, Using a private UDDI for publishing location-based information to mobile users, ICCC/IFIP 7th Intl. Conf. on Electronic Publishing (ElPub2003), Guimaraes, Portugal, June 2003
• 27: 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
• 28: UDDI: The UDDI Technical White Paper, UDDI.org, Sept. 2000, http://www.uddi.org/pubs/Iru_UDDI_Technical_White_Paper.pdf
• 29: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Spatial databases and GIS
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Experimentation, Performance

Keywords:
data integration, distributed query processing, federated database system, kNN, nearest neighbors, parallel query processing