A Range Query Parallel Algorithm in High-Dimensional Space

Abstract:

The performance of the spatial range query algorithms based on Brute-Force method, R-tree, VA-file and NB-tree suffers greatly in high-dimensional space. So the reduction of the dimensionality is the key to the spatial range query in high-dimensional space. The paper uses the parallel technique to present a spatial range query parallel algorithm in high-dimensional space. The algorithm transforms d-dimensional spatial range query to the linear space on d slave node processors. The d slave node processors run parallel. The master node processor only need calculate the union of d results which d slave node processors return. The experimental results indicate that its performance is better than that of the spatial range query algorithms based on Brute-Force method, R-tree, VA-file, NB-tree.

• Periodical: Applied Mechanics and Materials (Volumes 263-266)
• Pages: 2308-2313
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.263-266.2308
• Online since: December 2012
• Authors: Hong Bo Xu, Nian Min Yao
• Keywords: High-Dimensional Space, Node Processors, Parallel Computation, Reduction of Dimensionality, Spatial Range Query Algorithm

References

[1] Zhongxiao Hao: Spatio Temporal Database Query and Reasoning (Science Press, Beijing 2010).

[2] Beyer K, Goldstein J, Ramakrishnan R: When is "nearest neighbor" meaningful, edited by the 7th International Conference on Database Theory (1999), p.217.

DOI: 10.1007/3-540-49257-7_15

[3] Weber R, Blott S: An Approximation-based data structure for similarity search. ESPRIT Project HERMES NO. 9141 (1997).

[4] Manuel J F, Joaquim A J: Indexing high-dimensional data for content-based retrieval in large databases, edited by the 8th International Conference on Database Systems for Advanced Applications (2003), p.267.

DOI: 10.1109/dasfaa.2003.1192391

[5] CHEN Guo-Liang, SUN Guang-Zhong, XU Yun, LU Min: Methodology of Research on Parallel Algorithms, submitted to Chinese Journal of Computers, Vol. 31(9) (2008), p.1493.

[6] HUANG Hai, HOU Ying, ZHU Sheng-ping: A Multi-dimensional Vector Parallel Search Algorithms, submitted to Microelectronics & Computer, Vol. 27(8) (2010), pp.17-19.