A scalable approach for LRT computation in GPGPU environments

Linsey Xiaolin Pang, Sanjay Chawla, Bernhard Scholz, Georgina Wilcox

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations


In this paper we propose new algorithmic techniques for massively data parallel computation of the Likelihood Ratio Test (LRT) on a large spatial data grid. LRT is the state-of-the-art method for identifying hotspots or anomalous regions in spatially referenced data. LRT is highly adaptable permitting the use of a large class of statistical distributions to model the data. However, standard sequential implementations of LRT may take several days on modern machines to identify anomalous regions even for moderately sized spatial grids. This work claims three novel contributions. First, we devise a dynamic program with a pre-processing step of O(n2) that allows us to compute the statistic for any given region in O(1), where n is the length of the grid. Second, we propose a scheme to accelerate the likelihood computation of a complement region using a bounding technique. Third, we provide a parallelization strategy for the LRT computation on GPGPUs. In concert all three contributions result in a speed up of nearly four hundred times reducing the LRT computation time of large spatial grids from several days to minutes.

Original languageEnglish
Title of host publicationWeb Technologies and Applications - 15th Asia-Pacific Web Conference, APWeb 2013, Proceedings
Number of pages14
StatePublished - 2013
Externally publishedYes
Event15th Asia-Pacific Web Conference on Web Technologies and Applications, APWeb 2013 - Sydney, NSW, Australia
Duration: Apr 4 2013Apr 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7808 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Asia-Pacific Web Conference on Web Technologies and Applications, APWeb 2013
CitySydney, NSW


  • 1EXP
  • GPGPUs
  • LRT
  • Spatial outlier
  • upper-bounding


Dive into the research topics of 'A scalable approach for LRT computation in GPGPU environments'. Together they form a unique fingerprint.

Cite this