TY - GEN
T1 - MP-trie
T2 - 17th ACM/IFIP/USENIX International Middleware Conference, Middleware Industry 2016
AU - Ganti, Raghu
AU - Srivatsa, Mudhakar
AU - Agrawal, Dakshi
AU - Zerfos, Petros
AU - Ortiz, Jorge
N1 - Funding Information:
Research was sponsored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-09-2-0053 and W911NF-15-R-0003. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. The authors would like to thank Haris Koutsopoulos from KTH, Stockholm, Erling Weibust from IBM Sweden, Inga Maj Eriksson from the Swedish Road Administration and Tomas Julner from Trafik Stockholm for their support and provision of the data from the Stockholm taxicab deployment. We would also like to thank Princeton University for the hardware access.
Publisher Copyright:
© 2016 ACM.
PY - 2016/12/12
Y1 - 2016/12/12
N2 - As spatial data being collected by various industries (e.g., telecommunication, insurance, automotive) is on the increase, indexing and answering queries extremely quickly is necessary. This paper proposes a new mechanism, Mobile PATRICIA-trie (MP-trie), for fast queries on moving objects that provides a 1000x improvement in performance over state-ofthe-art spatial indexing mechanisms. We reduce the problem of spatial indexing to that of prefix-matching over binary strings, which is then coupled with off-the-shelf commercially available content-addressable memory (commonly used in IP routers for forwarding table lookups). We validate our approach on data collected from a real-world deployment in Stockholm, Sweden across 2000 cars for a period of one month.
AB - As spatial data being collected by various industries (e.g., telecommunication, insurance, automotive) is on the increase, indexing and answering queries extremely quickly is necessary. This paper proposes a new mechanism, Mobile PATRICIA-trie (MP-trie), for fast queries on moving objects that provides a 1000x improvement in performance over state-ofthe-art spatial indexing mechanisms. We reduce the problem of spatial indexing to that of prefix-matching over binary strings, which is then coupled with off-the-shelf commercially available content-addressable memory (commonly used in IP routers for forwarding table lookups). We validate our approach on data collected from a real-world deployment in Stockholm, Sweden across 2000 cars for a period of one month.
KW - Hardware acceleration
KW - Nearest neighbors
KW - Spatial indexing
UR - https://www.scopus.com/pages/publications/85009745486
UR - https://www.scopus.com/pages/publications/85009745486#tab=citedBy
U2 - 10.1145/3007646.3007653
DO - 10.1145/3007646.3007653
M3 - Conference contribution
AN - SCOPUS:85009745486
T3 - Proceedings of the Industry Track of the 17th ACM/IFIP/USENIX Middleware Conference, Middleware Industry 2016
BT - Proceedings of the Industry Track of the 17th ACM/IFIP/USENIX Middleware Conference, Middleware Industry 2016
PB - Association for Computing Machinery, Inc
Y2 - 12 December 2016 through 16 December 2016
ER -