Paper Info
Title
R-tree: A Hardware Implementation
Abstract
R-tree data structures are widely used in spatial databases to store, manage and manipulate spatial information. Because the data volume of such databases is typically very large, the query operation on R-tree data structure has an important impact on the performance of spatial databases. To boost the performance of R-tree search operations, we propose a new parallel R-tree search algorithm, which utilizes an adjacency matrix representation for an R-tree a nd performs the search using binary arithmetic among matrix elements. When the algorithm is implemented in hardware, we demonstrate through our simulation that the run-time complexity of the new algorithm is only bounded by the height of an R- tree. Furthermore, we find that the proposed algorithm in har dware is 30 times faster than its software counterpart in solving an example search problem. In the future, more research will be conducted to adapt the proposed algorithm with divide-conquer paradigm to handle large spatial data sets.
Year
Venue
Keywords
2008
CDES
parallel algorithm,spatial search,hardware implementation.,index terms: r-tree,spatial information,spatial database,spatial data,adjacency matrix,time complexity,indexing terms,search algorithm,data structure
Field
DocType
Citations 
Spatial analysis,Adjacency matrix,Data structure,R-tree,Search algorithm,Computer science,Theoretical computer science,Software,Search problem,Computer hardware,Spatial database
Conference
4
PageRank 
References 
Authors
0.48
10
4
Name
Order
Citations
PageRank
Xiang Xiao1233.92
Tuo Shi251.52
Pranav Vaidya3124.42
Jaehwan John Lee410416.97