Ring-constrained join: Deriving fair middleman locations from pointsets via a geometric constraint

Man Lung Yiu, Panagiotis Karras, Nikos Mamoulis

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)


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 〈p, q〉 (where p εP, q ε Q) satisfying an intuitive geometric constraint: the smallest circle enclosing p and q contains no other points in P, Q. This new operation has important applications in decision support, e.g., placing recycling stations at fair locations between restaurants and residential complexes. Clearly, RCJ is defined based on a geometric constraint but not on distances between points. Thus, our operation is fundamentally different from the conventional distance joins and closest pairs problems. We are not aware of efficient processing algorithms 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 develop 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.
Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings
Number of pages12
Publication statusPublished - 16 May 2008
Externally publishedYes
Event11th International Conference on Extending Database Technology, EDBT 2008 - Nantes, France
Duration: 25 Mar 200829 Mar 2008


Conference11th International Conference on Extending Database Technology, EDBT 2008

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems
  • Software

Cite this