检索结果-内蒙古大学图书馆

G-PICS: A Framework for GPU-Based spatial Indexing and query processing

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第3期34卷 1243-1257页

作者： Lewis, Zhila-Nouri Tu, Yi-Cheng Univ S Florida Comp Sci & Engn Tampa FL 33620 USA

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU's global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X).

关键词： query processing Graphics processing units spatial databases Indexing Parallel processing Computational modeling spatial indexes spatial query processing massively parallel algorithms GPU computing

来源：评论

学校读者我要写书评

暂无评论

GISQAF: MapReduce guided spatial query processing and analytics system

引用

SOFTWARE-PRACTICE & EXPERIENCE 2016年第10期46卷 1329-1349页

作者： Al-Naami, Khaled Mohammed Seker, Sadi Evren Khan, Latifur Univ Texas Dallas Dept Comp Sci Dallas TX USA Istanbul Medeniyet Univ Dept Business Istanbul Turkey

The Global Database of Event, Language, and Tone (GDELT) is the only global political georeferenced event dataset with more than 250 million observations covering all countries in the world since January 1, 1979. TABARI and CAMEO are the tools that are used to collect and code events from all international news coverage. To query such big geospatial data, traditional RDBMS can no longer be used, and the need for parallel distributed solutions has become a necessity. MapReduce paradigm has proven to be a scalable platform to process and analyze Big Data in the cloud. Hadoop, as an implementation of MapReduce, is an open-source application that has been widely used and accepted in academia and industry. However, when dealing with spatial Data, Hadoop is not equipped well and does not perform efficiently. spatialHadoop is an extension of Hadoop with the support of spatial data. In this paper, we present Geographic Information System query and Analytics Framework (GISQAF), which has been built on top of spatialHadoop. GISQAF focuses on two parts: query processing and data analytics. For the query processing part, we show how this solution outperforms Hadoop query processing by orders of magnitude when applying queries on the GDELT dataset with a size of 60 GB. We show the results for various types of queries. For the data analytics part, we present an approach for finding spatial co-occurring events. We show how GISQAF is suitable and efficient to handle data analytics techniques. Copyright (c) 2015 John Wiley & Sons, Ltd.

关键词： big data MapReduce Hadoop spatial query processing data analytics spatial co-occurring events

来源：评论

学校读者我要写书评

暂无评论

AT-GIS: Highly Parallel spatial query processing with Associative Transducers 16

AT-GIS: Highly Parallel Spatial Query Processing with Associ...

引用

ACM SIGMOD International Conference on Management of Data

作者： Ogden, Peter Thomas, David Pietzuch, Peter Imperial Coll London London England

ISBN: (纸本)9781450335317

Users in many domains, including urban planning, transportation, and environmental science want to execute analytical queries over continuously updated spatial datasets. Current solutions for large-scale spatial query processing either rely on extensions to RDBMS, which entails expensive loading and indexing phases when the data changes, or distributed map/reduce frameworks, running on resource-hungry compute clusters. Both solutions struggle with the sequential bottleneck of parsing complex, hierarchical spatial data formats, which frequently dominates query execution time. Our goal is to fully exploit the parallelism offered by modern multi core CPUs for parsing and query execution, thus providing the performance of a cluster with the resources of a single machine. We describe AT-GIS, a highly-parallel spatial query processing system that scales linearly to a large number of CPU cores. AT-GIS integrates the parsing and querying of spatial data using a new computational abstraction called associative transducers (ATs). ATs can form a single data-parallel pipeline for computation without requiring the spatial input data to be split into logically independent blocks. Using ATs, AT-GIS can execute, in parallel, spatial query operators on the raw input data in multiple formats, without any pre-processing. On a single 64-core machine, AT-GIS provides 3 x the performance of an 8-node Hadoop cluster with 192 cores for containment queries, and 10x for aggregation queries.

关键词： JSON XML spatial query processing NODB parallel automata multi-core CPUs

来源：评论

学校读者我要写书评

暂无评论

Optimizing the spatial query processing with A Proxy-Based Approach 6

Optimizing the Spatial Query Processing with A Proxy-Based A...

引用

6th International Conference on Advanced Computing (ICoAC)

作者： Geetha, K. Kannan, A. Anna Univ Dept Informat Sci & Technol Coll Engn Madras 600025 Tamil Nadu India

ISBN: (纸本)9781479981595

In recent years, processing spatial queries fastly is a major challenge in mobile environments. Introduction of a proxy for spatial query processing reduces the number of queries submitted by the mobile clients to provide the relevant results. Hence, proxy based approach is prefered to server based approach. This is done to the reduction in waiting time of the query retrieval by proxy. Morover, it reduces the server load in mobile environments. Continuous Nearest Neighbor query processing increases the server load done to the number of consecutive queries submitted by the mobile client who tries to get the desired results. The mutual support between the results of the nearest neighbor queries and window queries are used to enhance the performance. Caching a number of queries in the cache leads to performance degradation. This is overcome in this work by using a cache replacement technique, and hence this system improves the performance of the spatial query processing.

关键词： Mobile environments spatial query processing spatial database

来源：评论

学校读者我要写书评

暂无评论

ParSCL: A Parallel and Distributed Framework to Process All Nearest Neighbor Queries on a Road Network

引用

IEEE ACCESS 2023年 11卷 94043-94056页

作者： Bhandari, Aavash Hamandawana, Prince Attique, Muhammad Cho, Hyung-Ju Chung, Tae-Sun Ajou Univ Dept Artificial Intelligence Suwon 16499 South Korea Sejong Univ Dept Software Seoul 05006 South Korea Kyungpook Natl Univ Dept Software Sangju 37224 South Korea

The proliferation of current and next-generation mobile and sensing devices has increased at an alarming rate. With these state-of-the-art devices, the global positioning system (GPS) has made remote sensing and location tracking more viable. One such query is the All Nearest Neighbor (ANN) query, which extracts and returns all data objects that are in close vicinity to all query objects. An ANN is a combination of k-nearest neighbors (kNN), and join queries. Hence, ANN has useful for applications in different domains such as transportation optimization, locating safe zones, and ride-sharing. An example of its applications is, "find the nearest gas station for each car parking lot". Because these applications are responsible for generating a massive number of query requests, a large amount of computation is required to return these query requests. As a single machine cannot meet this demand in this study, we propose a distributed query processing framework to process ANN queries using the Apache Spark framework. In an empirical study, our proposed framework achieved superior query efficiency and scalability compared to other methods and design alternatives.

关键词： All nearest neighbor queries distributed and parallel processing spatial query processing

来源：评论

学校读者我要写书评

暂无评论

Towards Pareto-optimality with Multi-level Bi-objective Routing: A Summary of Results 17

Towards Pareto-optimality with Multi-level Bi-objective Rout...

引用

17th International Workshop on Computational Transportation Science

作者： Yang, Mingzhou Zeng, Ruolei Sharma, Arun Sawamura, Shunichi Northrop, William F. Shekhar, Shashi Univ Minnesota Minneapolis MN 55455 USA

ISBN: (纸本)9798400711510

Given an origin, a destination, and a directed graph in which each edge is associated with a pair of non-negative costs, the bi-objective routing problem aims to find the set of all Pareto-optimal paths. This problem is societally important due to several applications, such as route finding that considers both vehicle travel time and energy consumption. The problem is challenging due to the potentially large number of candidate Pareto-optimal paths to be enumerated during the search, making existing compute-on-demand methods inefficient due to their high time complexity. One way forward is the introduction of precomputation algorithms. However, the large size of the Pareto-optimal set makes it infeasible to precompute and store all-pair solutions. In addition, generalizing traditional single-objective hierarchical algorithms to bi-objective cases is non-trivial because of the non-comparability of candidate paths and the need to accommodate multiple Pareto-optimal paths for each node pair. To overcome these limitations, we propose Multi-Level Bi-Objective Routing (MBOR) algorithms using three novel ideas: boundary multigraph representation, Pareto frontier encoding, and two-dimensional cost-interval based pruning. Computational experiments using real road network data demonstrate that the proposed methods significantly outperform baseline methods in terms of online runtime and precomputation time.

关键词： Bi-objective routing Pareto optimality spatial query processing spatial algorithms

来源：评论

学校读者我要写书评

暂无评论

SIMD-ified R-tree query processing and Optimization 23

SIMD-ified R-tree Query Processing and Optimization

引用

31st ACM SIGspatial International Conference on Advances in Geographic Information Systems (ACM SIGspatial GIS)

作者： Rayhan, Yeasir Aref, Walid G. Purdue Univ W Lafayette IN 47907 USA

ISBN: (纸本)9798400701689

The introduction of Single Instruction Multiple Data (SIMD) instructions in mainstream CPUs has enabled modern database engines to leverage data parallelism by performing more computation with a single instruction, resulting in a reduced number of instructions required to execute a query as well as the elimination of conditional branches. Though SIMD in the context of traditional database engines has been studied extensively, it has been overlooked in the context of spatial databases. In this paper, we investigate how spatial database engines can benefit from SIMD vectorization in the context of an R-tree spatial index. We present vectorized versions of the spatial range select, and spatial join operations over a vectorized R-tree index. For each of the operations, we investigate two storage layouts for an R-tree node to leverage SIMD instructions. We design vectorized algorithms for each of the spatial operations given each of the two data layouts. We show that the introduction of SIMD can improve the latency of the spatial query operators up to 9x. We introduce several optimizations over the vectorized implementation of these query operators, and study their effectiveness in query performance and various hardware performance counters under different scenarios.

关键词： Single Instruction Multiple Data (SIMD) spatial query processing R-tree query Optimization

来源：评论

学校读者我要写书评

暂无评论

Algorithms for processing the group K nearest-neighbor query on distributed frameworks

引用

DISTRIBUTED AND PARALLEL DATABASES 2021年第3期39卷 733-784页

作者： Moutafis, Panagiotis Garcia-Garcia, Francisco Mavrommatis, George Vassilakopoulos, Michael Corral, Antonio Iribarne, Luis Univ Thessaly Dept Elect & Comp Engn Data Struct & Engn Lab Volos Greece Univ Almeria Dept Informat Almeria Spain

Given two datasets of points (called query and Training), the Group (K) Nearest-Neighbor (GKNN) query retrieves (K) points of the Training with the smallest sum of distances to every point of the query. This spatial query has been studied during the recent years and several performance improving techniques and pruning heuristics have been proposed. In previous work, we presented the first MapReduce algorithm, consisting of alternating local and parallel phases, which can be used to effectively process the GKNN query when the query fits in memory, while the Training one belongs to the Big Data category. In this paper, we present a significantly improved algorithm that incorporates a new high-performance refining method, a fast way to calculate distance sums for pruning purposes and several other minor coding and algorithmic improvements. Moreover, we transform this algorithm (which has been implemented in the Hadoop framework) to spatialHadoop (a popular distributed framework that is dedicated to spatial processing), using a novel two-level partitioning method. Using real world and synthetic datasets, we also present a thorough experimental study of the Hadoop and spatialHadoop versions of the algorithm, including a backstage analysis of the algorithm's performance, using metrics that highlight its internal functioning. Finally, we present an experimental comparison of the Hadoop, the spatialHadoop versions and the version of our previous work, showing that the improved versions are the big winners, with the spatialHadoop one being faster than its Hadoop counterpart.

关键词： spatial query processing Group nearest-neighbor query MapReduce algorithms Hadoop spatialHadoop

来源：评论

学校读者我要写书评

暂无评论

Finding Logic Bugs in spatial Database Engines via Affine Equivalent Inputs

引用

Proceedings of the ACM on Management of Data 2024年第6期2卷 1-26页

作者： Wenjing Deng Qiuyang Mang Chengyu Zhang Manuel Rigger East China Normal University Shanghai China The Chinese University of Hong Kong Shenzhen Shenzhen China ETH Zurich Zurich Switzerland National University of Singapore Singapore Singapore

spatial Database Management Systems (SDBMSs) aim to store, manipulate, and retrieve spatial data. SDBMSs are employed in various modern applications, such as geographic information systems, computer-aided design tools, and location-based services. However, the presence of logic bugs in SDBMSs can lead to incorrect results, substantially undermining the reliability of these applications. Detecting logic bugs in SDBMSs is challenging due to the lack of ground truth for identifying incorrect results. In this paper, we propose an automated geometry-aware generator to generate high-quality SQL statements for SDBMSs and a novel concept named Affine Equivalent Inputs (AEI) to validate the results of SDBMSs. We implemented them as a tool named Spatter (spatial DBMS Tester) for finding logic bugs in four popular SDBMSs: PostGIS, DuckDB spatial, MySQL, and SQL Server. Our testing campaign detected 34 previously unknown and unique bugs in these SDBMSs, of which 30 have been confirmed, and 18 have already been fixed. Our testing efforts have been well appreciated by the developers. Experimental results demonstrate that the geometry-aware generator significantly outperforms a naive random-shape generator in detecting unique bugs, and AEI can identify 14 logic bugs in SDBMSs that were totally overlooked by previous methodologies.

关键词： logic bug spatial query processing

来源：评论

学校读者我要写书评

暂无评论

Navigating the Maps: Euclidean vs. Road Network Distances in spatial Queries

引用

ALGORITHMS 2024年第1期17卷 29页

作者： Tatit, Pornrawee Adhinugraha, Kiki Taniar, David Monash Univ Fac Informat Technol Melbourne Vic 3800 Australia La Trobe Univ Dept Comp Sci & Informat Technol Melbourne Vic 3086 Australia

Using spatial data in mobile applications has grown significantly, thereby empowering users to explore locations, navigate unfamiliar areas, find transportation routes, employ geomarketing strategies, and model environmental factors. spatial databases are pivotal in efficiently storing, retrieving, and manipulating spatial data to fulfill users' needs. Two fundamental spatial query types, k-nearest neighbors (kNN) and range search, enable users to access specific points of interest (POIs) based on their location, which are measured by actual road distance. However, retrieving the nearest POIs using actual road distance can be computationally intensive due to the need to find the shortest distance. Using straight-line measurements could expedite the process but might compromise accuracy. Consequently, this study aims to evaluate the accuracy of the Euclidean distance method in POIs retrieval by comparing it with the road network distance method. The primary focus is determining whether the trade-off between computational time and accuracy is justified, thus employing the Open Source Routing Machine (OSRM) for distance extraction. The assessment encompasses diverse scenarios and analyses factors influencing the accuracy of the Euclidean distance method. The methodology employs a quantitative approach, thereby categorizing query points based on density and analyzing them using kNN and range query methods. Accuracy in the Euclidean distance method is evaluated against the road network distance method. The results demonstrate peak accuracy for kNN queries at k=1, thus exceeding 85% across classes but declining as k increases. Range queries show varied accuracy based on POI density, with higher-density classes exhibiting earlier accuracy increases. Notably, datasets with fewer POIs exhibit unexpectedly higher accuracy, thereby providing valuable insights into spatial query processing.

关键词： spatial query processing open street map (OSM) map navigation GIS spatial data location processing point of interest (POI)

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：