Density Approximation for Moving Groups

Max J.M. van Mulken; Bettina Speckmann; Kevin A.B. Verbeek

doi:10.1007/978-3-031-38906-1_45

Density Approximation for Moving Groups

Max J.M. van Mulken (Corresponding author), Bettina Speckmann, Kevin A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

3 Downloads (Pure)

Abstract

Sets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.

Original language	English
Title of host publication	Algorithms and Data Structures
Subtitle of host publication	18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings
Editors	Pat Morin, Subhash Suri
Place of Publication	Cham
Publisher	Springer
Pages	675-688
Number of pages	14
ISBN (Electronic)	978-3-031-38906-1
ISBN (Print)	978-3-031-38905-4
DOIs	https://doi.org/10.1007/978-3-031-38906-1_45
Publication status	Published - 28 Jul 2023
Event	18th International Symposium on Algorithms and Data Structures, WADS 2023 - Montreal, Canada Duration: 31 Jul 2023 → 2 Aug 2023

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	14079
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Symposium on Algorithms and Data Structures, WADS 2023
Country/Territory	Canada
City	Montreal
Period	31/07/23 → 2/08/23

Funding

Research at Princeton Univ. was partially supported by a gift from Microsoft. Research at Univ. of California, Irvine was supported by NSF Grant 2212129. Supported by the National Science Foundation grant CCF 2046730. Supported by the National Science Foundation grant CCF 2107434. Supported by DFG grant DI 2041/2. Work supported by Independent Research Fund Denmark, grant 9131-00113B. Acknowledgement. The authors thank Merav Parter for raising the question of designing distance sensitivity oracles that require only subquadratic space. This project received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)”). Acknowledgments. This work was supported, in part, by MUR of Italy, under Projects PRIN 20174LF3T8 (AHeAD: Efficient Algorithms for HArnessing Networked Data), and PNRR CN00000013 (National Centre for HPC, Big Data an d Quantum Computing), and by the University of Padova under Project SID 2020 (RATED-X: Resource-Allocation TradEoffs for Dynamic and eXtreme data). Acknowledgments. We thank Bernd Gärtner for his valuable insights and feedback. This research was supported by the Swiss National Science Foundation under project no. 204320. Keywords: Wiener Index · Optimum communication spanning tree · Minimum routing cost spanning tree This work was partially supported by Grant 2016116 from the United States – Israel Binational Science Foundation. Work by P. Carmi and O. Luwisch was partially supported by the Lynn and William Frankel Center for Computer Sciences. Work by J. Mitchell was partially supported by NSF (CCF-2007275) and by DARPA (Lagrange). This work was partially supported by JSPS KAKENHI Grant Numbers JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP21H03397, JP22H05001, JP23K10982. A full version is available at https://arxiv.org/abs/2305.02059. MdB is supported by the Dutch Research Council (NWO) through Gravitation grant NETWORKS-024.002.003. Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University. Tereza Klimoˇsová is supported by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004) and by GACR grant 22-19073S. This work is partially supported by NSF grant CCF 2049010. This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No.RS-2023-00209069). by the Natural Sciences and Engineering Research Council of Canada Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions. Most proofs from Sects. 3 and 4 are omitted. See [6] for full proofs. M. Chrobak—Research partially supported by National Science Foundation grant CCF-2153723. in part by NSF grant CCF- Acknowledgments. We thank the anonymous reviewers for their careful reading and insightful comments. This research is supported in part by Taiwan NSTC Grant 110-2221-E-007-043. This research was supported in part by NSF under Grants CCF-2005323 and CCF-2300356. A full version of this paper is available at http://arxiv.org/abs/2305.09045.

Funders	Funder number
National Science Foundation	CCF-2153723, 2212129, CCF 2049010, CCF-2300356, CCF-2005323, CCF 2107434, CCF-2007275, CCF 2046730
European Union's Horizon 2020 - Research and Innovation Framework Programme	101019564
Natural Sciences and Engineering Research Council of Canada
H2020 European Research Council
Deutsche Forschungsgemeinschaft	DI 2041/2
Japan Society for the Promotion of Science	JP20K11670, JP20K11692, JP19K11814, JP22H05001, JP20H05793, JP20H05795, JP21H03397, JP23K10982
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung	204320
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	NETWORKS-024.002.003
Ministero dell’Istruzione, dell’Università e della Ricerca	PNRR CN00000013, PRIN 20174LF3T8
University of Padova
National Research Foundation of Korea
Israel Science Foundation	1736/19
Tel Aviv University
Danmarks Frie Forskningsfond	9131-00113B
National Science and Technology Council	110-2221-E-007-043

Keywords

Group density
Quadtrees
Topological persistence

Access to Document

10.1007/978-3-031-38906-1_45

pdfFinal published version, 799 KBLicence: TAVERNE

Cite this

van Mulken, M. J. M., Speckmann, B., & Verbeek, K. A. B. (2023). Density Approximation for Moving Groups. In P. Morin, & S. Suri (Eds.), Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings (pp. 675-688). (Lecture Notes in Computer Science (LNCS); Vol. 14079). Springer. https://doi.org/10.1007/978-3-031-38906-1_45

@inproceedings{a7a95f092510479497600b929c2d22d6,

title = "Density Approximation for Moving Groups",

abstract = "Sets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.",

keywords = "Group density, Quadtrees, Topological persistence",

author = "\{van Mulken\}, \{Max J.M.\} and Bettina Speckmann and Verbeek, \{Kevin A.B.\}",

year = "2023",

month = jul,

day = "28",

doi = "10.1007/978-3-031-38906-1\_45",

language = "English",

isbn = "978-3-031-38905-4",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "675--688",

editor = "Pat Morin and Subhash Suri",

booktitle = "Algorithms and Data Structures",

address = "Germany",

note = "18th International Symposium on Algorithms and Data Structures, WADS 2023 ; Conference date: 31-07-2023 Through 02-08-2023",

}

van Mulken, MJM , Speckmann, B & Verbeek, KAB 2023, Density Approximation for Moving Groups. in P Morin & S Suri (eds), Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 14079, Springer, Cham, pp. 675-688, 18th International Symposium on Algorithms and Data Structures, WADS 2023, Montreal, Canada, 31/07/23. https://doi.org/10.1007/978-3-031-38906-1_45

Density Approximation for Moving Groups. / van Mulken, Max J.M. (Corresponding author); Speckmann, Bettina ; Verbeek, Kevin A.B.
Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings. ed. / Pat Morin; Subhash Suri. Cham: Springer, 2023. p. 675-688 (Lecture Notes in Computer Science (LNCS); Vol. 14079).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Density Approximation for Moving Groups

AU - van Mulken, Max J.M.

AU - Speckmann, Bettina

AU - Verbeek, Kevin A.B.

PY - 2023/7/28

Y1 - 2023/7/28

N2 - Sets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.

AB - Sets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.

KW - Group density

KW - Quadtrees

KW - Topological persistence

UR - http://www.scopus.com/inward/record.url?scp=85172724599&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_45

DO - 10.1007/978-3-031-38906-1_45

M3 - Conference contribution

SN - 978-3-031-38905-4

T3 - Lecture Notes in Computer Science (LNCS)

SP - 675

EP - 688

BT - Algorithms and Data Structures

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer

CY - Cham

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

Y2 - 31 July 2023 through 2 August 2023

ER -

Density Approximation for Moving Groups

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this