一种位置优先并维护最小外接矩形的KD树构建方法

摘要

发明公开了一种位置优先并维护最小外接矩形的KD树构建方法，该方法特点是：（1）在选择划分维度时优先选择空间维度即经度和纬度，当划分后的数据集所包含的对象数目小于一个指定的参数θ后，其后的划分使用全部的维度；（2）在非叶节点上维护一个最小外接矩形即MBR来界定以当前节点为根节点的子树中所包含的数据节点在各个维度上的上下界。由于一种位置优先的本发明LPKD树的构建过程对空间维度进行了优先划分，并且非叶节点维护了一个最小外接矩形MBR，这使得在使用本发明的LPKD树进行基于位置的个性化服务匹配（比如为用户推荐最喜欢的餐馆或者酒店）时，可以快速对最不相关的POI进行有效的剪枝，从而为基于位置的个性化服务的实时性提供有力的保证。