How many users have been here for a long time? Efficient solutions for counting long aggregated visits CCS: Theory of computation Data structures and algorithms for data management CCS: Theory of computation Sketching and sampling CCS: Theory of computation Lower bounds and information complexity
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami, Francesco Silvestri, Mariafiore Tognon · 2026
Read How many users have been here for a long time? Efficient solutions for counting long aggregated visits CCS: Theory of computation Data structures and algorithms for data management CCS: Theory of computation Sketching and sampling CCS: Theory of computation Lower bounds and information complexity by Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami, Francesco Silvestri, Mariafiore Tognon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09489.txt.
Introduction
Peyman Afshani and five co-authors tackle a counting problem over streams of visits. Their 2026 arXiv paper asks, given many users moving among many regions, how many users stayed long in total. Each user's time is spread across regions, and only the summed time counts.
Answering exactly would need tracking every user in full detail. The authors seek fast methods, drawing on data structures, sketching, and sampling. They also prove lower bounds that mark what no method can beat. Problems like this arise in location analytics, where firms must count loyal visitors without storing raw trails.
Catalog record
| CREATOR | Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami, Francesco Silvestri, Mariafiore Tognon |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-09489
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How many users have been here for a long time? Efficient solutions for counting long aggregated visits CCS: Theory of computation Data structures and algorithms for data management CCS: Theory of computation Sketching and sampling CCS: Theory of computation Lower bounds and information complexity Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz, Mayank Goswami, Francesco Silvestri, Mariafiore Tognon Abstract . This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given n n users and m m regions, where each user spends some time visiting some regions. For a parameter k k and a query consisting of a subset of r r regions, the task is to count the number of distinct users whose aggregate time spent visiting the query regions is at least k 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 ℝ d \mathbb{R}^{d} and queries are hyperrectangles, and derive exact data structures that achieve improved performance in these structured spaces. 1. Introduction A common data type in large-scale mobility datasets consists of geo-located data with time information ( 28 ) . For the sake of simplicity, we can view these datasets as consisting of triplets, where each triplet (u,r,t) denotes that a given user u has spent some time t in a given region r . According to the different technologies used to collect data, the datasets might differ in how a region is denoted. One common approach leverages mobile network logs (i.e., CDR), which record the cell towers used by each smartphone at a given time. These datasets provide broad population coverage; however, they cannot pinpoint a user’s exact location and instead only indicate that the user was somewhere within the coverage area of a given cell tower. One alternative approach relies on applications that periodically record GPS coordinates together with timestamps, such as navigation apps. Although these data might not provide the same statistical guarantees as network logs, they provide precise GPS coordinates. Mobility datasets are typically very large: for instance, the telecommunications company Vodafone collects approximately 30 billion records per day just from users in Italy ( 36 ) , while TomTom collects 61 billion GPS data points per day from their navigation devices ( 25 ) . These mobility datasets are used to extract information on human behaviors that are of interest, for instance, for urban development, economics, and tourism. Common queries on these datasets are, for example: " How many commuters have spent more than 1 hour stuck in the highway? ", " How many unique individuals have visited the city center for more than an hour? ", " How many unique tourists have visited Venice and Florence for more than 2 days? " (e.g. ( 23 ; 27 ; 4 ) ). As users move, the queries require recognizing the same user in different regions and computing the overall time in the desired area. Consider the input triplets (u_{1},r_{1},20h) , (u_{2},r_{1},15h) , (u_{1},r_{2},15h) , (u_{3},r_{2},30h) , (u_{2},r_{3},20h) and the area of interest defined by the regions \{r_{1},r_{2}\} : then, the two users u_{1},u_{3} have spent at least 30h in the area, while u_{2} does not reach the required minimum time. The area specified by these questions can be translated into a list of cell towers that cover the area of interest for network logs, or as bounding boxes for GPS coordinates. Moreover, for privacy reasons, these queries do not ask to list users, but rather to provide counts. Note that similar queries arise in different scenarios, such as when evaluating user engagement on websites (e.g. ( 30 ) ). In this paper, we provide formal definitions of the above problem, which we name Counting Long Aggregated Visits or just CLAV for short. We first provide a generic definition that does not make any assumptions about region properties and can also be used for non-geometric objects (e.g., visits to a webpage). Then we define Geometric-CLAV , a variant in which users and regions belong to the Euclidean space \mathbb{R}^{d} . We provide efficient approaches to compute exact and approximate solutions to these problems, as well as unconditional and conditional lower bounds. We now describe the CLAV and Geometric-CLAV problems and our results, which are also summarized in Table 1 . Type of CLAV Space Query time Guarantees Theorem (k,r) -CLAV, exact solution S \tilde{\Omega}\left(N/S^{1/r}\right) Conditional lower bound 2.2 (k,r) -CLAV, exact solution {O}\left((N/\lambda)^{r}n+N\right) \tilde{O}\left(r\lambda\right) For any \lambda>0 2.4 (k,r) -CLAV, approximate solution, sampling based {O}\left(N\right) {O}\left(\frac{r^{3}}{\varepsilon^{2}}\log n\right) {\varepsilon}n_{Q} additive error with high probability, \varepsilon>0 3.1 (k,r) -CLAV, approximate solution, sketch based {O}\left(m\varepsilon^{-1}\log^{2}n\log r\right) bits {O}\left(\frac{1}{\varepsilon}\log^{2}n\right) {\Theta}\left(n_{Q,k}+\varepsilon n_{Q}\right) additive error with high probability, \varepsilon=\Omega\left({n_{Q,k}}/{n_{Q}}\right) ; it might count users with aggregate time \geq k(1-1/r) 3.2 Geometric CLAV, exact \Omega\left(\min\{n,\left(\frac{m}{2d}\right)^{2d}\}\right) bits - Unconditional lower bound for any query time 4.1 Geometric CLAV, exact \Omega(m^{2d-1-o(1)}) \tilde{O}\left(1\right) Conditional lower bound 4.3 Geometric CLAV, exact, d=2 \Omega(m^{3-\varepsilon}) preprocessing time O(m^{1-\varepsilon}) Conditional lower bound for any \varepsilon>0 4.6 Geometric CLAV, exact {O}\left(\min\{Nm^{2d-2},m^{2d}\}\right) O(\log_{w}n_{Q,k}) For points in \mathbb{R}^{d} 4.11 Table 1. Our main results are summarized here. Bounds are provided in a simplified version for readability. Space is in words, unless differently stated. Recall that n is the number of users, m is the number of regions, N=|T| , n_{Q} is the number of distinct users in the query region Q and n_{Q,k} is the number of distinct users in the query region Q with aggregated time \geq k (the required output), and d={O}\left(1\right) is the dimension of the points in the geometric version. w is the word-size, which is at least \log(n+m) . The \tilde{O}\left(\cdot\right) and \tilde{\Omega}(\cdot) notations hide polylogarithmic factors. 1.1. (k,r) -CLAV The first definition of the counting long aggregated visits problem for general objects is as follows: Definition 1.1. Let U=\{u_{0},\ldots u_{n-1}\} be a set of n distinct users, R=\{r_{0},\ldots r_{m-1}\} be a set of m regions, and let T=\{(i,j,\tau_{i,j}),\text{with }0\leq i<n,0\leq j<m,\tau_{i,j}>0\} be a set of N triplets where each triplet (i,j,\tau_{i,j}) denotes that user u_{i} has spent time \tau_{i,j} in region r_{j} ; we assume \tau_{i,j}=0 if there are no triplets (i,j,\cdot)\in T . Let k>0 and 1\leq r\leq m be two given parameters. The (k,r) -CLAV requires constructing a data structure, given the U,R,T as input, that returns for any query Q\subseteq R with |Q|=r the number n_{Q,k} of users who have spent no less than a total time k in regions denoted by Q . That is: n_{Q,k}=\left|\left\{u_{i}\in U:\sum_{j\in Q}\tau_{i,j}\geq k\right\}\right|. Without loss of generality, we assume that there are no two triplets (i,j,k_{1}),(i,j,k_{2}) in T with the same i and j values; this property easily follows by replacing the triplets with the (i,j,k_{1}+k_{2}) . We use the following notation: N is the number of triplets in T (i.e., N=\|T\| ); R_{j} denotes the set of users u_{i} with \tau_{i,j}>0 (i.e. R_{j}=\{i:\tau_{i,j}>0)\} ) with j\in[r] ; 1 1 1