移动定位技术在近年来快速地发展,使得使用全球定位设备（Global Positioning System,通常简称GPS）收集大规模的轨迹数据成为了可能。轨迹数据是基于定位服务（Location Based Service,通常简称LBS）的关键部分。但是轨迹数据由于GPS定位的误差经常充斥着噪音,消除误差最常用的一个办法就是对轨迹数据应用路网匹配算法（Map Matching）,即在数字化的路网中将轨迹数据匹配到路段上。另外,轨迹相似度查询则可以获取轨迹数据中极具价值的信息,例如人类共同运动模式的挖掘,旅游中的路径导航和车辆停泊等应用场景,也可以对大规模的轨迹数据进行压缩,以节省数据所占用的空间资源和管理资源,在轨迹数据分析中扮演了一个重要的角色。随着轨迹数据的规模的不断增加,路网匹配算法需要具备处理更大规模的轨迹数据的能力,并且保障算法时间和空间效率的高效。基于此设计了一种基于预计算机制的路网匹配算法,整合了隐式马尔科夫模型,并提供了开源的实现。方法在预计算过程中对路网中的每一个点使用Dijkstra算法来计算路网节点之间的路径与距离标签,算法的关键点在于搜索的过程中使用了剪枝进行优化,通过保存这样一个路网端点间最短路径的索引,路网匹配过程中最耗时的瓶颈——重复的最短距离查询,被优化为线性时间的搜索O（n）。在保证匹配精确性的同时,算法大幅降低了搜索的空间开销和时间开销。然后,基于现有的动态时间弯曲（DTW）和最长公共道路路段（LCRS）的度量方法实现了轨迹相似度搜索算法,可以进行高效的轨迹相似度查询。最后通过在大规模轨迹数据上的实验,将算法与当下最前沿的相关算法进行对比,证明了基于预计算机制的路网匹配算法和轨迹相似度查询算法时间和空间上的高效性。