Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Ring-constrained Join: Deriving Fair Middleman Locations from Pointsets via a Geometric Constraint |
| Organization Unit | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Event Title | 11th Intl Conf. on Extending Database Technology (EDBT) |
| Event Type | other |
| Event Location | Nantes, France |
| Event Start Date | February 26 - 2008 |
| Event End Date | February 28 - 2008 |
| Abstract Text | We introduce a novel spatial join operator, the ring-constrained join (RCJ). Given two sets P and Q of spatial points, the result of RCJ consists of pairs hp, qi (where p ∈ P, q ∈ Q) satisfying an intuitive geometric constraint: the smallest cir- cle enclosing p and q contains no other points in P, Q. This new operation has important applications in decision sup- port, e.g., placing recycling stations at fair locations between restaurants and residential complexes. Clearly, RCJ is de- fined based on a geometric constraint but not on distances between points. Thus, our operation is fundamentally dif- ferent from the conventional distance joins and closest pairs problems. We are not aware of efficient processing algo- rithms for RCJ in the literature. A brute-force solution requires computational cost quadratic to input size and it does not scale well for large datasets. In view of this, we de- velop efficient R-tree based algorithms for computing RCJ, by exploiting the characteristics of the geometric constraint. We evaluate experimentally the efficiency of our methods on synthetic and real spatial datasets. The results show that our proposed algorithms scale well with the data size and have robust performance across different data distributions. |
| Digital Object Identifier | 10.1145/1353343.1353416 |
| Other Identification Number | merlin-id:341 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|