基于关键词选择最大化时空文本对象影响力

### 基于关键词选择最大化时空文本对象影响力 #### 1. 相关研究概述 在时空文本查询领域，不同学者提出了多种方法： - **Gkorgkas等人**：旨在找到满足时空查询且具有期望空间属性的最优关键词覆盖。关键词覆盖是指一组对象，每个对象与时空查询中的一个术语精确关联。 - **Lu等人**：研究反向空间和文本k最近邻搜索问题。给定查询点q，目标是定位q为k最近邻之一的时空文本对象集。对象间距离是文本和欧几里得距离的线性组合，并引入了IUR - 树，它是IR - 树的改进，每个节点包含以该节点为根的子树中对象所含术语的并集和交集。 - **Wu等人**：提出W - IR树，与IR - 树类似，但主要基于文本距离构建。对于批量查询，只有包含查询所有术语的对象才被认为与查询相关，该树在这种情况下性能有所提升。 - **Gao等人**：提出用于处理反向布尔top - k空间关键词查询的过滤 - 细化框架，关注时空文本对象必须包含查询所有术语才能作为有效结果的查询。 - **Lin等人**：研究确定时空文本对象文本描述中导致该对象在特定查询或特定区域中排名较高的重要术语。 #### 2. 预备知识 - **时空文本对象**：设D为对象集，每个对象o表示为元组o = ⟨o.T, o.L⟩，其中o.T是描述o特征的关键词集，o.L是R²中的点描述o的位置。A = ⋃ₒ∈D o.T是D中所有关键词的集合，称这些对象为时空文本对象，对象o的大小为|o.T|。 - **top - k空间关键词查询** - **用户偏好查询**：用户偏好查询u表示为元组u = ⟨u.T, u.L, α⟩，u.T ⊆ A是描述用户期望特征的文本，u.L ∈ R²是期望位置，α ∈ [0, 1]表示位置相对于匹配期望特征的重要性。 - **对象得分计算**：使用公式f(o, u) = α × δ(o.L, u.L) + (1 - α) × θ(o.T, u.T)计算对象得分，其中δ(o.L, u.L)是空间距离，θ(o.T, u.T)是文本距离。假定较低得分更好，空间和文本距离都归一化到[0, 1]区间，若θ(o.T, u.T) = 1，则f(o, u) = 1.0。文本相关性采用时空文本对象描述o.T和用户偏好关键词集u.T的归一化术语交集，即θ(o.T, u.T) = 1 - |o.T ∩ u.T| / |u.T|。 - **top - k查询定义**：给定时空文本对象集D、术语集A、评分函数f、整数k和查询u，top - k查询的结果集TOPk(u)是时空文本对象集，满足TOPk(u) ⊆ D，|TOPk(u)| = k，且对于任意o₁ ∈ TOPk(u)，o₂ ∈ D - TOPk(u)，有o₁.T ∩ u.T ≠ ∅且f(o₁, u) ≤ f(o₂, u)。若对象o属于用户偏好u的TOPk(u)集，则称o对u可见。 - **反向top - k查询**：给定时空文本对象集D、用户查询集U、评分函数f、整数k和时空文本对象q，反向top - k查询的结果集RTOPk(q)满足RTOPk(q) ⊆ U，u ∈ RTOPk(q)当且仅当存在o ∈ TOPk(u)使得f(q, u) ≤ f(o, u)。查询对象q的RTOPk集的基数称为对象的影响力得分，记为I(q)。 - **IR树**：是一种用于处理空间关键词查询的先进索引结构，是R树的一种，每个节点与以该节点为根的子树中对象的倒排索引相关联。它能检索到靠近查询点但文本不相关的对象，这对识别可能有趣的术语很重要。每个叶节点包含节点中时空文本对象的倒排索引，由最小边界矩形（MBR）和伪文档组成的时空文本伪对象表征；非叶节点包含子节点时空文本伪对象的倒排索引，也由类似的时空文本伪对象表征。 #### 3. 问题定义 给定时空文本对象集D和时空文本偏好集U，对象q的影响力得分是q对其可见的偏好数量。假设时空文本对象的位置不能改变，提高q影响力得分的唯一方法是增强其文本描述，以增加q与U中用户偏好的文本相关性。研究的问题是找到一组b个术语，添加到q的文本描述中能最大化q的影响力得分，称为Best - terms问题。 - **Best - terms查询定义**：给定时空文本对象集D、术语集A = ⋃ₒ∈D o.T、查询集U、评分函数f、整数k、时空文本对象q = ⟨q.T, q.L⟩和整数b，集合BT是一组术语，满足BT ⊆ A，BT ∩ q.T = ∅，|BT| ≤ b，且对于任意T ⊆ A - BT，|T| ≤ b，有I(q₁) ≥ I(q₂)，其中q₁ = ⟨q.T ∪ BT, q.L⟩，q₂ = ⟨q.T ∪ T, q.L⟩。 - **Best - terms问题复杂度**：Best - terms问题是NP难的。通过研究Best - terms查询的一个特殊情况，即判断是否存在一组术语