Multi-granularity Spatiotemporal Flow Patterns
Chrysanthi Kosyfaki, Nikos Mamoulis, Reynold Cheng, Ben Kao · 2025
Read Multi-granularity Spatiotemporal Flow Patterns by Chrysanthi Kosyfaki, Nikos Mamoulis, Reynold Cheng, Ben Kao (2025) 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-2512-16255.txt.
Introduction
Chrysanthi Kosyfaki and three co-authors mine movement data in a paper published on arXiv in 2025, which carries an arXiv admin note about text overlap with an earlier paper. Transport firms aggregate trips to spot how passengers flow between regions over time. Patterns can hide at many scales of space and time, so a single fixed view misses trends.
The authors define origin, destination, and time patterns, and give a bottom-up algorithm that enumerates them all. Clever pruning cuts the search space and cost sharply. They add constrained and top-k pattern variants for different applications, plus a fast approximate method for patterns of a given size. Tests on three real data sets showed the methods work efficiently and surfaced interesting flow patterns. The tools suit any field that tracks movement, from transit planning to logistics.
Catalog record
| CREATOR | Chrysanthi Kosyfaki, Nikos Mamoulis, Reynold Cheng, Ben Kao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-16255
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-granularity Spatiotemporal Flow Patterns Chrysanthi Kosyfaki, Nikos Mamoulis, Reynold Cheng, Ben Kao Abstract Analyzing flow of objects or data at different granularities of space and time can unveil interesting insights or trends. For example, transportation companies, by aggregating passenger travel data (e.g., counting passengers traveling from one region to another), can analyze movement behavior. In this paper, we study the problem of finding important trends in passenger movements between regions at different granularities. We define Origin ( O O ), Destination ( D D ), and Time ( T T ) patterns (ODT patterns) and propose a bottom-up algorithm that enumerates them. We suggest and employ optimizations that greatly reduce the search space and the computational cost of pattern enumeration. We also propose pattern variants (constrained patterns and top- k k patterns) that could be useful to different applications scenarios. Finally, we propose an approximate solution that fast identifies ODT patterns of specific sizes, following a generate-and-test approach. We evaluate the efficiency and effectiveness of our methods on three real datasets and showcase interesting ODT flow patterns in them. keywords transportation networks, spatiotemporal patterns, flow, pattern enumeration 1 Introduction In a transportation network, nodes represent stations (or districts) and edges model the connections between the nodes carrying information related to movement or flow (e.g., passengers travel between districts during different times of a day). Examples include car or taxi passengers moving from one district of a city to another, metro or railway passengers, global travellers by air, etc. Transportation companies and organizations collect large volumes of data from their passengers, regarding their origins, destinations, and times of their trips. For each individual trip, the available information is typically the starting (or entry) location (or station) and time of the trip and the final (or exit) location (or station) and time. In-between locations (i.e., the entire trajectories) are often unavailable due to incapability of tracing and privacy constraints. For example, passengers of a metro network use their travel or credit cards at the entry and exit points of their trips and in-between locations can only be inferred. Similarly, taxi companies usually report the starting and ending locations (or districts) of trips instead of the entire trajectories. Information on individual trips can be used in personalized services, after obtaining consent from the passengers. Other than that, it is hard to use such detailed data, mainly due to privacy constraints. However, aggregate information about passenger trips can be invaluable to the company since it can provide time-parameterized estimates and predictions about the passenger flow between regions, which can help to improve their service. Problem We propose a novel analysis tool for transportation data, called Origin-Destination-Time (ODT) patterns. An ODT pattern captures information about the origins, destinations, and the volume (flow) of the passengers at different times of the day where the trips take place. We first use the application domain to define the finest granularity of regions on the map (e.g., each region corresponds to a metro station or a district) and also define the finest time intervals of interest (e.g., divide the 24-hour time interval of a day into 48 equal 30-minute timeslots or use short slots at peak hours and long ones at night). We call these atomic regions and atomic timeslots , respectively. This means that, a trip can be described by its origin region, its destination region, and the timeslot when the trip starts, i.e., as an (o,d,t) triple. For all (o,d,t) triples, where o and d are (different) atomic regions and t is an atomic timeslot, we measure the total number of passengers who took a trip from o to d at time t . The total flow of an (o,d,t) triple characterizes its importance; the triples with high flow are considered to be important and they are called atomic ODT-patterns (we drop the ODT prefix whenever the context is clear). In a generalized ODT-triple, denoted by (O,D,T) , O and D are sets of neighboring atomic regions and T consists of one or more consecutive timeslots. An atomic (o,d,t) triple is a component of an (O,D,T) triple if o\in O , d\in D , and t\in T . (O,D,T) is non-atomic , if at least one of O , D , or T is non-atomic. Figure 1 exemplifies a generalized ODT pattern, which captures statistically significant movement in Brooklyn from boroughs {35,77,177} to boroughs {25,40,106} in the mornings of weekdays. Figure 1 : Example of an ODT pattern Methodology The number of possible atomic region combinations that can form a generalized (i.e., non-atomic) region O or D is huge and it is not practical to consider all these combinations and their flows. At the same time, for a given generalized ODT triple, it is hard to estimate the flow quantity that can be deemed significant enough to characterize the triple an interesting pattern. To solve these issues, we follow a voting approach, where we characterize an ODT triple as a pattern if at least a certain percentage of its constituent (o,d,t) triples are atomic patterns (i.e., they have large enough flow). This allows us to design and use a pattern enumeration algorithm, which, starting from the atomic patterns, identifies all ODT patterns progressively by synthesizing them from less generalized ODT patterns. We propose a number of optimizations, which significantly reduce the time spent for generating candidate patterns and measuring their significance. Problem variants Given the potentially large number of ODT patterns and the high cost of their enumeration, we also study practical ODT variants. First, we investigate the detection of patterns which are constrained to a subset of regions and timeslots, allowing us to focus on under-represented regions and to greatly reduce the pattern enumeration cost. Second, we study pattern detection by limiting the number of atomic regions and timeslots that a pattern may have. Finally, we define and solve the problem of finding the top-ranked patterns at each granularity level, by a novel algorithm that significantly outperforms the baseline approach of finding all patterns at each level and then selecting the top ones. Approximate algorithms In this paper, our primary focus shifts in addressing the computational challenges of enumerating ODT patterns Kosyfaki et al. 2025 . As we mention earlier, enumerating all the possible ODT triples makes exhaustive enumeration computational prohibitive. To futher accelerate the enumeration of generalized ODT patterns, we propose an approximate solution that significantly reduces both space and time complexity compared to the baseline algorithm. Assuming that we are interested in ODT patterns, where the O, D, and T components have specific sizes (e.g., O consists of 4 neighboring districts), we first generate thee pools of O-candidates, D-candidates and T-candidates. O-candidates and D-candidates are connected subgraphs in the region neighborhood graph, which have the requested sizes. T-candidates are sequences of consecutive timeslots of the requested size (e.g., 2-hour periods). Our approximate algorithm follows a generate-and-test approach, which samples triples of ODT combinations from the candidates and counts whether they include a sufficient number of atomic patterns. To improve the effectiveness of our approximate algorithm, we also propose a weighted version, which tests the most promising ODT combinations to become ODT patterns. Applications The problem of identifying ODT patterns finds application in a wide