Data indexing using bit vectors

Details Data indexing using bit vectors Data indexing using bit vectors

2005-04-12

2005-04-12

Wassum, Luke S (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06879976

ABSTRACT:
The present invention provides for indexing of occurrences of a value in at least one data record using a bit vector wherein a bit vector is associated with the value and a bit of the bit vector representation is associated with the at least one data record, a determination is made whether the value exists in the at least one data record, a bit value is assigned to the bit in the bit vector representation based on the outcome of the determination. Further, operations may be performed on multiple bit vectors indexing data records and values used in the data records to determine the existence of combinations and associations between the corresponding values and the indexed data records.

REFERENCES:
patent: 4817036 (1989-03-01), Millett et al.
patent: 5649181 (1997-07-01), French et al.
patent: 5706495 (1998-01-01), Chadha et al.
patent: 5761652 (1998-06-01), Wu et al.
patent: 5799184 (1998-08-01), Fulton et al.
patent: 5848408 (1998-12-01), Jakobsson et al.
patent: 5852821 (1998-12-01), Chen et al.
patent: 5884307 (1999-03-01), Depledge et al.
patent: 5899988 (1999-05-01), Depledge et al.
patent: 5903888 (1999-05-01), Cohen et al.
patent: 5907297 (1999-05-01), Cohen et al.
patent: 5924088 (1999-07-01), Jakobsson et al.
patent: 5963935 (1999-10-01), Ozbutun et al.
patent: 6067540 (2000-05-01), Ozbutun et al.
patent: 6070164 (2000-05-01), Vagnozzi
patent: 6081800 (2000-06-01), Ozbutun et al.
patent: 6141656 (2000-10-01), Ozbutun et al.
patent: 6154741 (2000-11-01), Feldman
patent: 6285994 (2001-09-01), Bui et al.
patent: 6405187 (2002-06-01), Egan et al.
patent: 6658405 (2003-12-01), Ozbutun
patent: 6804664 (2004-10-01), Hartman et al.
O'Neil, P. and G. Graefe “Multi-Table Joins Through Bitmapped Join Indices”, ACM SIGMOD Record, vol. 24, No. 3, pp. 8-11, Sep. 1995.*
Gupta, H., V. Harinarayan, A. Rajaraman and J.D. Ullman “Index Selection for OLAP”, Proceedings of the 13th International Conference on Data Engineering, pp. 208-219, Apr. 7-11, 1997.*
O'Neil, P. and D. Quass “Improved Query Performance with Variant Indexes”, Proceedings of the ACM SIGMOD Conference o Management of Data, pp. 38-49, Jun. 1997.*
Wu, M-C, and A.P. Buchmann “Encoded Bitmap Indexing for Data Warehouses”, Proceedings of the 14th International Conference on Data Engineering (ICDE), pp. 220-230, Feb. 1998.*
Chan, C-Y and Y.E. Ioannidis “Bitmap Index Design and Evaluation”, Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 355-366, Jun. 1-4, 1998.*
Datta, A. and I. Viguier “The DataIndex: A Structure for Smaller, Faster Data Warehouses”, The DATA BASE for Advances in Information Systems, vol. 29, No. 4, pp. 33-44, Fall 1998.*
Wikiepedia “Logical Conjunction”, definition, downloaded from en.wikipedia.org on Apr. 6, 2004.*
Wikipedia “Bitwise Operation”, definition, downloaded from en.wikipedia.org on Apr. 6, 2004.*
Schildt, H. “C: The Complete Reference, Second Edition”, Berkeley:McGraw-Hill, pp. 47-54, 1990.*
Babb, E. “Implementing a Relational Database by Means of Specialized Hardware”, ACM Transactions on Database Systems, vol. 4, No. 1, pp. 1-29, Mar. 1979.*
Schneider, D.A. and D.J. DeWitt “A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocess Environment”, Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 110-121, Jun. 1989.*
Chaudhuri, S. and D. Umeshwar “An Overview of Data Warehousing and OLAP Technology”, AMC SIGMOD Record, vol. 26, No. 1, Mar. 1997.*
Perrizo, W., Z. Zhang and S. Krebsbach “A Query Processing Method for Data Warehouses Which Contain Multimedia”, Proceedings of the ACM Symposium on Applied Computing, pp. 323-327, Apr. 1997.

Affiliated with

Also associated with

Rating

Data indexing using bit vectors does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data indexing using bit vectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data indexing using bit vectors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3386084