File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Evaluation of iceberg distance joins
  • Basic View
  • Metadata View
  • XML View
TitleEvaluation of iceberg distance joins
 
AuthorsShou, Y1
Mamoulis, N1
Cao, H1
Papadias, D2
Cheung, DW1
 
Issue Date2003
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2750, p. 270-288 [How to Cite?]
 
AbstractThe iceberg distance join 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 approach, 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. © Springer-Verlag Berlin Heidelberg 2003.
 
ISSN0302-9743
2012 SCImago Journal Rankings: 0.332
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorShou, Y
 
dc.contributor.authorMamoulis, N
 
dc.contributor.authorCao, H
 
dc.contributor.authorPapadias, D
 
dc.contributor.authorCheung, DW
 
dc.date.accessioned2010-09-25T14:54:57Z
 
dc.date.available2010-09-25T14:54:57Z
 
dc.date.issued2003
 
dc.description.abstractThe iceberg distance join 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 approach, 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. © Springer-Verlag Berlin Heidelberg 2003.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2750, p. 270-288 [How to Cite?]
 
dc.identifier.epage288
 
dc.identifier.hkuros81296
 
dc.identifier.issn0302-9743
2012 SCImago Journal Rankings: 0.332
 
dc.identifier.scopuseid_2-s2.0-35248901991
 
dc.identifier.spage270
 
dc.identifier.urihttp://hdl.handle.net/10722/93234
 
dc.identifier.volume2750
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.titleEvaluation of iceberg distance joins
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Shou, Y</contributor.author>
<contributor.author>Mamoulis, N</contributor.author>
<contributor.author>Cao, H</contributor.author>
<contributor.author>Papadias, D</contributor.author>
<contributor.author>Cheung, DW</contributor.author>
<date.accessioned>2010-09-25T14:54:57Z</date.accessioned>
<date.available>2010-09-25T14:54:57Z</date.available>
<date.issued>2003</date.issued>
<identifier.citation>Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2750, p. 270-288</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/93234</identifier.uri>
<description.abstract>The iceberg distance join 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., &quot;find hotels which are within 1km to at least 10 restaurants&quot;. The output of this query is the subset of the corresponding distance join (e.g., &quot;find hotels which are within 1km to some restaurant&quot;) 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 approach, 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. &#169; Springer-Verlag Berlin Heidelberg 2003.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<title>Evaluation of iceberg distance joins</title>
<type>Article</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-35248901991</identifier.scopus>
<identifier.hkuros>81296</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-35248901991&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>2750</identifier.volume>
<identifier.spage>270</identifier.spage>
<identifier.epage>288</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Hong Kong University of Science and Technology