Paper Info
Title
A new indexing method with high storage utilization and retrieval efficiency for large spatial databases
Abstract
Storing and querying high-dimensional data are important problems in designing an information retrieval system. Two crucial issues, time and space efficiencies, must be considered when evaluating the performance of such a system. The KDB-tree and its variants have been reported to have good performance by using them as the index structure for retrieving multidimensional data. However, they all suffer from low storage utilization problem caused by imperfect ''splitting policies.'' Unnecessary splits increase the size of the index structure and deteriorate the performance of the system. In this paper, a new data insertion algorithm with a better splitting policy was proposed, which arranges data entries in the leaf nodes as many as possible. Our new index scheme can increase the storage utilization up to nearly 100% and reduce the index size to a smaller scale. As a result, both time and space efficiencies are significantly improved. Analytical and experimental results show that our indexing method outperforms the traditional KDB-tree and its variants.
Year
DOI
Venue
2007
10.1016/j.infsof.2006.09.005
Information & Software Technology
Keywords
Field
DocType
retrieval efficiency,space efficiency,querying high-dimensional data,data entry,new indexing method,index structure,new data,high storage utilization,large spatial databases,splitting policy,new index scheme,multidimensional data,good performance,spatial database,index size,storage utilization,kdb -trees,high dimensional data,indexation,information retrieval system
Data mining,Imperfect,Computer science,Search engine indexing,Spatial database,Database
Journal
Volume
Issue
ISSN
49
8
Information and Software Technology
Citations 
PageRank 
References 
2
0.40
11
Authors
3
Name
Order
Citations
PageRank
Hung-Yi Lin1398.74
Po-Whei Huang230720.59
Kuang-Hua Hsu331.14