A portion of the disclosure of this patent document contains material, which is subject to copyright protection. This patent document may show and/or describe matter, which is or may become trade dress of the owner. The copyright and trade dress owner has no objection to the facsimile reproduction by any one of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright and trade dress rights whatsoever.
1. Field of the Invention
The present invention relates to database design, database query technologies and content targeting systems.
2. Description of Related Art
Database management systems (DBMSes) typically store and manipulate data in a manner that closely mirrors the users"" view of the data. Users typically think of data as a sequence of records, each logically composed of a fixed number of fields that contain specific content about the entity described by that record. This view is naturally represented by a logical table (or xe2x80x9crelationxe2x80x9d) structure, such as a rectilinear grid, in which the rows represent records and the columns represent fields.
The long-standing existence of record-based tables and their correspondence to a conventional user view, in the absence of generally recognized drawbacks, has led to their nearly universal acceptance as the major underlying internal representation of databases. Yet record-based tables contain key structural weaknesses including high levels of unorderedness and redundancy that have traditionally been regarded as unavoidable. For example, such tables can be sorted or grouped (i.e., the contiguous positioning of identical values) on at most one criterion at a time (based upon column values or some function of either column values or multiple column values). This limitation renders essential database functions, such as querying, on all criteria other than this privileged one awkward and overly resource-intensive.
Database research provides palliatives for these problems, but fails to uncover and address their underlying cause (i.e., the reliance on record-based table structures). For example, the inability to represent a natural, multi-dimensional grouping within the confines of a record-based table structure has led to the creation of index-based data structures. These supplementary structures are inherently and often massively redundant, but they establish groupings and orderings that cannot be directly represented using a conventional table. Index-based structures typically grow to be overly lengthy, convoluted and are cumbersome to maintain, optimize and especially update. Examples of common indexes are b-trees, t-trees, star-indexes, and various bit maps.
The ability to quickly obtain a non-redundant, multi-dimensional data set from a database using flexible sorting criteria is extremely useful to database management.
In advertising, it is considered highly desirable to target advertisements to the appropriate potential customer base, rather than to broadcast advertisements in general. It has long been known that, for example, advertisements for computers should generally not appear in magazines on gardening and, conversely, advertisements for gardening tools should not appear in magazines on computers. Similarly, advertisers have generally targeted their advertisements on television to programs appropriate for the desired customer base.
The development of on-line networks, such as the Internet, has led to on-line advertising. For example, on the Internet, often such on-line advertisements will appear on a web page, such as a banner on the top or the bottom of the page. When the user views a web page using a browser, the banner appears at the appropriate location and the user may then try to find out more information regarding the advertisement by selecting the advertisement (called a xe2x80x9cclick-throughxe2x80x9d) through the use of the mouse or other pointing device. This will cause a HTTP message to be generated by the browser using the information encapsulated in association with the banner to send a request for an object with a given URL address to a different appropriate web site to access, for example, the advertiser""s home page.
Attempts have been made to provide targeting for on-line advertisements. With a small number of users and a small number of ads to be displayed, typical database systems provide acceptable performance. However, as the number of users increases, the number of advertisements increase, and the attributes to be targeted increase, traditional databases perform poorly.
The present invention provides a new and efficient way of structuring databases enabling efficient query processing, reduced database storage requirements, and more flexible content targeting.
In accordance with one aspect of the present invention, a database is defined having bit mapped data. The data to be stored in the database is characterized as a number of binary questions. That is, there are a number of xe2x80x9cyes/noxe2x80x9d questions, and each record comprises the answers to these questions. Each record is simply one or more groups of bit responding to the answers to the questions.
According to another aspect of the invention, for some types of data, there may be two or more possible values. In such cases, each possible value is itself a binary question.
In some cases, there may be data which does not lend itself to characterization as binary questions. In such cases, the database includes numeric and string values.
Queries of the database may be obtained through simple bit wise Boolean operations directly on the records in the database.
The database and query techniques described herein are useful in a content targeting system. The database is sufficiently flexible to support rapid targeting of a wide variety of content.
Rather than achieve orderedness through increasing redundancy (i.e., superimposing an ordered data representation on top of the original unordered representation of the same data), the present invention eliminates redundancy on a fundamental level. This reduces storage requirements, in turn enabling more data to be concurrently stored in RAM (enhancing application performance and reducing hardware costs) and speeds up transmission of databases across communication networks, making high-speed main-memory databases practical for a wide spectrum of business and scientific applications. Database operations in general are thus more efficient using the present invention. In addition, certain operations such as histographic analysis, data compression, and multiple orderings, which are computionally intensive in typical structures, are obtainable immediately from the structures described herein. The invention also provides improved processing in parallel computing environments.