NDLI: Multi-Way Distance Join Queries in Spatial Databases

Please wait, while we are loading the content...

Multi-Way Distance Join Queries in Spatial Databases

Content Provider	Springer Nature Link
Author	Corral, Antonio Malopoulos, Yannis Theodoridis, Yannis Vassilakopoulos, Michael
Copyright Year	2004
Abstract	Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The “D_distance-value” of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest D_distance-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results.
Starting Page	373
Ending Page	402
Page Count	30
File Format	PDF
ISSN	13846175
Journal	GeoInformatica
Volume Number	8
Issue Number	4
e-ISSN	15737624
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2004-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Science Data Structures, Cryptology and Information Theory Information Storage and Retrieval Multimedia Information Systems
Content Type	Text
Resource Type	Article
Subject	Geography, Planning and Development Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

New plane-sweep algorithms for distance-based join queries in spatial databases

On reverse-k-nearest-neighbor joins

Spatial skyline queries: exact and approximation algorithms

Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases

Data Partitioning for Parallel Spatial Join Processing

Retrieval of Spatial Join Pattern Instances from Sensor Networks

Polyline Spatial Join Evaluation Using Raster Approximation

A comparative study of two approaches for supporting optimal network location queries

Efficient Window Block Retrieval in Quadtree-Based Spatial Databases

Multi-Way Distance Join Queries in Spatial Databases

Similar Documents

New plane-sweep algorithms for distance-based join queries in spatial databases

On reverse-k-nearest-neighbor joins

Spatial skyline queries: exact and approximation algorithms

Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases

Data Partitioning for Parallel Spatial Join Processing

Retrieval of Spatial Join Pattern Instances from Sensor Networks

Polyline Spatial Join Evaluation Using Raster Approximation

A comparative study of two approaches for supporting optimal network location queries

Efficient Window Block Retrieval in Quadtree-Based Spatial Databases

Multi-Way Distance Join Queries in Spatial Databases