dorsal/arxiv
View SchemaHow many users have been here for a long time? Efficient solutions for counting long aggregated visits
| Authors | Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami, Francesco Silvestri, Mariafiore Tognon |
|---|---|
| Categories | |
| ArXiv ID | 2601.09489vv1 |
| URL | https://arxiv.org/abs/2601.09489 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given $n$ users and $m$ regions, where each user spends some time visiting some regions. For a parameter $k$ and a query consisting of a subset of $r$ regions, the task is to count the number of distinct users whose aggregate time spent visiting the query regions is at least $k$. This problem is motivated by queries arising in the analysis of large-scale mobility datasets. We present several exact and approximate data structures for supporting counting long aggregated visits, as well as conditional and unconditional lower bounds. First, we describe an exact data structure that exhibits a space-time tradeoff, as well as efficient approximate solutions based on sampling and sketching techniques. We then study the problem in geometric settings where regions are points in $\mathbb{R}^d$ and queries are hyperrectangles, and derive exact data structures that achieve improved performance in these structured spaces.
{
"annotation_id": "3b77c160-8609-49fc-a275-7c5cc045c6b3",
"date_created": "2026-02-17T05:53:20.460000Z",
"date_modified": "2026-02-17T05:53:20.460000Z",
"file_hash": "ed2526c4a7f07962d914d06dc8451d5204906394ab36b54817cc1690c996e6b1",
"private": false,
"record": {
"abstract": "This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given $n$ users and $m$ regions, where each user spends some time visiting some regions. For a parameter $k$ and a query consisting of a subset of $r$ regions, the task is to count the number of distinct users whose aggregate time spent visiting the query regions is at least $k$. This problem is motivated by queries arising in the analysis of large-scale mobility datasets. We present several exact and approximate data structures for supporting counting long aggregated visits, as well as conditional and unconditional lower bounds. First, we describe an exact data structure that exhibits a space-time tradeoff, as well as efficient approximate solutions based on sampling and sketching techniques. We then study the problem in geometric settings where regions are points in $\\mathbb{R}^d$ and queries are hyperrectangles, and derive exact data structures that achieve improved performance in these structured spaces.",
"arxiv_id": "2601.09489",
"authors": [
"Peyman Afshani",
"Rezaul Chowdhury",
"Inge Li G\u00f8rtz",
"Mayank Goswami",
"Francesco Silvestri",
"Mariafiore Tognon"
],
"categories": [
"cs.DS"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "How many users have been here for a long time? Efficient solutions for counting long aggregated visits",
"url": "https://arxiv.org/abs/2601.09489",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "63553510-7873-439e-a1be-29738ec62458",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}