Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-01-25
2002-04-30
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S201000, C709S241000
Reexamination Certificate
active
06381607
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of databases and data warehousing, and in particular to a system for searching and retrieving information from catalogs.
BACKGROUND
The widespread advent of the Internet is well known, with individuals and businesses using the Internet as a new media of exchange. Increasingly electronic commerce, or e-commerce, is becoming widely accepted. In e-commerce applications, sellers often put descriptions of their product on a web site. Further, to better publish a product line, a seller typically arranges products into a “catalog”, intending to facilitate buyers finding the products that the buyers want. Examples of marketing products for building catalog applications are Intershop, iCat and Open Market.
Many buyers are not, however, well versed in how sellers categorize their products (e.g., the particular name associated with a category of goods, etc.). Therefore, contrary to the intended purpose of a catalog, a catalog regularly creates confusion and is difficult to use for ordinary buyers. This can result in frustration on the buyer's part and loss of revenue on the seller's part.
The difficulty arises in existing methods due to the B-tree like indexing schemes used in many ordinary databases. The B-tree indexing scheme is used to save space and time in searching and navigating a hierarchical data structure. This can be visualized by considering
FIGS. 1A and 1B
.
FIG. 1A
is a block diagram illustrating a table
100
of a relational database. The table
100
has six columns labeled Key, Country, State, City, Name and Income. Each of the keys S
45
to S
55
is associated with a different person and that person's data. In addition to the person's name, their income and residence (country, state, and city) are given in fields in each row. Thus, the first row having the Key S
45
is for “Wu” and has entries of US, CA (California) and LA (Los Angeles) for the country, state and city fields, respectively. The last column “Income” has an entry of 1200. The fields in the three columns Country, State and City are highlighted with thicker borders to point out that the values of the fields are repetitive in terms of information content. For example, the entries “US” and “Canada” appear several times under the Country column.
FIG. 1B
is a B-tree representation
150
of the entries in the columns Country, State and City and the corresponding Keys, which seeks to reduce the redundancy of the table
100
. The tree
150
contains nine nodes numbered 1 to 9. The first node is for the world. The second and third nodes depending from the first node are US and CANADA (CA). This results in a significant compaction of the data contained in the Country column of table
100
. Corresponding to these two nodes are Keys S
54
and S
52
, respectively, since the State and City fields in table
100
are “Nil” for these two keys. The fourth node CA depends from the second node for the US. Likewise, BC (British Columbia) depends from the third node for Canada. The fourth and fifth nodes have corresponding Keys S
46
and S
51
, respectively, since the corresponding City field entries are “Nil” for these keys. The sixth and seventh nodes for LA and SF (San Francisco) depend from the fourth node for CA. The sixth node has corresponding Keys S
45
, S
49
, and S
53
. The seventh node has Key S
50
. Finally, the eighth and ninth nodes VC (Vancouver) and IV depend from the fifth node BC. The eighth node has Keys S
47
and S
55
, and the ninth node has Key S
48
.
Again, the tree representation
150
of the indices is more compact for storage than the database structure shown in the first four columns of table
100
. However, conventional methods are disadvantageous in that they do not specify how indices and keys can be compacted for faster access of keys. Consequently, Keys such as S
54
and S
52
corresponding to nodes
2
and
3
of
FIG. 1B
are not contiguously stored; this similarly applies to other subgroups of Keys, such as the group consisting of S
45
, S
49
, S
53
, in relation to Key S
50
. For example, if Keys S
45
, S
49
, and S
53
are stored on a disk storage medium at a discontinuous position for S
50
, a read latency occurs after Key S
53
is read to obtain Key S
50
. This can result in significant degradation of the performance of accessing Keys in the database or catalog. Therefore, due to the randomness in the key/index organization, the speed of retrieval processing is substantially degraded, because (1) each successive traversal along the tree nodes of FIG.
1
B and (2) each retrieval of groups of keys incurs latencies for setting up a disk scan due to the storage randomness.
Therefore, a need clearly exists for an improved system of organizing keys and indices to facilitate better retrieval of information from a catalog, especially a system that can use rough and ambiguous user input.
SUMMARY
In accordance with a first aspect of the invention, there is disclosed a method of organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval. The method including the steps of: storing indices according to categories and subcategories in an array of indices, wherein indices of a category or subcategory are stored contiguously in the array, each index having one or more means for linking the index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of the indices in the tree-like data structure; storing the keys according to the categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding category or subcategory level and keys of any subordinate subcategories within a category or subcategory are stored hierarchically in the array of keys; and linking each index of the array of indices with one or more corresponding keys of the array of keys corresponding to the category or subcategory associated with the index.
Preferably, the method includes the step of naming each subcategory according to one or more indices corresponding to the category or subcategory to provide a named path. The method may also include the step of searching a category or subcategory of keys using a named path.
Preferably, each index of the array of indices is linked with one or more corresponding keys of the array of keys corresponding to a category or subcategory associated with the index.
Optionally, the method further includes the step of adding at least one alternative view path to the tree-like data structure, including at least one additional node. The method may further include the step of generating at least one equivalent named path for an existing named path of a category or subcategory. The method may also include the step of adding one or more additional indices to the array of indices corresponding to the alternative view path. Still further, the method may further include the step of adding one or more additional keys to the array of indices corresponding to the alternative view path.
In accordance with a second aspect of the invention, there is disclosed an apparatus for organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval. The apparatus includes: a device for storing indices according to categories and subcategories in an array of indices, wherein indices of a category or subcategory are stored contiguously in the array, each index having one or more means for linking the index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of the indices in the tree-like data structure; a device for storing the keys according to the categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding category or subcategory level and keys of any subordinate subcategories within a category or subcategory are stored hierarchically in the array of keys; and a device for linking each index of th
Lin Tian
Lui Ho Chung
Wu Horng Jyh Paul
Alam Hosain T.
Alam Shahid
Kent Ridge Digital Labs
Ladas & Parry
LandOfFree
System of organizing catalog data for searching and retrieval does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System of organizing catalog data for searching and retrieval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System of organizing catalog data for searching and retrieval will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820160