Approximate entity extraction in temporal databases
Approximate entity extraction in temporal databases
复制标题
DOI：
10.1007/s11280-011-0109-5
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
Wei Lu;G. Fung;Xiaoyong Du;Xiaofang Zhou;Lijiang Chen;K. Deng
中科院分区：
文献类型：
--
作者：
Wei Lu;G. Fung;Xiaoyong Du;Xiaofang Zhou;Lijiang Chen;K. Deng
我们研究的问题，有效地提取Kentities，在时态数据库中，这是最相似的一个给定的搜索查询。这个问题在关系数据库中得到了很好的研究，其中每个实体被表示为单个记录，并且存在多种方法来定义记录和搜索查询之间的相似性。然而，在时态数据库中，每个实体都被表示为历史记录的序列。如何正确地定义时态数据库中各个实体的相似度仍然是一个悬而未决的问题。主要的挑战是，当用户发出对实体的搜索查询时，他或她倾向于在不同的时间点混淆相同实体的信息。因此，在基于记录粒度的关系数据库中使用的方法无法进一步工作。相反，我们将每个实体视为一组“虚拟记录”，其中“虚拟记录”的属性值可以来自同一实体的不同记录。本文提出了一种新的评价模型，该模型可以有效地量化每个“虚拟记录”与查询之间的相似度，并将其“虚拟记录”的最大相似度作为实体的相似度。对于每个实体，由于其“虚拟记录”的数量是指数级的，计算实体的相似性是具有挑战性的。在此基础上，提出了一种基于边界剪枝细化策略的支配树算法（DTA），有效地提取K个具有最大相似度的实体。我们在真实的和合成数据集上进行了广泛的实验。令人鼓舞的结果表明，我们的模型来定义每个实体和搜索查询之间的相似性是有效的，所提出的DTA可以执行至少两个数量级的性能相比，天真的方法。
We study the problem of efficiently extractingKentities, in a temporal database, which are most similar to a given search query. This problem is well studied in relational databases, where each entity is represented as a single record and there exist a variety of methods to define the similarity between a record and the search query. However, in temporal databases, each entity is represented as a sequence of historical records. How to properly define the similarity of each entity in the temporal database still remains an open problem. The main challenging is that, when a user issues a search query for an entity, he or she is prone to mix up information of the same entity at different time points. As a result, methods, which are used in relational databases based on record granularity, cannot work any further. Instead, we regard each entity as a set of “virtual records”, where attribute values of a “virtual record” can be from different records of the same entity. In this paper, we propose anovel evaluation model, based on which the similarity between each “virtual record” and the query can be effectively quantified, and the maximum similarity of its “virtual records” is taken as the similarity of an entity. For each entity, as the number of its “virtual records” is exponentially large, calculating the similarity of the entity is challenging. As a result, we further propose aDominatingTreeAlgorithm (DTA), which is based on the bounding-pruning-refining strategy, to efficiently extractKentities with greatest similarities. We conduct extensive experiments on both real and synthetic datasets. The encouraging results show that our model for defining the similarity between each entity and the search query is effective, and the proposed DTA can perform at least two orders of magnitude improvement on the performance comparing with the naive approach.