mopdf.com

partition-passing time for FPQ and partition-passing contact forLCPQ should be defined differently for the two partition types.Existing techniques cannot handle the novel FPQ and LCPQ. First,techniques for outdoor route planning [2, 3, 5, 11, 14, 29, 36, 39]do not work for indoor spaces with distinct entities like doors,walls, and rooms, altogether forming a complex topology. Second,the existing indoor route planning methods [12, 26, 31, 32] do notconsider the effect of crowds, lacking the modeling foundation forFPQ and LCPQ. Third, some works study indoor flow and density [20,21], but they do not touch upon route planning.To solve FPQ and LCPQ efficiently, we design a crowd-awarequery processing framework. The framework is composed of threelayers. First, the indoor crowd model is the foundation layer ofthe framework. The model can handle three kinds of information,namely indoor topology, indoor geometry, and crowd-evolution. Atime-evolving population estimator derives the future flows andpopulations for indoor partitions. The estimated values are usedas basic routing costs in FPQ and LCPQ. The query processing layerconsists of two parts. In part one, two functions, namely partitionpassing time function and partition-passing contact function,calculate the routing cost for FPQ and LCPQ, respectively. Again, thedifferences in routing costs for different partition types are unifiedinto a single computing process. On top of that, part two providestwo exact and two approximate path search algorithms that eachcan process both query types. One of the exact searches uses a globalestimator, whereas the other uses an estimator that only estimates apartition’s population by looking up its upstream partitions’ flows.The two approximate algorithms speed up query processing at thecost of query accuracy. One of them only derives populations forpartial partitions, and the other derives populations only whennecessary. All proposed techniques are experimentally evaluatedon synthetic and real data. The experimental results demonstratethe efficiency and scalability of the proposed framework and queryprocessing algorithms. The results also show the two approximatesearch algorithms achieve good routing accuracy.This paper makes the following key contributions. We formulate Indoor Crowd-Aware Fastest Path Query (FPQ) andIndoor Least Crowded Path Query (LCPQ), and propose a unifiedprocessing framework for these queries (Section 2). We design an indoor crowd model that organizes indoor topologyand captures indoor partition flows and densities (Section 3). We devise a time-evolving population estimator to derive futuretime-dependent flows and populations for partitions (Section 4). We design two exact and two approximate query processingalgorithms that each can process both query types (Section 5). We conduct extensive experiments on synthetic and real datasetsto evaluate our proposals (Section 6).In addition, Section 7 reviews the related work and Section 8concludes the paper.2PRELIMINARIESTable 1 lists the notations frequently used in this paper.2.1Indoor CrowdsAn indoor space is divided by walls and doors into indoor partitions.A Queue Partition (Q-partition) requests objects to enter and1366Symbol𝑣, 𝑑, 𝑝𝑜, 𝑂𝐶𝑡𝑜 𝐶 , 𝑡𝐶 𝑜RT (𝑑𝑖 )UTI (𝑣𝑘 )𝛿𝑡𝑥 ,𝑡𝑥 1 (𝑣𝑘 )𝜌 (𝑣𝑘 , 𝑡𝑐 )𝑇 (𝑑𝑖 , 𝑑 𝑗 , 𝑣𝑘 , 𝑡𝑐 )𝜅 (𝑑𝑖 , 𝑑 𝑗 , 𝑣𝑘 , 𝑡𝑐 )Table 1: NotationsMeaningPartition, door, and indoor pointObject, object setIndoor crowdThe times 𝑜 joins and leaves 𝐶The sequence of 𝑑𝑖 ’s report timestampsThe set of 𝑣𝑘 ’s unit (update) time intervals𝑣𝑘 ’s density over [𝑡𝑥 , 𝑡𝑥 1 ]𝑣𝑘 ’s lagging coefficient at time 𝑡𝑐The time to pass 𝑣𝑘 from 𝑑𝑖 to 𝑑 𝑗 at 𝑡𝑐The object contact to pass 𝑣𝑘 from 𝑑𝑖 to 𝑑 𝑗 at 𝑡𝑐leave sequentially, while a Random Partition (R-partition) has nosuch a restriction and objects can enter and leave it randomly. Notethat the type of partition is usually fixed and will change only whenthe space layout is redesigned. The issue of topological change isout of the scope of this paper.Within a partition, moving objects (e.g., persons) may form acrowd. Corresponding to the partition types, we formally define anindoor crowd as follows.Definition 1 (Indoor Crowd). An indoor crowd 𝐶𝑡𝑠 ,𝑡𝑒 (𝑣𝑘 ) 1 is a setof moving objects in a partition 𝑣𝑘 during a certain time interval[𝑡𝑠 , 𝑡𝑒 ]. 𝐶.𝜏 denotes the type of crowd 𝐶.1) In a Queue Crowd (Q-crowd), objects join and leave the crowd inthe first-in-first-out (FIFO) manner. Formally, 𝑜𝑖 , 𝑜 𝑗 𝐶𝑘 𝐶𝑘 .𝜏 Q, 𝑡𝑜𝑖 𝐶𝑘 𝑡𝑜 𝑗 𝐶𝑘 𝑡𝐶𝑘 𝑜𝑖 𝑡𝐶𝑘 𝑜 𝑗 , where 𝑡𝑜𝑖 𝐶𝑘 and 𝑡𝐶𝑘 𝑜𝑖is the time 𝑜𝑖 joins and leaves 𝐶𝑘 , respectively.2) In a Random Crowd (R-crowd), objects join and leave the crowdwithout any ordering restrictions. Formally, 𝑜𝑖 , 𝑜 𝑗 𝐶𝑘 𝐶𝑘 .𝜏 R, 𝑡𝑜𝑖 𝐶𝑘 𝑡𝑜 𝑗 𝐶𝑘 , 𝑡𝐶𝑘 𝑜𝑖 𝑡𝐶𝑘 𝑜 𝑗 .A crowd changes as objects join and leave from time to time.In other words, the object population and density of a partitionare time-varying, rendering an object’s routing cost passing thepartition to change as well. Therefore, for crowd-aware routing, it isof fundamental importance to know a crowd’s dynamic populationor density. This demands dynamic data from a localization system.However, a localization system may not record the exact trajectory or join/leave time of each individual object due to computing/storage limitations and location privacy concerns. Alternatively,a system may maintain the current number of objects in eachpartition (or a crowd) and records the number of objects joining andleaving during a time interval. This can be easily achieved, e.g., byinstalling a counter at a door. In our setting, each door counterreports objects’ joining and leaving at a predefined frequency.This means that the object numbers in a crowd are updated ata number of discrete timestamps. Specifically, we use a timeordered sequence RT (𝑑𝑖 ) (𝑡𝑖1, . . . , 𝑡𝑖𝑛 ) to denote the reporttimestamps of the counter at door 𝑑𝑖 . As a result, the updatetimestamps relevant to a partition 𝑣𝑘 is a time-ordered sequenceÐUT (𝑣𝑘 ) 𝑑 𝑗 P2D (𝑣𝑘 ) RT (𝑑 𝑗 ) where P2D(𝑣𝑘 ) refers to all doorsof partition 𝑣𝑘 . Each two consecutive timestamps in the sequenceUT (𝑣𝑘 ) forms an unit (update) time interval. The set of all suchintervals from UT (𝑣𝑘 ) is denoted by UTI (𝑣𝑘 ).1 Whentime is not of particular interest, we use 𝐶𝑘 to denote 𝑣𝑘 ’s associated crowd.

At the routing query time, it is necessary to know the flows in thefuture. However, future exact object numbers from door countersare unavailable at that moment. To this end, we employ door flowfunctions to model the crowd-evolution (detailed in Section 3.2).We define a partition’s time-parameterized density as follows.Definition 2 (Time-Parameterized Density). Given a partition 𝑣𝑘and its unit time interval [𝑡𝑥 , 𝑡𝑥 1 ] UTI (𝑣𝑘 ), its time-parameterizeddensity over [𝑡𝑥 , 𝑡𝑥 1 ] is 𝛿𝑡𝑥 ,𝑡𝑥 1 (𝑣𝑘 ) 𝐶𝑘 /Area(𝑣𝑘 ), where 𝐶𝑘 is𝑣𝑘 ’s population over [𝑡𝑥 , 𝑡𝑥 1 ] and Area(𝑣𝑘 ) is 𝑣𝑘 ’s area.The population and density in this paper are time-parameterizedunless mentioned otherwise. A partition 𝑣𝑘 ’s density at an arbitrarytimestamp 𝑡𝑐 is estimated with respect to the unit time intervalcovering 𝑡𝑐 . Specifically, we have 𝛿𝑡𝑐 (𝑣𝑘 ) 𝛿𝑡𝑥 ,𝑡𝑥 1 (𝑣𝑘 ) where 𝑡𝑥 𝑡𝑐 𝑡𝑥 1, [𝑡𝑥 , 𝑡𝑥 1 ] UTI (𝑣𝑘 ).2.2Problem FormulationIn an indoor routing problem, a basic step is to move from one doorto another through their in-between partition. To measure the costto pass a partition, the intra-partition door-to-door distance [12]for two doors 𝑑𝑖 and 𝑑 𝑗 is( 𝑑𝑖 , 𝑑 𝑗 𝐸 , if D2P (𝑑𝑖 ) D2P (𝑑 𝑗 ) ;d2d (𝑑𝑖 , 𝑑 𝑗 ) (1) ,otherwise.where D2P (𝑑𝑖 ) gives the set of partitions that one can enterthrough door 𝑑𝑖 and D2P (𝑑 𝑗 ) gives those that one can leavethrough door 𝑑 𝑗 . Therefore, D2P (𝑑𝑖 ) D2P (𝑑 𝑗 ) means𝑑𝑖 and 𝑑 𝑗 share a common partition that one can enter via 𝑑𝑖 andleave via 𝑑 𝑗 . In this case, the Euclidean distance is used between 𝑑𝑖and 𝑑 𝑗 . Otherwise, the distance between them is set to infinite.Definition 3 (Indoor Path). An indoor path from the source 𝑝𝑠to the target 𝑝𝑡 is 𝜙 (𝑝𝑠 , 𝑑𝑥 , . . . , 𝑑 𝑦 , 𝑝𝑡 ), where (𝑑𝑥 , . . . , 𝑑 𝑦 ) is adoor sequence, 𝑑𝑥 is a leaveable door of 𝑝𝑠 ’s host partition, 𝑑 𝑦 is anenterable door of 𝑝𝑡 ’s host partiton, and each two consecutive doors𝑑𝑛 , 𝑑𝑛 1 (𝑥 𝑛 𝑦) on 𝜙 have D2P (𝑑𝑛 ) D2P (𝑑𝑛 1 ) . Eachtwo consecutive path nodes form a path segment. The distance of 𝜙Í𝑦 1is computed as dist𝜙 𝑝𝑠 , 𝑑𝑥 𝐸 𝑛 𝑥 d2d (𝑑𝑛 , 𝑑𝑛 1 ) 𝑑 𝑦 , 𝑝𝑡 𝐸 .When there is no crowd, the basic time cost of passing an inbetween partition 𝑣𝑘 from 𝑑𝑖 to 𝑑 𝑗 can be estimated based on theaverage object moving speed 𝑠 , i.e., 𝑇 (𝑏) (𝑑𝑖 , 𝑑 𝑗 ) d2d (𝑑𝑖 , 𝑑 𝑗 )/ 𝑠 . Toreflect a crowd’s impact, we use the lagging coefficient 𝜌 (𝑣𝑘 , 𝑡𝑐 )that takes into account the crowd’s density and type as follows.(max1 𝑒 𝛿𝑡𝑐 (𝑣𝑘 )/D𝑘 ,if 𝐶𝑘 .𝜏 Q;𝜌 (𝑣𝑘 , 𝑡𝑐 ) (2)(𝛿𝑡𝑐 (𝑣𝑘 )/D𝑘max ) 21 𝑒, otherwise.where 𝛿𝑡𝑐 (𝑣𝑘 ) is 𝑣𝑘 ’s density at time 𝑡𝑐 and D𝑘max corresponds to themaximum density2 of 𝑣𝑘 . For a Q-partition, the ratio 𝛿𝑡𝑐 (𝑣𝑘 )/D𝑘maxis applied to reflect the crowding degree. We modify the speeddensity model [35] to calculate the lagging coefficient in Equation 2which reflects real-world scenarios, e.g., in common sense, a crowdusually impacts people’s moving speed and results in longer traveltime. Equation 2 guarantees that the coefficient is always greaterthan 1 and it increases monotonically as 𝑣𝑘 ’s density increases. Foran R-partition, the square of the ratio is used because R-crowdsincur less lagging effect.Note that other forms of lagging coefficients can be defined andsupported within our framework, e.g., lagging can be multiplied bythe object number for a queue crowd. Since the lagging coefficientis not our research focus, we simply apply Equation 2 in this study.Using the lagging coefficient, we can calculate our crowd-awareand time-dependent partition-passing time as follows.𝑇 (𝑑𝑖 , 𝑑 𝑗 , 𝑣𝑘 , 𝑡𝑐 ) 𝑇 (𝑏) (𝑑𝑖 , 𝑑 𝑗 ) · 𝜌 (𝑣𝑘 , 𝑡𝑐 )(3)An object needs longer time to pass a more crowded partition.As a special case, we replace 𝑑𝑖 with 𝑝𝑠 or replace 𝑑 𝑗 with 𝑝𝑡 inEquation 3, to estimate the cost of a path segment starting with 𝑝𝑠or ending with 𝑝𝑡 . Accordingly, 𝑣𝑘 is the host partition of 𝑝𝑠 or 𝑝𝑡 .With the partition-passing time, we can plan the fastest indoorpath for users to avoid undesirable congestion caused by indoorcrowds. An indoor path 𝜙’s overall travel time 𝑇𝜙 is computed asthe sum of the time of passing the partition between each pathsegment on 𝜙. The fastest path query problem is defined as follows.Problem 1 (Indoor Crowd-Aware Fastest Path Query FPQ). Givena source 𝑝𝑠 and a target 𝑝𝑡 , an indoor crowd-aware fastest pathquery FPQ(𝑝𝑠 , 𝑝𝑡 , 𝑡) returns a path 𝜙 (𝑝𝑠 , 𝑑𝑖 , . . . , 𝑑 𝑗 , 𝑝𝑡 ) such that a)the overall travel time 𝑇𝜙 is minimized and b) 𝜙 is the shortest amongall satisfying a). Formally, 𝜙 ′ 𝜙, 𝑇𝜙 ′ 𝑇𝜙 dist𝜙 ′ dist𝜙 .Note that the partition-passing time is determined by the timeone arrives at that partition, while the arrival time, in turn, isdependent on the partition-passing time of the previous partition.This calls for on-the-fly computation during the search to obtainthe overall travel time 𝑇𝜙 , which is to be detailed in Section 5.Example 1. Figure 1 illustrates an indoor space at time 𝑡𝑞 . Thequery time and crowd-evolution snapshot are considered. We indicate the distance, partition-passing time and object contact oneach path segment in the top sketch. We suppose that there aresome events in 𝑣 7 , and 𝑣 4 , 𝑣 6 and 𝑣 8 are Q-partitions for ID checkbefore entering 𝑣 7 . Given a query FPQ(𝑝𝑠 , 𝑝𝑡 , 𝑡𝑞 ), there are threecandidate paths, namely 𝜙 1 (𝑝𝑠 , 𝑑 2, 𝑑 5, 𝑑 8, 𝑝𝑡 ), 𝜙 2 (𝑝𝑠 , 𝑑 1, 𝑑 3, 𝑑 6, 𝑝𝑡 ),and 𝜙 3 (𝑝𝑠 , 𝑑 1, 𝑑 4, 𝑑 7, 𝑑 9, 𝑝𝑡 ). Only considering the distance but not theimpact from crowds, 𝜙 1 is the shortest with a length of 32 meters, whilethose of 𝜙 2 and 𝜙 3 are 35 meters and 48 meters, respectively. However,𝜙 1 is not expected to be the fastest path when crowds are concerned. Tobe specific, 𝜙 1 goes through a highly crowded R-partition 𝑣 3 , incurringa total travel time of 144 seconds. For 𝜙 2 , the low-populated Q-partition𝑣 4 with a long queue is involved, making the total time cost be 96seconds. Among all, 𝜙 3 is expected to be the fastest with an overall costof 78 seconds, though it is the longest distance passing 5 partitions.Another practically interesting problem is to find the shortestpath that contacts the least objects. E.g., it is useful to find a paththat avoids human contact as much as possible in the COVID-19case. Given a path segment (𝑑𝑖 , 𝑑 𝑗 ) that goes through a partition𝑣𝑘 , we calculate the partition-passing contact as follows.𝜅 (𝑑𝑖 , 𝑑 𝑗 , 𝑣𝑘 , 𝑡𝑐 ) (( 𝑑𝑖 , 𝑑 𝑗 𝐸 · w) · 𝛿𝑡𝑐 (𝑣𝑘 ),(w/ 𝑑𝑖 , 𝑑 𝑗 𝐸 ) · (𝛿𝑡𝑐 (𝑣𝑘 ) · Area(𝑣𝑘 )),if 𝐶𝑘 .𝜏 R;otherwise.(4)Given a partition 𝑣𝑘 , its enterable door 𝑑𝑖 , and its leaveable door 𝑑 𝑗 ,for any object reaching 𝑑𝑖 at time 𝑡𝑐 , the partition-passing contact2 Themaximum capacity (and therefore the maximum density) of a partition is usuallyknown, such as the room capacity for fire safety.1367

Enabled by the indoor crowd model, a time-evolving populationestimator in the middle layer derives populations (and densities)of partitions at a future time and provides them to the queryalgorithms. The population estimation process will be detailed inSection 4.In the top layer, crowd-aware search algorithms process FPQand LCPQ. Both algorithms are based on graph traversal over theindoor crowd model. To expand to the next path node with theminimum cost, FPQ’s algorithm estimates the partition-passing time,while LCPQ search algorithm estimates the partition-passing contact.Both costs are estimated based on the time-evolving populationsderived in the middle layer. For both queries, two exact and twoapproximate search algorithms are proposed. Their main differencelies in the strategy of updating population(s) during the search. Allsearch algorithms will be presented in Section 5. Thanks to modularconstruction, our framework can be easily extended or reduced.For example, to support regular path planning, we only need thecomponents Indoor Topology and an appropriate query processingalgorithm that can be a variant of Algorithm 3.to pass 𝑣𝑘 and reach 𝑑 𝑗 is defined in terms of the number of objectscovered by the buffer of the path segment. The contact to pass anR-partition is the partition density multiplied by the buffer areathat is approximated as 𝑑𝑖 , 𝑑 𝑗 𝐸 · w where w is the buffer width. Thecontact to pass a Q-partition is the objects within the w long queueline centered at the user’s position, i.e., the proportion w/ 𝑑𝑖 , 𝑑 𝑗 𝐸of the total objects in the queue. This reflects common sense. Forexample, if we pass a random crowd, the close contacts are thosewho we meet in the buffer width. If we pass a queue crowd, weonly have close distance with those in front of or behind us.In our implementation, we set w as the unit distance of 1m. Forexample, many countries suggest people keep a physical distanceof 1m in the COVID-19 pandemic. Similar to the computation ofthe overall travel time 𝑇𝜙 , an indoor path 𝜙’s overall contact 𝜅𝜙is computed as the sum of the partition-passing contacts of pathsegments on 𝜙. Likewise, Equation 4 applies to the path segmentstarting with 𝑝𝑠 and ending with 𝑝𝑡 . Accordingly, we formulate theleast crowded path query as follows.Problem 2 (Indoor Least Crowded Path Query LCPQ). Given asource 𝑝𝑠 and a target 𝑝𝑡 , an indoor least crowded path queryLCPQ(𝑝𝑠 , 𝑝𝑡 , 𝑡) returns a path 𝜙 (𝑝𝑠 , 𝑑𝑖 , . . . , 𝑑 𝑗 , 𝑝𝑡 ) such that a) theoverall contact is the least, and b) 𝜙 is the shortest among all satisfyinga). Formally, 𝜙 ′ 𝜙, 𝜅𝜙 ′ 𝜅𝜙 dist𝜙 ′ dist𝜙 .Example 2. Consider a query LCPQ(𝑝𝑠 , 𝑝𝑡 , 𝑡𝑞 ) in Figure 1, thecandidates 𝜙 1 , 𝜙 2 and 𝜙 3 involve 18, 3 and 5 contacts from thepartitions which they pass, respectively. The query returns 𝜙 2 since itcontacts the fewest objects.Exact Search(Alg.3 Alg.2)Exact SearchGlobalApprox.Search PPApprox.Search NT(Alg.3 Alg.1)(Strategy 1)(Strategy 2)apply toLCPQFPQPartition-Passing Time (Alg.4) Partition-Passing ContactcallcallTime-evolving Population Estimator(Section 4, Alg.1 and Alg.2)Indoor GeometryIndoor Crowd-Evolutionpartition shape, door-to-door distanceabsolute population, door flowsIndoor Topologydoor directionality, partition connectivity/accessibilityFigure 2: Crowd-Aware Path Planning FrameworkArea90m2Md2d[(d1, d2, 5),(d2, d1, 5)]𝛕R(P, t)(0, 10:01)f(v1, v2, d ),1 F[t]Indoor Crowd Model (Section 3)),f(v 1, v 3, d2v1v3f(v3, v6, d5), F[t]f(v2, v4, d3), F[t]v2f(v5,2, v5, d4 ),F[t]v2 ,d4 )v6f(v6, v7, d8), F[t]f(v2, v1, d1), F[t]f(vIn the bottom, an indoor crowd model (cf. Section 3) maintainsthe following aspects of an indoor space: Indoor Topology thatcaptures the directionality of doors and connectivity/accessibility ofpartitions, Indoor Geometry that records the shapes of partitions andwalking distances between two doors, and Indoor Crowd-Evolutionthat models the objects joining and leaving the crowds.f(v6, v3, d5), F[t]F[t],Fv4]d ), F[tf(v 4, v 7, 6f(v7, v8, d9), F[t]]f(v8, v5, d7), F[t[t]v5v7v8f(v7, v6, d8), F[t]Query Processing (Section 5)F[t]We propose a crowd-aware query processing framework as illustrated in Figure 2.9 ),Solution FrameworkAs an extension of the accessibility graph [17], the indoor crowdmodel is a directed, labeled graph 𝐺 (𝑉 , 𝐸, 𝐿𝑉 , 𝐿𝐸 ) where1) 𝑉 is the set of vertices, each for an indoor partition.2) 𝐸 is the set of directed edges such that each edge 𝑒 (𝑣𝑖 , 𝑣 𝑗 , 𝑑𝑘 ) 𝐸means one can reach 𝑣 𝑗 from 𝑣𝑖 through a door 𝑑𝑘 , i.e., 𝑣𝑖 D2P (𝑑𝑘 ) and 𝑣 𝑗 D2P (𝑑𝑘 ).3) 𝐿𝑉 is the set of vertex labels. Each label in 𝐿𝑉 is attached toa partition and captured as a five tuple [𝑣𝑖 , Area(𝑣𝑖 ), Md2d , 𝜏,(P𝑖𝑡𝑙 , 𝑡𝑙 )]. In particular, 𝑣𝑖 identifies the associated partition,Area(𝑣𝑖 ) is 𝑣𝑖 ’s area, Md2d is a matrix that stores the intrapartition distance (See Equation 1) between each pair of doorsof 𝑣𝑖 . In addition, 𝜏 {R, Q} indicates the type of 𝑣𝑖 ’s crowdand (P𝑖𝑡𝑙 , 𝑡𝑙 ) means that 𝑣𝑖 ’s absolute population at a latesttimestamp 𝑡𝑙 is known as P𝑖𝑡𝑙 . In practice, the model can recordthe populations at historical timestamps, though only the latestpopulation is relevant to a query.4) 𝐿𝐸 is the edge label set. For an edge (𝑣𝑖 , 𝑣 𝑗 , 𝑑𝑘 ) 𝐸, its labelconsists of a door flow function 𝑓 (𝑣𝑖 , 𝑣 𝑗 , 𝑑𝑘 ) that models thedynamic object flows from 𝑣𝑖 to 𝑣 𝑗 via 𝑑𝑘 and a local array F[𝑡]storing the actual object flows at each update timestamp 𝑡.f(v ,8 v ,7 d2.33 INDOOR CROWD MODEL3.1 Model Structure]f(v5, v8, d7), F[tFigure 3: An Example of Indoor Crowd ModelFigure 3 depicts the indoor crowd model corresponding to thespace in Figure 1. Unlike a general time-dependent graph (GTG) [11,1368

44], our model represents doors as edges and partitions as vertices.A GTG may model doors as vertices and partitions as edges andcapture time-varying populations or distances as edge weights, butthis way falls short in solving our problem. First, GTG’s verticesfail to capture the door directionality (e.g., unidirectional securitycheck doors) directly. Referring to Figure 1, 𝑑 2 is unidirectional suchthat one can only go through 𝑑 2 from 𝑣 1 to 𝑣 3 . In a GTG, the edgescannot be directed because each edge connects two doors and onecan always go from one door to any other door in the same room.E.g., one cannot go through 𝑑 2 from 𝑣 3 to 𝑣 1 , but she can go to anydoor in 𝑣 1 from 𝑑 2 if she is in 𝑣 1 . The directionality informationcan be added in each node, e.g., that for node 𝑑 2 can be {(𝑣 1 , 𝑣 3 )},and that for node 𝑑 1 can be {(𝑣 1 , 𝑣 2 ), (𝑣 2, 𝑣 1 )}. However, it will resultin considerably more space and search costs. Second, a GTG willresult in many door-to-door edges for the same partition, whichwill render the graph-based search inefficient. The experimentalcomparison with GTG is reported in Section 6.The time-evolving function 𝑓 (𝑣𝑖 , 𝑣 𝑗 , 𝑑𝑘 ) models the number ofobjects flowing from 𝑣𝑖 to 𝑣 𝑗 at each report time interval of 𝑑𝑘 . Inpractice, it can be implemented as a time-series prediction modeldriven by historical data such as ARIMA [8] and LSTM [22], or itcan be approximated by a queueing distribution function. For theease of presentation, in this paper, we employ a specific queueingdistribution function to predict the door flows (Section 3.2). Nevertheless, the door flow function can be replaced by other appropriatemodels or functions, which entails no change to any of the otherparts in the overall computation framework (Figure 2).3.2Door Flow FunctionFollowing the classic Poisson distribution in queueing theory [7],we design the following door flow function:𝑓 (𝑣𝑖 , 𝑣 𝑗 , 𝑑𝑘 ) : 𝑡 P𝑡 , 𝑡 RT (𝑑𝑘 ), P𝑡 Poisson(𝜆)(5)where 𝑡 RT (𝑑𝑘 ) is a report timestamp of 𝑑𝑘 , P𝑡 is the populationthat flows from 𝑣𝑖 to 𝑣 𝑗 between 𝑡 and 𝑑𝑘 ’s next report timestamp,and 𝜆 is the expected value of P𝑡 under Poisson distribution.The door flow function is parameterized by 𝜆 and fitted basedon a recent period of historical records in a format of (𝑡 ′, P𝑡 ′ ).In practice, for each door counter, the most recent timestamps’flows can be accessed from the local array F in the graph edge. Anindependent thread estimates 𝜆 upon such most recent records. Notethat the focus of this paper is not to estimate 𝜆 based on historicaldata. For its technical details, we refer readers to a previous work [4].In our setting, at any query time, an up-to-date door flow functionis ready to predict flows for future report timestamps.4 TIME-EVOLVING POPULATIONS4.1 Rectifying Door FlowsAt a query time 𝑡𝑞 , we can access a partition 𝑣𝑘 ’s latest populationP𝑘𝑡𝑙 at an earlier time 𝑡𝑙 𝑡𝑞 from the indoor crowd model. To enablethe cost estimation for routing, we need to derive 𝑣𝑘 ’s time-evolvingpopulation and its future inflows/outflows based on P𝑘𝑡𝑙 .Let [𝑡 0, 𝑡 1 ] UTI (𝑣𝑘 ) be the unit time interval covering 𝑡𝑙 . Wehave P𝑘𝑡0 ,𝑡1 P𝑘𝑡𝑙 , meaning that 𝑣𝑘 ’s population over [𝑡 0, 𝑡 1 ] is equalto P𝑘𝑡𝑙 . Subsequently, for a future unit time interval [𝑡𝑥 , 𝑡𝑥 1 ] 1369UTI (𝑣𝑘 ), we compute its population asP𝑘𝑡𝑥 ,𝑡𝑥 1 P𝑘𝑡𝑥 1 ,𝑡𝑥 out (𝑣𝑘 , 𝑡𝑥 ) in(𝑣𝑘 , 𝑡𝑥 ), 𝑥 1, 2, . . .(6)where out (𝑣𝑘 , 𝑡𝑥 ) and in(𝑣𝑘 , 𝑡𝑥 ) are 𝑣𝑘 ’s estimated outflow andinflow at update timestamp 𝑡𝑥 , respectively.Suppose that all relevant door flow functions are ready at 𝑡𝑞 . Theinflow and outflow at a future update timestamp can be directlyestimated based on the expected values 𝜆. Formally,ÕÕout (𝑣𝑘 , 𝑡𝑥 ) 𝑓 (𝑣𝑘 , 𝑣 𝑝 , 𝑑𝑖 ).𝜆𝑑𝑖 P2D (𝑣𝑘 ) 𝑡𝑥 RT (𝑑𝑖 ) 𝑣𝑝 D2P (𝑑𝑖 )in(𝑣𝑘 , 𝑡𝑥 ) ÕÕ𝑓 (𝑣𝑞 , 𝑣𝑘 , 𝑑 𝑗 ).𝜆𝑑 𝑗 P2D (𝑣𝑘 ) 𝑡𝑥 RT (𝑑 𝑗 ) 𝑣𝑞 D2P (𝑑 𝑗 )where 𝑑𝑖 (resp. 𝑑 𝑗 ) is a leaveable (resp. enterable) door updated attime 𝑡𝑥 and 𝑣 𝑝 D2P (𝑑𝑖 ) (resp. 𝑣𝑞 D2P (𝑑𝑖 )) is its enterable(resp. leaveable) partition.However, the estimated flows may be contrary to the realsituation such that a partition’s current population (P𝑘𝑡𝑥 1 ,𝑡𝑥 inEquation 6) cannot satisfy its outflow (out (𝑣𝑘 , 𝑡𝑥 ) in Equation 6). Inthis case, flows at doors should be rectified.A basic idea is to rectify the expected outflow at each step suchthat it is not larger than the partition 𝑣𝑘 ’s current population.Meanwhile, 𝑣𝑘 ’s inflow is naturally rectified as it is derived from theoutflows of its adjacent partitions at the previous step. In general,a dependency exists between partitions. It demands a suitable wayto rectify the relevant outflows at the update timestamps.An example is depicted in Figure 4, which rectifies the doorflows globally. To ease the presentation, at each particular updatetimestamp 𝑡𝑥 we put the absolute populations and door flows ina 𝑉 𝑉 matrix M, where 𝑉 corresponds to the total numberof partitions. In particular, M[𝑖, 𝑖] refers to partition 𝑣𝑖 ’s absolutepopulation over unit time interval [𝑡𝑥 1, 𝑡𝑥 ], while M[𝑖, 𝑗] (𝑖 𝑗)means the flow value from partition 𝑣𝑖 to 𝑣 𝑗 over the next unit timeinterval [𝑡𝑥 , 𝑡𝑥 1 ]. Referring to Figure 4(a), partition 𝑣 1 ’s populationover [𝑡𝑥 1, 𝑡𝑥 ] is 3 and that of 𝑣 2 is 7. Besides, 𝑣 1 ’s expected outflowsto 𝑣 2 and 𝑣 3 are 4 and 2, respectively; 𝑣 2 ’s inflow from 𝑣 1 and 𝑣 3are 4 and 1, respectively. Considering the space efficiency, in theimplementation, we store the absolute populations on the graphnodes and the estimated flows on graph edges. That is, the spacecomplexity at each update timestamp is 𝑉 𝐸 .A rectification is then applied to each row of the original matrixas exemplified in Figure 4(b). Specifically, 𝑣 1 ’s current population(i.e., 3) is less than the summation of its subsequent outflows(i.e., 4 2 6). In this case, we scale down the outflows at alldoors to ensure that the actual number of objects outflowingis exactly equal to the current population. That is, M ′ [1, 2] M[1, 2] · (3/6) 2 and M ′ [1, 3] M[1, 3]

security-check line in an airport or a ticketing entrance in a theater. A Random Partition (R-partition) refers to a more general case where there is no restriction on how to pass the partition but one's movement slows down when encountering a crowd. Due to the different topological natures of the Q-partitions and R-partitions, 1365