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 -