@Preamble{"\input bibnames.sty" #
"\def \TM {${}^{\sc TM}$}"
}
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
@String{j-TSAS = "ACM Transactions on Spatial Algorithms and
Systems (TSAS)"}
@Article{Gemsa:2015:MBL,
author = "Andreas Gemsa and Jan-Henrik Haunert and Martin
N{\"o}llenburg",
title = "Multirow Boundary-Labeling Algorithms for Panorama
Images",
journal = j-TSAS,
volume = "1",
number = "1",
pages = "1:1--1:30",
month = aug,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2794299",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:00 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2794299",
abstract = "Boundary labeling deals with placing annotations for
objects in an image on the boundary of that image. This
problem occurs frequently in situations in which
placing labels directly in the image is impossible or
produces too much visual clutter. Examples are
annotating maps, photos, or technical/medical
illustrations. Previous algorithmic results for
boundary labeling consider a single layer of labels
along some or all sides of a rectangular image. If,
however, the number of labels is large or the labels
are too long, multiple layers of labels are needed. In
this article, we study boundary labeling for panorama
images, where $ n $ points in a rectangle R are to be
annotated by disjoint unit-height rectangular labels
placed above R in K different rows (or layers). Each
point is connected to its label by a vertical leader
that does not intersect any other label. We present
polynomial time algorithms based on dynamic programming
that either minimize the number of rows to place all n
labels or maximize the number (or total weight) of
labels that can be placed in K rows for a given integer
K. For weighted labels, the problem is shown to be
(weakly) NP-hard; in this case, we give a
pseudo-polynomial algorithm to maximize the weight of
the selected labels. We have implemented our
algorithms; the experimental results show that
solutions for realistically sized instances are
computed instantaneously. We have also investigated
two-sided panorama labeling, for which the labels may
be placed above or below the panorama image. In this
model, all of the aforementioned problems are NP-hard.
For solving them, we propose mixed-integer linear
program formulations.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{To:2015:SAS,
author = "Hien To and Cyrus Shahabi and Leyla Kazemi",
title = "A Server-Assigned Spatial Crowdsourcing Framework",
journal = j-TSAS,
volume = "1",
number = "1",
pages = "2:1--2:28",
month = aug,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2729713",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:00 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2729713",
abstract = "With the popularity of mobile devices, spatial
crowdsourcing is rising as a new framework that enables
human workers to solve tasks in the physical world.
With spatial crowdsourcing, the goal is to crowdsource
a set of spatiotemporal tasks (i.e., tasks related to
time and location) to a set of workers, which requires
the workers to physically travel to those locations in
order to perform the tasks. In this article, we focus
on one class of spatial crowdsourcing, in which the
workers send their locations to the server and
thereafter the server assigns to every worker tasks in
proximity to the worker's location with the aim of
maximizing the overall number of assigned tasks. We
formally define this maximum task assignment (MTA)
problem in spatial crowdsourcing, and identify its
challenges. We propose alternative solutions to address
these challenges by exploiting the spatial properties
of the problem space, including the spatial
distribution and the travel cost of the workers. MTA is
based on the assumptions that all tasks are of the same
type and all workers are equally qualified in
performing the tasks. Meanwhile, different types of
tasks may require workers with various skill sets or
expertise. Subsequently, we extend MTA by taking the
expertise of the workers into consideration. We refer
to this problem as the maximum score assignment (MSA)
problem and show its practicality and generality.
Extensive experiments with various synthetic and two
real-world datasets show the applicability of our
proposed framework.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ahmed:2015:PBD,
author = "Mahmuda Ahmed and Brittany Terese Fasy and Kyle S.
Hickmann and Carola Wenk",
title = "A Path-Based Distance for Street Map Comparison",
journal = j-TSAS,
volume = "1",
number = "1",
pages = "3:1--3:28",
month = aug,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2729977",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:00 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2729977",
abstract = "Comparing two geometric graphs embedded in space is
important in the field of transportation network
analysis. Given street maps of the same city collected
from different sources, researchers often need to know
how and where they differ. However, the majority of
current graph comparison algorithms are based on
structural properties of graphs, such as their degree
distribution or their local connectivity properties,
and do not consider their spatial embedding. This
ignores a key property of road networks since the
similarity of travel over two road networks is
intimately tied to the specific spatial embedding.
Likewise, many current algorithms specific to street
map comparison either do not provide quality guarantees
or focus on spatial embeddings only. Motivated by road
network comparison, we propose a new path-based
distance measure between two planar geometric graphs
that is based on comparing sets of travel paths
generated over the graphs. Surprisingly, we are able to
show that using paths of bounded link-length, we can
capture global structural and spatial differences
between the graphs. We show how to utilize our distance
measure as a local signature in order to identify and
visualize portions of high similarity in the maps.
Finally, we present an experimental evaluation of our
distance measure and its local signature on street map
data from Berlin, Germany and Athens, Greece.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Mckennney:2015:GMR,
author = "Mark Mckennney and Roger Frye",
title = "Generating Moving Regions from Snapshots of Complex
Regions",
journal = j-TSAS,
volume = "1",
number = "1",
pages = "4:1--4:30",
month = aug,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2774220",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:00 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2774220",
abstract = "Moving regions are a form of spatiotemporal data in
which a region changes in shape and/or position over
time. In many fields, moving regions representing
real-world phenomena are collected using sensors that
take temporally encoded snapshots of regions. We
provide a novel algorithm that creates a moving region
between any two complex regions. The proposed algorithm
has worst-case time bounds of O; ( n; 2 ), but can use
approximation techniques to achieve O ( $ n $ lg $ n $ ) in
practice, space bounds of O; ( n; ), and output size
bounded by O; ( n; ) (where n; is the number of line
segments that define the boundaries of the regions).",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Tang:2015:EGF,
author = "Suhua Tang and Yi Yu and Roger Zimmermann and Sadao
Obana",
title = "Efficient Geo-Fencing via Hybrid Hashing: A
Combination of Bucket Selection and In-Bucket Binary
Search",
journal = j-TSAS,
volume = "1",
number = "2",
pages = "5:1--5:22",
month = nov,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2774219",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/hash.bib;
http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2774219",
abstract = "Geo-fencing, as a spatial join between points (moving
objects) and polygons (spatial range), is widely used
in emerging location-based services to trigger
context-aware events. It faces the challenge of
real-time processing a large number of time-variant
complex polygons, when points are constantly moving.
Following the filter-and-refine policy, in our previous
work, we proposed to organize edges per polygon in hash
tables to improve the performance of the refining
stage. The number of edges, however, is uneven among
buckets. As a result, some points that happen to match
big buckets with many edges will have much longer
responses than usual. In this article, we solve this
problem from two aspects: (i) Constructing multiple
parallel hash tables and dynamically selecting the
bucket with fewest edges and (ii) sorting edges in a
bucket so as to realize the crossing number algorithm
by binary search. We further combine the two to suggest
a hybrid hashing scheme that takes a better tradeoff
between real-time pairing points with polygons and
system overhead of building hash tables. Extensive
analyses and evaluations on two real-world datasets
confirm that the proposed scheme can effectively reduce
the pairing time in terms of both the average and
distribution.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{That:2015:TGT,
author = "Dai Hai Ton That and Iulian Sandu Popa and Karine
Zeitouni",
title = "{TRIFL}: A Generic Trajectory Index for Flash
Storage",
journal = j-TSAS,
volume = "1",
number = "2",
pages = "6:1--6:44",
month = nov,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2786758",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2786758",
abstract = "Due to several important features, such as high
performance, low power consumption, and shock
resistance, NAND flash has become a very popular stable
storage medium for embedded mobile devices, personal
computers, and even enterprise servers. However, the
peculiar characteristics of flash memory require
redesigning the existing data storage and indexing
techniques that were devised for magnetic hard disks.
In this article, we propose TRIFL, an efficient and
generic TRajectory Index for FLash. TRIFL is designed
around the key requirements of trajectory indexing and
flash storage. TRIFL is generic in the sense that it is
efficient for both simple flash storage devices such as
SD cards and more powerful devices such as solid state
drives. In addition, TRIFL is supplied with an online
self-tuning algorithm that allows adapting the index
structure to the workload and the technical
specifications of the flash storage device to maximize
the index performance. Moreover, TRIFL achieves good
performance with relatively low memory requirements,
which makes the index appropriate for many application
scenarios. The experimental evaluation shows that TRIFL
outperforms the representative indexing methods on
magnetic disks and flash disks.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Guting:2015:ST,
author = "Ralf Hartmut G{\"u}ting and Fabio Vald{\'e}s and Maria
Luisa Damiani",
title = "Symbolic Trajectories",
journal = j-TSAS,
volume = "1",
number = "2",
pages = "7:1--7:51",
month = nov,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2786756",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2786756",
abstract = "Due to the proliferation of GPS-enabled devices in
vehicles or with people, large amounts of position data
are recorded every day and the management of such
mobility data, also called trajectories, is a very
active research field. A lot of effort has gone into
discovering ``semantics'' from the raw geometric
trajectories by relating them to the spatial
environment or finding patterns, for example, by data
mining techniques. A question is how the resulting
``meaningful'' trajectories can be represented or
further queried. In this article, we propose a
systematic study of annotated trajectory databases. We
define a very simple generic model called symbolic
trajectory to capture a wide range of meanings derived
from a geometric trajectory. Essentially, a symbolic
trajectory is just a time-dependent label; variants
have sets of labels, places, or sets of places. They
are modeled as abstract data types and integrated into
a well-established framework of data types and
operations for moving objects. Symbolic trajectories
can represent, for example, the names of roads
traversed obtained by map matching, transportation
modes, speed profile, cells of a cellular network,
behaviors of animals, cinemas within 2km distance, and
so forth. Symbolic trajectories can be combined with
geometric trajectories to obtain annotated
trajectories. Besides the model, the main technical
contribution of the article is a language for pattern
matching and rewriting of symbolic trajectories. A
symbolic trajectory can be represented as a sequence of
pairs (called units) consisting of a time interval and
a label. A pattern consists of unit patterns
(specifications for time interval and/or label) and
wildcards, matching units and sequences of units,
respectively, and regular expressions over such
elements. It may further contain variables that can be
used in conditions and in rewriting. Conditions and
expressions in rewriting may use arbitrary operations
available for querying in the host DBMS environment,
which makes the language extensible and quite powerful.
We formally define the data model and syntax and
semantics of the pattern language. Query operations are
offered to integrate pattern matching, rewriting, and
classification of symbolic trajectories into a DBMS
querying environment. Implementation of the model using
finite state machines is described in detail. An
experimental evaluation demonstrates the efficiency of
the implementation. In particular, it shows dramatic
improvements in storage space and response time in a
comparison of symbolic and geometric trajectories for
some simple queries that can be executed on both
symbolic and raw trajectories.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Kovanen:2015:TAC,
author = "Janne Kovanen and Tapani Sarjakoski",
title = "Tilewise Accumulated Cost Surface Computation with
Graphics Processing Units",
journal = j-TSAS,
volume = "1",
number = "2",
pages = "8:1--8:27",
month = nov,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2803172",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/pvm.bib;
http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2803172",
abstract = "Accumulated cost surfaces are used in a variety of
fields that employ spatial analysis. Several algorithms
have been suggested in the past for solving them
efficiently or with minimal errors. Meanwhile, a new
wave on the technological frontier has brought about
general-purpose computing on GPUs. In this article, we
describe how accumulated cost surfaces can be solved
with CUDA. To verify the performance of our solution,
we performed an experimental comparison against
implementations run on a CPU. Our results with
realistic cost models indicate that the move to GPUs
can engender a speed-up of an order of magnitude.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Belussi:2016:SRR,
author = "Alberto Belussi and Sara Migliorini and Mauro Negri
and Giuseppe Pelagatti",
title = "Snap Rounding with Restore: An Algorithm for Producing
Robust Geometric Datasets",
journal = j-TSAS,
volume = "2",
number = "1",
pages = "1:1--1:36",
month = apr,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2811256",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2811256",
abstract = "This article presents a new algorithm called Snap
Rounding with Restore (SRR), which aims to make
geometric datasets robust and to increase the quality
of geometric approximation and the preservation of
topological structure. It is based on the well-known
Snap Rounding algorithm but improves it by eliminating
from the snap rounded arrangement the configurations in
which the distance between a vertex and a nonincident
edge is smaller than half the width of a pixel of the
rounding grid. Therefore, the goal of SRR is exactly
the same as the goal of another algorithm, Iterated
Snap Rounding (ISR), and of its evolution, Iterated
Snap Rounding with Bounded Drift (ISRBD). However, SRR
produces an output with a quality of approximation that
is on average better than ISRBD, under the viewpoint
both of the distance from the original segments and of
the conservation of their topological structure. The
article also reports some cases where ISRBD,
notwithstanding the bounded drift, produces strong
topological modifications while SRR does not. A
statistical analysis on a large collection of input
datasets confirms these differences. It follows that
the proposed Snap Rounding with Restore algorithm is
suitable for applications that require robustness, a
guaranteed geometric approximation, and a good
topological approximation.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Buchin:2016:APS,
author = "Kevin Buchin and Wouter Meulemans and Andr{\'e} {Van
Renssen} and Bettina Speckmann",
title = "Area-Preserving Simplification and Schematization of
Polygonal Subdivisions",
journal = j-TSAS,
volume = "2",
number = "1",
pages = "2:1--2:36",
month = apr,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2818373",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2818373",
abstract = "In this article, we study automated simplification and
schematization of territorial outlines. We present a
quadratic-time simplification algorithm based on an
operation called edge-move. We prove that the number of
edges of any nonconvex simple polygon can be reduced
with this operation. Moreover, edge-moves preserve area
and topology and do not introduce new orientations. The
latter property in particular makes the algorithm
highly suitable for schematization in which all
resulting lines are required to be parallel to one of a
given set of lines (orientations). To obtain such a
result, we need only to preprocess the input to use
only lines that are parallel to one of the given set.
We present an algorithm to enforce such orientation
restrictions, again without changing area or topology.
Experiments show that our algorithms obtain results of
high visual quality.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ali:2016:SCQ,
author = "Mohammed Eunus Ali and Egemen Tanin and Peter
Scheuermann and Sarana Nutanong and Lars Kulik",
title = "Spatial Consensus Queries in a Collaborative
Environment",
journal = j-TSAS,
volume = "2",
number = "1",
pages = "3:1--3:37",
month = apr,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2829943",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2829943",
abstract = "We introduce a new type of query for a location-based
social network platform. Consider a scenario in which a
group of users is trying to find a common meeting
location, yet attempting to include all group members
is introducing a significant traveling cost to most of
them. In this article, we formulate a new query type
called the consensus query, which can be used to help
users explore these trade-off options to find a
solution upon which everyone can agree. Specifically,
we study the problem of evaluating consensus queries in
the context of nearest neighbor queries, where the
group is interested in finding a meeting place that
minimizes the travel distance for at least a specified
number of group members. To help the group in selecting
a suitable solution, the major challenge is to find
optimal subgroups of all allowable subgroup sizes,
i.e., greater or equal to the minimum specified
subgroup size, that minimize the travel distances. We
develop incremental algorithms to evaluate in one pass
the optimal query subgroups of different sizes along
with their corresponding nearest data points. These
subsets, which are evaluated by the location-based
service provider, constitute the answer set that is
returned to the group. The group then collaboratively
selects the final answer from the candidate answer set.
An extensive experimental study shows the efficiency
and effectiveness of our proposed techniques.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Goel:2016:PAD,
author = "Preeti Goel and Lars Kulik and Kotagiri
Ramamohanarao",
title = "Privacy-Aware Dynamic Ride Sharing",
journal = j-TSAS,
volume = "2",
number = "1",
pages = "4:1--4:41",
month = apr,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2845080",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:01 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2845080",
abstract = "Dynamic ride sharing is a service that enables shared
vehicle rides in real time and on short notice. It can
be an effective solution to counter the problem of
increasing traffic jams at peak hours in cities. The
growing use and popularity of smart phones and
GPS-enabled devices provides us with tools required to
efficiently implement ride sharing and significantly
enhance carpooling. However, privacy and safety
concerns are the main obstacles faced when encouraging
people to use such a service. In this work, we present
``Match Maker,'' a negotiation-based model that hides
exact location information data for system participants
while implementing privacy preserving ride sharing. We
use the concept of imprecision (not being precise about
location of the user out of set of $ n $ locations) and
follow the idea of obfuscation, which equates a higher
degree of imprecision with a higher degree of privacy.
We identify two attack types that could circumvent
privacy preserving ride sharing. We compare the Match
Maker model with the standard central trusted server
model collecting precise location data, which we term
eBay model. We provide the first comprehensive approach
that integrates privacy, safety and trust in a single
model. We present a recursive ellipse-based algorithm
to compute an optimal driver path as well as three
negotiation strategies for drivers and passengers. We
conduct extensive experiments on real road networks and
compare the strategies for privacy and effectiveness of
ride sharing in terms of traffic load and vehicle km
reduction. We show that ride sharing saves between 9\%
and 21\% (on average 12\%) of vehicle km if drivers are
only prepared to accept slight detours of their usual
trips. In the city of Melbourne, with 11.6 million
trips a weekday and an average trip length of 10.2 km,
this would save 14.2 million km per weekday.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Skoumas:2016:LEU,
author = "Georgios Skoumas and Dieter Pfoser and Anastasios
Kyrillidis and Timos Sellis",
title = "Location Estimation Using Crowdsourced Spatial
Relations",
journal = j-TSAS,
volume = "2",
number = "2",
pages = "5:1--5:23",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2894745",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 15:01:39 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2894745",
abstract = "The ``crowd'' has become a very important geospatial
data provider. Specifically, nonexpert users have been
providing a wealth of quantitative geospatial data
(e.g., geotagged tweets or photos, online). With
spatial reasoning being a basic form of human
cognition, textual narratives expressing user travel
experiences (e.g., travel blogs) would provide an even
bigger source of geospatial data. Narratives typically
contain qualitative geospatial data in the form of
objects and spatial relations (e.g., ``St. John's
church is to the North of the Acropolis museum.''). The
scope of this work is (i) to extract these spatial
relations from textual narratives, (ii) to quantify
(model) them, and (iii) to reason about object
locations based only on the quantified spatial
relations. We use information extraction methods to
identify toponyms and spatial relations, and we
formulate a quantitative approach based on distance and
orientation features to represent the latter.
Probability density functions (PDFs) for spatial
relations are determined by means of a greedy
expectation maximization (EM)-based algorithm. These
PDFs are then used to estimate unknown object
locations. Experiments using a text corpus harvested
from travel blog sites establish the considerable
location estimation accuracy of the proposed approach
on synthetic and real-world scenarios.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ferreira:2016:EEM,
author = "Chaulio R. Ferreira and Marcus V. A. Andrade and
Salles V. G. Magalh{\~a}es and W. Randolph Franklin",
title = "An Efficient External Memory Algorithm for Terrain
Viewshed Computation",
journal = j-TSAS,
volume = "2",
number = "2",
pages = "6:1--6:17",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2903206",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 15:01:39 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2903206",
abstract = "This article presents TiledVS, a fast external
algorithm and implementation for computing viewsheds.
TiledVS is intended for terrains that are too large for
internal memory, even more than 100,000 $ \times $
100,000 points. It subdivides the terrain into tiles
that are stored compressed on disk and then paged into
memory with a custom cache data structure and least
recently used algorithm. If there is sufficient
available memory to store a whole row of tiles, which
is easy, then this specialized data management is
faster than relying on the operating system's virtual
memory management. Applications of viewshed computation
include siting radio transmitters, surveillance, and
visual environmental impact measurement. TiledVS runs a
rotating line of sight from the observer to points on
the region boundary. For each boundary point, it
computes the visibility of all terrain points close to
the line of sight. The running time is linear in the
number of points. No terrain tile is read more than
twice. TiledVS is very fast, for instance, processing a
104,000 $ \times $ 104,000 terrain on a modest computer
with only 512MB of RAM took only $ 1.5 $ hours. On
large datasets, TiledVS was several times faster than
competing algorithms, such as the ones included in
GRASS. The source code of TiledVS is freely available
for nonprofit researchers to study, use, and extend. A
preliminary version of this algorithm appeared in a
four-page ACM SIGSPATIAL GIS 2012 conference paper,
``More Efficient Terrain Viewshed Computation on
Massive Datasets Using External Memory.'' This more
detailed version adds the fast lossless compression
stage that reduces the time by 30\% to 40\%, and many
more experiments and comparisons.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Agarwal:2016:TNN,
author = "Pankaj K. Agarwal and Alex Beutel and Thomas
M{\o}lhave",
title = "{TerraNNI}: Natural Neighbor Interpolation on {$2$D}
and {$3$D} Grids Using a {GPU}",
journal = j-TSAS,
volume = "2",
number = "2",
pages = "7:1--7:31",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2786757",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 15:01:39 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2786757",
abstract = "With modern focus on remote sensing technology, such
as LiDAR, the amount of spatial data, in the form of
massive point clouds, has increased dramatically.
Furthermore, repeated surveys of the same areas are
becoming more common. This trend will only increase as
topographic changes prompt surveys over already scanned
areas, in which case we obtain large spatiotemporal
datasets. An initial step in the analysis of such
spatial data is to create a digital elevation model
representing the terrain, possibly over time. In the
case of spatial (spatiotemporal, respectively)
datasets, these models often represent elevation on a
2D (3D, respectively) grid. This involves interpolating
the elevation of LiDAR points on these grid points. In
this article, we show how to efficiently perform
natural neighbor interpolation over a 2D and 3D grid.
Using a graphics processing unit (GPU), we describe
different algorithms to attain speed and GPU-memory
tradeoffs. Our experimental results demonstrate that
our algorithms not only are significantly faster than
earlier ones but also scale to much bigger datasets
that previous algorithms were unable to handle.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ghinita:2016:PAV,
author = "Gabriel Ghinita and Maria Luisa Damiani and Claudio
Silvestri and Elisa Bertino",
title = "Protecting Against Velocity-Based, Proximity-Based,
and External Event Attacks in Location-Centric Social
Networks",
journal = j-TSAS,
volume = "2",
number = "2",
pages = "8:1--8:36",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2910580",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 15:01:39 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2910580",
abstract = "Mobile devices with positioning capabilities allow
users to participate in novel and exciting
location-based applications. For instance, users may
track the whereabouts of their acquaintances in
location-aware social networking applications (e.g.,
Foursquare). Furthermore, users can request information
about landmarks in their proximity. Such scenarios
require users to report their coordinates to other
parties, which may not be fully trusted. Reporting
precise locations may result in serious privacy
violations, such as disclosure of lifestyle details,
sexual orientation, and so forth. A typical approach to
preserve location privacy is to generate a cloaking
region (CR) that encloses the user position. However,
if locations are continuously reported, an attacker can
correlate CRs from multiple timestamps to accurately
pinpoint the user position within a CR. In this work,
we protect against a broad range of attacks that breach
location privacy using knowledge about (1) maximum user
velocity, (2) external events that may occur outside
the process of self-reporting locations (e.g., social
network posts tagged by peers), and (3) information
about mutual proximity between users. Assume user u who
reports two consecutive cloaked regions A and B. We
consider two distinct protection scenarios: in the
first case, the attacker does not have information
about the sensitive locations on the map, and the
objective is to ensure that u can reach some point in B
from any point in A; in the second case, the attacker
knows the placement of sensitive locations, and the
objective is to ensure that u can reach any point in B
from any point in A. We propose spatial and temporal
cloaking transformations to preserve user privacy, and
we show experimentally that privacy can be achieved
without significant quality-of-service deterioration.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Efstathiades:2016:EPR,
author = "Christodoulos Efstathiades and Alexandros Efentakis
and Dieter Pfoser",
title = "Efficient Processing of Relevant Nearest-Neighbor
Queries",
journal = j-TSAS,
volume = "2",
number = "3",
pages = "9:1--9:28",
month = oct,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2934675",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:02 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2934675",
abstract = "Novel Web technologies and resulting applications have
led to a participatory data ecosystem that, when
utilized properly, will lead to more rewarding
services. In this work, we investigate the case of
Location-Based Services, specifically how to improve
the typical location-based Point-of-Interest (POI)
request processed as a k -Nearest-Neighbor query. This
work introduces Links-of-Interest (LOI) between POIs as
a means to increase the relevance and overall result
quality of such queries. By analyzing user-contributed
content in the form of travel blogs, we establish the
overall popularity of an LOI, that is, how frequently
the respective POI pair was visited and is mentioned in
the same context. Our contribution is a
query-processing method for so-called k -Relevant
Nearest Neighbor ( k -RNN) queries that considers
spatial proximity in combination with LOI information
to retrieve close-by and relevant (as judged by the
crowd) POIs. Our method is based on intelligently
combining indices for spatial data (a spatial grid) and
for relevance data (a graph) during query processing.
Using landmarks as a means to prune the search space in
the Relevance Graph, we improve the proposed methods.
Using in addition A*-directed search, the query
performance can be further improved. An experimental
evaluation using real and synthetic data establishes
that our approach efficiently solves the k -RNN
problem.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Pillai:2016:MMT,
author = "Karthik Ganesan Pillai and Rafal A. Angryk and Juan M.
Banda and Dustin Kempton and Berkay Aydin and Petrus C.
Martens",
title = "Mining At Most Top-{$K$ \%} Spatiotemporal
Co-occurrence Patterns in Datasets with Extended
Spatial Representations",
journal = j-TSAS,
volume = "2",
number = "3",
pages = "10:1--10:27",
month = oct,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2936775",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:02 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2936775",
abstract = "Spatiotemporal co-occurrence patterns (STCOPs) in
datasets with extended spatial representations are two
or more different event types, represented as polygons
evolving in time, whose instances often occur together
in both space and time. Finding STCOPs is an important
problem in domains such as weather monitoring, wildlife
migration, and solar physics. Nevertheless, in real
life, it is difficult to find a suitable prevalence
threshold without prior domain-specific knowledge. In
this article, we focus our work on the problem of
mining at most top-K\% of STCOPs from continuously
evolving spatiotemporal events that have polygon-like
representations, without using a user-specified
prevalence threshold.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Pelekis:2016:SOL,
author = "Nikos Pelekis and Stylianos Sideridis and Panagiotis
Tampakis and Yannis Theodoridis",
title = "Simulating Our {LifeSteps} by Example",
journal = j-TSAS,
volume = "2",
number = "3",
pages = "11:1--11:39",
month = oct,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2937753",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:02 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2937753",
abstract = "During the past few decades, a number of effective
methods for indexing, query processing, and knowledge
discovery in moving object databases have been
proposed. An interesting research direction that has
recently emerged handles semantics of movement instead
of raw spatio-temporal data. Semantic annotations, such
as ``stop,'' ``move,'' ``at home,'' ``shopping,''
``driving,'' and so on, are either declared by the
users (e.g., through social network apps) or
automatically inferred by some annotation method and
are typically presented as textual counterparts along
with spatial and temporal information of raw
trajectories. It is natural to argue that such
``spatio-temporal-textual'' sequences, called semantic
trajectories, form a realistic representation model of
the complex everyday life (hence, mobility) of
individuals. Towards handling semantic trajectories of
moving objects in Semantic Mobility Databases, the lack
of real datasets leads to the need to design realistic
simulators. In the context of the above discussion, the
goal of this work is to realistically simulate the
mobility life of a large-scale population of moving
objects in an urban environment. Two simulator
variations are presented: the core Hermoupolis
simulator is parametric driven (i.e., user-defined
parameters tune every movement aspect), whereas the
expansion of the former, called Hermoupolis by-example,
follows the generate-by-example paradigm and is
self-tuned by looking inside a real small (sample)
dataset. We stress test our proposal and demonstrate
its novel characteristics with respect to related
work.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Hung:2016:SIA,
author = "Hui-Ju Hung and De-Nian Yang and Wang-Chien Lee",
title = "Social Influence-Aware Reverse Nearest Neighbor
Search",
journal = j-TSAS,
volume = "2",
number = "3",
pages = "12:1--12:35",
month = oct,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2964906",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:02 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2964906",
abstract = "Business-location planning, critical to the success of
many businesses, can be addressed by the reverse
nearest neighbors (RNN) query using geographical
proximity to the customers as the main metric to find a
store location close to many customers. Nevertheless,
we argue that other marketing factors, such as social
influence, could be considered in the process of
business-location planning. In this article, we propose
a framework for business-location planning that takes
into account both factors of geographical proximity and
social influence. An essential task in this framework
is to compute the ``influence spread'' of RNNs for
candidate locations. Here, the influence spread refers
to the number of people influenced via the
word-of-mouth effect. To alleviate the excessive
computational overhead and long latency in the
framework, we trade storage overhead for processing
speed by precomputing and storing the social influence
between pairs of customers. Based on Targeted Region
(TR)-Oriented and RNN-Oriented processing strategies,
we develop two suites of algorithms that incorporate
various efficient pruning and segmentation techniques
to enhance our framework. Experiments validate our
ideas and evaluate the efficiency of the proposed
algorithms over various parameter settings. The
experimental results show that (a) TR-oriented and
RNN-oriented processing are feasible for supporting the
task of location planning; (b) RNN-oriented processing
is more efficient than TR-oriented processing; and (c)
the optimization technique that we developed
significantly improves the efficiency of RNN-oriented
and TR-oriented processing.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Budig:2016:MLM,
author = "Benedikt Budig and Thomas C. {Van Dijk} and Alexander
Wolff",
title = "Matching Labels and Markers in Historical Maps: An
Algorithm with Interactive Postprocessing",
journal = j-TSAS,
volume = "2",
number = "4",
pages = "13:1--13:24",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2994598",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2994598",
abstract = "In this article, we present an algorithmic system for
determining the proper correspondence between place
markers and their labels in historical maps. We assume
that the locations of place markers (usually
pictographs) and labels (pieces of text) have already
been determined -- either algorithmically or by hand --
and we want to match the labels to the markers. This
time-consuming step in the digitization process of
historical maps is nontrivial even for humans but
provides valuable metadata (e.g., when subsequently
georeferencing the map). To speed up this process, we
model the problem in terms of combinatorial
optimization, solve that problem efficiently, and show
how user interaction can be used to improve the quality
of the results. We also consider a version of the model
where we are given label fragments and additionally
have to decide which fragments go together. We show
that this problem is NP-hard. However, we give a
polynomial-time algorithm for a restricted version of
this fragment assignment problem. We have implemented
the algorithm for the main problem and tested it on a
manually extracted ground truth for eight historical
maps with a combined total of more than 12,800 markers
and labels. On average, the algorithm correctly matches
96\% of the labels and is robust against noisy input.
It furthermore performs a sensitivity analysis and in
this way computes a measure of confidence for each of
the matches. We use this as the basis for an
interactive system where the user's effort is directed
to checking those parts of the map where the algorithm
is unsure; any corrections the user makes are
propagated by the algorithm. We discuss a prototype of
this system and statistically confirm that it
successfully locates those areas on the map where the
algorithm needs help.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Niu:2016:LED,
author = "Wei Niu and Zhijiao Liu and James Caverlee",
title = "On Local Expert Discovery via Geo-Located Crowds,
Queries, and Candidates",
journal = j-TSAS,
volume = "2",
number = "4",
pages = "14:1--14:24",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2994599",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2994599",
abstract = "Local experts are critical for many location-sensitive
information needs, and yet there is a research gap in
our understanding of the factors impacting who is
recognized as a local expert and in methods for
discovering local experts. Hence, in this article, we
explore a geo-spatial learning-to-rank framework for
identifying local experts. Three of the key features of
the proposed approach are: (i) a learning-based
framework for integrating multiple user-based,
content-based, list-based, and crowd-based factors
impacting local expertise that leverages the
fine-grained GPS coordinates of millions of social
media users; (ii) a location-sensitive random walk that
propagates crowd knowledge of a candidate's expertise;
and (iii) a comprehensive controlled study over
AMT-labeled local experts on eight topics and in four
cities. We find significant improvements of local
expert finding versus two state-of-the-art
alternatives, as well as evidence for the
generalizability of local expert ranking models to new
topics and new locations.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Zhao:2016:OSE,
author = "Liang Zhao and Feng Chen and Chang-Tien Lu and Naren
Ramakrishnan",
title = "Online Spatial Event Forecasting in Microblogs",
journal = j-TSAS,
volume = "2",
number = "4",
pages = "15:1--15:39",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2997642",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2997642",
abstract = "Event forecasting from social media data streams has
many applications. Existing approaches focus on
forecasting temporal events (such as elections and
sports) but as yet cannot forecast spatiotemporal
events such as civil unrest and influenza outbreaks,
which are much more challenging. To achieve
spatiotemporal event forecasting, spatial features that
evolve with time and their underlying correlations need
to be considered and characterized. In this article, we
propose novel batch and online approaches for
spatiotemporal event forecasting in social media such
as Twitter. Our models characterize the underlying
development of future events by simultaneously modeling
the structural contexts and their spatiotemporal
burstiness based on different strategies. Both batch
and online-based inference algorithms are developed to
optimize the model parameters. Utilizing the trained
model, the alignment likelihood of tweet sequences is
calculated by dynamic programming. Extensive
experimental evaluations on two different domains
demonstrate the effectiveness of our proposed
approach.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Purushotham:2016:PGR,
author = "Sanjay Purushotham and C.-C. Jay Kuo",
title = "Personalized Group Recommender Systems for Location-
and Event-Based Social Networks",
journal = j-TSAS,
volume = "2",
number = "4",
pages = "16:1--16:29",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2987381",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=2987381",
abstract = "Location-Based Social Networks (LBSNs) such as
Foursquare, Google+ Local, and so on, and Event-Based
Social Networks (EBSNs) such as Meetup, Plancast, and
so on, have become popular platforms for users to plan,
organize, and attend social events with friends and
acquaintances. These LBSNs and EBSNs provide rich
content such as online and offline user interactions,
location/event descriptions that can be leveraged for
personalized group recommendations. In this article, we
propose novel Collaborative Filtering-based Bayesian
models to capture the location or event semantics and
group dynamics such as user interactions, user group
membership, user influence, and the like for
personalized group recommendations. Empirical
experiments on two large real-world datasets (Gowalla
LBSN dataset and Meetup EBSN dataset) show that our
models outperform the state-of-the-art group
recommender systems. We discuss the group
characteristics of our datasets and show that modeling
of group dynamics learns better group preferences than
aggregating individual user preferences. Moreover, our
model provides human interpretable results that can be
used to understand group participation behavior and
location/event popularity.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Amagata:2017:GFM,
author = "Daichi Amagata and Takahiro Hara",
title = "A General Framework for {MaxRS} and {MaxCRS}
Monitoring in Spatial Data Streams",
journal = j-TSAS,
volume = "3",
number = "1",
pages = "1:1--1:34",
month = may,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3080554",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=3080554",
abstract = "This article addresses the MaxRS (Maximizing Range
Sum) monitoring problem. Given a set of weighted
spatial stream objects, this problem is to monitor a
location of a user-specified sized rectangle where the
sum of the weights of the objects covered by the
rectangle is maximized. This problem supports modern
applications (e.g., traffic analysis and event
detection in urban sensing) but has not yet been
addressed. Although some algorithms for static objects
have been proposed, such algorithms are not scalable to
stream environments. These motivate us to devise an
algorithm for efficient MaxRS monitoring. We first
propose G2 (Graph in Grid index) and a G2-based
algorithm to incrementally update the result. We then
propose aG2 (aggregate G2), by enhancing G2, and a
branch-and-bound algorithm that employs aG2 and can
deal with error-guaranteed approximation. We also
address MaxCRS monitoring, which is the circle version
of the aforementioned problem. Its importance is
evident from the fact that distance is also popular as
a range criterion. We then have an emerging challenge
of developing a general and efficient solution for both
continuous MaxRS and MaxCRS queries. Based on a common
property of the two problems, we generalize aG2 so as
to be employed in both continuous MaxRS and MaxCRS
queries. The branch-and-bound algorithm is also
extended to suit the generalized index. We conduct
extensive experiments using synthetic and real
datasets. The experimental results show that our
algorithms support a fast result update and
significantly outperform the algorithms for static
data.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Iwata:2017:EPF,
author = "Tomoharu Iwata and Hitoshi Shimizu and Futoshi Naya
and Naonori Ueda",
title = "Estimating People Flow from Spatiotemporal Population
Data via Collective Graphical Mixture Models",
journal = j-TSAS,
volume = "3",
number = "1",
pages = "2:1--2:18",
month = may,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3080555",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=3080555",
abstract = "Thanks to the prevalence of mobile phones and GPS
devices, spatiotemporal population data can be obtained
easily. In this article, we propose a mixture of
collective graphical models for estimating people flow
from spatiotemporal population data. The spatiotemporal
population data we use as input is the number of people
in each grid cell area over time, which is aggregated
information about many individuals; to preserve
privacy, they do not contain trajectories of each
individual. Therefore, it is impossible to directly
estimate people flow. To overcome this problem, the
proposed model assumes that transition populations are
hidden variables and estimates the hidden transition
populations and transition probabilities
simultaneously. The proposed model can handle changes
of people flow over time by segmenting time-of-day
points into multiple clusters, where different clusters
have different flow patterns. We develop an efficient
variational Bayesian inference procedure for the
collective graphical mixture model. In our experiments,
the effectiveness of the proposed method is
demonstrated by using four real-world spatiotemporal
population datasets in Tokyo, Osaka, Nagoya, and
Beijing.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Karagiorgou:2017:LAM,
author = "Sophia Karagiorgou and Dieter Pfoser and Dimitrios
Skoutas",
title = "A Layered Approach for More Robust Generation of Road
Network Maps from Vehicle Tracking Data",
journal = j-TSAS,
volume = "3",
number = "1",
pages = "3:1--3:21",
month = may,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3061713",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Thu Jun 15 14:51:03 MDT 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "http://dl.acm.org/citation.cfm?id=3061713",
abstract = "Nowadays, large amounts of tracking data are generated
via GPS-enabled devices and other advanced tracking
technologies. These constitute a rich source for
inferring the structure of transportation networks. In
this work, we present a novel methodology for revealing
a road network map from vehicle trajectories.
Specifically, we propose an enhanced and robust map
construction algorithm that is based on segmenting the
original tracking data according to different types of
movement and then constructing the topology of the road
network hierarchically. The segmentation produces
separate road network layers, which are then fused into
a single network. This provides a more efficient way to
addresses the challenges imposed by noisy and low
sampling rate trajectories. It also allows for a
mechanism to accommodate automatic map maintenance on
updates. Thus, the proposed approach overcomes the
limitations of existing methods and introduces a map
construction algorithm that is robust against
heterogeneous and sparse data and capable to
incorporate changes and improvements. An experimental
evaluation extensively assesses the quality of the
proposed methodology by constructing large parts of the
road networks of four major cities, namely Athens,
Berlin, Vienna, and Chicago, using as input GPS
tracking data of utility vehicles and taxi fleets. Our
results show significant improvements concerning the
spatial accuracy and the quality of the constructed
road network over the current state of the art.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Aly:2017:AEE,
author = "Heba Aly and Anas Basalamah and Moustafa Youssef",
title = "Accurate and Energy-Efficient {GPS}-Less Outdoor
Localization",
journal = j-TSAS,
volume = "3",
number = "2",
pages = "4:1--4:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3085575",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3085575",
abstract = "Location-based services have become an important part
of our daily lives. However, such services require
continuous user tracking while preserving the scarce
cell-phone battery resource. In this article, we
present Dejavu, a system that uses standard cell-phone
sensors to provide accurate and energy-efficient
outdoor localization. Dejavu is capable of localizing
and navigating both pedestrian and in-vehicle users in
real time. Our analysis shows that, whether walking or
in-vehicle, when the user encounters a road landmark
such as going inside a tunnel, ascending a staircase,
or even moving over a bump, all these different
landmarks affect the inertial sensors on the phone in a
unique pattern. Dejavu employs a dead-reckoning
localization approach and leverages these road
landmarks, among other automatically discovered virtual
landmarks, to reset the dead-reckoning accumulated
error and achieve accurate localization. To maintain a
low energy profile, Dejavu uses only energy-efficient
sensors or sensors that are already running for other
purposes. Moreover, Dejavu provides a localization
confidence measure along with its predicted location.
This improves the usability of the predicted location
from end users' perspective. We present the design of
Dejavu and how it leverages crowd-sourcing to
automatically learn virtual landmarks and their
locations. Our evaluation results from implementation
on different Android devices using different testbeds
showing that Dejavu can localize cell-phones in
vehicles with a median error of 8.4 m in city roads and
16.6 m on highways and can localize cell-phones carried
by pedestrians with a median error of 3.0m. Moreover,
compared to the global position system (GPS) and other
state-of-the-art systems, Dejavu can extend the battery
lifetime by up to 347\%, while achieving even better
localization results than GPS in the more challenging
in-city areas. In addition, Dejavu estimates the
localization confidence measure accurately with a
median error of 2.3m and 31cm for in-vehicle and
pedestrian users, respectively.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Long:2017:SPB,
author = "Yuan Long and Xiaolin Hu",
title = "Spatial Partition-Based Particle Filtering for Data
Assimilation in Wildfire Spread Simulation",
journal = j-TSAS,
volume = "3",
number = "2",
pages = "5:1--5:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3099471",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3099471",
abstract = "This article develops a spatial partition-based
particle filtering framework to support data
assimilation for large-scale wildfire spread simulation
effectively. The developed spatial partition-based
particle filtering framework breaks the system state
and observation data into smaller spatial regions and
then carries out localized particle filtering based on
these spatial regions. Particle Filters (PFs) hold
great promise to support data assimilation for spatial
temporal simulations, such as wildfire spread
simulation, to achieve more accurate simulation or
prediction results. However, PFs face major challenges
to work effectively for complex spatial temporal
simulations due to the high-dimensional state space of
the simulation models, which typically cover large
areas and have a large number of spatially dependent
state variables. The developed framework exploits the
spatial locality property of system state and
observation data and employs the divide-and-conquer
principle to reduce state dimension and data
complexity. This framework is especially developed for
a discrete event cellular space model (the wildfire
simulation model), which significantly differs from
prior works that use numerical models specified by
partial differential equations (PDEs) with continuous
variables. Within this framework, a two-level automated
spatial partitioning method is presented to provide
automated and balanced spatial partitions with fewer
boundary sensors. The developed framework is applied to
a wildfire spread simulation and achieved improved
results compared to using standard PF-based data
assimilation methods.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Chawla:2017:CPF,
author = "Sanjay Chawla and Jo{\"e}l Estephan and Joachim
Gudmundsson and Michael Horton",
title = "Classification of Passes in Football Matches Using
Spatiotemporal Data",
journal = j-TSAS,
volume = "3",
number = "2",
pages = "6:1--6:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105576",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3105576",
abstract = "A knowledgeable observer of a game of football
(soccer) can make a subjective evaluation of the
quality of passes made between players during the game,
such as rating them as Good, OK, or Bad. In this
article, we consider the problem of producing an
automated system to make the same evaluation of passes
and present a model to solve this problem. Recently,
many professional football leagues have installed
object tracking systems in their stadiums that generate
high-resolution and high-frequency spatiotemporal
trajectories of the players and the ball. Beginning
with the thesis that much of the information required
to make the pass ratings is available in the trajectory
signal, we further postulated that using complex data
structures derived from computational geometry would
enable domain football knowledge to be included in the
model by computing metric variables in a principled and
efficient manner. We designed a model that computes a
vector of predictor variables for each pass made and
uses machine learning techniques to determine a
classification function that can accurately rate passes
based only on the predictor variable vector.
Experimental results show that the learned
classification functions can rate passes with 90.2\%
accuracy. The agreement between the classifier ratings
and the ratings made by a human observer is comparable
to the agreement between the ratings made by human
observers, and suggests that significantly higher
accuracy is unlikely to be achieved. Furthermore, we
show that the predictor variables computed using
methods from computational geometry are among the most
important to the learned classifiers.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Teng:2017:TMS,
author = "Shan-Yun Teng and Wei-Shinn Ku and Kun-Ta Chuang",
title = "Toward Mining Stop-by Behaviors in Indoor Space",
journal = j-TSAS,
volume = "3",
number = "2",
pages = "7:1--7:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3106736",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3106736",
abstract = "In this article, we explore a new mining paradigm,
called Indoor Stop-by Patterns (ISP), to discover user
stop-by behavior in mall-like indoor environments. The
discovery of ISPs enables new marketing collaborations,
such as a joint coupon promotion, among stores in
indoor spaces (e.g., shopping malls). Moreover, it can
also help in eliminating the overcrowding situation. To
pursue better practicability, we consider the
cost-effective wireless sensor-based environment and
conduct the analysis of indoor stop-by behaviors on
real data. However, it is a highly challenging issue,
in indoor environments, to retrieve frequent ISPs,
especially when the issue of user privacy is
highlighted nowadays. The mining of ISPs will face a
critical challenge from spatial uncertainty. Previous
work on mining indoor movement patterns usually relies
on precise spatio-temporal information by a specific
deployment of positioning devices, which cannot be
directly applied. In this article, the proposed
Probabilistic Top- k Indoor Stop-by Patterns Discovery
(PTkISP) framework incorporates the probabilistic model
to identify top- k ISPs over uncertain data collected
from sensing logs. Moreover, we develop an uncertain
model and devise an Index 1-itemset (IIS) algorithm to
enhance the accuracy and efficiency. Our experimental
studies show that the proposed PTkISP framework can
efficiently discover high-quality ISPs and can provide
insightful observations for marketing collaborations.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Mariescu-Istodor:2017:GBM,
author = "Radu Mariescu-Istodor and Pasi Fr{\"a}nti",
title = "Grid-Based Method for {GPS} Route Analysis for
Retrieval",
journal = j-TSAS,
volume = "3",
number = "3",
pages = "8:1--8:??",
month = nov,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3125634",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3125634",
abstract = "Grids are commonly used as histograms to process
spatial data in order to detect frequent patterns,
predict destinations, or to infer popular places.
However, they have not been previously used for GPS
trajectory similarity searches or retrieval in general.
Instead, slower and more complicated algorithms based
on individual point-pair comparison have been used. We
demonstrate how a grid representation can be used to
compute four different route measures: novelty,
noteworthiness, similarity, and inclusion. The measures
may be used in several applications such as identifying
taxi fraud, automatically updating GPS navigation
software, optimizing traffic, and identifying commuting
patterns. We compare our proposed route similarity
measure, C-SIM, to eight popular alternatives including
Edit Distance on Real sequence (EDR) and Frechet
distance. The proposed measure is simple to implement
and we give a fast, linear time algorithm for the task.
It works well under noise, changes in sampling rate,
and point shifting. We demonstrate that by using the
grid, a route similarity ranking can be computed in
real-time on the Mopsi2014 1 route dataset, which
consists of over 6,000 routes. This ranking is an
extension of the most similar route search and contains
an ordered list of all similar routes from the
database. The real-time search is due to indexing the
cell database and comes at the cost of spending 80\%
more memory space for the index. The methods are
implemented inside the Mopsi 2 route module.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Aydin:2017:MSS,
author = "Berkay Aydin and Ahmet Kucuk and Rafal A. Angryk and
Petrus C. Martens",
title = "Measuring the Significance of Spatiotemporal
Co-Occurrences",
journal = j-TSAS,
volume = "3",
number = "3",
pages = "9:1--9:??",
month = nov,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3139351",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3139351",
abstract = "Spatiotemporal co-occurrences are the appearances of
spatial and temporal overlap relationships among
trajectory-based spatiotemporal instances with
region-based geometric representations. Assessing the
significance of spatiotemporal co-occurrences plays an
important role in the spatiotemporal frequent pattern
mining applications of moving region objects. A
spatiotemporal version of the popular Jaccard measure
has been used for measuring the strength of
spatiotemporal co-occurrences. We will demonstrate the
shortcomings of the Jaccard (J) measure when it is used
for assessing the significance of co-occurrences among
spatiotemporal instances with highly different
spatiotemporal evolution characteristics. We will
present two extended novel measures (J + and J *) that
address the problems linked to the J measure. Our work
includes algorithms for the significance measure
calculations, the proofs and explanations about the key
properties of measures, and a detailed experimental
evaluation section. Our experiments include in-depth
relevancy and running time analyses demonstrating the
suitability of our proposed measures for spatiotemporal
frequent pattern mining algorithms.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Robles-Ortega:2017:EVD,
author = "M. D. Robles-Ortega and L. Ortega and F. R. Feito",
title = "Efficient Visibility Determination in Urban Scenes
Considering Terrain Information",
journal = j-TSAS,
volume = "3",
number = "3",
pages = "10:1--10:??",
month = nov,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3152536",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:48 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3152536",
abstract = "In this article, we introduce a novel occlusion
culling method working on the server side to provide
real-time navigation on web-based systems. Nowadays,
virtual navigation in urban environments is a rising
trend in several contexts such as tourism, GPS
navigation systems, and video games. A city environment
is usually associated with a complex data model that is
better stored, maintained, and updated on a server
system. Mobile devices are regular clients in these
cases, demanding this information in a fast, reliable,
and engaging way. Even though these gadgets have been
increasing their capabilities in computation and
visualization, the bottleneck is still the transmission
of information over the network. The advantage of urban
environments is that, from a user viewpoint, only a
small portion of the scene is visible. This feature
makes crucial the use of occlusion culling techniques
working on the server side in order to transmit to the
client side only the small set of visible elements
compared to the whole scene. The input data are the
city geometry from the 2D cadastral information system,
the building textures, and DEM (Digital Elevation
Model) files with the urban terrain features. In a
first stage, the process creates a 2.5D urban model
with all these data in preprocessing time. Then the
client provides the user location point, and the server
sends back the exact portion of visible city. This
approach is implemented using polar diagrams for
visibility determination and LOD (Level of Detail)
techniques for further geometry reduction.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ayala:2018:STM,
author = "Daniel Ayala and Ouri Wolfson and Bhaskar Dasgupta and
Jie Lin and Bo Xu",
title = "Spatio-Temporal Matching for Urban Transportation
Applications",
journal = j-TSAS,
volume = "3",
number = "4",
pages = "11:1--11:??",
month = may,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3183344",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3183344",
abstract = "In this article, we present a search problem in which
mobile agents are searching for static resources. Each
agent wants to obtain exactly one resource. Both agents
and resources are spatially located on a road network
and the movement of the agents is constrained to the
road network. This problem applies to various
transportation applications including: vehicles
(agents) searching for parking (resources) and taxicabs
(agents) searching for clients to pick up (resources).
In this work, we design search algorithms for such
scenarios. We model the problem in different scenarios
that vary based on the level of information that is
available to the agents. These scenarios vary from
scenarios in which agents have complete information
about other agents and resources, to scenarios in which
agents only have access to a fraction of the data about
the availability of resources (uncertain data). We also
propose pricing schemes that incentivize vehicles to
search for resources in a way that benefits the system
and the environment. Our proposed algorithms were
tested in a simulation environment that uses real-world
data. We were able to attain up to 40\% improvements
over other approaches that were tested against our
algorithms.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Belesiotis:2018:APS,
author = "Alexandros Belesiotis and George Papadakis and
Dimitrios Skoutas",
title = "Analyzing and Predicting Spatial Crime Distribution
Using Crowdsourced and Open Data",
journal = j-TSAS,
volume = "3",
number = "4",
pages = "12:1--12:??",
month = may,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3190345",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3190345",
abstract = "Data analytics has an ever increasing impact on
tackling various societal challenges. In this article,
we investigate how data from several heterogeneous
online sources can be used to discover insights and
make predictions about the spatial distribution of
crime in large urban environments. A series of
important research questions is addressed, following a
purely data-driven approach and methodology. First, we
examine how useful different types of data are for the
task of crime levels prediction, focusing especially on
how prediction accuracy can be improved by combining
data from multiple information sources. To that end, we
not only investigate prediction accuracy across all
individual areas studied, but also examine how these
predictions affect the accuracy of identified crime
hotspots. Then, we look into individual features,
aiming to identify and quantify the most important
factors. Finally, we drill down to different crime
types, elaborating on how the prediction accuracy and
the importance of individual features vary across them.
Our analysis involves six different datasets, from
which more than 3,000 features are extracted, filtered,
and used to learn models for predicting crime rates
across 14 different crime categories. Our results
indicate that combining data from multiple information
sources can significantly improve prediction accuracy.
They also highlight which features affect prediction
accuracy the most, as well as for which particular
crime categories the predictions are more accurate.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Choudhury:2018:BPT,
author = "Farhana M. Choudhury and J. Shane Culpepper and
Zhifeng Bao and Timos Sellis",
title = "Batch Processing of Top-$k$ Spatial-Textual Queries",
journal = j-TSAS,
volume = "3",
number = "4",
pages = "13:1--13:??",
month = may,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3196155",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3196155",
abstract = "Since the mid-2000s, several indexing techniques have
been proposed to efficiently answer top-$k$
spatial-textual queries. However, all of these
approaches focus on answering one query at a time. In
contrast, how to design efficient algorithms that can
exploit similarities between incoming queries to
improve performance has received little attention. In
this article, we study a series of efficient approaches
to batch process multiple top-$k$ spatial-textual
queries concurrently. We carefully design a variety of
indexing structures for the problem space by exploring
the effect of prioritizing spatial and textual
properties on system performance. Specifically, we
present an efficient traversal method, SF-S ep, over an
existing space-prioritized index structure. Then, we
propose a new space-prioritized index structure, the
MIR-Tree to support a filter-and-refine based
technique, SF-Grp. To support the processing of
text-intensive data, we propose an augmented, inverted
indexing structure that can easily be added into
existing text search engine architectures and a novel
traversal method for batch processing of the queries.
In all of these approaches, the goal is to improve the
overall performance by sharing the I/O costs of similar
queries. Finally, we demonstrate significant I/O
savings in our algorithms over traditional approaches
by extensive experiments on three real datasets and
compare how properties of different datasets affect the
performance. Many applications in streaming,
micro-batching of continuous queries, and privacy-aware
search can benefit from this line of work.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Fujino:2018:DDI,
author = "Takumi Fujino and Atsushi Hashimoto and Hidekazu
Kasahara and Mikihiko Mori and Masaaki Iiyama and
Michihiko Minoh",
title = "Detecting Deviations from Intended Routes Using
Vehicular {GPS} Tracks",
journal = j-TSAS,
volume = "4",
number = "1",
pages = "1:1--1:??",
month = jun,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3204455",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3204455",
abstract = "This article proposes a method to find intersections
at which cars tend to deviate from the optimal route
based on global positioning system (GPS) tracking data
under the assumption that such deviations indicate that
car navigation systems (CNSs) and road signage are not
readily available. If the intended route is known,
deviations can be enumerated by comparing the intended
route with the vehicle's actual route as observed by a
GPS; however, the intended route is unknown and can
differ from the route suggested by a CNS. To identify
intersections with high deviation rates without knowing
intended routes, we exhaustively sampled subsequences
from each vehicular GPS track, and detected deviations
from the optimal route for the subsequences. Although
the detected deviations are not always caused by driver
confusion, accumulating such erroneous detection
results would yield a meaningful difference in the
number of accumulated deviations at each intersection.
We applied the proposed method to 3,843 GPS tracks
collected from visitor drivers in the city of Kyoto.
Thresholding the estimated deviation rate yielded 39
intersections from 14,543 candidates. The results show
a certain level of correlation between obtained
deviations and rerouting locations from actual CNS
data. We also found several intersections where faulty
route suggestions are provided by CNSs.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Toll:2018:MAM,
author = "Wouter Van Toll and Atlas F. Cook Iv and Marc J. Van
Kreveld and Roland Geraerts",
title = "The Medial Axis of a Multi-Layered Environment and Its
Application as a Navigation Mesh",
journal = j-TSAS,
volume = "4",
number = "1",
pages = "2:1--2:??",
month = jun,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3204456",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3204456",
abstract = "Path planning for walking characters in complicated
virtual environments is a fundamental task in
simulations and games. A navigation mesh is a data
structure that allows efficient path planning. The
Explicit Corridor Map (ECM) is a navigation mesh based
on the medial axis. It enables path planning for
disk-shaped characters of any radius. In this article,
we formally extend the medial axis (and therefore the
ECM) to 3D environments in which characters are
constrained to walkable surfaces. Typical examples of
such environments are multi-storey buildings, train
stations, and sports stadiums. We give improved
definitions of a walkable environment (WE: a
description of walkable surfaces in 3D) and a
multi-layered environment (MLE: a subdivision of a WE
into connected layers). We define the medial axis of
such environments based on projected distances on the
ground plane. For an MLE with $n$ boundary vertices and
k connections, we show that the medial axis has size O
(n), and we present an improved algorithm that
constructs the medial axis in O (n \log $n$ \log k)
time. The medial axis can be annotated with
nearest-obstacle information to obtain the ECM
navigation mesh. Our implementations show that the ECM
can be computed efficiently for large 2D and
multi-layered environments and that it can be used to
compute paths within milliseconds. This enables
simulations of large virtual crowds of heterogeneous
characters in real-time.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Koide:2018:EIQ,
author = "Satoshi Koide and Yukihiro Tadokoro and Takayoshi
Yoshimura and Chuan Xiao and Yoshiharu Ishikawa",
title = "Enhanced Indexing and Querying of Trajectories in Road
Networks via String Algorithms",
journal = j-TSAS,
volume = "4",
number = "1",
pages = "3:1--3:??",
month = jun,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3200200",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3200200",
abstract = "In this article, we propose a novel indexing and
querying method for trajectories constrained in a road
network. We aim to provide efficient algorithms for
various types of spatiotemporal queries that involve
routing in road networks, such as (1) finding moving
objects that have traveled along a given path during a
given time interval, (2) extracting all paths traveled
after a given spatiotemporal context, and (3)
enumerating all paths between two locations traveled
during a certain time interval. Unlike the existing
methods in spatial database research, we employ
indexing techniques and algorithms from string
processing. This idea is based on the fact that we can
represent spatial paths as strings, because
trajectories in a network are represented as sequences
of road segment IDs. The proposed SNT-index
(suffix-array-based network-constrained trajectory
index) introduces two novel concepts to trajectory
indexing. The first is FM-index, which is a compact
in-memory data structure for pattern matching. The
second is an inverse suffix array, which allows the
FM-index to be integrated with the temporal information
stored in a forest of B + -trees. Thanks to these
concepts, we can reduce the number of B + -tree
accesses required by the query processing algorithms to
a constant number, something that cannot be achieved
with existing methods. Although an FM-index is
essentially a static index, we also propose a practical
method of appending new data to the index. Finally,
experiments show that our method can process the target
queries for more than 1 million trajectories in a few
tens of milliseconds, which is significantly faster
than what the baseline algorithms can achieve without
string algorithms.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Yin:2018:FBM,
author = "Yifang Yin and Rajiv Ratn Shah and Guanfeng Wang and
Roger Zimmermann",
title = "Feature-based Map Matching for Low-Sampling-Rate {GPS}
Trajectories",
journal = j-TSAS,
volume = "4",
number = "2",
pages = "4:1--4:??",
month = aug,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3223049",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3223049",
abstract = "With the increasing availability of GPS-equipped
mobile devices, location-based services have become an
integral part of everyday life. Among one of the
initial steps of positioning data management, map
matching aims to reduce the uncertainty in a trajectory
by matching the GPS points to the road network on a
digital map. Most existing work has focused on
estimating the likelihood of a candidate route based on
the GPS observations, while neglecting to model the
probability of a route choice from the perspective of
drivers. In this work, we propose a novel feature-based
map matching algorithm that estimates the cost of a
candidate route based on both GPS observations and
human factors. To take human factors into consideration
is highly important, especially when dealing with low
sampling rate data where most of the movement details
are lost. Additionally, we simultaneously analyze a
subsequence of coherent GPS points by utilizing a new
segment-based probabilistic map matching strategy,
which is less susceptible to the noisiness of the
positioning data. We have evaluated both the offline
and the online versions of our proposed approach on a
public large-scale GPS dataset, which consists of 100
trajectories distributed all over the world. The
experimental results show that our method is robust to
sparse data with large sampling intervals (e.g.,
60s--300s) and challenging track features (e.g.,
u-turns and loops). Measurements including map matching
accuracy and system efficiency have been thoroughly
evaluated and discussed. Compared with two
state-of-the-art map matching algorithms, our method
substantially reduces the route mismatch error by
6.4\%--32.3\% (either offline or online with the window
size set to 360s), with a slight increase in terms of
the processing time. The experimental results show that
our proposed method obtains the state-of-the-art map
matching results in all the different combinations of
sampling rates and challenging features.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Dong:2018:WAR,
author = "Yuyang Dong and Hanxiong Chen and Jeffrey Xu Yu and
Kazutaka Furuse and Hiroyuki Kitagawa",
title = "Weighted Aggregate Reverse Rank Queries",
journal = j-TSAS,
volume = "4",
number = "2",
pages = "5:1--5:??",
month = aug,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3225216",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3225216",
abstract = "In marketing, helping manufacturers to find the
matching preferences of potential customers for their
products is an essential work, especially in e-commerce
analyzing with big data. The aggregate reverse rank
query has been proposed to return top-$k$ customers who
have more potential to buy a given product bundling
than other customers, where the potential is evaluated
by the aggregate rank, which is defined as the sum of
each product's rank. This query correctly reflects the
request only when the customers consider the products
in the product bundling equally. Unfortunately, rather
than thinking products equally, in most cases, people
buy a product bundling because they appreciate a
special part of the bundling. Manufacturers, such as
video games companies and cable television industries,
are also willing to bundle some attractive products
with less popular products for the purpose of maximum
benefits or inventory liquidation. Inspired by the
necessity of general aggregate reverse rank query for
unequal thinking, we propose a weighted aggregate
reverse rank query, which treats the elements in
product bundling with different weights to target
customers from all aspects of thought. To solve this
query efficiently, we first try a straightforward
extension. Then, we rebuild the bound-and-filter
framework for the weighted aggregate reverse rank
query. We prove, theoretically, that the new approach
finds the optimal bounds, and we develop the highly
efficient algorithm based on these bounds. The
theoretical analysis and experimental results
demonstrated the efficacy of the proposed methods.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Both:2018:ISE,
author = "Alan Both and Matt Duckham and Michael F. Worboys",
title = "Identifying Surrounds and Engulfs Relations in Mobile
and Coordinate-Free Geosensor Networks",
journal = j-TSAS,
volume = "4",
number = "2",
pages = "6:1--6:??",
month = aug,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3234505",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:49 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3234505",
abstract = "This article concerns the definition and
identification of qualitative spatial relationships for
the full and partial enclosure of spatial regions. The
article precisely defines three relationships between
regions-``surrounds,'' ``engulfs,'' and
``envelops''-highlighting the correspondence to similar
definitions in the literature. An efficient algorithm
capable of identifying these qualitative spatial
relations in a network of dynamic (mobile) geosensor
nodes is developed and tested. The algorithms are
wholly decentralized, and operate in-network with no
centralized control. The algorithms are also
``coordinate-free,'' able to operate in distributed
spatial computing environments where coordinate
locations are expensive to capture or otherwise
unavailable. Experimental evaluation of the algorithms
designed demonstrates the efficiency of the approach.
Although the algorithm communication complexity is
dominated by an overall worst-case O (n 2) leader
election algorithm, the experiments show in practice an
average-case complexity approaching linear, O (n
1.1).",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Mahmood:2018:DBI,
author = "Ahmed R. Mahmood and Ahmed M. Aly and Tatiana
Kuznetsova and Saleh Basalamah and Walid G. Aref",
title = "Disk-Based Indexing of Recent Trajectories",
journal = j-TSAS,
volume = "4",
number = "3",
pages = "7:1--7:??",
month = sep,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3234941",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3234941",
abstract = "The plethora of location-aware devices has led to
countless location-based services in which huge amounts
of spatiotemporal data get created every day. Several
applications require efficient processing of queries on
the locations of moving objects over time, i.e., the
moving object trajectories. This calls for efficient
trajectory-based indexing methods that capture both the
spatial and temporal dimensions of the data in a way
that minimizes the number of disk I/Os required for
both updating and querying. Most existing
spatiotemporal index structures capture either the
current locations of the moving objects or the entire
history of the moving objects. Historical
spatiotemporal indexing methods require multiple disk
I/Os to process new updates and use a discrete
trajectory representation that may result in incomplete
query results. In this article, we introduce the
trails-tree, a disk-based data structure for indexing
recent trajectories. The trails-tree requires half the
number of disk I/Os needed by other historical
spatiotemporal indexing methods for the insertion and
querying operations. We give a detailed description of
the trails-tree, and we mathematically analyze its
performance. Moreover, we present a novel query
processing algorithm that ensures the completeness of
the query result set. We experimentally verify the
performance of the trails-tree using various real and
synthetic datasets.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Mariescu-Istodor:2018:CIR,
author = "Radu Mariescu-Istodor and Pasi Fr{\"a}nti",
title = "{CellNet}: Inferring Road Networks from {GPS}
Trajectories",
journal = j-TSAS,
volume = "4",
number = "3",
pages = "8:1--8:??",
month = sep,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3234692",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3234692",
abstract = "Road networks are essential nowadays, especially for
people travelling to large, unfamiliar cities.
Moreover, cities are constantly growing and road
networks need periodic updates to provide reliable
information. We propose an automatic method to generate
the road network using a GPS trajectory dataset. The
method, called CellNet, works by first detecting the
intersections (junctions) using a clustering-based
technique and then creating the road segments
in-between. We compare CellNet against conceptually
different alternatives using Chicago and Joensuu
datasets. The results show that CellNet provides better
accuracy and is less sensitive to parameter setup. The
size of the generated road network is only 25\% of the
networks produced by other methods. This implies that
the network provided by CellNet has much less
redundancy.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Vollmer:2018:HSA,
author = "Jan Ole Vollmer and Matthias Trapp and Heidrun
Schumann and J{\"u}rgen D{\"o}llner",
title = "Hierarchical Spatial Aggregation for Level-of-Detail
Visualization of {$3$D} Thematic Data",
journal = j-TSAS,
volume = "4",
number = "3",
pages = "9:1--9:??",
month = sep,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3234506",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3234506",
abstract = "Thematic maps are a common tool to visualize semantic
data with a spatial reference. Combining thematic data
with a geometric representation of their natural
reference frame aids the viewer's ability in gaining an
overview, as well as perceiving patterns with respect
to location; however, as the amount of data for
visualization continues to increase, problems such as
information overload and visual clutter impede
perception, requiring data aggregation and
level-of-detail visualization techniques. While
existing aggregation techniques for thematic data
operate in a 2D reference frame (i.e., map), we present
two aggregation techniques for 3D spatial and
spatiotemporal data mapped onto virtual city models
that hierarchically aggregate thematic data in real
time during rendering to support on-the-fly and
on-demand level-of-detail generation. An object-based
technique performs aggregation based on scene-specific
objects and their hierarchy to facilitate per-object
analysis, while the scene-based technique aggregates
data solely based on spatial locations, thus supporting
visual analysis of data with arbitrary reference
geometry. Both techniques can apply different
aggregation functions (mean, minimum, and maximum) for
ordinal, interval, and ratio-scaled data and can be
easily extended with additional functions. Our
implementation utilizes the programmable graphics
pipeline and requires suitably encoded data, i.e.,
textures or vertex attributes. We demonstrate the
application of both techniques using real-world
datasets, including solar potential analyses and the
propagation of pressure waves in a virtual city
model.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Khan:2018:ECO,
author = "A. K. M. Mustafizur Rahman Khan and Lars Kulik and
Egemen Tanin and Hua Hua and Tanzima Hashem",
title = "Efficient Computation of the Optimal Accessible
Location for a Group of Mobile Agents",
journal = j-TSAS,
volume = "4",
number = "4",
pages = "10:1--10:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3239124",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3239124",
abstract = "Nowadays, people can access location-based services
(LBSs) as a group via mobile devices to plan their
daily activities with friends and relatives. In this
article, we introduce an important class of
group-oriented LBSs, group optimal accessible location
(GOAL) queries that enable users to identify the
location of a point of interest (POI) that has the
minimum total distance to a given set of paths. GOAL
queries have many applications, such as the selection
of an optimal location for group meet-ups or for a
mobile facility such as a food truck. In a GOAL query,
each trip or path is represented as a set of line
segments, and the distance of a POI from a path is
computed as the minimum distance of the POI to any line
segment of the path. We develop an efficient approach
to evaluate GOAL queries. The novelty of our GOAL query
processing algorithm in contrast to other spatial query
processing algorithms is the reformulation of a GOAL
query by considering only a subset of path segments
from the given set of paths, which is also the key
factor behind the efficiency of our proposed algorithm.
We exploit geometric properties and develop pruning
techniques to eliminate both POIs and path segments
that cannot provide the optimal solution for a GOAL
query. Our experimental results demonstrate that we
provide a readily deployable solution for real-life
applications.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Nur:2018:GRI,
author = "Abdullah Yasin Nur and Mehmet Engin Tozal",
title = "Geography and Routing in the {Internet}",
journal = j-TSAS,
volume = "4",
number = "4",
pages = "11:1--11:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3239162",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3239162",
abstract = "The Internet is a network of networks consisting of
tens of thousands of Autonomous Systems ({ASes}). These
ASes connect to each other in different forms to enable
the `global'' Internet communication. In this study, we
investigate the geographical characteristics of the
visible Internet as well as examine the relation
between geography and intra-AS and inter-AS routing
policies. We show that the ingress-to-egress subpaths
have lower circuitousness compared to the end-to-end
paths. Our findings not only demonstrate the efficient
backbone infrastructures and routing schemes deployed
by ASes but also show the consequences of economical
incentives on the adoption of inter-AS paths. We
present and examine the existence of a strong
correlation between the geographical distance and round
trip delay time as well as the lack of a correlation
between the geographical distance and hop length in the
Internet. We investigate the relation between the
geographical distance and intra-AS routing policies by
employing cross-AS (X-AS) Internet topology maps. Our
results show that more than two thirds of the intra-AS
subpaths are congruent with the shortest geographical
distance whether or not geographical distance is
employed as a custom parameter in routing decisions.
Our results provide new insights into the relations
between geography and Internet routing, which allow the
network researchers and practitioners to improve their
networking infrastructures, reevaluate their routing
policies, deploy geography-aware network overlays, and
develop more realistic network simulation processes.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Wang:2018:VMF,
author = "Nana Wang and Mohan Kankanhalli",
title = "{$2$D} Vector Map Fragile Watermarking with Region
Location",
journal = j-TSAS,
volume = "4",
number = "4",
pages = "12:1--12:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3239163",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3239163",
abstract = "Locating the original region of tampered features is a
challenging task for existing 2D vector map fragile
watermarking methods. This article presents a 2D vector
map fragile watermarking framework that locates not
only the current but also the original region of
tampered feature groups. In particular, we propose
dividing the features of the host vector map into
groups, and embedding a watermark consisting of
location-bits and check-bits into each group at the
sender side. At the receiver side, by comparing the
extracted and calculated check-bits, one can identify
tampered groups and locate their current regions. Then
the location-bits extracted from the mapping groups are
used to indicate the original regions of the tampered
groups. To demonstrate and analyze the applicability of
this framework, we instantiate it by proposing a
simulated annealing (SA)-based group division method, a
group mapping method, a minimum encasing rectangle
(MER) based location-bits generation method and a
check-bits generation method, and use an existing
reversible data hiding method for watermark embedding.
The experimental results show that the proposed
framework can locate all the regions influenced by
tampering, and the SA-based group division method can
get a better region location ability.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Aref:2019:ISI,
author = "Walid G. Aref",
title = "Introduction to the Special Issue on the Best Papers
from the {2017 ACM SIGSPATIAL Conference}",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "1:1--1:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325134",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325134",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Rav:2019:FRA,
author = "Mathias Rav and Aaron Lowe and Pankaj K. Agarwal",
title = "Flood Risk Analysis on Terrains",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "2:1--2:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3295459",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3295459",
abstract = "An important problem in terrain analysis is modeling
how water flows across a terrain and creates floods by
filling up depressions. In this article, we study the
flooding query problem: Preprocess a given terrain $
\Sigma $, represented as a triangulated xy-monotone
surface with $n$ vertices, into a data structure so
that for a query rain region $R$ and a query point $q$
on $ \Sigma $, one can quickly determine how much rain
has to fall in $R$ so that $q$ is flooded. Available
terrain data is often subject to uncertainty, which
must be incorporated into the terrain analysis. For
instance, the digital elevation models of terrains have
to be refined to incorporate underground pipes,
tunnels, and waterways under bridges, but there is
often uncertainty in their existence. By representing
the uncertainty in the terrain data explicitly, we can
develop methods for flood risk analysis that properly
incorporate terrain uncertainty when reporting what
areas are at risk of flooding. We present two results.
First, we present an $ O (n \log n)$-time algorithm for
preprocessing $ \Sigma $ with a linear-size data
structure that can answer a flooding query in $ O (| R
| + m \log n)$ time, where $ | R |$ is the number of
vertices in $R$, $m$ is the number of so-called
tributaries of $q$ at which rain is falling, and $n$ is
the number of vertices of the terrain. Next, we extend
this data structure to handle ``uncertain'' terrains
using a standard Monte Carlo method. Given a
probability distribution on terrain data, our data
structure returns the probability of a query point
being flooded if a specified amount of rain falls on a
query region. We implement our data structure and test
it on real terrains, showing that a small number of
samples suffice to accurately estimate the flood
risk.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Pavlovic:2019:DCP,
author = "Mirjana Pavlovic and Kai-Niklas Bastian and Hinnerk
Gildhoff and Anastasia Ailamaki",
title = "Dictionary Compression in Point Cloud Data
Management",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "3:1--3:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3299770",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/datacompression.bib;
http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3299770",
abstract = "Nowadays, massive amounts of point cloud data can be
collected thanks to advances in data acquisition and
processing technologies such as dense image matching
and airborne LiDAR scanning. With the increase in
volume and precision, point cloud data offers a useful
source of information for natural-resource management,
urban planning, self-driving cars, and more. At the
same time, on the scale that point cloud data is
produced, management challenges are introduced: it is
important to achieve efficiency both in terms of
querying performance and space requirements.
Traditional file-based solutions to point cloud
management offer space efficiency, however, they cannot
scale to such massive data and provide the declarative
power of a DBMS. In this article, we propose a time-
and space-efficient solution to storing and managing
point cloud data in main memory column-store DBMS. Our
solution, Space-Filling Curve Dictionary-Based
Compression (SFC-DBC), employs dictionary-based
compression in the spatial data management domain and
enhances it with indexing capabilities by using
space-filling curves. SFC-DBC does so by constructing
the space-filling curve over a compressed, artificially
introduced dictionary space. Consequently, SFC-DBC
significantly optimizes query execution and yet does
not require additional storage resources, compared to
traditional dictionary-based compression. With respect
to space-filling-curve-based approaches, it minimizes
storage footprint and increases resilience to skew. As
a proof of concept, we develop and evaluate our
approach as a research prototype in the context of SAP
HANA. SFC-DBC outperforms other dictionary-based
compression schemes by up to 61\% in terms of space and
up to $ 9.4 \times $ in terms of query performance.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Li:2019:PTT,
author = "Yang Li and Dimitrios Gunopulos and Cewu Lu and
Leonidas J. Guibas",
title = "Personalized Travel Time Prediction Using a Small
Number of Probe Vehicles",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "4:1--4:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3317663",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3317663",
abstract = "Predicting the travel time of a path is an important
task in route planning and navigation applications. As
more GPS probe data has been collected to monitor urban
traffic, GPS trajectories of the probe vehicles have
been frequently used to predict path travel time.
However, most trajectory-based methods rely on
deploying GPS devices and collect real-time data on a
large taxi fleet, which can be expensive and unreliable
in smaller cities. This work deals with the problem of
predicting path travel time when only a small number of
cars are available. We propose an algorithm that learns
local congestion patterns of a compact set of
frequently shared paths from historical data. Given a
travel time prediction query, we identify the current
congestion patterns around the query path from recent
trajectories, then infer its travel time in the near
future. Driver identities are also used in predicting
personalized travel time. Experimental results using
10--25 taxis in urban areas of Shenzhen, China, show
that personal prediction has on average 3.4mins of
error on trips of duration 10--75mins. This result
improves the baseline approach of using purely
historical trajectories by 16.8\% on average, over four
regions with various degrees of path regularity. It
also outperforms a state-of-the-art travel time
prediction method that uses both historical
trajectories and real-time trajectories.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Correa:2019:CAR,
author = "Oscar Correa and A. K. M. Mustafizur Rahman Khan and
Egemen Tanin and Lars Kulik and Kotagiri
Ramamohanarao",
title = "Congestion-Aware Ride-Sharing",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "5:1--5:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3317639",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3317639",
abstract = "In its current form, ride-sharing is responsible for a
small fraction of traffic load compared to other
transportation modes, especially private vehicles. As
its benefits became more evident, and obstacles, e.g.,
lack of liability legislation, that may hinder its
larger scale adoption are being overcome, ride-sharing
will be a more common mode of transportation. In
particular, autonomous vehicles (AVs) are showing their
proficiency on the roads, which may also catalyze
ride-sharing ubiquity. For example, while an AV owner
is at work, he may find it appealing to offer his AV as
a service or rent it to Uber so that the vehicle serves
others' transportation requests. Furthermore, this
disruptive technology is backed up by companies like
Google (Waymo), Tesla, and Uber. Therefore,
ride-sharing will soon become a source of traffic
congestion itself. In this article, we present an
efficient congestion-aware ride-sharing algorithm
which, instead of finding optimal travel plans based on
traffic load generated by other means of
transportation, it computes optimal travel plans for
thousands of ride-sharing requests within a time
interval. Note that in this problem, an optimal travel
plan for a group of requests may affect an already
computed travel plan for another concurrent group of
requests, therefore plans cannot be isolated from each
other.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Whitman:2019:DSS,
author = "Randall T. Whitman and Bryan G. Marsh and Michael B.
Park and Erik G. Hoel",
title = "Distributed Spatial and Spatio-Temporal Join on
{Apache} Spark",
journal = j-TSAS,
volume = "5",
number = "1",
pages = "6:1--6:??",
month = jun,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325135",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:50 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325135",
abstract = "Effective processing of extremely large volumes of
spatial data has led to many organizations employing
distributed processing frameworks. Apache Spark is one
such open source framework that is enjoying widespread
adoption. Within this data space, it is important to
note that most of the observational data (i.e., data
collected by sensors, either moving or stationary) has
a temporal component or timestamp. To perform advanced
analytics and gain insights, the temporal component
becomes equally important as the spatial and attribute
components. In this article, we detail several variants
of a spatial join operation that addresses both
spatial, temporal, and attribute-based joins. Our
spatial join technique differs from other approaches in
that it combines spatial, temporal, and attribute
predicates in the join operator. In addition, our
spatio-temporal join algorithm and implementation
differs from others in that it runs in commercial
off-the-shelf (COTS) application. The users of this
functionality are assumed to be GIS analysts with
little if any knowledge of the implementation details
of spatio-temporal joins or distributed processing.
They are comfortable using simple tools that do not
provide the ability to tweak the configuration of the
algorithm or processing environment. The
spatio-temporal join algorithm behind the tool must
always succeed, regardless of input data parameters
(e.g., it can be highly irregularly distributed,
contain large numbers of coincident points, it can be
extremely large, etc.). These factors combine to place
additional requirements on the algorithm that are
uncommonly found in the traditional research
environment. Our spatio-temporal join algorithm was
shipped as part of the GeoAnalytics Server [12], part
of the ArcGIS Enterprise platform from version 10.5
onward.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Gollapudi:2019:ISI,
author = "Sreenivas Gollapudi",
title = "Introduction to the Special Issue on Urban Mobility:
Algorithms and Systems",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "7:1--7:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3346023",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3346023",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Cao:2019:UMC,
author = "Hancheng Cao and Jagan Sankaranarayanan and Jie Feng
and Yong Li and Hanan Samet",
title = "Understanding Metropolitan Crowd Mobility via Mobile
Cellular Accessing Data",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "8:1--8:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3323345",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3323345",
abstract = "Understanding crowd mobility in a metropolitan area is
extremely valuable for city planners and decision
makers. However, crowd mobility is a relatively new
area of research and has significant technical
challenges: lack of large-scale fine-grained data,
difficulties in large-scale trajectory processing, and
issues with spatial resolution. In this article, we
propose a novel approach for analyzing crowd mobility
on a ``city block'' level. We first propose algorithms
to detect homes, working places, and stay regions for
individual user trajectories. Next, we propose a method
for analyzing commute patterns and spatial correlation
at a city block level. Using mobile cellular accessing
trace data collected from users in Shanghai, we
discover commute patterns, spatial correlation rules,
as well as a hidden structure of the city based on
crowd mobility analysis. Therefore, our proposed
methods contribute to our understanding of human
mobility in a large metropolitan area.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Cabannes:2019:RRN,
author = "Th{\'e}ophile Cabannes and Marco Sangiovanni and
Alexander Keimer and Alexandre M. Bayen",
title = "Regrets in Routing Networks: Measuring the Impact of
Routing Apps in Traffic",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "9:1--9:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325916",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325916",
abstract = "The impact of the recent increase in routing apps
usage on road traffic remains uncertain to this day.
The article introduces, for the first time, a criterion
to evaluate a distance between an observed state of
traffic and the user equilibrium of the traffic
assignment: the average marginal regret. The average
marginal regret provides a quantitative measure of the
impact of routing apps on traffic using only link
flows, link travel times, and travel demand. In
non-atomic routing games (or static traffic assignment
models), the average marginal regret is a measure of
selfish drivers' behaviors. Unlike the price of
anarchy, the average marginal regret in the routing
game can be computed in polynomial time without any
knowledge of user equilibria and socially optimal
states of traffic. First, this article demonstrates on
a small example that the average marginal regret is
more appropriate to define proximity between an
observed state of traffic and an user equilibrium state
of traffic than comparing flows, travel times, or total
cost. Then, experiments on two different models of app
usage and three networks (including the whole L.A.
network with more than 50,000 nodes) demonstrate that
the average marginal regret decreases with an increase
of app usage. Sensitivity analysis of the equilibrium
state with respect to the app usage ratio proves that
the average marginal regret monotonically decreases to
0 with an increase of app usage. Finally, using a toy
example, the article concludes that app usage could
become the new Braess paradox.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Rayhan:2019:ESG,
author = "Yeasir Rayhan and Tanzima Hashem and Roksana Jahan and
Muhammad Aamir Cheema",
title = "Efficient Scheduling of Generalized Group Trips in
Road Networks",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "10:1--10:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325915",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325915",
abstract = "In this article, we introduce generalized group trip
scheduling (GGTS) queries that enable friends and
families to perform activities at different points of
interest (POIs), such as a shopping center, a
restaurant and a pharmacy with the minimum total travel
distance. Trip planning and scheduling for groups, an
important class of location-based services (LBSs), have
recently received attention from researchers. However,
both group trip planning (GTP) and group trip
scheduling (GTS) queries have restrictions: a GTP query
assumes that all group members visit all required POIs
together, whereas a GTS query requires that each POI is
visited by a single group member. A GGTS query is more
general and allows any number of group members to visit
a POI together. We propose an efficient algorithm to
evaluate the exact answers for GGTS queries in road
networks. Since finding the answer for a GGTS query is
an NP-hard problem, to reduce the processing overhead
for a large group size or a large number of required
POI types or a large POI dataset, we propose two
heuristic solutions-trip-scheduling heuristic (TSH) and
search region refinement heuristic (SRH)-for processing
GGTS queries. Extensive experiments with real datasets
show that our optimal algorithm is preferable for small
parameter settings, and the heuristic solutions reduce
the processing overhead significantly in return for
sacrificing the accuracy slightly.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Wang:2019:ADR,
author = "Haiquan Wang and Yilin Li and Guoping Liu and Xiang
Wen and Xiaohu Qie",
title = "Accurate Detection of Road Network Anomaly by
Understanding Crowd's Driving Strategies from Human
Mobility",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "11:1--11:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325913",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325913",
abstract = "There are thousands of road closures and changed
traffic rules that impact vehicle routing every day.
Detecting the road closures and traffic rule changes is
essential for dynamic route planning and navigation
serving. In this article, we propose a driving-behavior
modeling-based method for accurately and effectively
detecting the road anomalies. In the first step, we
detect the areas of anomalies by using the deviation
between drivers' actual and expected behaviors. To
discover the cause of anomalies, we explore the
drivers' short-term destination and find the crucial
link pairs in anomalous areas through a novel optimized
link entanglement search algorithm, namely, the Select
Link Entanglements (SELES) algorithm. Finally, we
analyze the crowd's driving patterns to explain the
road network anomalies further. Experiments on a very
large GPS dataset demonstrate that the proposed
approach outperforms the existing methods in terms of
both accuracy and effectiveness.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Pietrobon:2019:ARC,
author = "Davide Pietrobon and Andrew P. Lewis and Gavin S.
Heverly-Coulson",
title = "An Algorithm for Road Closure Detection from Vehicle
Probe Data",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "12:1--12:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325912",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325912",
abstract = "We developed an algorithm for automatically detecting
road closures by monitoring vehicle probe data. The
algorithm applies to a large class of roads and in the
implementation presented was optimized for lower-volume
roads. It is suitable for batch as well as real-time
applications, the latter class being the most valuable
to guarantee a continuously up-to-date traffic product.
The algorithm compares the likelihood that every road
segment meeting certain requirements is closed or open,
and it triggers an alert whenever the likelihood of the
observed probe activity is too small given a historical
model. We implemented the algorithm and tested it on 12
metro areas in Western Europe. After optimizing
parameters for performance on lower-volume roads, we
obtained a precision of 92\% on those roads and of 80\%
overall.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Albert:2019:IMD,
author = "Marc Albert and Claudio Ruch and Emilio Frazzoli",
title = "Imbalance in Mobility-on-Demand Systems: A Stochastic
Model and Distributed Control Approach",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "13:1--13:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3325914",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3325914",
abstract = "The control of large-scale mobility-on-demand systems
is an emerging topic that has been considered from a
system theoretical, transportation scientific, and
algorithmic point of view. Existing formulations model
mobility-on-demand systems in a queuing theoretical,
network flow-based, or continuous, kinematic framework.
In this work, we model a mobility-on-demand system as a
stochastic differential equation that represents a
generalization of previous approaches. Based on the
model, we define system imbalance as the difference of
the stochastic processes of service request arrival and
vehicle arrival. We formally derive the first moment of
the system imbalance for an imbalance control strategy
that consists of a feedforward control approach
(reference trajectory) and an additional feedback
component. A distributed feedback control policy is
defined that averages the imbalance across the system
and therefore aims at a uniform quality of service
distribution. Finally, we verify our results in a
high-fidelity and large-scale agent-based simulation of
a hypothetical mobility-on-demand system.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Doocy:2019:RPM,
author = "Lauren Doocy and Steven D. Prager and Joseph T.
{Kider, Jr.} and R. Paul Wiegand",
title = "Robust Path Matching and Anomalous Route Detection
Using Posterior Weighted Graphs",
journal = j-TSAS,
volume = "5",
number = "2",
pages = "14:1--14:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3338905",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3338905",
abstract = "Understanding movement behaviors is critical for urban
mobility and transport problems, including robust path
matching, behavior analysis, and anomaly detection. We
investigate a graph-based, probabilistic method for
matching behaviors of entities operating on networks
embedded in some geographic context (e.g., road
networks) under different types of uncertainty. Our
method uses a decay function that allows network
topology and attribute information associated with that
topology (geographic or otherwise) to guide
generalizations of the activity patterns and model
learning process. This allows the system to recognize
when two routes within a network are similar, even when
those routes share little explicit path information. We
demonstrate this method's robust ability to distinguish
between fundamentally different behaviors, even when
data are both incomplete and subject to noise. The
results show good performance when matching behaviors
on different sized and attributed synthetic networks,
as well as on a real-world road network; it examines
situations in which observed entity behavior is noisy,
as well as situations in which observed behaviors
differ from learned models as a result of systemic
noise in the underlying network. Finally, our approach
provides a robust method of detecting anomalous
activity patterns on the network.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Hemminki:2019:CRS,
author = "Samuli Hemminki and Keisuke Kuribayashi and Shin'ichi
Konomi and Petteri Nurmi and Sasu Tarkoma",
title = "Crowd Replication: Sensing-Assisted Quantification of
Human Behavior in Public Spaces",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "15:1--15:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3317666",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3317666",
abstract = "A central challenge for public space design is to
evaluate whether a given space promotes different types
of activities. In this article, as our first
contribution, we develop crowd replication as a novel
sensor-assisted method for quantifying human behavior
within public spaces. In crowd replication, a
researcher is tasked with recording the behavior of
people using a space while being instrumented with a
mobile device that captures a sensor trace of the
replicated movements and activities. Through
mathematical modeling, behavioral indicators extracted
from the replicated trajectories can be extrapolated to
represent a larger target population. As our second
contribution, we develop a novel highly accurate
pedestrian sensing solution for reconstructing movement
trajectories from sensor traces captured during the
replication process. Our key insight is to tailor
sensing to characteristics of the researcher performing
replication, which allows reconstruction to operate
robustly against variations in pace and other walking
characteristics. We validate crowd replication through
a case study carried out within a representative
example of a metropolitan-scale public space. Our
results show that crowd-replicated data closely mirrors
human dynamics in public spaces and reduces overall
data collection effort while producing high-quality
indicators about behaviors and activities of people
within the space. We also validate our pedestrian
modeling approach through extensive benchmarks,
demonstrating that our approach can reconstruct
movement trajectories with high accuracy and robustness
(median error below 1\%). Finally, we demonstrate that
our contributions enable capturing detailed indicators
of liveliness, extent of social interaction, and other
factors indicative of public space quality.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Suzuki:2019:PVP,
author = "Jun Suzuki and Yoshihiko Suhara and Hiroyuki Toda and
Kyosuke Nishida",
title = "Personalized Visited-{POI} Assignment to Individual
Raw {GPS} Trajectories",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "16:1--16:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3317667",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3317667",
abstract = "Knowledge discovery from GPS trajectory data is an
essential topic in several scientific areas, including
data mining, human behavior analysis, and user
modeling. This article proposes a task that assigns
personalized visited points of interest (POIs). Its
goal is to assign every fine-grain location (i.e.,
POIs) that a user actually visited, which we call
visited-POI, to the corresponding span of his or her
(personal) GPS trajectories. We also introduce a novel
algorithm to solve this assignment task. First, we
exhaustively extract stay-points as span candidates of
visits using a variant of a conventional stay-point
extraction method and then extract POIs that are
located close to the extracted stay-points as
visited-POI candidates. Then, we simultaneously predict
which stay-points and POIs can be actual user visits by
considering various aspects, which we formulate as
integer linear programming. Experimental results
conducted on a real user dataset show that our method
achieves higher accuracy in the visited-POI assignment
task than the various cascaded procedures of
conventional methods.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Jagadeesh:2019:FCC,
author = "George R. Jagadeesh and Thambipillai Srikanthan",
title = "Fast Computation of Clustered Many-to-many Shortest
Paths and Its Application to Map Matching",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "17:1--17:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3329676",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3329676",
abstract = "We examine the problem of computing shortest paths in
a transportation network from a set of geographically
clustered source nodes to a set of target nodes. Such
many-to-many shortest path computations are an
essential and computationally expensive part of many
emerging applications that involve map matching of
imprecise trajectories. Existing solutions to this
problem mostly conform to the obvious approach of
performing a single-source shortest path computation
for each source node. We present an algorithm that
exploits the clustered nature of the source nodes.
Specifically, we rely on the observation that paths
originating from a cluster of nodes typically exit the
source region's boundary through a small number of
nodes. Evaluations on a real road network show that the
proposed algorithm provides a speed-up of several times
over the conventional approach when the source nodes
are densely clustered in a region. We also demonstrate
that the presented technique is capable of
substantially accelerating map matching of sparse and
noisy trajectories.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Brown:2019:RPS,
author = "Philip E. Brown and Tamraparni Dasu and Yaron Kanza
and Divesh Srivastava",
title = "From Rocks to Pebbles: Smoothing Spatiotemporal Data
Streams in an Overlay of Sensors",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "18:1--18:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3329677",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3329677",
abstract = "Spatiotemporal streams are prone to data quality
issues such as missing, duplicated and delayed
data-when data generating sensors malfunction, data
transmissions experience problems, or when data are
stored or processed improperly. However, many important
real-time applications rely on the continuous
availability of stream values, e.g., to monitor traffic
flow, resource usage, weather phenomena, and so on.
Other non real-time applications that support
continuous or offline historical analytics also require
high quality data to avoid producing misleading output
such as false positives, erroneous conclusions, and
decisions. In this article, we study the problem of
smoothing streams produced by an overlay of sensors. We
present nonparametric (data-driven, distribution free)
statistical methods to provide an uninterrupted stream
of high-quality spatiotemporal data to real-time
applications, even when the raw stream suffers data
quality issues, such as noise or missing values. Our
novel family of robust methods computes smoothed values
(SVs) that could be used as proxies for data of
questionable quality. The methods make use of a
partition of the monitored area into cells to compute
SVs based on historical data and the deviation from
normalcy in neighboring spatial cells in a way that
outperforms standard regression or interpolation. Our
methods use incremental computation for efficiency, and
they differ in how the deviations are normalized, e.g.,
with respect to zeroth-order, first-order, and
second-order moments. We use three real data sets to
run a suite of experiments and empirically demonstrate
the superiority of the method that uses normalization
with respect to variability.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Zhao:2019:SAR,
author = "Liang Zhao and Olga Gkountouna and Dieter Pfoser",
title = "Spatial Auto-regressive Dependency Interpretable
Learning Based on Spatial Topological Constraints",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "19:1--19:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3339823",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3339823",
abstract = "Spatial regression models are widely used in numerous
areas, including detecting and predicting traffic
volume, air pollution, and housing prices. Unlike
conventional regression models, which commonly assume
independent and identical distributions among
observations, existing spatial regression requires the
prior knowledge of spatial dependency among the
observations in different spatial locations. Such a
spatial dependency is typically predefined by domain
experts or heuristics. However, without sufficient
consideration on the context of the specific prediction
task, it is prohibitively difficult for one to
pre-define the numerical values of the spatial
dependency without bias. More importantly, in many
situations, the existing techniques are insufficient to
sense the complete connectivity and topological
patterns among spatial locations (e.g., in underground
water networks and human brain networks). Until now,
these issues have been extremely difficult to address
and little attention has been paid to the automatic
optimization of spatial dependency in relation to a
prediction task, due to three challenges: (1) necessity
and complexity of modeling the spatial topological
constraints; (2) incomplete prior spatial knowledge;
and (3) difficulty in optimizing under spatial
topological constraints that are usually discrete or
nonconvex. To address these challenges, this article
proposes a novel convex framework that automatically
jointly learns the prediction mapping and spatial
dependency based on spatial topological constraints.
There are two different scenarios to be addressed.
First, when the prior knowledge on existence of
conditional independence among spatial locations is
known (e.g., via spatial contiguity), we propose the
first model named Spatial-Autoregressive Dependency
Learning I (SADL-I) to further quantify such spatial
dependency. However, when the knowledge on the
conditional independence is unknown or incomplete, our
second model named Spatial-Autoregressive Dependency
Learning II (SADL-II) is proposed to automatically
learn the conditional independence pattern as well as
quantify the numerical values of the spatial dependency
based on spatial topological constraints. Topological
constraints are usually discrete and nonconvex, which
makes them extremely difficult to be optimized together
with continuous optimization problems of spatial
regression. To address this, we propose a convex and
continuous equivalence of the original discrete
topological constraints with a theoretical guarantee.
The proposed models are then transferred to convex
problems that can be iteratively optimized by our new
efficient algorithms until convergence to a global
optimal solution. Extensive experimentation using
several real-world datasets demonstrates the
outstanding performance of the proposed models. The
code of our SADL framework is available at:
http://mason.gmu.edu/~lzhao9/materials/codes/SADL.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Mahin:2019:AAR,
author = "Mehnaz Tabassum Mahin and Tanzima Hashem",
title = "Activity-aware Ridesharing Group Trip Planning Queries
for Flexible {POIs}",
journal = j-TSAS,
volume = "5",
number = "3",
pages = "20:1--20:??",
month = sep,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3341818",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3341818",
abstract = "In recent years, ridesharing has become a popular
model that enables users to share their rides with
others. In this article, we introduce a novel
ridesharing service, an Activity-aware Ridesharing
Group Trip Planning (ARGTP) query, in road networks
that exhibits three novel features: (i) ensures a
complete trip for visiting more than two locations,
(ii) allows visiting both fixed and flexible locations,
and (iii) provides true ridesharing services instead of
taxilike ridesourcing services by matching a group of
riders' flexible trips with a driver's fixed trip. A
trip visits a point-of-interest (POI) like a bank,
restaurant, or supermarket for an activity in between
source and destination locations. In a fixed trip, the
POI is predetermined (e.g., a specific branch of a
bank) and in a flexible trip, the POI is a flexible one
(e.g., any branch of a bank). Considering the spatial
proximity of the riders' trips with a driver's trip, an
ARGTP query returns an optimal ridesharing group that
minimizes the group cost. We develop the first solution
to process ARGTP queries in real time and extend our
solution for generalized ARGTP queries with multiple
POIs. The efficiency of ARGTP query processing
algorithms depends on the number of candidate riders
and POIs to be explored. We introduce novel pruning
techniques to refine the riders and POI search space.
We perform extensive experiments using both real and
synthetic datasets to validate the efficiency and
effectiveness of our approach and show that it
outperforms two baseline approaches with a large
margin.",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Aly:2019:BBC,
author = "Heba Aly and John Krumm and Gireeja Ranade and Eric
Horvitz",
title = "To Buy or Not to Buy: Computing Value of
Spatiotemporal Information",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "22:1--22:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3320431",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3320431",
abstract = "Location data from mobile devices is a sensitive yet
valuable commodity for location-based services and
advertising. We investigate the intrinsic value of
location data in the context of strong privacy, where
location information is only available from end users
via purchase. We present an algorithm to compute the
expected value of location data from a user, without
access to the specific coordinates of the location data
point. We use decision-theoretic techniques to provide
a principled way for a potential buyer to make
purchasing decisions about private user location data.
We illustrate our approach in three scenarios: the
delivery of targeted ads specific to a user's home
location, the estimation of traffic speed, and location
prediction. In all three cases, the methodology leads
to quantifiably better purchasing decisions than
competing methods.",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Kannangara:2019:SSG,
author = "Sameera Kannangara and Egemen Tanin and Aaron Harwood
and Shanika Karunasekera",
title = "Stepping Stone Graph: A Graph for Finding Movement
Corridors using Sparse Trajectories",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "23:1--23:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3324883",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3324883",
abstract = "There are many real world applications that require
identifying public movements such as identifying
movement corridors in cities and most popular paths. If
one is not given user trajectories but rather sporadic
location data, such as location-based social network
data, finding movement related information becomes
difficult. Rather than processing all points in a
dataset given a query, a clever approach is to
construct a graph, based on user locations, and query
this graph to answer questions such as shortest paths,
most popular paths, and movement corridors. Shortest
path graph is one of the popular graphs. However, the
shortest path graph can be inefficient and ineffective
for analysing movement data, as it calculates the graph
edges considering the shortest paths over all the
points in a dataset. Therefore, edge sets resulting
from shortest path graphs are usually very restrictive
and not suitable for movement analysis because of its
global view of the dataset. We propose the stepping
stone graph, which calculates the graph considering
point pairs rather than all points; the stepping stone
graph focuses on possible local movements, making it
both efficient and effective for location-based social
network related data. We demonstrate its capabilities
by applying it in the Location-Based Social Network
domain and comparing with the shortest path graph. We
also compare its properties to a range of other graphs
and demonstrate how stepping stone graph relates to
Gabriel graph, relative neighbourhood graph, and
Delaunay triangulation.",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Ayhan:2019:DDF,
author = "Samet Ayhan and Pablo Costas and Hanan Samet",
title = "A Data-driven Framework for Long-Range Aircraft
Conflict Detection and Resolution",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "24:1--24:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3328832",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3328832",
abstract = "At the present time, there is no mechanism for Air
Navigation Service Providers (ANSPs) to probe new
flight plans filed by the Airlines Operation Centers
(AOCs) against the existing approved flight plans to
see if they are likely to cause conflicts or bring
sector traffic densities beyond control. In the current
Air Traffic Control (ATC) operations, aircraft
conflicts and sector traffic densities are resolved
tactically, increasing workload and leading to
potential safety risks and loss of capacity and
efficiency. We propose a novel Data-driven Framework to
address a long-range aircraft conflict detection and
resolution (CDR) problem. Given a set of predicted
trajectories, the framework declares a conflict when a
protected zone of an aircraft on its trajectory is
infringed upon by another aircraft. The framework
resolves the conflict by prescribing an alternative
solution that is optimized by perturbing at least one
of the trajectories involved in the conflict. To
achieve this, the framework learns from descriptive
patterns of historical trajectories and pertinent
weather observations and builds a Hidden Markov Model
(HMM). Using a variant of the Viterbi algorithm, the
framework avoids the airspace volume in which the
conflict is detected and generates a new optimal
trajectory that is conflict free. The key concept upon
which the framework is built is the assumption that the
airspace is nothing more than a horizontally and
vertically concatenated set of spatio-temporal data
cubes where each cube is considered as an atomic unit.
We evaluate our framework using real trajectory
datasets with pertinent weather observations from two
continents and demonstrate its effectiveness for
strategic CDR.",
acknowledgement = ack-nhfb,
articleno = "24",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Bast:2019:EGG,
author = "Hannah Bast and Patrick Brosi and Sabine Storandt",
title = "Efficient Generation of Geographically Accurate
Transit Maps",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "25:1--25:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3337790",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3337790",
abstract = "We present LOOM (Line-Ordering Optimized Maps), an
automatic generator of geographically accurate transit
maps. The input to LOOM is data about the lines of a
transit network: for each line, its station sequence
and geographical course. LOOM proceeds in three stages:
(1) construct a line graph, where edges correspond to
network segments with the same set of lines following
the same course; (2) apply a set of local
transformation rules that compute an optimal partial
ordering of the lines and speed up the next stage; (3)
construct an Integer Linear Program (ILP) that yields a
line ordering for each edge and minimizes the total
number of line crossings and line separations; and (4)
based on the line graph and the computed line ordering,
draw the map. As our maps respect the geography of the
transit network, they can be used as overlays in
typical map services. Previous research either did not
take the network geography into account or was only
concerned with schematic metro map layouting. We
evaluate LOOM on six real-world transit networks, with
line-ordering search-space sizes up to $ 2 \times
10^{267} $. Using our transformation rules and an
improved ILP formulation, we compute optimal line
orderings in a fraction of a second for all networks.
This enables interactive use of our method in map
editors.",
acknowledgement = ack-nhfb,
articleno = "25",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Lowe:2019:FRA,
author = "Aaron Lowe and Pankaj K. Agarwal",
title = "Flood-Risk Analysis on Terrains under the
Multiflow-Direction Model",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "26:1--26:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3340707",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3340707",
abstract = "An important problem in terrain analysis is modeling
how water flows across a terrain and creates floods by
filling up depressions. In this article, we study a
number of flood-risk related problems: Given a terrain
$ \Sigma $, represented as a triangulated xy-monotone
surface with $n$ vertices, a rain distribution R, and a
volume of rain \psi, determine which portions of $
\Sigma $ are flooded. We develop efficient algorithms
for flood-risk analysis under the multiflow-directions
(MFD) model, in which water at a point can flow along
multiple downslope edges and which more accurately
represent flooding events. We present three main
results: First, we present an O (n \log n)-time
algorithm to answer a terrain-flood query: if it rains
a volume \psi according to a rain distribution R,
determine what regions of $ \Sigma $ will be flooded.
Second, we present a $ O (n \log n + n m)$-time
algorithm for preprocessing $ \Sigma $ containing $m$
sinks into a data structure of size $ O (n m)$ for
answering point-flood queries: Given a rain
distribution $R$, a volume of rain $ \psi $ falling
according to $R$, and point $q$ \in $ \Sigma $,
determine whether $q$ will be flooded. A point-flood
query can be answered in $ O (| R | k + k^2)$ time,
where $k$ is the number of maximal depressions in $
\Sigma $ containing the query point $q$ and | R | is
the number of vertices in $R$ with positive rainfall.
Finally, we present algorithms for answering a
flood-time query: given a rain distribution $R$ and a
point $ q \in \Sigma $, determine the volume of rain
that must fall before $q$ is flooded. Assuming that the
product of two $ k \times k $ matrices can be computed
in $ O (k \omega)$ time, we show that a flood-time
query can be answered in $ O (n k + k \omega)$ time. We
also give an $ \alpha $-approximation algorithm, for $
\alpha > 1$, which runs in $ O(n \log n \log \alpha
\rho)$-time, where $ \rho $ is a variable on the
terrain that depends on the ratio between depression
volumes. We implemented our algorithms for computing
terrain and point-flood queries as well as approximate
flood-time queries. We tested the efficacy and
efficiency of these algorithms on three real terrains
of different types (urban, suburban, and
mountainous.)",
acknowledgement = ack-nhfb,
articleno = "26",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Sabek:2019:RSM,
author = "Ibrahim Sabek and Mashaal Musleh and Mohamed F.
Mokbel",
title = "{RegRocket}: Scalable Multinomial Autologistic
Regression with Unordered Categorical Variables Using
{Markov} Logic Networks",
journal = j-TSAS,
volume = "5",
number = "4",
pages = "27:1--27:??",
month = dec,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3366459",
ISSN = "2374-0353",
bibdate = "Fri Dec 6 16:16:51 MST 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/citation.cfm?id=3366459",
abstract = "Autologistic regression is one of the most popular
statistical tools to predict spatial phenomena in
several applications, including epidemic diseases
detection, species occurrence prediction, earth
observation, and business management. In general,
autologistic regression divides the space into a
two-dimensional grid, where the prediction is performed
at each cell in the grid. The prediction at any
location is based on a set of predictors (i.e.,
features) at this location and predictions from
neighboring locations. In this article, we address the
problem of building efficient autologistic models with
multinomial (i.e., categorical) prediction and
predictor variables, where the categories represented
by these variables are unordered. Unfortunately,
existing methods to build autologistic models are
designed for binary variables in addition to being
computationally expensive (i.e., do not scale up for
large-scale grid data such as fine-grained satellite
images). Therefore, we introduce RegRocket: a scalable
framework to build multinomial autologistic models for
predicting large-scale spatial phenomena. RegRocket
considers both the accuracy and efficiency aspects when
learning the regression model parameters. To this end,
RegRocket is built on top of Markov Logic Network
(MLN), a scalable statistical learning framework, where
its internals and data structures are optimized to
process spatial data. RegRocket provides an equivalent
representation of the multinomial prediction and
predictor variables using MLN where the dependencies
between these variables are transformed into
first-order logic predicates. Then, RegRocket employs
an efficient framework that learns the model parameters
from the MLN representation in a distributed manner.
Extensive experimental results based on two large real
datasets show that RegRocket can build multinomial
autologistic models, in minutes, for 1 million grid
cells with 0.85 average F1-score.",
acknowledgement = ack-nhfb,
articleno = "27",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "http://dl.acm.org/pub.cfm?id=J1514",
}
@Article{Li:2020:TGF,
author = "Wei Li and Haiquan Chen and Wei-Shinn Ku and Xiao
Qin",
title = "{Turbo-GTS}: a Fast Framework of Optimizing Task
Throughput for Large-Scale Mobile Crowdsourcing",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "1:1--1:29",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3363450",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3363450",
abstract = "In mobile crowdsourcing, workers are financially
motivated to perform as many self-selected tasks as
possible to maximize their revenue. Unfortunately, the
existing task scheduling approaches in mobile
crowdsourcing fail to consider task execution
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Zhang:2020:DPS,
author = "Rui Zhang and Kevin G. Stanley and Daniel Fuller and
Scott Bell",
title = "Differentiating Population Spatial Behavior Using
Representative Features of Geospatial Mobility
{(ReFGeM)}",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "2:1--2:25",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3362063",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3362063",
abstract = "Understanding how humans use and consume space by
comparing stratified groups, either through observation
or controlled study, is key to designing better spaces,
cities, and policies. GPS data traces provide detailed
movement patterns of individuals but \ldots{}",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Naghizade:2020:PCA,
author = "Elham Naghizade and Lars Kulik and Egemen Tanin and
James Bailey",
title = "Privacy- and Context-aware Release of Trajectory
Data",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "3:1--3:25",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3363449",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3363449",
abstract = "The availability of large-scale spatio-temporal
datasets along with the advancements in analytical
models and tools have created a unique opportunity to
create valuable insights into managing key areas of
society from transportation and urban planning
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Souza:2020:STD,
author = "Roberto C. S. N. P. Souza and Derick M. Oliveira and
Denise E. F. de Brito and Renato M. Assun{\c{c}}{\~a}o
and Wagner {Meira Jr.}",
title = "Space-Time Drift Point Detection in Mobility
Patterns",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "4:1--4:24",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3360721",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3360721",
abstract = "Location-aware information is now commonplace, as the
ubiquity and pervasiveness of technology enabled its
generation and storage at large scale. These data
constitute a rich representation of entities'
whereabouts and behavior as they move on the map.
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Mishra:2020:TSP,
author = "Suman Mishra and Lina Kattan and S. C. Wirasinghe",
title = "Transit Signal Priority Along a Signalized Arterial: a
Passenger-based Approach",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "5:1--5:19",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355611",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3355611",
abstract = "This article develops a passenger-based priority for
transit buses by balancing the trade-offs between the
benefits at major streets and delays on side streets. A
rule-based Transit Signal Priority (TSP) is set to
assign priority to scheduled-based \ldots{}",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Chambers:2020:MMU,
author = "Erin Chambers and Brittany Terese Fasy and Yusu Wang
and Carola Wenk",
title = "Map-Matching Using Shortest Paths",
journal = j-TSAS,
volume = "6",
number = "1",
pages = "6:1--6:17",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3368617",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Tue Apr 7 07:13:55 MDT 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3368617",
abstract = "We consider several variants of the map-matching
problem, which seeks to find a path Q in graph G that
has the smallest distance to a given trajectory P
(which is likely not to be exactly on the graph). In a
typical application setting, P models a noisy
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Costa:2020:RTS,
author = "Camila F. Costa and Mario A. Nascimento",
title = "In-Route Task Selection in Spatial Crowdsourcing",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "7:1--7:45",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3368268",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3368268",
abstract = "Consider a city's road network and a worker who is
traveling on a given path from a starting point s to a
destination d (e.g., from school or work to home) in
said network. Consider further that there is a set of
tasks in the network available to be \ldots{}",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Tampakis:2020:DSJ,
author = "Panagiotis Tampakis and Christos Doulkeridis and Nikos
Pelekis and Yannis Theodoridis",
title = "Distributed Subtrajectory Join on Massive Datasets",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "8:1--8:29",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373642",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3373642",
abstract = "Joining trajectory datasets is a significant operation
in mobility data analytics and the cornerstone of
various methods that aim to extract knowledge out of
them. In the era of Big Data, the production of
mobility data has become massive and, \ldots{}",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Das:2020:EDD,
author = "Nabanita Das and Souvik Basu and Sipra Das Bit",
title = "Efficient {DropBox} Deployment toward Improving
Post-Disaster Information Exchange in a Smart City",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "9:1--9:18",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373645",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3373645",
abstract = "In the face of a disaster, the already installed
gadgets in a smart city can be leveraged to gather
post-disaster situational information. However, owing
to the typical disruption of cellular and Internet
connectivity during disasters, the possibility
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Huang:2020:IIT,
author = "Xiaohui Huang and Pan He and Anand Rangarajan and
Sanjay Ranka",
title = "Intelligent Intersection: Two-stream Convolutional
Networks for Real-time Near-accident Detection in
Traffic Video",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "10:1--10:28",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373647",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3373647",
abstract = "Camera-based systems are increasingly used for
collecting information on intersections and arterials.
Unlike loop controllers that can generally be only used
for detection and movement of vehicles, cameras can
provide rich information about the traffic \ldots{}",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Yang:2020:SFB,
author = "Dongfang Yang and {\"U}mit {\"O}zg{\"u}ner and Keith
Redmill",
title = "A Social Force Based Pedestrian Motion Model
Considering Multi-Pedestrian Interaction with a
Vehicle",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "11:1--11:27",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373646",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3373646",
abstract = "Pedestrian motion modeling in mixed traffic scenarios
is crucial to the development of autonomous systems in
transportation related applications. This work
investigated how pedestrian motion is affected by
surrounding pedestrians and vehicles, i.e., \ldots{}",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Qian:2020:UOD,
author = "Xinwu Qian and Dheeraj Kumar and Wenbo Zhang and
Satish V. Ukkusuri",
title = "Understanding the Operational Dynamics of Mobility
Service Providers: a Case of {Uber}",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "12:1--12:20",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3378888",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3378888",
abstract = "The rise of mobility service providers (MSPs) is
reforming the traditional taxi service (TTS) market.
MSPs differ from TTS with the core idea of using
technology to optimally match riders with drivers,
features like ride-sharing and surge pricing, and
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Zhou:2020:SST,
author = "Fan Zhou and Hantao Wu and Goce Trajcevski and Ashfaq
Khokhar and Kunpeng Zhang",
title = "Semi-supervised Trajectory Understanding with {POI}
Attention for End-to-End Trip Recommendation",
journal = j-TSAS,
volume = "6",
number = "2",
pages = "13:1--13:25",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3378890",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:22 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3378890",
abstract = "Trip planning/recommendation is an important task for
a plethora of applications in urban settings (e.g.,
tourism, transportation, social outings), relying on
services provided by Location-Based Social Networks
(LBSN). To provide greater context-. \ldots{}",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Wang:2020:TTG,
author = "Lijing Wang and Jiangzhuo Chen and Madhav Marathe",
title = "{TDEFSI}: Theory-guided Deep Learning-based Epidemic
Forecasting with Synthetic Information",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "15:1--15:39",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380971",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380971",
abstract = "Influenza-like illness (ILI) places a heavy social and
economic burden on our society. Traditionally, ILI
surveillance data are updated weekly and provided at a
spatially coarse resolution. Producing timely and
reliable high-resolution spatiotemporal \ldots{}",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Das:2020:SSA,
author = "Monidipa Das and Mahardhika Pratama and Soumya K.
Ghosh",
title = "{SARDINE}: a Self-Adaptive Recurrent Deep Incremental
Network Model for Spatio-Temporal Prediction of Remote
Sensing Data",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "16:1--16:26",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380972",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380972",
abstract = "The timely and accurate prediction of remote sensing
data is of utmost importance especially in a situation
where the predicted data is utilized to provide
insights into emerging issues, like environmental
nowcasting. Significant research progress can
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Ferreira:2020:DLA,
author = "Danielle L. Ferreira and Bruno A. A. Nunes and Carlos
Alberto V. Campos and Katia Obraczka",
title = "A Deep Learning Approach for Identifying User
Communities Based on Geographical Preferences and Its
Applications to Urban and Environmental Planning",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "17:1--17:24",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380970",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380970",
abstract = "Understanding human mobility plays a vital role in
urban and environmental planning as cities continue to
grow. Ubiquitous geo-location, localization technology,
and availability of big-data-ready computing
infrastructure have enabled the development of
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Jauhri:2020:GRR,
author = "Abhinav Jauhri and Brad Stocks and Jian Hui Li and
Koichi Yamada and John Paul Shen",
title = "Generating Realistic Ride-Hailing Datasets Using
{GANs}",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "18:1--18:14",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380968",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380968",
abstract = "This article focuses on the synthetic generation of
human mobility data in urban areas. We present a novel
application of generative adversarial networks (GANs)
for modeling and generating human mobility data. We
leverage actual ride requests from ride-. \ldots{}",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Steininger:2020:MEN,
author = "Michael Steininger and Konstantin Kobs and Albin Zehe
and Florian Lautenschlager and Martin Becker and
Andreas Hotho",
title = "{MapLUR}: Exploring a New Paradigm for Estimating Air
Pollution Using Deep Learning on Map Images",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "19:1--19:24",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380973",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380973",
abstract = "Land-use regression (LUR) models are important for the
assessment of air pollution concentrations in areas
without measurement stations. While many such models
exist, they often use manually constructed features
based on restricted, locally available \ldots{}",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Shao:2020:ILA,
author = "Wei Shao and Siyu Tan and Sichen Zhao and Kyle Kai Qin
and Xinhong Hei and Jeffrey Chan and Flora D. Salim",
title = "Incorporating {LSTM} Auto-Encoders in Optimizations to
Solve Parking Officer Patrolling Problem",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "20:1--20:21",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3380966",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3380966",
abstract = "The smart parking system is one of the most important
problems in smart cities. Recently, an increasing
number of sensors installed in parking spaces have
provided big spatio-temporal data that be used to
analyze parking situations in the city and help
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Touya:2020:DLE,
author = "Guillaume Touya and Imran Lokhat",
title = "Deep Learning for Enrichment of Vector Spatial
Databases: Application to Highway Interchange",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "21:1--21:21",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3382080",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3382080",
abstract = "Spatial analysis and pattern recognition with vector
spatial data is particularly useful to enrich raw data.
In road networks, for instance, there are many patterns
and structures that are implicit with only road line
features, among which highway \ldots{}",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Youssef:2020:ISI,
author = "Moustafa Youssef and John Krum and Muhammad Aamir
Cheema",
title = "Introduction to the Special Issue on Deep Learning for
Spatial Algorithms and Systems",
journal = j-TSAS,
volume = "6",
number = "3",
pages = "14:1--14:2",
month = may,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3386878",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3386878",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Wang:2020:SGS,
author = "Senzhang Wang and Jiannong Cao and Hao Chen and Hao
Peng and Zhiqiu Huang",
title = "{SeqST-GAN}: {Seq2Seq} Generative Adversarial Nets for
Multi-step Urban Crowd Flow Prediction",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "22:1--22:24",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3378889",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3378889",
abstract = "Citywide crowd flow data are ubiquitous nowadays, and
forecasting the flow of crowds is of great importance
to many real applications such as traffic management
and mobility-on-demand (MOD) services. The challenges
of accurately predicting urban crowd \ldots{}",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Fellegara:2020:TTF,
author = "Riccardo Fellegara and Leila {De Floriani} and Paola
Magillo and Kenneth Weiss",
title = "Tetrahedral Trees: a Family of Hierarchical Spatial
Indexes for Tetrahedral Meshes",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "23:1--23:34",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3385851",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3385851",
abstract = "We address the problem of performing efficient spatial
and topological queries on large tetrahedral meshes
with arbitrary topology and complex boundaries. Such
meshes arise in several application domains, such as 3D
Geographic Information Systems (GISs), \ldots{}",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Smolyak:2020:CIG,
author = "Daniel Smolyak and Kathryn Gray and Sarkhan Badirli
and George Mohler",
title = "Coupled {IGMM-GANs} with Applications to Anomaly
Detection in Human Mobility Data",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "24:1--24:14",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3385809",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3385809",
abstract = "Detecting anomalous activity in human mobility data
has a number of applications, including road hazard
sensing, telematics-based insurance, and fraud
detection in taxi services and ride sharing. In this
article, we address two challenges that arise in
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "24",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Li:2020:CPM,
author = "Qingzhe Li and Liang Zhao and Yi-Ching Lee and Jessica
Lin",
title = "Contrast Pattern Mining in Paired Multivariate Time
Series of a Controlled Driving Behavior Experiment",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "25:1--25:28",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3397272",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3397272",
abstract = "The controlled experiment is an important scientific
method for researchers seeking to determine the
influence of the intervention, by interpreting the
contrast patterns between the temporal observations
from control and experimental groups (i.e., \ldots{})",
acknowledgement = ack-nhfb,
articleno = "25",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Tokuda:2020:NAP,
author = "Eric K. Tokuda and Yitzchak Lockerman and Gabriel B.
A. Ferreira and Ethan Sorrelgreen and David Boyle and
Roberto M. {Cesar, Jr.} and Claudio T. Silva",
title = "A New Approach for Pedestrian Density Estimation Using
Moving Sensors and Computer Vision",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "26:1--26:20",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3397575",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3397575",
abstract = "An understanding of person dynamics is indispensable
for numerous urban applications, including the design
of transportation networks and planning for business
development. Pedestrian counting often requires
utilizing manual or technical means to count \ldots{}",
acknowledgement = ack-nhfb,
articleno = "26",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Emiris:2020:PEM,
author = "Ioannis Z. Emiris and Ioannis Psarros",
title = "Products of {Euclidean} Metrics, Applied to Proximity
Problems among Curves: Unified Treatment of Discrete
{Fr{\'e}chet} and Dynamic Time Warping Distances",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "27:1--27:20",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3397518",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3397518",
abstract = "Approximate Nearest Neighbor (ANN) search is a
fundamental computational problem that has benefited
from significant progress in the past couple of
decades. However, most work has been devoted to
pointsets, whereas complex shapes have not been
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "27",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Babu:2020:TTB,
author = "Sarath Babu and B. S. Manoj",
title = "Toward a Type-based Analysis of Road Networks",
journal = j-TSAS,
volume = "6",
number = "4",
pages = "28:1--28:45",
month = aug,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3397579",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:23 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3397579",
abstract = "Road networks are major influential factors in the
development of any nation. Due to different factors
involved in their evolution, road networks exhibit
complex structures, which result in problems such as
inefficient traffic patterns, congestion, and
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "28",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Paoluzzi:2021:TCA,
author = "Alberto Paoluzzi and Vadim Shapiro and Antonio Dicarlo
and Francesco Furiani and Giulio Martella and Giorgio
Scorzelli",
title = "Topological Computing of Arrangements with
(Co)Chains",
journal = j-TSAS,
volume = "7",
number = "1",
pages = "1:1--1:29",
month = jan,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3401988",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3401988",
abstract = "In many areas of applied geometric/numeric
computational mathematics, including geo-mapping,
computer vision, computer graphics, finite element
analysis, medical imaging, geometric design, and solid
modeling, one has to compute incidences, adjacencies,
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{DeBock:2021:SDD,
author = "Jelle {De Bock} and Steven Verstockt",
title = "{SmarterROUTES} --- a Data-driven Context-aware
Solution for Personalized Dynamic Routing and
Navigation",
journal = j-TSAS,
volume = "7",
number = "1",
pages = "2:1--2:25",
month = jan,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3402125",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3402125",
abstract = "SmarterROUTES contributes to personalised routing and
navigation by data-driven route ranking and an
environmentally aware road scene complexity-estimation
mechanism. Traditional routing algorithms provide the
fastest, shortest, or most ecological route \ldots{}",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Vu:2021:UDL,
author = "Tin Vu and Alberto Belussi and Sara Migliorini and
Ahmed Eldway",
title = "Using Deep Learning for Big Spatial Data
Partitioning",
journal = j-TSAS,
volume = "7",
number = "1",
pages = "3:1--3:37",
month = jan,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3402126",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3402126",
abstract = "This article explores the use of deep learning to
choose an appropriate spatial partitioning technique
for big data. The exponential increase in the volumes
of spatial datasets resulted in the development of big
spatial data frameworks. These systems \ldots{}",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Peng:2021:FOS,
author = "Dongliang Peng and Alexander Wolff and Jan-Henrik
Haunert",
title = "Finding Optimal Sequences for Area Aggregation --- {$
A^\star $} vs. Integer Linear Programming",
journal = j-TSAS,
volume = "7",
number = "1",
pages = "4:1--4:40",
month = jan,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3409290",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3409290",
abstract = "To provide users with maps of different scales and to
allow them to zoom in and out without losing context,
automatic methods for map generalization are needed. We
approach this problem for land-cover maps. Given two
land-cover maps at two different \ldots{}",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Brito:2021:SPP,
author = "Denise E. F. Brito and Renato M. Assun{\c{c}}{\~a}o
and Roberto C. S. N. P. Souza and Wagner {Meira, Jr.}",
title = "{SCPP}: a Point Process-based Clustering of Spatial
Visiting Patterns",
journal = j-TSAS,
volume = "7",
number = "1",
pages = "5:1--5:30",
month = jan,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3423405",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3423405",
abstract = "A collection of individuals is represented by point
patterns. Each individual is a finite set of
geographical locations representing their visiting
pattern to places in a region. We present SCPP, an
algorithm for clustering these individuals considering
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Zhang:2021:ADI,
author = "Xiaowei Zhang and Aly Shehata and Bedrich Benes and
Daniel Aliaga",
title = "Automatic Deep Inference of Procedural Cities from
Global-scale Spatial Data",
journal = j-TSAS,
volume = "7",
number = "2",
pages = "6:1--6:28",
month = feb,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3423422",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3423422",
abstract = "Recent advances in big spatial data acquisition and
deep learning allow novel algorithms that were not
possible several years ago. We introduce a novel
inverse procedural modeling algorithm for urban areas
that addresses the problem of spatial data \ldots{}",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Damiani:2021:LRD,
author = "Maria Luisa Damiani and Fatima Hachem and Christian
Quadri and Matteo Rossini and Sabrina Gaito",
title = "On Location Relevance and Diversity in Human Mobility
Data",
journal = j-TSAS,
volume = "7",
number = "2",
pages = "7:1--7:38",
month = feb,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3423404",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3423404",
abstract = "The theme of human mobility is transversal to multiple
fields of study and applications, from ad hoc networks
to smart cities, from transportation planning to
recommendation systems on social networks. Despite the
considerable efforts made by a few \ldots{}",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Zhu:2021:PCK,
author = "Huaijie Zhu and Xiaochun Yang and Bin Wang and
Wang-Chien Lee and Jian Yin and Jianliang Xu",
title = "Processing Continuous k Nearest Neighbor Queries in
Obstructed Space with {Voronoi} Diagrams",
journal = j-TSAS,
volume = "7",
number = "2",
pages = "8:1--8:27",
month = feb,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3425955",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3425955",
abstract = "With the emergence and growing popularity of and
location-based service (LBS) technologies, the
continuous k nearest neighbor (CO k NN) query in
obstructed space is becoming a very important service.
In this article, we study the CO k NN in obstructed
space,. \ldots{}",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{He:2021:MIA,
author = "Eric He and Fan Bai and Curtis Hay and Jinzhu Chen and
Vijayakumar Bhagavatula",
title = "A Map Inference Approach Using Signal Processing from
Crowd-sourced {GPS} Data",
journal = j-TSAS,
volume = "7",
number = "2",
pages = "9:1--9:23",
month = feb,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3431785",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3431785",
abstract = "The amount of GPS data that can be collected is
increasing tremendously, thanks to the increased
popularity of Global Position System (GPS) devices
(e.g., smartphones). This article aims to develop novel
methods of converting crowd-sourced GPS traces
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Laoudias:2021:IQP,
author = "Christos Laoudias and Artyom Nikitin and Panagiotis
Karras and Moustafa Youssef and Demetrios
Zeinalipour-Yazti",
title = "Indoor Quality-of-position Visual Assessment Using
Crowdsourced Fingerprint Maps",
journal = j-TSAS,
volume = "7",
number = "2",
pages = "10:1--10:32",
month = feb,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3433026",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Sat Mar 27 09:18:24 MDT 2021",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3433026",
abstract = "Internet-based Indoor Navigation (IIN) architectures
organize signals collected by crowdsourcers in
Fingerprint Maps (FMs) to improve localization given
that satellite-based technologies do not operate
accurately in indoor spaces where people spend 80\%-.
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Bose:2021:PST,
author = "Sunanda Bose and Sumit Kumar Paul and Nandini
Mukherjee",
title = "Predicting Spatio-Temporal Phenomena of Mobile
Resources in Sensor Cloud Infrastructure",
journal = j-TSAS,
volume = "7",
number = "3",
pages = "11:1--11:38",
month = sep,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3446936",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:28 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3446936",
abstract = "Integration of sensor and cloud technologies enable
distributed sensing and data collection. We consider a
scenario when sensing requests are originated from
sensor aware applications that are hosted inside
sensor-cloud infrastructures. These requests \ldots{}",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Sun:2021:RTE,
author = "Yuhan Sun and Mohamed Sarwat",
title = "\pkg{Riso-Tree}: an Efficient and Scalable Index for
Spatial Entities in Graph Database Management Systems",
journal = j-TSAS,
volume = "7",
number = "3",
pages = "12:1--12:39",
month = sep,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3450945",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:28 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3450945",
abstract = "With the ubiquity of spatial data, vertexes or edges
in graphs can possess spatial location attributes side
by side with other non-spatial attributes. For
instance, as of June 2018, the Wikidata knowledge graph
contains 48,547,142 data items (i.e., \ldots{})",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Middya:2021:SIT,
author = "Asif Iqbal Middya and Sarbani Roy",
title = "Spatial Interpolation Techniques on Participatory
Sensing Data",
journal = j-TSAS,
volume = "7",
number = "3",
pages = "13:1--13:32",
month = sep,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3457609",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:28 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3457609",
abstract = "Spatial distributions of data of natural phenomena can
be estimated by using different spatial interpolation
techniques. These techniques can be used for the
purpose of developing urban noise pollution monitoring
applications, so they can truly describe \ldots{}",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Daghistani:2021:SAL,
author = "Anas Daghistani and Walid G. Aref and Arif Ghafoor and
Ahmed R. Mahmood",
title = "\pkg{SWARM}: Adaptive Load Balancing in Distributed
Streaming Systems for Big Spatial Data",
journal = j-TSAS,
volume = "7",
number = "3",
pages = "14:1--14:43",
month = sep,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3460013",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:28 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3460013",
abstract = "The proliferation of GPS-enabled devices has led to
the development of numerous location-based services.
These services need to process massive amounts of
streamed spatial data in real-time. The current scale
of spatial data cannot be handled using \ldots{}",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Gudmundsson:2021:PIS,
author = "Joachim Gudmundsson and Michael Horton and John
Pfeifer and Martin P. Seybold",
title = "A Practical Index Structure Supporting {Fr{\'e}chet}
Proximity Queries among Trajectories",
journal = j-TSAS,
volume = "7",
number = "3",
pages = "15:1--15:33",
month = sep,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3460121",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:28 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3460121",
abstract = "We present a scalable approach for range and k nearest
neighbor queries under computationally expensive
metrics, like the continuous Fr{\'e}chet distance on
trajectory data. Based on clustering for metric
indexes, we obtain a dynamic tree structure whose size
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Aref:2021:ISS,
author = "Walid G. Aref",
title = "Introduction to the Special Section on the Best Papers
from the {2019 ACM SIGSPATIAL Conference}",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "16:1--16:2",
month = dec,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3485049",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3485049",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Custers:2021:MPC,
author = "Bram Custers and Mees Van De Kerkhof and Wouter
Meulemans and Bettina Speckmann and Frank Staals",
title = "Maximum Physically Consistent Trajectories",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "17:1--17:33",
month = jun,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3452378",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3452378",
abstract = "Trajectories are usually collected with physical
sensors, which are prone to errors and cause outliers
in the data. We aim to identify such outliers via the
physical properties of the tracked entity, that is, we
consider its physical possibility to visit \ldots{}",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Werner:2021:GAE,
author = "Martin Werner",
title = "\pkg{GloBiMapsAI}: an {AI}-Enhanced Probabilistic Data
Structure for Global Raster Datasets",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "18:1--18:24",
month = jun,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3453184",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3453184",
abstract = "In the last decade, more and more spatial data has
been acquired on a global scale due to satellite
missions, social media, and coordinated governmental
activities. This observational data suffers from huge
storage footprints and makes global analysis \ldots{}",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Teixeira:2021:ISR,
author = "Douglas {Do Couto Teixeira} and Aline {Carneiro Viana}
and Jussara M. Almeida and M{\'a}rio S. Alvim",
title = "The Impact of Stationarity, Regularity, and Context on
the Predictability of Individual Human Mobility",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "19:1--19:24",
month = jun,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3459625",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3459625",
abstract = "Predicting mobility-related behavior is an important
yet challenging task. On the one hand, factors such as
one's routine or preferences for a few favorite
locations may help in predicting their mobility. On the
other hand, several contextual factors, \ldots{}",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Almaslukh:2021:TGS,
author = "Abdulaziz Almaslukh and Yunfan Kang and Amr Magdy",
title = "Temporal Geo-Social Personalized Keyword Search Over
Streaming Data",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "20:1--20:28",
month = dec,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3473006",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3473006",
abstract = "The unprecedented rise of social media platforms,
combined with location-aware technologies, has led to
continuously producing a significant amount of
geo-social data that flows as a user-generated data
stream. This data has been exploited in several
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Petroff:2021:SEA,
author = "Matthew A. Petroff",
title = "A Square Equal-Area Map Projection with Low Angular
Distortion, Minimal Cusps, and Closed-Form Solutions",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "21:1--21:16",
month = dec,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3460521",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3460521",
abstract = "A novel square equal-area map projection is proposed.
The projection combines closed-form forward and inverse
solutions with relatively low angular distortion and
minimal cusps, a combination of properties not
manifested by any previously published square
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Cicerone:2021:CPS,
author = "Serafino Cicerone and Mattia D'emidio and Daniele
Frigioni and Filippo Tirabassi Pascucci",
title = "Combining Polygon Schematization and Decomposition
Approaches for Solving the Cavity Decomposition
Problem",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "22:1--22:37",
month = jun,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3462760",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3462760",
abstract = "The cavity decomposition problem is a computational
geometry problem, arising in the context of modern
electronic CAD systems, that concerns detecting the
generation and propagation of electromagnetic noise
into multi-layer printed circuit boards. \ldots{}",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
@Article{Mariescu-Istodor:2021:VDC,
author = "Radu Mariescu-Istodor and Alexandru Cristian and Mihai
Negrea and Peiwei Cao",
title = "\pkg{VRPDiv}: a Divide and Conquer Framework for Large
Vehicle Routing Problems",
journal = j-TSAS,
volume = "7",
number = "4",
pages = "23:1--23:41",
month = dec,
year = "2021",
CODEN = "????",
DOI = "https://doi.org/10.1145/3474832",
ISSN = "2374-0353 (print), 2374-0361 (electronic)",
ISSN-L = "2374-0353",
bibdate = "Wed Mar 2 06:18:29 MST 2022",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tsas.bib",
URL = "https://dl.acm.org/doi/10.1145/3474832",
abstract = "The Vehicle Routing Problem (VRP) is an NP hard
problem where we need to optimize itineraries for
agents to visit multiple targets. When considering
real-world travel (road-network topology, speed limits
and traffic), modern VRP solvers can only process
\ldots{}",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Spatial Algorithms and Systems
(TSAS)",
journal-URL = "https://dl.acm.org/loi/tsas",
}
