Fast High-Dimensional Data Search in Incomplete Databases
作者： Beng Chin Ooi , Kian-Lee Tan , Cheng Hian Goh
DOI:
关键词:
摘要: We propose and evaluate two indexing schemes for improving the efficiency of data retrieval in high-dimensional databases that are incomplete. These novel search keys may contain missing attribute values. The first is a multi-dimensional index structure, called Bitstring-augmented R-tree (BR-tree), whereas second comprises family multiple one-dimensional one-attribute (MOSAIC) indexes. Our results show both can be superior over exhaustive search. Experimental suggest BRtrees have lower update storage costs able to support range queries more efficiently under most circumstances, when compared MOSAIC scheme. However, contrary conventional wisdom, structure outperforms BR-tree time point queries, as well incomplete dimension-unrestricted distributions.
sigmod.org 参考文章(19)
C. Mohan, Don Haderle, Yun Wang, Josephine Cheng, Single table access using multiple indexes: optimization, execution, and concurrency control techniques extending database technology. ,vol. 416, pp. 29- 43 ,(1990) , 10.1007/BFB0022162
Alon Y. Levy, Obtaining Complete Answers from Incomplete Databases very large data bases. pp. 402- 412 ,(1996)
Beng Chin Ooi, Chee Yong Chan, Hongjun Lu, Extensible Buffer Management of Indexes very large data bases. pp. 444- 454 ,(1992)
Curtis E. Dyreson, Information Retrieval from an Incomplete Data Cube very large data bases. pp. 532- 543 ,(1996)
Ron Sacks-Davis, Elisa Bertino, Justin Zobel, Beng Chin Ooi, Kian-Lee Tan, Boris Shidlovsky, Daniele Andronico, Indexing Techniques for Advanced Database Systems ,(1997)
Tolga Bozkaya, Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces international conference on management of data. ,vol. 26, pp. 357- 368 ,(1997) , 10.1145/253260.253345
C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack, D. Petkovic, W. Equitz, Efficient and effective querying by image content intelligent information systems. ,vol. 3, pp. 231- 262 ,(1994) , 10.1007/BF00962238
Beng Chin Ooi, Ron Sacks-Davis, Ken J McDonell, Spatial indexing in binary decomposition and spatial bounding Information Systems. ,vol. 16, pp. 211- 237 ,(1991) , 10.1016/0306-4379(91)90016-3
King-Ip Lin, H. V. Jagadish, Christos Faloutsos, The TV-tree: an index structure for high-dimensional data very large data bases. ,vol. 3, pp. 517- 542 ,(1994) , 10.1007/BF01231606
S Altschula, Warren Gisha, Webb Millerb, E Meyersc, D Lipmana, None, Basic Local Alignment Search Tool Journal of Molecular Biology. ,vol. 215, pp. 403- 410 ,(1990) , 10.1016/S0022-2836(05)80360-2