In-memory grid files on graphics processors

ABSTRACT

Recently, graphics processing units, or GPUs, have become a viable alternative as commodity, parallel hardware for general-purpose computing, due to their massive data-parallelism, high memory bandwidth, and improved general-purpose programming interface. In this paper, we explore the use of GPU on the grid file, a traditional multidimensional access method. Considering the hardware characteristics of GPUs, we design a massively multi-threaded GPU-based grid file for static, memory-resident multidimensional point data. Moreover, we propose a hierarchical grid file variant to handle data skews efficiently. Our implementations on the NVIDIA G80 GTX graphics card are able to achieve two to eight times' higher performance than their CPU counterparts on a single PC.

REFERENCES

• 1: NVIDIA CUDA (Compute Unified Device Architecture), http://developer.nvidia.com/object/cuda.html.
• 2: Nagender Bandi , Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration in commercial databases: a case study of spatial operations, Proceedings of the Thirtieth international conference on Very large data bases, p.1021-1032, August 31-September 03, 2004, Toronto, Canada
• 3: Henk M. Blanken , Alle IJbema , Paul Meek , Bert van den Akker, The Generalized Grid File: Description and Performance Aspects, Proceedings of the Sixth International Conference on Data Engineering, p.380-388, February 05-09, 1990
• 4: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 5: Finkel, R. and Bentley, J. L., Quad trees: A data structure for retrieval of composite keys. Acta Informatica 4(1), 1--9. 1974.
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 8: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007594]
• 9: Naga K. Govindaraju , Nikunj Raghuvanshi , Dinesh Manocha, Fast and approximate stream mining of quantiles and frequencies using graphics processors, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066227]
• 10: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: He, B., Yang, K., Fang, R., Lu, M., Govindaraju, N., Luo, Q. and Sander, P., Relational Joins on Graphics Processors. Technical report, Department of Computer Science and Engineering, HKUST, March 2007.
• 12: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 13: Hans-Peter Kriegel , Bernhard Seeger, Multidimensional order preserving linear hashing with partial expansions, Proceedings on International conference on database theory, p.203-220, December 1986, Rome, Italy
• 14: Hans-Peter Kriegel , Bernhard Seeger, Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions, Proceedings of the Third International Conference on Data Engineering, p.10-17, February 03-05, 1987
• 15: Jianzhong Li , Doron Rotem , Jaideep Srivastava, Algorithms for loading parallel grid files, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.347-356, May 25-28, 1993, Washington, D.C., United States
• 16: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 17: S. Mohammed , B. Srinivasan , M. Bozyigit , Phu Dung Le, Novel parallel join algorithms for grid files, Proceedings of the Third International Conference on High-Performance Computing (HiPC '96), p.144, December 19-22, 1996
• 18: M. Aris Ouksel, The interpolation-based grid file, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.20-27, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325408]
• 19: Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., A. E. Lefohn and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, Volume 26, 2007.
• 20: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 21: Mireille Regnier, Analysis of grid file algorithms, BIT, v.25 n.2, p.335-358, 1985 [doi>10.1007/BF01934379]
• 22: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 23: Sagan, H., Space-Filling Curves. Berlin/Heidelberg/New York: Springer-Verlag, 1994.
• 24: Bernhard Seeger , Hans-Peter Kriegel, The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.590-601, August 13-16, 1990
• 25: Hans-Werner Six , Peter Widmayer, Spatial Searching in Geometric Databases, Proceedings of the Fourth International Conference on Data Engineering, p.496-503, February 01-05, 1988
• 26: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration for spatial selections and joins, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872813]
• 27: Tamminen, M. The extendible cell method for closest point problems. BIT 22, 27--41. 1982.
• 28: Whang, K.-Y. and Krishnamurthy, R., Multilevel grid files. Yorktown Heights, NY: IBM Research Laboratory. 1985.