Shortest Path Queries for Indoor Venues with Temporal Variations

Shortest Path Queries for Indoor Venues with Temporal Variations

Tiantian Liu Zijin Feng Huan Li Hua Lu Muhammad Aamir Cheema? Hong Cheng Jianliang Xu

Aalborg University, Denmark The Chinese University of Hong Kong, Hong Kong

?Monash University, Australia Hong Kong Baptist University, Hong Kong

1. Introduction

2. Problem Formulation

? Background.

- Indoor location-based services are becoming increasingly popular. - Shortest path/distance queries are fundamental in many indoor locationbased services. - Some temporal variations could change the indoor topology.

? Challenges of handling indoor temporal-variation aware shortest path

query (ITSPQ). - The existing graphs used to model the indoor space do not consider temporal variations. - The pre-computed and materialized door-to-door distances become invalid when one or more doors open or close at certain times.

? Contributions.

- A new type of query called Indoor Temporal-variation aware Shortest Path Query (ITSPQ) is defined. - A graph structure (IT-Graph) that captures indoor temporal variations is designed. - We design two algorithms that check a door's accessibility synchronously and asynchronously, respectively. - We experimentally evaluate the proposed techniques using synthetic data. The results show that our methods are efficient.

? Active Time Interval (ATI). We use

[open-time, close-time) to denote an active time interval (ATI) of a door.

? Indoor Temporal-variation Aware

Shortest Path Query (ITSPQ). Given a start point ps, a target point pt, and a current timestamp t, an indoor temporal-variation aware shortest path query ITSPQ(ps, pt, t) returns the valid shortest path from ps to pt that meets: 1) Each door di in the path should

be open at t + t, where t is

the walking time from ps to di and it is computed based on human's

average walking speed -- 5km/h;

2) The path should not go through any private partition except the private partitions that contain ps and/or pt.

Active Time Intervals (ATIs) of Doors

Door, ATIs

Door, ATIs

d1, [5:00, 23:00) d3, [6:00, 23:00) d5, [6:30, 23:00) d7, [6:00, 23:30) d9, [0:00, 6:00), [6:30, 23:00) d11, [5:00, 23:00) d13, [5:00, 17:00), [18:00, 23:00) d15, [8:00, 16:00) d17, [0:00, 24:00) d19, [8:00, 16:00) d21, [8:00, 16:00)

d2, [8:00, 16:00) d4, [9:00, 18:00) d6, [8:00, 16:00) d8, [9:00, 18:00) d10, [8:00, 16:00) d12, [5:00, 23:00) d14, [0:00, 24:00) d16, [8:00, 17:00) d18, [0:00, 23:00) d20, [5:00, 23:00)

v1

v3

v4

v9

d1 p1

d4

d8

v7 d12

v2

10m d5

v5

d9

d13

d2

d10

v10

d3

d6 d7

v6

v8 d14

d2 d14 doors

v17

5m 2m 6m

4m d17

p2

v11 d18

8m

p3

3m

door directionality

d21

d19 d20 v14 4m d16 5md15

v10

public partition

v16 v12

p4 2m v13 d11

v15

v8

private partition

4. Experimental Results

3. ITSPQ Processing

? Indoor temporal-variation graph (IT-Graph) GIT (V , E, Lv, LE): 1) V is the set of vertices such that each vertex v V is an indoor partition. 2) E is the set of directed edges such that each edge (vi, vj, dk ) E means

one can reach vj from vi through a door dk . 3) LV is the set of vertex labels, each being a 3-tuple(IDv, p-type, DM). 4) LE is the set of edge labels, each being a 3-tuple (IDd, d-type, ATIs).

v1

v4

d1 v2

d2

v3 d5 d3 d6 v6

v16

v12

v7 v5

v8 v11

v9 v10

v14 v0

v17

v13

public partition

outdoors

v15 private partition

Door Table

IDd d-type ATIs

d7 PRD [6:00, 23:30)

d3 PBD [6:00, 23:00)

......

...

Partition Table

IDv p-type DM

v1 PRP [[(d1, d1), 0]]

v16 PBP

[[(d3, d17), 2], [(d3, d21), 4], [(d17, d21), 5]]

......

...

? Different Methods for ITSPQ Processing

Method 1: ITG/S

ITSPQ_ITGraph

( Algorithm 1 )

Method 2: ITG/A

TV_Check()

Syn_Check()

( Algorithm 2 )

instantiated

Asyn_Check()

( Algorithm 4 )

IT-Graph

Graph_Update()

( Algorithm 3 )

? Indoor Space Settings. A 5-floor

indoor space with 705 partitions and 1120 doors.

? Temporal Variations. We select

random pairs of open time and close time to form the checkpoint

Parameter Settings for Synthetic Data

Parameters

Settings

|T | s2t (m)

t

4, 8, 12, 16 1100, 1300, 1500, 1700, 1900 0:00, 2:00, . . . , 12:00, . . . , 22:00

set T in size of 4, 8, 12, or 16.

? Query Instances. For each setting of s2t, we generate five pairs of ps and pt

to form the query instances. In each query instance, time t is fixed to 12:00

to make a fair comparison.

? Performance Metrics. We run each query instance ten times, and measure

the average running time and memory cost.

? Results.

40k

IT G /S (t= 1 2 )

IT G /S (t= 8 )

105

IT G /A (t= 1 2 )

IT G /A (t= 8 )

IT G /S IT G /A

30k

S e a r c h T im e ( u s .)

S e a r c h T im e ( u s .)

20k 104

10k

4

8

12

16

1100 1300 1500 1700 1900

|T |

(m )

s2 t

105

1500

IT G /S

IT G /A

104

1000

M e m o ry C o s t (K B .)

S e a r c h T im e ( u s .)

1) Synchronous Check. Look up a door d's ATIs and compare it to the arrival time when one just leaves for d.

2) Asynchronous Check. Directly refer to a time-dependent IT-Graph that only keeps all currently open doors. The information of IT-Graph only needs to be updated asynchronously at the next checkpoint.

103 IT G /S IT G /A

102 0 2 4 6 8 10121416182022

t ( o 'c lo c k )

500

0 0 2 4 6 8 10 12 14 16 18 20 22

t ( o 'c l o c k )

D ICDE 2020

liutt@cs.aau.dk

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download