eBay Inc.
COMPACT SPARSE COLUMN GROUPS

Abstract:

Methods and systems for improving memory utilization and access speed of database indexes are disclosed. A representation of attributes of items listed on a network-based publication system is identified. The representation includes a plurality of lists of the attributes as a sequence of serialized attributes, each of which stores an attribute identifier (ID) and data corresponding to the attribute identifier. A compact or compressed structure is used to represent the attribute IDs. This representation allows a reader application to quickly determine whether an attribute ID is present in the lists or not. Directly-addressable variable-length codes (DACs) are used, in an unconventional manner, to represent the data. By representing the data in this way, the index takes up less memory for certain types of data and the reader application is able to gain faster access to the index.