research-article

Detecting single file movement

Authors:

J. GudmundssonAuthors Info & Claims

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Article No.: 33, Pages 1 - 10

https://doi.org/10.1145/1463434.1463476

Published: 05 November 2008 Publication History

Abstract

We study the problem of detecting a single file behavior in a set of trajectories. A group of entities is moving in single file if they are following each other, one behind the other. This movement pattern occurs often, among animals, humans, and vehicles. It is challenging to detect because it does not have a fixed layout.

In this paper we first model the notion of following behind, on which we base our definition of single file. We present efficient algorithms for detecting following behind and single file behaviors. We test and evaluate these algorithms on real and generated test data.

References

[1]

H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. International Journal on Computational Geometry and Applications, 5:75--91, 1995.

[2]

M. Andersson, J. Gudmundsson, P. Laube and T. Wolle. Reporting leaders and followers among trajectories of moving point objects. GeoInformatica, 12(4):497--528, 2008.

Digital Library

[3]

M. Benkert, J. Gudmundsson, F. Hübner and T. Wolle. Reporting flock patterns. Computational Geometry - Theory and Applications, 41(3):11--125, 2008.

Digital Library

[4]

K. Buchin, M. Buchin, J. Gudmundsson, J. Luo and M. Löffler. Detecting commuting patterns by clustering subtrajectories. Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), 2008.

Digital Library

[5]

F. E. Fish. Energetics of swimming and flying in formation. Comments on Theoretical Biology 5: 283--304, 1999.

[6]

J. Gudmundsson, P. Laube and T. Wolle. Movement patterns in spatio-temporal data. In Encyclopedia of GIS, Eds. S. Shekhar and H. Xiong, Springer, 2008.

[7]

J. Gudmundsson, M. van Kreveld and B. Speckmann. Efficient detection of motion patterns in spatio-temporal data sets. GeoInformatica, 11(2):195--215, 2007.

Digital Library

[8]

J. Gudmundsson and M. van Kreveld. Computing longest duration flocks in spatio-temporal data. Proceedings of the 16th International Conference on Advances in Geographic Information Systems (ACM GIS), 2006.

Digital Library

[9]

C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects. IEEE Transactions on Data Engineering, 19(9):1161--1174, 2007.

Digital Library

[10]

H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen and H. T. Shen. Discovery of convoys in trajectory databases. Proceedings of the 34th International Conference on Very Large Data Bases (VLDB), 2008.

Digital Library

[11]

P. Kalnis, N. Mamoulis and S. Bakiras. On discovering moving clusters in spatio-temporal data. Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases (SSTD), pp. 364--381, 2005.

Digital Library

[12]

P. Laube, M. van Kreveld and S. Imfeld. Finding REMO -- detecting relative motion patterns in geospatial lifelines. Proceedings of the 11th International Symposium on Spatial Data Handling, pp. 201--214, 2004.

[13]

Y. Li, J. Han and J. Yang. Clustering moving objects. Proceedings of the 10th ACM SIGKDD International Conference on Knowledge discovery and data mining, pp. 617--622, 2004.

Digital Library

[14]

T. Shirabe. Correlation analysis of discrete motions. Proceedings of the 4th International Conference on Geographic Information Science (GIScience), pp. 370--382, 2006.

Digital Library

[15]

F. Verhein and S. Chawla. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases. Proceedings of the 11th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 187--201, 2006.

Digital Library

Cited By

Scheffer C(2021)The Prefix Fréchet SimilarityComputational Geometry10.1016/j.comgeo.2021.101853(101853)Online publication date: Nov-2021
https://doi.org/10.1016/j.comgeo.2021.101853
Wang QSong WZhang JLian LLo S(2019)Experimental Study on Single-File Movement with Different Stop DistancesThe Proceedings of 11th Asia-Oceania Symposium on Fire Science and Technology10.1007/978-981-32-9139-3_19(241-253)Online publication date: 13-Sep-2019
https://doi.org/10.1007/978-981-32-9139-3_19
Scheffer C(2018)The Prefix Fréchet SimilarityWALCOM: Algorithms and Computation10.1007/978-3-030-10564-8_8(96-107)Online publication date: 21-Dec-2018
https://doi.org/10.1007/978-3-030-10564-8_8
Show More Cited By

Index Terms

Detecting single file movement
1. Information systems
  1. Information systems applications
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A multiple-file write scheme for improving write performance of small files in Fast File System

Fast File System (FFS) stores files to disk in separate disk writes, each of which incurs a disk positioning (seek + rotation) limiting the write performance for small files. We propose a new scheme called co-writing to accelerate small file writes in ...
The Zebra striped network file system

Zebra is a network file system that increases throughput by striping the file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an ...
The Zebra striped network file system
SOSP '93: Proceedings of the fourteenth ACM symposium on Operating systems principles

Zebra is a network file system that increases throughput by striping file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

November 2008

559 pages

ISBN:9781605583235

DOI:10.1145/1463434

Program Chairs:
Walid G. Aref
Purdue University
,
Mohamed F. Mokbel
University of Minnesota
,
Markus Schneider
University of Florida

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ESRI
Google Inc.
Oak Ridge National Laboratory
Microsoft: Microsoft
SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Conference

GIS '08

Sponsor:

Microsoft
SIGSPATIAL

GIS '08: 16th International Symposium on Advances in Geographic Information Systems

November 5 - 7, 2008

California, Irvine

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
264
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Scheffer C(2021)The Prefix Fréchet SimilarityComputational Geometry10.1016/j.comgeo.2021.101853(101853)Online publication date: Nov-2021
https://doi.org/10.1016/j.comgeo.2021.101853
Wang QSong WZhang JLian LLo S(2019)Experimental Study on Single-File Movement with Different Stop DistancesThe Proceedings of 11th Asia-Oceania Symposium on Fire Science and Technology10.1007/978-981-32-9139-3_19(241-253)Online publication date: 13-Sep-2019
https://doi.org/10.1007/978-981-32-9139-3_19
Scheffer C(2018)The Prefix Fréchet SimilarityWALCOM: Algorithms and Computation10.1007/978-3-030-10564-8_8(96-107)Online publication date: 21-Dec-2018
https://doi.org/10.1007/978-3-030-10564-8_8
Har-Peled SNayyeri ASalavatipour MSidiropoulos A(2016)How to Walk Your Dog in the Mountains with No Magic LeashDiscrete & Computational Geometry10.1007/s00454-015-9737-355:1(39-73)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s00454-015-9737-3
Laube P(2015)The low hanging fruit is goneSIGSPATIAL Special10.1145/2782759.27827627:1(3-10)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2782759.2782762
Avraham RFiltser OKaplan HKatz MSharir M(2015)The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and SelectionACM Transactions on Algorithms10.1145/270022211:4(1-29)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1145/2700222
Schwaninger CMenshykau DIber D(2015)Simulating OrganogenesisACM Transactions on Modeling and Computer Simulation10.1145/268890825:2(1-19)Online publication date: 17-Feb-2015
https://dl.acm.org/doi/10.1145/2688908
Dannenberg FHahn EKwiatkowska M(2015)Computing Cumulative Rewards Using Fast Adaptive UniformizationACM Transactions on Modeling and Computer Simulation10.1145/268890725:2(1-23)Online publication date: 17-Feb-2015
https://dl.acm.org/doi/10.1145/2688907
Ruess JLygeros J(2015)Moment-Based Methods for Parameter Inference and Experiment Design for Stochastic Biochemical Reaction NetworksACM Transactions on Modeling and Computer Simulation10.1145/268890625:2(1-25)Online publication date: 17-Feb-2015
https://dl.acm.org/doi/10.1145/2688906
Shi MSun XTao DXu CBaciu GLiu H(2015)Exploring Spatial Correlation for Visual Object RetrievalACM Transactions on Intelligent Systems and Technology10.1145/26415766:2(1-21)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2641576
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten