Book chapter
Indexing Incomplete Databases
Advances in Database Technology - EDBT 2006, pp.884-901
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2006
DOI: 10.1007/11687238_52
Abstract
Incomplete databases, that is, databases that are missing data, are present in many research domains. It is important to derive techniques to access these databases efficiently. We first show that known indexing techniques for multi-dimensional data search break down in terms of performance when indexed attributes contain missing data. This paper utilizes two popularly employed indexing techniques, bitmaps and quantization, to correctly and efficiently answer queries in the presence of missing data. Query execution and interval evaluation are formalized for the indexing structures based on whether missing data is considered to be a query match or not. The performance of Bitmap indexes and quantization based indexes is evaluated and compared over a variety of analysis parameters for real and synthetic data sets. Insights into the conditions for which to use each technique are provided.
Details
- Title: Subtitle
- Indexing Incomplete Databases
- Creators
- Guadalupe Canahuate - Department of Computer Science and Engineering, The Ohio State University,Michael Gibas - Department of Computer Science and Engineering, The Ohio State University,Hakan Ferhatosmanoglu - Department of Computer Science and Engineering, The Ohio State University,
- Resource Type
- Book chapter
- Publication Details
- Advances in Database Technology - EDBT 2006, pp.884-901
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/11687238_52
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2006
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083891902771
Metrics
8 Record Views