基于位置序列的广义后缀树用户相似性计算方法
来源：计算机应用杂志2015年第6期北京时间：
作者：肖艳丽, 张振宇, 袁江涛
单位：新疆大学 信息科学与工程学院, 乌鲁木齐 830046
摘要：为了解决移动数据形成的轨迹间用户相似性问题,提出了一种基于位置序列的广义后缀树(LSGST)用户相似性计算方法。该算法首先从移动数据中抽取位置序列,同时将位置序列映射为字符串,完成了对位置序列的处理到对字符串处理的转化工作;然后,构建不同用户间的位置序列广义后缀树;最后,分别从经过的相似地方个数、最长公共子序列、频繁公共位置序列三方面对相似性进行具体计算。理论分析和仿真表明,该算法提出的三个计算指标在计算相似性方面具有理想的效果;除此之外,与构造后缀树的普通方法相比,时间复杂度较低;与动态规划和朴素字符串匹配方法相比,该算法在寻找最长公共子串、频繁公共位置序列时,效率更高。实验结果表明LSGST能够有效测量相似性,同时减少了寻找测量指标时需要处理的轨迹数据量,并在时间复杂度方面明显优于对比算法。
关键词：移动数据,用户相似性,位置序列,字符串匹配,广义后缀树
基金资助：国家自然科学基金资助项目(61262089,61262087);新疆教育厅高校教师科研计划重点项目 (XJEDU2012I09);新疆大学博士毕业生科研启动基金资助项目 (BS110127)。
