The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Topological signatures for fast mobility analysis
Open accessAbstract
Analytic methods can be difficult to build and costly to train for mobility data. We show that information about the topology of the space and how mobile objects navigate the obstacles can be used to extract insights about mobility at larger distance scales. The main contribution of this paper is a topological signature that maps each trajectory to a relatively low dimensional Euclidean space, so that now they are amenable to standard analytic techniques. Data mining tasks: nearest neighbor search with locality sensitive hashing, clustering, regression, etc., work more efficiently in this signature space. We define the problem of mobility prediction at different distance scales, and show that with the signatures simple k nearest neighbor based regression perform accurate prediction. Experiments on multiple real datasets show that the framework using topological signatures is accurate on all tasks, and substantially more efficient than machine learning applied to raw data. Theoretical results show that the signatures contain enough topological information to reconstruct non-self-intersecting trajectories upto homotopy type. The construction of signatures is based on a differential form that can be generated in a distributed setting using local communication, and a signature can be locally and inexpensively updated and communicated by a mobile agent.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The text we found for this paper looks like another document, so the self-check wasn’t run.
Citations
Cites
TensorFlow: A system for large-scale machine learningPreprint
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al. (2016) · arXiv (Cornell University) · doi:10.5555/3026877.3026899 · Cited by 16,548
Dynamic Programming Algorithm Optimization for Spoken Word Recognition
Sakoe, H., & Chiba, S. (1978) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1978.1163055 · Cited by 6,727
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997857 · Cited by 2,971
Learning to forget: continual prediction with LSTM
Gers, F. A. (1999) · International Conference on Artificial Neural Networks · doi:10.1049/cp:19991218 · Cited by 2,467
Maximum Entropy Inverse Reinforcement Learning
Ziebart, B. D., Maas, A. L., Bagnell, J. A., & Dey, A. K. (2018) · doi:10.1184/r1/6555512 · Cited by 1,868
Computational topology an introduction
Edelsbrunner, H., & Harer, J. (2010) · Cited by 1,718
COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
Alt, H., & Godau, M. (1995) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195995000064 · Cited by 1,051
Edelsbrunner, H., & Harer, J. (2009) · American Mathematical Society eBooks · doi:10.1090/mbk/069 · Cited by 829
Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks
Liu, T., Bahl, P., & Chlamtac, I. (1998) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.709453 · Cited by 561
Discrete exterior calculusPreprint
Marsden, J. E., & Hirani, A. N. (2003) · arXiv (Cornell University) · doi:10.7907/zhy8-v329 · Cited by 491
Boundary recognition in sensor networks by topological methods
Wang, Y., Gao, J., & Mitchell, J. S. B. (2006) · Proceedings of the 28th Annual International Conference on Mobile Computing And Networking · doi:10.1145/1161089.1161104 · Cited by 374
From GPS traces to a routable road map
Cao, L., & Krumm, J. C. (2009) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1653771.1653776 · Cited by 330
Discrete Differential Geometry
Bobenko, A. I., & Suris, Y. B. (2008) · Graduate studies in mathematics · doi:10.1090/gsm/098 · Cited by 268
Destination prediction by sub-trajectory synthesis and privacy protection against such prediction
Xue, A. Y., Zhang, R., Zheng, Y., Xie, X., Huang, J., & Xu, Z. (2013) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544830 · Cited by 255
Computing minimum length paths of a given homotopy class
Hershberger, J. E., & Snoeyink, J. S. (1994) · Computational Geometry · doi:10.1016/0925-7721(94)90010-8 · Cited by 226
CRAWDAD dataset roma/taxi (v. 2014-07-17)
Bracciale, L., Bonola, M., Loreti, P., Bianchi, G., Amici, R., & Rabuffi, A. (2014) · CRAWDAD wireless network data archive · doi:10.15783/c7qc7m · Cited by 205
Modeling Trajectories with Recurrent Neural Networks
Wu, H., Chen, Z., Sun, W., Zheng, B., & Wang, W. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/430 · Cited by 163
Kinsey, L. C. (1993) · Undergraduate texts in mathematics · doi:10.1007/978-1-4612-0899-0 · Cited by 130
Greedy routing with guaranteed delivery using Ricci flows
Sarkar, R., Yin, X., Gao, J., Luo, F., & Gu, X. D. (2009) · doi:10.5555/1602165.1602178 · Cited by 110
Self-citationNath, B., & Niculescu, D. (2003) · ACM SIGCOMM Computer Communication Review · doi:10.1145/774763.774788 · Cited by 109
T-CONV: A Convolutional Neural Network for Multi-scale Taxi Trajectory Prediction
Lv, J., Li, Q., Sun, Q., & Wang, X. (2018) · IEEE International Conference on Big Data and Smart Computing (BigComp) · doi:10.1109/bigcomp.2018.00021 · Cited by 100
Target Enumeration via Euler Characteristic Integrals
Baryshnikov, Y. M., & Ghrist, R. (2009) · SIAM Journal on Applied Mathematics · doi:10.1137/070687293 · Cited by 89
Approximate nearest neighbor algorithms for Frechet distance via product metrics
Indyk, P. (2002) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/513400.513414 · Cited by 87
Buchin, K., Buchin, M., van Kreveld, M. J., Löffler, M., Silveira, R. I., Wenk, C., & Wiratma, L. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15775-2_40 · Cited by 71
Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
Chambers, E. W., de Verdière, É. C., Erickson, J., Sylvain Lazard, A., Lazarus, F., & Thite, S. (2009) · Computational Geometry · doi:10.1016/j.comgeo.2009.02.008 · Cited by 67
Network sketching or: "How Much Geometry Hides in Connectivity?--Part II"
Funke, S., & Milosavljević, N. (2007) · Max Planck Institute for Plasma Physics · doi:10.5555/1283383.1283486 · Cited by 48
Srivatsa, M., Ganti, R., Wang, J., & Kolar, V. (2013) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2525314.2525466 · Cited by 35
Differential Forms for Target Tracking and Aggregate Queries in Distributed Networks
Sarkar, R., & Gao, J. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2012.2220857 · Cited by 30
Self-citationPersistence based online signal and trajectory simplification for mobile devices
Katsikouli, P., Sarkar, R., & Gao, J. (2014) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2666310.2666388 · Cited by 30
Self-citationMeasuring similarity between curves on 2-manifolds via homotopy area
Chambers, E. W., & Wang, Y. (2013) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/2462356.2462375 · Cited by 26
Multi-resolution sketches and locality sensitive hashing for fast trajectory processing
Astefanoaei, M., Cesaretti, P., Katsikouli, P., Goswami, M., & Sarkar, R. (2018) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/3274895.3274943 · Cited by 25
Self-citationTopological trajectory clustering with relative persistent homology
Pokorny, F. T., Goldberg, K. Y., & Kragić, D. (2016) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2016.7487092 · Cited by 24
Zeng, J., Telang, G., Johnson, M. P., Sarkar, R., Gao, J., Arkin, E. M., & Mitchell, J. S. B. (2017) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/3084041.3084056 · Cited by 12
Self-citationDecentralized human trajectories tracking using hodge decomposition in sensor networks
Yin, X., Ni, C.-C., Ding, J., Han, W., Zhou, D., Gao, J., & Gu, X. D. (2015) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2820783.2820844 · Cited by 9
Distributed submodular maximization
MirzasoleimanBaharan, KarbasiAmin, SarkarRik, & KrauseAndreas (2016) · Journal of Machine Learning Research · doi:10.5555/2946645.3053517 · Cited by 3
Flagged first, then by citations
Research works printed but not linked: 4
- 10.1007/s00453-012-9654-2 · DOI
- Jimmy Ba Diederik P. Kingma . 2015 . Adam: A Method for Stochastic Optimization . In Proceedings of the 3rd International Conference on Learning Representations (ICLR) (ICLR '15) . Jimmy Ba Diederik P. Kingma. 2015. Adam: A Method for Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR) (ICLR '15).
- Anne Driemel and Francesco Silvestri . 2017 . Locality-Sensitive Hashing of Curves. In 33rd International Symposium on Computational Geometry (SoCG 2017), Vol. 77 . 37:1--37:16. Anne Driemel and Francesco Silvestri. 2017. Locality-Sensitive Hashing of Curves. In 33rd International Symposium on Computational Geometry (SoCG 2017), Vol. 77. 37:1--37:16.
- Panagiota Katsikouli , Maria Astefanoaei , and Rik Sarkar . 2018 . Distributed Mining of Popular Paths in Road Networks. In DCOSS 2018-International Conference on Distributed Computing in Sensor Systems. IEEE, 1--8. Panagiota Katsikouli, Maria Astefanoaei, and Rik Sarkar. 2018. Distributed Mining of Popular Paths in Road Networks. In DCOSS 2018-International Conference on Distributed Computing in Sensor Systems. IEEE, 1--8.
Cited by
Sorted by citations
Signal processing on higher-order networks: Livin’ on the edge... and beyond
Schaub, M. T., Zhu, Y., Seby, J.-B., Roddenberry, T. M., & Segarra, S. (2021) · Signal Processing · doi:10.1016/j.sigpro.2021.108149 · Cited by 161
Principled Simplicial Neural Networks for Trajectory PredictionPreprint
Roddenberry, T. M., Glaze, N., & Segarra, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.10058 · Cited by 48
Human-centred artificial intelligence for mobile health sensing: challenges and opportunities
Dang, T., Spathis, D., Ghosh, A., & Mascolo, C. (2023) · Royal Society Open Science · doi:10.1098/rsos.230806 · Cited by 30
Self-citationMulti-resolution sketches and locality sensitive hashing for fast trajectory processing
Astefanoaei, M., Cesaretti, P., Katsikouli, P., Goswami, M., & Sarkar, R. (2018) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/3274895.3274943 · Cited by 25
Self-citationHigher-Order Networks Representation and Learning: A Survey
Tian, H., & Zafarani, R. (2024) · ACM SIGKDD Explorations Newsletter · doi:10.1145/3682112.3682114 · Cited by 17
Outlier Detection for Trajectories via Flow-embeddings
Frantzen, F., Seby, J.-B., & Schaub, M. T. (2021) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf53345.2021.9723128 · Cited by 6
Differentially Private Range Counting in Planar Graphs for Spatial Sensing
Ghosh, A., Ding, J., Sarkar, R., & Gao, J. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155480 · Cited by 5
Self-citationEfficient Path Planning with Soft Homology Constraints
Taveras, C. A., Segarra, S., & Uribe, C. A. (2024) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta60707.2024.10666586 · Cited by 1
Exploiting Cross-Order Patterns and Link Prediction in Higher-Order Networks
Tian, H., Jin, S., & Zafarani, R. (2022) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw58026.2022.00156 · Cited by 1
Higher Order Information Identifies Tie Strength.Preprint
Sarker, A., Seby, J.-B., Benson, A. R., & Jadbabaie, A. (2021) · arXiv (Cornell University)
Topological Trajectory Classification and Landmark Inference on Simplicial Complexes
Grande, V. P., Hoppe, J., Frantzen, F., & Schaub, M. T. (2024) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf60004.2024.10942887
Omni Geometry Representation Learning Versus Large Language Models for Geospatial Entity Resolution
Wijegunarathna, K., Stock, K. M., & Jones, C. (2026) · Transactions in GIS · doi:10.1111/tgis.70199
Metadata
- Authors
- Ghosh, A., Rozemberczki, B., Ramamoorthy, S., & Sarkar, R.
- Affiliations
- University of Edinburgh (GB)
- University of Edinburgh, U.K.
- FiveAI Ltd. Edinburgh, U.K.
- Venue
- Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
- Publisher
- ACM
- Published
- 2018-11-06
- Pages
- 159-168
- OpenAlex
- W2901062758
- Cited by
- 12
- References
- 35
- Citations by year
- 2026: 1 · 2024: 3 · 2023: 1 · 2022: 1 · 2021: 4 · 2020: 1 · 2018: 1
- FWCI
- 1.15
- Type
- conference paper
- Language
- en
- Open access
- Locations
- ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) (publishedVersion)
- Edinburgh Research Explorer (University of Edinburgh) (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Information Systems › Data Management and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
- Social Sciences › Transportation › Human Mobility and Location-Based Analysis
- Keywords
- topological signatures, mobility analysis, trajectory analysis, mobility prediction, distance scale, k-nearest neighbors regression, locality-sensitive hashing, trajectory clustering, differential forms, distributed computing, mobile agents, obstacle navigation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
