Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-10-23
2007-10-23
Kindred, Alford W. (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C715S252000
Reexamination Certificate
active
10379002
ABSTRACT:
A method for encoding hierarchical data stored in an index, partitioned into blocks, over keys representing the data. For every key K representing a record R in the index, the key of the children records of record R are prefixed with K. The method includes traversing to a first R record represented in the index, traversing from the record R to the next sequential R such that the path in the index from the position representing R to the position representing the next sequential R does not include information relating to the children of R. Next, repeating the latter operation for 0 or more R records, and for any 0 or more particular R records, traversing from the particular R to its children. The index constitutes a balanced structure of blocks.
REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4611272 (1986-09-01), Lomet
patent: 4945475 (1990-07-01), Bruffey et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5202986 (1993-04-01), Nickel
patent: 5230047 (1993-07-01), Frey, Jr. et al.
patent: 5257365 (1993-10-01), Powers et al.
patent: 5295261 (1994-03-01), Simonetti
patent: 5333317 (1994-07-01), Dann
patent: 5377281 (1994-12-01), Ballard et al.
patent: 5392363 (1995-02-01), Fujisaki et al.
patent: 5404510 (1995-04-01), Smith et al.
patent: 5418947 (1995-05-01), Hsu et al.
patent: 5487166 (1996-01-01), Cossock
patent: 5488717 (1996-01-01), Gibson et al.
patent: 5495609 (1996-02-01), Scott
patent: 5497485 (1996-03-01), Ferguson et al.
patent: 5528701 (1996-06-01), Aref
patent: 5530957 (1996-06-01), Koenig
patent: 5534861 (1996-07-01), Chang et al.
patent: 5551027 (1996-08-01), Choy et al.
patent: 5557786 (1996-09-01), Johnson, Jr.
patent: 5560007 (1996-09-01), Thai
patent: 5644763 (1997-07-01), Roy
patent: 5649023 (1997-07-01), Barbara et al.
patent: 5651099 (1997-07-01), Konsella
patent: 5664172 (1997-09-01), Antoshenkov
patent: 5694591 (1997-12-01), Du et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5717921 (1998-02-01), Lomet et al.
patent: 5737732 (1998-04-01), Gibson et al.
patent: 5752243 (1998-05-01), Reiter et al.
patent: 5761652 (1998-06-01), Wu et al.
patent: 5765168 (1998-06-01), Burrows
patent: 5768423 (1998-06-01), Aref et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5799184 (1998-08-01), Fulton et al.
patent: 5799299 (1998-08-01), Fujiwara
patent: 5809296 (1998-09-01), Yong et al.
patent: 5832182 (1998-11-01), Zhang et al.
patent: 5842196 (1998-11-01), Agarwal et al.
patent: 5848416 (1998-12-01), Tikkanen
patent: 5873087 (1999-02-01), Brosda et al.
patent: 5884297 (1999-03-01), Noven
patent: 5963956 (1999-10-01), Smartt
patent: 5970170 (1999-10-01), Kadashevich et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6153591 (2000-11-01), Cai et al.
patent: 6175835 (2001-01-01), Shadmon
patent: 6208993 (2001-03-01), Shadmon
patent: 6240418 (2001-05-01), Shadmon
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6654734 (2003-11-01), Mani et al.
patent: 6697363 (2004-02-01), Carr
patent: 6735595 (2004-05-01), Gobeille et al.
patent: 6816856 (2004-11-01), Baskins et al.
patent: 6859455 (2005-02-01), Yazdani et al.
patent: 2002/0120598 (2002-08-01), Shadmon et al.
patent: WO98/04980 (1998-02-01), None
patent: WO99/38094 (1998-07-01), None
Donald Knuth, “The Art of Computer Programming”, vol. 3, Sorting and Searching, 1973, pp. 471-479, 490-499, 501-504.
Orcle 9i Index-Organized Tables, Technical Whitepaper, Sep. 2001.
Peter Blumulis et al., “A Compact B-tree” SIGMOD Conference, Jun. 3-6, 2002, 9 pages.
Horowitz and Shani, “Fundamentals of Data Structures”, Computer Science Press, 1976.
P. Ferragina et al., “An experimental study of SB-trees”, (Jun. 1996), NECResearchIndex.
Rumbaugh J. et al., “Object Oriented Modeling and Design”, Chap. 3, pp. 21-56, 1987.
H.F. Korth et al., “Database System Concepts”, 1986, Chapters 3-5 and 7-8, pp. 45-172 and 229-299.
G. Wiederhold, “File Organization for Database Design”, 1987, pp. 272, 273.
J.D. Ullman, “Physical Data Organization Principles of Database Systems”, Jan. 1980, pp. 30-51.
Harder, Theo, “Implenetierung von Operationalen Schnittstellen”, in: Lockemann, P.C., Schmidt, J.W.: Daten bank-Handbuch, Chapter 3, here: pp. 238-243 1987, SPRINGER, Berlin, Germany, translation into English enclosed.
P. Ferragina et al., “A Fully-Dynamic Data Structure for External Substring Search” ACM Symposium on Theory of Computing (1995), pp. 693-702.
P. Ferragina et al., “The String B-Tree: A new Data Structure for String Search in External Memory and its Applications”, Journal of the ACM 46 (2), Mar. 1999, pp. 236-280.
Arne Andersson et al., “Efficient Implementation of Suffix Trees”, Software-Practice and Experience, vol. 25, No. 2, Feb. 1995, pp. 129-141.
Witold A. Litwin et al., “Trie Hashing With Controlled Load”, IEEE Transactions on Software Engineering, vol. 17, No. 7, Jul. 1991, pp. 678-691.
Donald Knuth, “The Art of Computer Programming”, vol. 3, Sorting and Searching, 1973, pp. 481-505, 681-687.
Donald Knuth, “The Art of Computer Programming”, vol. 3, Sorting and Searching, 1973, pp. 552-559.
Houghton Mifflin Company, The American Heritage Dictionary of the English Language, Third Edition, 1996, “Of or relating to meaning, especially meaning in language.”
Buneman et al., “Keys for XML”, Aug. 2000.
Banerjee et al., “Oracle8i—The XML Enabled Data Management System”, 2000, 8 pages.
Josephine Cheng et al., “XML and DB2”, 2000, 5 pages.
Serge Abiteboul et al., “The Lorel Query Language for Semistructured Data.”, International Journal on Digital Libraries, 1(1), Department of Computer Science, Stanford University, Apl. 1997, pp. 68-88.
James Clark et al., XML Path Language (Xpath), Version 1. 0, W3C Recommendation 16, Nov. 1999, pp. 1-48.
Don Chamberlain et all, “Quilt: An XML Query Language for Heterogeneous Data Sources”, International Workshop on Web and Databases (WebDB'2000), Dallas, Texas, May 2000, 25 pages.
Siberschatz A. et al., “Database Systems Concepts”, Chapter 7, pp. 215-250, WCB McGraw-Hill, Third Edition, 1997.
Girardot M. et al., “Millau: An Encoding Format for Efficient Representation and Exchange of XML over the Web”, Computer Networks and ISDN Systems, North Holland Publishing, Amsterdam, NL, vol. 33, No. 1-6, Jun. 2000, pp. 747-765.
Liefke H. et al., “XMILL: An Efficient Compressor for XML Data”, Sigmond Record, Association for Computing Machenery, New York, US, vol. 29, No. 2, Jun. 2000, pp. 153-164.
Sample Neal
Shadmon Moshe
Kindred Alford W.
Oliff & Berridg,e PLC
ORI Software Development Ltd.
LandOfFree
Efficient traversals over hierarchical data and indexing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient traversals over hierarchical data and indexing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient traversals over hierarchical data and indexing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3855156