位置服务的分布式k-NN查询处理

# 位置服务的分布式 k-NN 查询处理 ## 1 引言 随着定位导航技术的进步和移动设备的广泛普及，基于位置的服务（LBS）受到了越来越多的关注。然而，目前大多数与 LBS 系统相关的研究活动都是单节点导向的，难以处理至少数百万个移动对象的极端情况。 GALIS（Gracefully Aging Location Information System）是一种基于集群的分布式计算系统架构，由多个计算节点组成，每个节点负责保存不同地理区域和不同时区的记录。GALIS 由控制移动对象当前位置信息的 SLDS（短期位置数据子系统）和控制过去位置信息的 LLDS（长期位置数据子系统）组成。 为了实现位置服务，需要支持基于项目的查询、范围查询和 k-NN（k 最近邻）查询。对于 k-NN 查询，用户指定一个点，系统需要返回 k 个最近的移动对象。本文提出了一种用于多个计算节点上移动对象的分布式 k-NN 查询处理方案，以及一种混合 k-NN 方案，该方案利用范围查询代替相邻重叠节点的 k-NN 查询，从而使查询处理成本降低 30%。 ## 2 朴素的分布式 k-NN 查询处理方案 ### 2.1 总体方案 二维空间被划分为 n 个空间区域，一维时间轴被划分为 p 个时区。LBS 系统处理的地理区域的一个区域（或分区）称为宏单元。每个宏单元覆盖一个方形区域，默认单位长度为 25.6 公里，但可以不同设置。不同宏单元覆盖的区域可能大小不同。 对于当前（最近观察到）位置的记录，空间区域中的移动项由 SDP 节点覆盖。对于位置历史记录，空间区域中的移动项最多由 p 个 LDP 节点处理。这里，p 表示时区（或时间区域）的数量。 k-NN 查询可以在单个节点上执行，对于多个节点，需要考虑相邻重叠节点的移动对象。查询处理系统由索引创建器、查询分析器、查询检查器和查询创建器组成。具体流程如下： 1. 索引创建器利用每个节点中存储的移动对象的位置信息配置索引结构。 2. 查询分析器使用适当的索引结构处理给定的查询。 3. 查询检查器根据当前节点的查询结果检查相邻节点，以确定是否需要将查询传输到相邻节点。 4. 查询创建器为目标相邻节点创建部分查询，并将该部分查询发送到相邻节点。 5. 所有相邻节点的查询处理结果被组合，索引创建器创建一个临时 R 树索引结构。 6. 最后使用最终的 R 树处理 k-NN 查询，并将结果返回给用户。 下面是该流程的 mermaid 流程图： ```mermaid graph LR A[索引创建器] --> B[查询分析器] B --> C[查询检查器] C --> D{是否传输查询} D -- 是 --> E[查询创建器] E --> F[相邻节点查询处理] F --> G[结果组合] G --> H[临时 R 树创建] H --> I[k-NN 查询处理] I --> J[返回结果] D -- 否 --> I ``` ### 2.2 查询在相邻节点的分布 如果计算节点的数量较少，可以在所有节点上处理相同的 k-NN 查询，并组合所有查询结果。但如果节点数量较大，在所有节点（包括当前节点）上并发处理相同的查询可能会导致计算资源的严重浪费。 为了减少计算开销，需要确定相邻重叠节点，并在 k-NN 查询的查询点靠近当前节点边界时将查询传输到这些节点。确定相邻节点的步骤如下： 1. 运行当前节点的 k-NN 查询。 2. 计算查询点 Pq 与第 k 个最近点 Pk 之间的距离 R。 3. 计算查询点 Pq 与每个方向边界点（北边界点 Pbn、东边界点 Pbe、南边界点 Pbs 和西边界点 Pbw）之间的距离 N、S、E、W。 4. 距离（N、S、E、W）小于 R 的方向上的相邻节点是要发送查询的目标节点。 5. 还需要将查询传输到与当前节点对角位置且与选定目标节点相邻的相邻节点。 以下是确定相邻节点的算法： ```plaintext Algorithm 1. Determining Neighboring Nodes to Send Queries ( ) // Pbn, Pbe, Pbs, Pbw : boundary points for the current node // R : distance between the query point and Pk // N, S, E, W: the distance between the query point and the boundary points in each direction // T: target node list begin if (N<R) then add north node to T; if (E<R) add east node and northeast node to T; if (W<R) add west node and northwest node to T; else if (S<R) then add south node to T; if (E<R) add east node and southeast node to T; if (W<R) add west node and southwest node to T; else if (E<R) then add east node to T; else if (W<R) then add west node to T; else add empty node to T; endif end. ``` 对于相邻重叠节点，位于当前节点与相邻节点边界上的边界点成为新的查询点。对于对角位置的相邻节点，当前节点面向相邻节点的一个角点成为新的查询点。 ## 3 混合 k-NN 查询处理 通过利用范围查询代替相邻重叠节点的 k-NN 查询，可以减少整个查询处理时间，同时获得完全相同的查询结果。这种稍微修改的方案称为混合 k-NN 查询处理方案。 在混合方案中，查询处理系统的查询检查器将 k-NN 查询转换为范围查询。具体步骤如下： 1. 再次使用查询点 Pq 与第 k 个最近点 Pk 之间的距离 R。 2. 定义 Rn（北半径）、Rw（西半径）、Rs（南半径）和 Re（东半径）为与 R 相同的距离到相应方向。 3. 定义 Pqn（北查询点）、Pqw（西查询点）、Pqs（南查询点）和 Pqe（东查询点）为每个位于相应方向距离 R 的虚拟点。 以下是创建范围查询的算法： ```plaintext Algorithm 2. Range Query Creation (d direction_of_neighbor_node) // Pbn, Pbe, Pbs, Pbw : boundary points for the current node // Pqn, Pqw, Pqs, Pqe : shifted query points to the corresponding direction with distance R begin if (d=north) then create query with range (Pqw(x), Pqn(y), Pqe (x), Pbn (y)); if (d=south) then create query with range (Pqw(x), Pqs(y), Pqe (x), Pbs (y)); if (d=east) then create query with range (Pqe(x), Pqn(y), Pbe(x), Pqs(y)); if (d=west) then create query with range (Pqw(x), Pqn(y), Pbw(x), Pqs(y)); end. ``` 下面是创建范围查询的 mermaid 流程图： ```mermaid graph LR A[获取距离 R] --> B[定义半径和查询点] B --> C{方向判断} C -- 北 --> D[创建北范围查询] C -- 南 --> E[创建南范围查询] C -- 东 --> F[创建东范围查询] C -- 西 --> G[创建西范围查询] ``` ## 4 实验 为了排除节点之间的通信延迟，在单个系统上配置了四个节点。使用配备 3.0 GHz D 处理器和 1GB 内存的 PC，运行 Red Hat FEDARA Core 4 操作系统。使用加州大学河滨分校的 Marios Hadjieleftheriou 开发的对象位置信息生成器生成移动对象。 实验重复 18 次，每次逐渐增加每个节点中的移动对象数量，从 1000 个对象开始，直到达到 50000 个对象。为了比较查询处理时间，对每个查询的处理时间进行了 5 次测量，并使用排除最高和最低值后的 3 次测量值的平均值。k 值固定为 10。 实验结果表明： | 方案 | 节点 1 处理时间 | 其他节点处理时间 | 总体表现 | | ---- | ---- | ---- | ---- | | 朴素 k-NN 方案 | 与混合方案相同 | 较慢 | 较差 | | 混合 k-NN 方案 | 与朴素方案相同 | 较快 | 较好 | 混合 k-NN 方案在其他节点上的查询处理时间比朴素方案快，因为混合方案利用范围查询代替相邻重叠节点的 k-NN 查询。同时，比较了单节点上 80000 个对象的 k-NN 查询处理结果与多个计算节点（每个节点 20000 个对象）上的朴素方案和混合方案的查询结果，三种方法的最终结果相同，这意味着朴素和混合 k-NN 查询处理方案不会遗漏任何正确的对象。 ## 5 结论 本文提出了一种用于多个计算节点上移动对象的分布式 k-NN 查询处理方案，以及一种混合 k-NN 方案。朴素方法首先在目标节点上处理 k-NN 查询，然后决定查询区域是否与其他节点重叠，最后处理相邻重叠节点的 k-NN 查询。混合 k-NN 方案利用范围查询代替相邻重叠节点的 k-NN 查询，从而降低了查询处理成本，同时提供了完全相同的查询结果。通过实验证明了混合 k-NN 方案相对于朴素 k-NN 方案的效率。未来还需要对数百万个移动对象的更重流量进行进一步的实验。 ### 5.1 混合 k-NN 方案优势分析 混合 k-NN 方案之所以能够降低查询处理成本，主要基于以下几点原因： - **减少计算复杂度**：范围查询相较于 k-NN 查询，计算复杂度更低。在处理相邻重叠节点时，范围查询可以一次性获取一定区域内的对象，避免了 k-NN 查询中对每个对象进行距离计算和排序的过程，从而减少了计算量。 - **避免重复计算**：在朴素 k-NN 方案中，可能会对相邻节点进行重复的 k-NN 查询，导致计算资源的浪费。而混合 k-NN 方案通过范围查询，能够更精准地获取所需对象，避免了不必要的重复计算。 ### 5.2 未来研究方向 虽然混合 k-NN 方案在实验中表现出了较好的效率，但在实际应用中，还需要考虑更多复杂的情况。以下是一些未来的研究方向： - **处理大规模移动对象**：目前的实验仅处理了每个节点最多 50000 个移动对象的情况。在实际的 LBS 系统中，可能需要处理数百万甚至更多的移动对象。因此，需要进一步研究如何优化混合 k-NN 方案，以应对大规模移动对象的查询需求。 - **考虑动态变化**：移动对象的位置是动态变化的，而本文的方案主要针对静态或准静态的位置数据。未来的研究可以考虑如何实时更新对象的位置信息，并及时调整查询处理策略，以保证查询结果的准确性和及时性。 - **多维度查询**：除了地理位置信息，LBS 系统还可以包含其他维度的信息，如时间、属性等。未来的研究可以探索如何在混合 k-NN 方案中集成多维度信息，以支持更复杂的查询需求。 ### 5.3 总结 本文围绕位置服务的分布式 k-NN 查询处理展开研究，提出了朴素的分布式 k-NN 查询处理方案和混合 k-NN 查询处理方案。通过实验对比，验证了混合 k-NN 方案在查询处理成本上的优势。同时，也指出了未来研究的方向，为进一步优化位置服务的查询处理提供了思路。 以下是两种方案的对比表格： | 方案 | 处理方式 | 计算复杂度 | 查询处理成本 | 适用场景 | | ---- | ---- | ---- | ---- | ---- | | 朴素 k-NN 方案 | 在当前节点和相邻节点都执行 k-NN 查询 | 高 | 高 | 节点数量较少，数据量较小 | | 混合 k-NN 方案 | 当前节点执行 k-NN 查询，相邻节点执行范围查询 | 低 | 低 | 节点数量较多，数据量较大 | 下面是整个查询处理流程的 mermaid 流程图： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(初始化查询):::process B --> C(当前节点 k-NN 查询):::process C --> D(计算距离 R):::process D --> E{是否与相邻节点重叠}:::decision E -- 是 --> F(确定相邻节点):::process F --> G{选择方案}:::decision G -- 朴素 k-NN 方案 --> H(相邻节点 k-NN 查询):::process G -- 混合 k-NN 方案 --> I(相邻节点范围查询):::process H --> J(结果组合):::process I --> J J --> K(最终 k-NN 查询处理):::process K --> L([返回结果]):::startend E -- 否 --> K ``` 综上所述，混合 k-NN 方案在位置服务的分布式查询处理中具有明显的优势，但仍有许多方面需要进一步研究和优化。希望本文的研究能够为相关领域的发展提供一定的参考和借鉴。