Continuous monitoring of exclusive closest pairs

U. Leong Hou; Nikos Mamoulis; Man Lung Yiu

Continuous monitoring of exclusive closest pairs

U. Leong Hou, Nikos Mamoulis, Man Lung Yiu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Advances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings
Pages	1-19
Number of pages	19
Publication status	Published - 1 Dec 2007
Externally published	Yes
Event	10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007 - Boston, MA, United States Duration: 16 Jul 2007 → 18 Jul 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4605 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007
Country/Territory	United States
City	Boston, MA
Period	16/07/07 → 18/07/07

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Cite this

@inproceedings{27535a80888741ed8dd8fc9a24ad8e50,

title = "Continuous monitoring of exclusive closest pairs",

abstract = "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.",

author = "{Leong Hou}, U. and Nikos Mamoulis and Yiu, {Man Lung}",

year = "2007",

month = dec,

day = "1",

language = "English",

isbn = "9783540735397",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "1--19",

booktitle = "Advances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings",

note = "10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007 ; Conference date: 16-07-2007 Through 18-07-2007",

}

Leong Hou, U, Mamoulis, N & Yiu, ML 2007, Continuous monitoring of exclusive closest pairs. in Advances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4605 LNCS, pp. 1-19, 10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007, Boston, MA, United States, 16/07/07.

Continuous monitoring of exclusive closest pairs. / Leong Hou, U.; Mamoulis, Nikos; Yiu, Man Lung.
Advances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings. 2007. p. 1-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4605 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

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 -

Continuous monitoring of exclusive closest pairs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this