III: Small: Investigating Spatial Big Data for Next Generation Routing Services

越来越多的位置感知数据集的大小，种类和更新速率超过了空间计算技术的能力。该项目解决了这些数据集带来的新挑战，这些数据集有时也被称为空间大数据（SBD）。SBD的例子包括手机和GPS设备的轨迹，时间详细（TD）的道路地图，车辆发动机测量等SBD有可能改变社会。麦肯锡全球研究所（McKinsey Global Institute）最近的一份报告估计，到2020年，个人位置数据可以帮助车辆通过下一代路由服务（如生态路由）避免拥堵，从而每年为消费者节省数千亿美元。生态路线可以利用各种形式的SBD来通过燃料消耗或温室气体（GHG）排放而不是总距离或旅行时间来比较路线。为了开发下一代生态路由服务，该项目在三个方面进行了创新。首先，拉格朗日Xgraphs，一个新的概念，在计算机科学中，探索在概念，逻辑和物理数据库水平，以模型旅行者的参考系，一个重大的偏离传统的二元关系（例如，邻接）图。其次，探讨了路由集合的概念，以及路由集合的可扩展算法。例如，为了在给定时间间隔的所有可能的开始时间上识别路线集合，该项目探索了一种关键时间点方法，该方法将给定的时间间隔划分为一组不相交的子间隔，这些子间隔在替代路线之间进行静态排名。该方法不仅新颖，而且对该领域非常重要。关键时间点可能成为动态规划（DP）解决方案的一个重要组成部分，这将需要重新考虑，在面对新兴的时间详细的SBD，违反DP假设的固定排名的替代解决方案。第三，为了解决SBD方法的日益多样性，开发了允许快速集成新数据源和路由算法的算法集成和灵活架构。拟议的工作为减少燃料消耗和温室气体排放的生态路线和其他与旅行有关的服务奠定了基础，从而有助于实现能源独立和可持续性的国家目标。通过增加SBD的可用性，该项目还增强了其他研究人员的研究基础设施。教育活动包括在新兴的SBD和生态路线方面制定课程和培训学生。计划通过在相关同行评审会议和期刊上发表来传播成果。更多详情可在项目网站（www.spatial.cs.umn.edu/eco-routing/）上查阅。

Increasingly, location-aware datasets are of a size, variety, and update rate that exceed the capability of spatial computing technologies. This project addresses the emerging challenges posed by such datasets, which sometimes are also referred to as Spatial Big Data (SBD). SBD examples include trajectories of cell-phones and GPS devices, temporally detailed (TD) road maps, vehicle engine measurements, etc. SBD has the potential to transform society. A recent McKinsey Global Institute report estimates that personal location data could save consumers hundreds of billions of dollars annually by 2020 by helping vehicles avoid congestion via next generation routing services such as eco-routing. Eco-routing may leverage various forms of SBD to compare routes by fuel consumption or greenhouse gas (GHG) emissions rather than total distance or travel-time. To develop next-generation eco-routing services, this project innovates in three areas. Frist, Lagrangian Xgraphs, a novel concept in computer science, is explored at conceptual, logical and physical database levels to model traveler's frame of reference, a major departure from traditional binary relationship (e.g., adjacency) graphs. Second, it probes the concept of route-collections, and scalable algorithms for finding route-collections. For example, to identify a route-collection over all possible start-times of a given time-interval, the project explores a critical time point approach which divides a given time-interval into a set of disjoint sub-intervals of stationary-rankings among alternative routes. The approach is not only novel but also very important for the field. Critical time points may become a vital component of dynamic programming (DP) solutions, which would need reconsideration in the face of emerging temporally detailed SBD that violate DP assumptions about stationary ranking of alternate solutions. Third, to address the increasing diversity of SBD methods, algorithm-ensembles and flexible architectures that allow rapid integration of new data sources and routing algorithms are developed. The proposed work serves national goals for energy independence and sustainability by laying the ground work for eco-routing and other travel-related services that reduce fuel consumption and greenhouse gas emissions. By increasing the availability of SBD, the project also enhances the research infrastructure for other researchers. Educational activities include curriculum development and training of students in the emerging area of SBD and Eco-routing. Result dissemination is planned via publication in relevant peer-reviewed conferences and journals. More details are available on the project website (www.spatial.cs.umn.edu/eco-routing/).