Gowanlock et al., 2018 - Google Patents

GPU accelerated self-join for the distance similarity metric

Gowanlock et al., 2018

Document ID: 6599315929678738824
Author: Gowanlock M; Karsin B
Publication year: 2018
Publication venue: 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)

External Links

Cited by

Snippet

The self-join finds all objects in a dataset within a threshold of each other defined by a similarity metric. As such, the self-join is a building block for the field of databases and data mining, and is employed in Big Data applications. In this paper, we advance a GPU-efficient …

Continue reading at arxiv.org (PDF) (other versions)

238000000034 method 0 abstract description 15

Classifications

- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30386—Retrieval requests
- G06F17/30424—Query processing
- G06F17/30533—Other types of queries
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30386—Retrieval requests
- G06F17/30424—Query processing
- G06F17/30477—Query execution
- G06F17/30483—Query execution of query operations
- G06F17/30486—Unary operations; data partitioning operations
- G06F17/30492—Efficient disk access during query execution
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30386—Retrieval requests
- G06F17/30424—Query processing
- G06F17/30442—Query optimisation
- G06F17/30445—Query optimisation for parallel queries
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30312—Storage and indexing structures; Management thereof
- G06F17/30321—Indexing structures
- G06F17/30333—Multidimensional index structures
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30587—Details of specialised database models
- G06F17/30592—Multi-dimensional databases and data warehouses, e.g. MOLAP, ROLAP
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
- G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30575—Replication, distribution or synchronisation of data between databases or within a distributed database; Distributed database system architectures therefor
- G06F17/30584—Details of data partitioning, e.g. horizontal or vertical partitioning
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F17/30705—Clustering or classification
- G06F17/3071—Clustering or classification including class or cluster creation or modification
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
- G06F17/30994—Browsing or visualization
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30861—Retrieval from the Internet, e.g. browsers
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication	Publication Date	Title
Pan et al.	2011	Fast GPU-based locality sensitive hashing for k-nearest neighbor computation
Eltabakh et al.	2013	Eagle-eyed elephant: split-oriented indexing in Hadoop
Bouros et al.	2019	Spatial joins: What's next?
Cha et al.	2002	The GC-tree: a high-dimensional index structure for similarity search in image databases
Tseng et al.	2021	Parallel index-based structural graph clustering and its approximation
US11176631B1 (en)	2021-11-16	GPU-based parallel indexing for concurrent spatial query
Su et al.	2012	Indexing and parallel query processing support for visualizing climate datasets
Gowanlock et al.	2015	Distance threshold similarity searches: Efficient trajectory indexing on the GPU
Tsitsigkos et al.	2021	A Two-layer Partitioning for Non-point Spatial Data.
Li et al.	2024	A survey of multi-dimensional indexes: past and future trends
Gowanlock et al.	2019	GPU-accelerated similarity self-join for multi-dimensional data
Gallet et al.	2022	Leveraging GPU tensor cores for double precision Euclidean distance calculations
Zeng et al.	2022	Sgsi–a scalable gpu-friendly subgraph isomorphism algorithm
Gowanlock et al.	2018	GPU accelerated self-join for the distance similarity metric
Gowanlock et al.	2017	Clustering throughput optimization on the GPU
Gowanlock	2019	Hybrid CPU/GPU clustering in shared memory on the billion point scale
Gowanlock	2019	KNN-joins using a hybrid approach: exploiting CPU/GPU workload characteristics
Böhm et al.	2009	Index-supported similarity join on graphics processors
Donnelly et al.	2020	A coordinate-oblivious index for high-dimensional distance similarity searches on the GPU
Leal et al.	2015	TKSimGPU: A parallel top-K trajectory similarity query processing algorithm for GPGPUs
Roh et al.	2010	Hierarchically organized skew-tolerant histograms for geographic data objects
Tian et al.	2014	An efficient processing of k-dominant skyline query in mapreduce
Levchenko et al.	2018	Spark-parsketch: a massively distributed indexing of time series datasets
Moënne-Loccoz	2005	High-dimensional access methods for efficient similarity queries
Hasan et al.	2006	A parallel implementation scheme of relational tables based on multidimensional extendible array