HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >
Please use this identifier to cite or link to this item:
|Title: ||Evaluation of iceberg distance joins|
|Authors: ||Shou, Yutao|
Cheung, David W.
|Keywords: ||Iceberg distance joins|
|Issue Date: ||Jul-2003 |
|Citation: ||Advances in Spatial and Temporal Databases: 8th International Symposium, 2003 (LNCS 2750) p. 270-288|
|Abstract: ||The iceberg distance joins returns object pairs within some distance from each other, provided that the first object appears at least a number of times in the result, e.g., 'find hotels which are within 1km to at least 10 restaurants'. The output of this query is the subset of the corresponding distance join (e.g., 'find hotels which are within 1km to some restaurant') that satisfies the additional cardinality constraint. Therefore, it could be processed by using a conventional spatial join algorithm and then filtering-out the non-qualifying pairs. This approch, however, is expensive, especially when the cardinality constraint is highly selective. In this paper, we propose output-sensitive algorithms that prune the search space by integrating the cardinality with the distance constraint. We deal with cases of indexed/non-indexed datasets and evaluate the performance of the proposed techniques with extensive experimental evaluation covering a wide range of problem parameters.|
|Rights: ||The original publication is available at http://www.springerlink.com/. Please use the appropriate URL and/or DOI for the article.The access script to link to it is: http://library.ust.hk/cgi/db/doi.pl?10.1007/b11839|
|Appears in Collections:||CSE Conference Papers|
Files in This Item:
|papadias10.pdf||pre-published version||438Kb||Adobe PDF||View/Open|
All items in this Repository are protected by copyright, with all rights reserved.