Continuous monitoring of exclusive closest pairs

U. Leong Hou, Nikos Mamoulis, Man Lung Yiu

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

2 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 languageEnglish
Title of host publicationAdvances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings
Pages1-19
Number of pages19
Publication statusPublished - 1 Dec 2007
Externally publishedYes
Event10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007 - Boston, MA, United States
Duration: 16 Jul 200718 Jul 2007

Publication series

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

Conference

Conference10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007
CountryUnited States
CityBoston, MA
Period16/07/0718/07/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this