Please use this identifier to cite or link to this item:

Approximate processing of multiway spatial joins in very large databases

Authors Papadias, D. View this author's profile
Arkoumanis, D.
Issue Date 2002
Source Lecture Notes in Computer Science , v. 2287, 2002, p. 179-196
Summary Existing work on multiway spatial joins focuses on the retrieval of all exact solutions with no time limit for query processing. Depending on the query and data properties, however, exhaustive processing of multiway spatial joins can be prohibitively expensive due to the exponential nature of the problem. Furthermore, if there do not exist any exact solutions, the result will be empty even though there may exist solutions that match the query very closely. These shortcomings motivate the current work, which aims at the retrieval of the best possible (exact or approximate) solutions within a time threshold, since fast retrieval of approximate matches is the only way to deal with the ever increasing amounts of multimedia information in several real time systems. We propose various techniques that combine local and evolutionary search with underlying indexes to prune the search space. In addition to their usefulness as standalone methods for approximate query processing, the techniques can be combined with systematic search to enhance performance when the goal is retrieval of the best solutions.
ISSN 0302-9743
ISBN 3-540-43324-4
Rights The original publication is available at Please use the appropriate URL and/or DOI for the article.
Language English
Format Article
Access View full-text via Web of Science
Files in this item:
File Description Size Format
appro.pdf 312646 B Adobe PDF