 |
|
|
Fast High-Dimensional Data Search in Incomplete Databases |
Full Paper (PDF)
|
We propose and evaluate two indexing schemes for improving the efficiency of data retrieval in high-dimensional databases that are incomplete.
These schemes are novel in that the search keys may contain missing attribute values.
The first is a multi-dimensional index structure, called the Bitstring-augmented R-tree (BR-tree), whereas the second comprises a family of multipleone-dimensional one-attribute (MOSAIC) indexes.
Our results show that both schemes can be superior over exhaustive search.
Experimental results suggest that BR- trees have lower update and storage costs and are able to support range queries more efficiently under most circumstances, when compared to the MOSAIC indexing scheme.
However, contrary to conventional wisdom, the MOSAIC structure outperformsthe BR-tree in retrieval time for point queries, as well as in range queries over incomplete databases for dimension-unrestricted data distributions.
|
References, where available, link to the DBLP on the World Wide Web.
[1]...
[2]Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331[3]Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39[4]...
[5]Tolga Bozkaya, Z. Meral Özsoyoglu:
Distance-Based Indexing for High-Dimensional Metric Spaces.
SIGMOD Conference 1997: 357-368[6]Chee Yong Chan, Beng Chin Ooi, Hongjun Lu:
Extensible Buffer Management of Indexes.
VLDB 1992: 444-454[7]Curtis E. Dyreson:
Information Retrieval from an Incomplete Data Cube.
VLDB 1996: 532-543[8]Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
JIIS 3(3/4): 231-262(1994)[9]...
[10]G. H. Gessert:
Four Valued Logic for Relational Database Systems.
SIGMOD Record 19(1): 29-35(1990)[11]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[12]Norio Katayama, Shin'ichi Satoh:
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.
SIGMOD Conference 1997: 369-380[13]Alon Y. Levy:
Obtaining Complete Answers from Incomplete Databases.
VLDB 1996: 402-412[14]King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB Journal 3(4): 517-542(1994)[15]Rajiv Mehrotra, James E. Gary:
Feature-Based Retrieval of Similar Shapes.
ICDE 1993: 108-115[16]C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng:
Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques.
EDBT 1990: 29-43[17]Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
TODS 9(1): 38-71(1984)[18]Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell:
Spatial indexing in binary decomposition and spatial bounding.
IS 16(2): 211-237(1991)[19]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518[20]...
|
@inproceedings{DBLP:conf/vldb/OoiGT98,
author = {Beng Chin Ooi and
Cheng Hian Goh and
Kian-Lee Tan},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {Fast High-Dimensional Data Search in Incomplete Databases},
booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
Large Data Bases, August 24-27, 1998, New York City, New York,
USA},
publisher = {Morgan Kaufmann},
year = {1998},
isbn = {1-55860-566-5},
pages = {357-367},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
