HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Search algorithms for multiway spatial joins
Authors: Papadias, Dimitris
Arkoumanis, Dinos
Keywords: Multiway spatial joins
Search algorithms
Query processing
Multimedia data
Nondeterministic search heuristics
Issue Date: Oct-2002
Citation: International journal of geographical information science, v. 16, no. 7 (Oct-Nov 2002) p. 613-39
Abstract: This papers deals with multiway spatial joins when (i) there is limited time for query processing and the goal is to retrieve the best possible solutions within this limit (ii) there is unlimited time and the goal is to retrieve a single exact solution, if such a solution exists, or the best approximate one otherwise. The first case is motivated by the high cost of join processing in real-time systems involving large amounts of multimedia data, while the second one is motivated by applications that require “negative” examples. We propose several search algorithms for query processing under theses conditions. For the limited-time case we develop some non-deterministic search heuristics that can quickly retrieve good solutions. However, these heuristics are not guaranteed to find the best solutions, even without a time limit. Therefore, for the unlimited-time case we describe systematic search algorithms tailored specifically for the efficient retrieval of a single solution. Both types of algorithms are integrated with R-trees in order to prune the search space. Our proposal is evaluated with extensive experimental comparison.
Rights: This is an early version and therefore should not be cited.
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
search.pdfpre-published version132KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.