Abstract
We identify and formalize a novel join operator for two spatial pointsets P and Q. The common influence join (CIJ) returns the pairs of points (p,q),p isin P,q isin Q, such that there exists a location in space, being closer to p than to any other point in P and at the same time closer to q than to any other point in Q. In contrast to existing join operators between pointsets (i.e., e-distance joins and fc-closest pairs), CIJ is parameter- free, providing a natural join result that finds application in marketing and decision support. We propose algorithms for the efficient evaluation of CIJ, for pointsets indexed by hierarchical multi-dimensional indexes. We validate the effectiveness and the efficiency of these methods via experimentation with synthetic and real spatial datasets. The experimental results show that a non-blocking algorithm, which computes intersecting pairs of Voronoi cells on-demand, is very efficient in practice, incurring only slightly higher I/O cost than the theoretical lower bound cost for the problem.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Proceedings / International Conference on Data Engeenering |
Sider (fra-til) | 100-109 |
Antal sider | 10 |
ISSN | 1063-6382 |
DOI | |
Status | Udgivet - 2008 |
Begivenhed | The 24th IEEE International Conference on Data Engineering (ICDE) - Cancun, Mexico Varighed: 7 apr. 2008 → 12 apr. 2008 Konferencens nummer: 24 |
Konference
Konference | The 24th IEEE International Conference on Data Engineering (ICDE) |
---|---|
Nummer | 24 |
Land/Område | Mexico |
By | Cancun |
Periode | 07/04/2008 → 12/04/2008 |
Bibliografisk note
Værtspublikationstitel: IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008.INSPEC Accession Number: 9963665
Udgivelsesdato: 25.04.2008