TY - GEN

T1 - Continuous monitoring of exclusive closest pairs

AU - Leong Hou, U.

AU - Mamoulis, Nikos

AU - Yiu, Man Lung

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Given two datasets A and B, their exclusive closest pairs (ECP) join is a one-to-one assignment of objects from the two datasets, such that (i) the closest pair (a, b) in A × B is in the result and (ii) the remaining pairs are determined by removing objects a, b from A, B respectively, and recursively searching for the next closest pair. An application of exclusive closest pairs is the computation of (car, parking slot) assignments. In this paper, we propose algorithms for the computation and continuous monitoring of ECP joins in memory, given a stream of events that indicate dynamic assignment requests and releases of pairs. Experimental results on a system prototype demonstrate the efficiency of our solutions in practice.

AB - Given two datasets A and B, their exclusive closest pairs (ECP) join is a one-to-one assignment of objects from the two datasets, such that (i) the closest pair (a, b) in A × B is in the result and (ii) the remaining pairs are determined by removing objects a, b from A, B respectively, and recursively searching for the next closest pair. An application of exclusive closest pairs is the computation of (car, parking slot) assignments. In this paper, we propose algorithms for the computation and continuous monitoring of ECP joins in memory, given a stream of events that indicate dynamic assignment requests and releases of pairs. Experimental results on a system prototype demonstrate the efficiency of our solutions in practice.

UR - http://www.scopus.com/inward/record.url?scp=37849048363&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 9783540735397

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 19

BT - Advances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings

T2 - 10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007

Y2 - 16 July 2007 through 18 July 2007

ER -