title: Approximate Algorithms for Computing Spatial Distance Histograms with Accuracy Guarantees.
abstract: Particle simulation has become an important research tool in many scientific and engineering fields. Data generated by such simulations impose great challenges to database storage and query processing. One of the queries against particle simulation data, the spatial distance histogram (SDH) query, is the building block of many high-level analytics, and requires quadratic time to compute using a straightforward algorithm. Previous work has developed efficient algorithms that compute exact SDHs. While beating the naive solution, such algorithms are still not practical in processing SDH queries against large-scale simulation data. In this paper, we take a different path to tackle this problem by focusing on approximate algorithms with provable error bounds. We first present a solution derived from the aforementioned exact SDH algorithm, and this solution has running time that is unrelated to the system sizeN. We also develop a mathematical model to analyze the mechanism that leads to errors in the basic approximate algorithm. Our model provides insights on how the algorithm can be improved to achieve higher accuracy and efficiency. Such insights give rise to a new approximate algorithm with improved time/accuracy tradeoff. Experimental results confirm our analysis.
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620. vgrupcev@mail.usf.edu.
authors.forename: Vladimir
authors.initials: V
authors.lastname: Grupcev
authors.affiliation: Department of Industrial and Management Systems Engineering, University of South Florida, 4202 E. Fowler Ave., ENB118, Tampa, FL 33620. yyuan@usf.edu.
authors.forename: Yongke
authors.initials: Y
authors.lastname: Yuan
authors.affiliation: Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620. ytu@cse.usf.edu.
authors.forename: Yi-Cheng
authors.initials: YC
authors.lastname: Tu
authors.affiliation: Department of Computer Science, University of Texas at Arlington, 500 UTA Boulevard, Room 640, ERB Buildings, Arlington, TX 76019. jin.huang@mavs.uta.edu.
authors.forename: Jin
authors.initials: J
authors.lastname: Huang
authors.affiliation: Department of Mathematics, Wuhan University of Technology, 122 Luosi Road, Wuhan, Hubei 430070, P.R. China. chensp@whut.edu.cn.
authors.forename: Shaoping
authors.initials: S
authors.lastname: Chen
authors.affiliation: Department of Physics, University of South Florida, 4202 E. Fowler Ave., PHY114, Tampa, FL 33620. pandit@cas.usf.edu.
authors.forename: Sagar
authors.initials: S
authors.lastname: Pandit
authors.affiliation: Department of Industrial and Management Systems Engineering, University of South Florida, 4202 E. Fowler Ave., ENB118, Tampa, FL 33620. mxweng@usf.edu.
authors.forename: Michael
authors.initials: M
authors.lastname: Weng
keywords: Molecular simulation; quadtree; scientific databases; spatial distance histogram