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

Efficient processing of optimal meeting point queries in Euclidean space and road networks

KNOWLEDGE AND INFORMATION SYSTEMS 2015年第2期42卷 319-351页

作者： Yan, Da Zhao, Zhou Ng, Wilfred Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China

Finding an optimal meeting point (OMP) for a group of people (or a set of objects) at different locations is an important problem in spatial query processing. There are many real-life applications related to this problem, such as determining the location of a conference venue, deciding the pick-up location of a tourist bus, and planing tactics of artificial intelligence in real-time strategy games. Formally, given a set of query points in a spatial setting , an OMP query fetches the point that minimizes a cost function defined over the distances from to all points in . Since there are infinitely many locations in a given space setting, it is infeasible to examine all of them to find the OMP, and thus, the problem is challenging. In this paper, we study OMP queries in the following two spatial settings which are common in real-life applications: Euclidean space and road networks. In the setting of Euclidean space, we propose a general framework for answering all OMP query variants and also identify the best algorithms for particular types of OMP queries in the literature. In the setting of road networks, we study how to access only part of the road network and examine part of the candidates. Specifically, we explore two pruning techniques, namely Euclidean distance bound and threshold algorithm, which help improve the efficiency of OMP query processing. Extensive experiments are conducted to demonstrate the efficiency of our proposed approaches on both real and synthetic datasets.

关键词： Optimal meeting point spatial query processing Road network Threshold algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Nearest Surrounder Queries

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2010年第10期22卷 1444-1458页

作者： Lee, Ken C. K. Lee, Wang-Chien Leong, Hong Va Penn State Univ Dept Comp Sci & Engn University Pk PA 16803 USA Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China

In this paper, we present a new type of spatial queries called Nearest Surrounder (NS) queries. An NS query determines the nearest polygon-shaped spatial objects (referred to as nearest surrounder objects) and their orientations with respect to a query point from an object set. Besides, we derive two NS query variants, namely, multitier NS (m-NS) queries and angle-constrained NS (ANS) queries. An m-NS query searches multiple layers of NS objects for the same range of angles from a query point. An ANS query searches for NS objects within a specified range of angles. To evaluate NS queries and their variants, we explore angle-based and distance-based bound properties of polygons, and devise two efficient algorithms, namely, Sweep and Ripple, based on R-tree. The algorithms access objects in an order according to their orientations and distances with respect to a given query point, respectively. They are efficient as they can finish a search with one index lookup. Besides, they can progressively deliver a query result. Through empirical studies, we evaluate the proposed algorithms and report their performance for both synthetic and real object sets.

关键词： spatial query processing nearest surrounder queries R-tree algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient processing of all-k-nearest-neighbor queries in the MapReduce programming framework

引用

DATA & KNOWLEDGE ENGINEERING 2019年 121卷 42-70页

作者： Moutafis, Panagiotis Mavrommatis, George Vassilakopoulos, Michael Sioutas, Spyros Univ Thessaly Dept Elect & Comp Engn Data Structuring & Engn Lab Volos Greece Univ Patras Dept Comp Engn & Informat Patras Greece

Numerous modern applications, from social networking to astronomy, need efficient answering of queries on spatial data. One such query is the All k Nearest-Neighbor query, or k Nearest-Neighbor Join, that takes as input two datasets and, for each object of the first one, returns the k nearest-neighbors from the second one. It is a combination of the k nearest-neighbor and join queries and is computationally demanding. Especially, when the datasets involved fall in the category of Big Data, a single machine cannot efficiently process it. Only in the last few years, papers proposing solutions for distributed computing environments have appeared in the literature. In this paper, we focus on parallel and distributed algorithms using the Apache Hadoop framework. More specifically, we focus on an algorithm that was recently presented in the literature and propose improvements to tackle three major challenges that distributed processing faces: improvement of load balancing (we implement an adaptive partitioning scheme based on Quadtrees), acceleration of local processing (we prune points during calculations by utilizing plane-sweep processing), and reduction of network traffic (we restructure and reduce the output size of the most demanding phase of computation). Moreover, by using real 2D and 3D datasets, we experimentally study the effect of each improvement and their combinations on performance of this literature algorithm. Experiments show that by carefully addressing the three aforementioned issues, one can achieve significantly better performance. Thereby, we conclude to a new scalable algorithm that adapts to the data distribution and significantly outperforms its predecessor. Moreover, we present an experimental comparison of our algorithm against other well-known MapReduce algorithms for the same query and show that these algorithms are also significantly outperformed.

关键词： spatial query processing Nearest neighbor query Plane sweep Quadtrees MapReduce Apache hadoop

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for bulk-loading xBR⁺-trees

引用

COMPUTER STANDARDS & INTERFACES 2018年 57卷 83-100页

作者： Roumelis, George Vassilakopoulos, Michael Corral, Antonio Manolopoulos, Yannis Aristotle Univ Thessaloniki Dept Informat Thessaloniki Greece Univ Thessaly Dept Elect & Comp Engn Volos Greece Univ Almeria Dept Informat Almeria Spain

A major part of the interface to a database is made up of the queries that can be addressed to this database and answered (processed) in an efficient way, contributing to the quality of the developed software. Efficiently processed spatial queries constitute a fundamental part of the interface to spatial databases due to the wide area of applications that may address such queries, like geographical information systems (GIS), location-based services, computer visualization, automated mapping, facilities management, etc. Another important capability of the interface to a spatial database is to offer the creation of efficient index structures to speed up spatial query processing. The xBR(+)-tree is a balanced disk-resident quadtree-based index structure for point data, which is very efficient for processing such queries. Bulk-loading refers to the process of creating an index from scratch, when the dataset to be indexed is available beforehand, instead of creating the index gradually (and more slowly), when the dataset elements are inserted one-by-one. In this paper, we present an algorithm for bulk-loading xBR(+)-trees for big datasets residing on disk, using a limited amount of main memory. The resulting tree is not only built fast, but exhibits high performance in processing a broad range of spatial queries, where one or two datasets are involved. To justify these characteristics, using real and artificial datasets of various cardinalities, first, we present an experimental comparison of this algorithm vs. a previous version of the same algorithm and STR, a popular algorithm of bulk-loading R-trees, regarding tree creation time and the characteristics of the trees created, and second, we experimentally compare the query efficiency of bulk-loaded xBR(+)-trees vs. bulk-loaded R-trees, regarding I/O and execution time. Thus, this paper contributes to the implementation of spatial database interfaces and the efficient storage organization for big spatial data management

关键词： spatial database interfaces spatial indexes Bulk-loading xBR(+)-trees spatial query processing

来源：评论

学校读者我要写书评

暂无评论

User-Qualified Group Search using Bidirectional Sweep Planes

引用

JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING 2018年第4期9卷 1259-1265页

作者： Jung, Kyoung-Ho Jang, Hong-Jun Chung, Jaehwa Jung, Soon-Young Korea Univ Dept Comp Sci & Engn Seoul South Korea Korea Natl Open Univ Dept Comp Sci Seoul South Korea

In this paper, we propose a nearest user-qualified group (NUG) query that searches a group of objects to obtain a result. In detail, given a dataset P, query q, distance delta, and cardinality k, the NUG query returns the nearest group of objects from q, such that more than k objects within delta distance from the point, called a representative, are in the group. Although the NUG query has large spectrum of applications, an efficient processing algorithm for NUG queries has not been studied so far. Therefore, we propose the plane sweep-based incremental search algorithm and heuristic that stops the plane sweep early to reduce the search space. A performance study is conducted on both synthetic and real datasets and our experimental results show that the proposed algorithm can improve the query performance in a variety of conditions.

关键词： Nearest neighbor query Nearest user-qualified group query spatial query processing

来源：评论

学校读者我要写书评

暂无评论

Efficient tracking of 2D objects with spatiotemporal properties in wireless sensor networks

引用

DISTRIBUTED AND PARALLEL DATABASES 2011年第1-2期29卷 3-30页

作者： Jin, Guang Nittel, Silvia Intelligent Automat Inc Rockville MD 20855 USA Univ Maine Dept Spatial Informat & Engn Orono ME USA

Wireless sensor networks (WSN) are deployed to detect, monitor and track environmental phenomena such as toxic clouds or dense areas of air pollution in an urban environment. Most phenomena are often modeled as 2D objects (e.g., a fire region based on the temperature sensor readings). People model the objects by their properties, and like to know how the properties change over time. This paper presents a distributed algorithm, which uses deformable curves to track the spatiotemporal changes of 2D objects. In order to save the constrained resources in WSN, our distributed algorithm only allows neighboring nodes to exchange messages to maintain the curve structures. In addition, our algorithm can also support tracking of multiple objects. Based on the in-network tracking of deformable 2D curves, we show that many spatiotemporal properties can be extracted by the in-network aggregation. Our experimental results have confirmed that our approach is resource-efficient with regard to the in-network communication and on-board computation.

关键词： Wireless sensor networks spatial query processing Active contour

来源：评论

学校读者我要写书评

暂无评论

Merging R-trees: Efficient strategies for local bulk insertion

引用

GEOINFORMATICA 2002年第1期6卷 7-34页

作者： Chen, L Choubey, R Rundensteiner, EA Worcester Polytech Inst Dept Comp Sci Worcester MA 01609 USA

A lot of recent work has focussed on bulk loading of data into multidimensional index structures in order to efficiently construct such structures for large datasets. In this paper, we address this problem with particular focus, on R-trees-which are an important class of index structures used widely in commercial database systems. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk inserts entire new datasets into an active R-tree. This technique, called STLT (for small-tree-large-tree), considers the new dataset as an R-tree itself (small tree), identifies and prepares a suitable location in the original R-tree (large tree) for insertion, and lastly performs the insert of the small tree into the large tree. Besides,an analytical cost model of STLT, extensive experimental studies both on synthetic and real GIS data sets are also reported. These experiments not only compare STLT against the conventional technique, but also evaluate the suitability and limitations of STLT under different conditions, such as varying buffer sizes, ratio between existing and new data sizes, and skewness of new data with respect to the whole spatial region. We find that STLT does much better (in average, about 65%) than the existing technique for skewed datasets as well for large sizes of both the large tree and the small tree in terms of insertion time, while keeping comparable query tree quality. STLT consistently outperforms the alternate technique in all other circumstances in terms of bulk insertion time, especially, even up to 2,000% for the cases when the area of new data sets covers up to 4% of the global region covered by the existing index tree, however, at the cost of a deteriorating resulting tree quality.

关键词： multidimensional index structures localized datasets bulk loading bulk insertion performance evaluation spatial query processing

来源：评论

学校读者我要写书评

暂无评论

Enabling search services on outsourced private spatial data

引用

VLDB JOURNAL 2010年第3期19卷 363-384页

作者： Yiu, Man Lung Ghinita, Gabriel Jensen, Christian S. Kalnis, Panos Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Aalborg Univ Dept Comp Sci Aalborg Denmark KAUST Univ Div Math & Comp Sci & Engn Thuwal Saudi Arabia

Cloud computing services enable organizations and individuals to outsource the management of their data to a service provider in order to save on hardware investments and reduce maintenance costs. Only authorized users are allowed to access the data. Nobody else, including the service provider, should be able to view the data. For instance, a real-estate company that owns a large database of properties wants to allow its paying customers to query for houses according to location. On the other hand, the untrusted service provider should not be able to learn the property locations and, e.g., selling the information to a competitor. To tackle the problem, we propose to transform the location datasets before uploading them to the service provider. The paper develops a spatial transformation that re-distributes the locations in space, and it also proposes a cryptographic-based transformation. The data owner selects the transformation key and shares it with authorized users. Without the key, it is infeasible to reconstruct the original data points from the transformed points. The proposed transformations present distinct trade-offs between query efficiency and data confidentiality. In addition, we describe attack models for studying the security properties of the transformations. Empirical studies demonstrate that the proposed methods are efficient and applicable in practice.

关键词： Data outsourcing spatial query processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：