A compact representation for trips over networks built on self-indexes
作者：
Highlights：
• We provide a representation for trips over networks and answer counting-based queries.
• We adapt a Compressed Suffix Array to deal with the spatial component of trips.
• We use a wavelet matrix or a Hu–tucker-shaped Wavelet Tree for the temporal component.
• Experiments show space needs until a 50% when compared with a plain representation.
• Experiments show counting-based query-times typically within 1–1000 µs.
摘要
•We provide a representation for trips over networks and answer counting-based queries.•We adapt a Compressed Suffix Array to deal with the spatial component of trips.•We use a wavelet matrix or a Hu–tucker-shaped Wavelet Tree for the temporal component.•Experiments show space needs until a 50% when compared with a plain representation.•Experiments show counting-based query-times typically within 1–1000 µs.
论文关键词：Trips on networks,Counting queries,Self-index,Compression
论文评审过程：Received 23 May 2017, Revised 21 June 2018, Accepted 25 June 2018, Available online 6 July 2018, Version of Record 18 July 2018.
论文官网地址：https://doi.org/10.1016/j.is.2018.06.010
