Computation and Monitoring of Exclusive Closest Pairs
Computation and Monitoring of Exclusive Closest Pairs
复制标题
DOI：
10.1109/tkde.2008.85
复制
发表时间：
2008-12
影响因子：
8.9
通讯作者：
Leong Hou U;N. Mamoulis;Man Lung Yiu
中科院分区：
文献类型：
--
作者：
Leong Hou U;N. Mamoulis;Man Lung Yiu
给定两个数据集A和B，它们的排他最近对（ECP）联接是来自两个数据集的对象的一对一分配，使得（i）A乘以B中的最近对（a，B）在结果中，以及（ii）通过分别从A，B中移除对象a，B，并且递归地搜索下一个最近对来确定剩余的对。排他最近对的一个真实的应用是（汽车，停车位）分配的计算。本文介绍了这个问题，并提出了几种解决方案，解决它在主存中，利用空间分区。此外，我们定义了一个动态版本的问题，其目标是不断监测ECP加入解决方案，在环境中，加入数据集的位置和内容的变化。最后，我们研究了查询的扩展形式，其中两个连接集中的一个中的对象（例如，停车位）具有容量约束，允许它们与来自另一组的多个对象匹配（例如，汽车）。我们展示了我们的技术如何可以扩展到这个变体，并将其与以前的解决方案进行比较。在一个系统原型上的实验结果证明了所提出的算法的有效性和适用性。
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 times 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. A real application of exclusive closest pairs is the computation of (car, parking slot) assignments. This paper introduces the problem and proposes several solutions that solve it in main-memory, exploiting space partitioning. In addition, we define a dynamic version of the problem, where the objective is to continuously monitor the ECP join solution, in an environment where the joined datasets change positions and content. Finally, we study an extended form of the query, where objects in one of the two joined sets (e.g., parking slots) have a capacity constraint, allowing them to match with multiple objects from the other set (e.g., cars). We show how our techniques can be extended for this variant and compare them with a previous solution to this problem. Experimental results on a system prototype demonstrate the efficiency and applicability of the proposed algorithms.