Header

UZH-Logo

Maintenance Infos

Ring-constrained Join: Deriving Fair Middleman Locations from Pointsets via a Geometric Constraint


Yiu, M L; Karras, P; Mamoulis, N (2008). Ring-constrained Join: Deriving Fair Middleman Locations from Pointsets via a Geometric Constraint. In: 11th Intl Conf. on Extending Database Technology (EDBT), Nantes, France, 26 February 2008 - 28 February 2008.

Abstract

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.

Abstract

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.

Statistics

Citations

Altmetrics

Downloads

154 downloads since deposited on 04 Feb 2009
6 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Event End Date:28 February 2008
Deposited On:04 Feb 2009 14:26
Last Modified:10 Aug 2017 18:31
Publisher DOI:https://doi.org/10.1145/1353343.1353416

Download

Preview Icon on Download
Preview
Filetype: PDF
Size: 1MB
View at publisher