When　mobile　users　search　points　of　interest　in　location-based　services,　they　should　always　provide　their　accurate　locations,　which　may　leak　location　privacy　of　themselves.　A　typical　approach　to　protect　users＇　location　privacy　is　to　generate　a　cloaked　region　(CR)　that　encloses　the　users＇　positions.　However,　if　locations　are　continuously　reported,　an　attacker　can　correlate　CRs　according　to　multiple　timestamps　to　accurately　pinpoint　the　users＇　positions　within　a　CR.　In　this　paper,　we　present　a　novel　approach,　called　Extended　Guess-answer　algorithm,　to　protect　against　velocity-based　linkage　attacks　in　location-based　services.　Through　the　interactions　between　the　users　and　the　server,　a　cloaked　region　that　contains　the　current　location　of　users　can　be　generated.　The　experimental　results　show　that　our　approach　is　effective　and　feasible.　©　2014　Binary　Information　Press.