Title :
Trajectory Pattern Matching Based on Bit-Parallelism for Large GPS Data
Author :
Sasakawa, Hirohito ; Arimura, Hiroki
Author_Institution :
Grad. Sch. of IST, Hokkaido Univ., Sapporo, Japan
Abstract :
In this paper, we study massive trajectory search based on string matching technology. We first propose byte-oriented encoding scheme for trajectory data allowing multi-resolution search. Then, we present an efficient bit-parallel trajectory matching algorithm on byte-oriented encoded texts based on Extended SHIFT-AND method (Navarro and Raffinot, RECOMB 2001). Finally, we ran experiments on the real world trajectory data to evaluate the efficiency of the proposed algorithm. The results showed good performance enough for real applications.
Keywords :
Global Positioning System; encoding; information retrieval; mobile computing; sensors; string matching; text analysis; bit-parallelism; byte-oriented encoded texts; byte-oriented encoding scheme; extended SHIFT-AND method; large GPS data; mobile devices; mobile sensors; multiresolution search; string matching technology; trajectory data; trajectory pattern matching; trajectory search; Databases; Educational institutions; Encoding; Global Positioning System; Pattern matching; Search problems; Trajectory; GPS trajectory data; bit-parallel string matching; byte-oriented encoding; regular expression matching;
Conference_Titel :
Advanced Applied Informatics (IIAIAAI), 2012 IIAI International Conference on
Conference_Location :
Fukuoka
Print_ISBN :
978-1-4673-2719-0
DOI :
10.1109/IIAI-AAI.2012.22
