Encoding semi-structured data for efficient search and browsing

Details Encoding semi-structured data for efficient search and browsing Encoding semi-structured data for efficient search and browsing

2007-10-12

2011-11-22

Fleurantin, Jean B (Department: 2162)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

C707S743000, C707S746000, C707S955000, C707S956000

Reexamination Certificate

active

08065308

ABSTRACT:
A method for encoding XML tree data that includes the step of encoding the semi-structured data into strings of arbitrary length in a way that maintains non-structural and structural information about the XML data, and enables indexing the encoded XML data in a way that facilitates efficient search and browsing.

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: 5293616 (1994-03-01), Flint
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), Takkanen
patent: 5852822 (1998-12-01), Srinivasan et al.
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, III et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6094649 (2000-07-01), Bowen et al.
patent: 6153591 (2000-11-01), Cai et al.
patent: 6154738 (2000-11-01), Call
patent: 6175835 (2001-01-01), Shadmon
patent: 6208993 (2001-03-01), Shadmon
patent: 6240407 (2001-05-01), Chang et al.
patent: 6240418 (2001-05-01), Shadmon
patent: 6279015 (2001-08-01), Fong et al.
patent: 6396842 (2002-05-01), Rochberger
patent: 6439783 (2002-08-01), Antoshenkov
patent: 6507846 (2003-01-01), Consens
patent: 6519597 (2003-02-01), Cheng et al.
patent: 6584459 (2003-06-01), Chang et al.
patent: 6675173 (2004-01-01), Shadmon
patent: 6694323 (2004-02-01), Bumbulis
patent: 6697363 (2004-02-01), Carr
patent: 6804677 (2004-10-01), Shadmon et al.
patent: 6910043 (2005-06-01), Iivonen et al.
patent: 7249149 (2007-07-01), Eatherton et al.
patent: 7257590 (2007-08-01), Heiner et al.
patent: 7287033 (2007-10-01), Shadmon et al.
patent: 2001/0049675 (2001-12-01), Mandler et al.
patent: 2002/0143747 (2002-10-01), Tal et al.
patent: 2004/0052251 (2004-03-01), Mehrotra et al.
patent: 2004/0111402 (2004-06-01), Waters et al.
patent: 2005/0027679 (2005-02-01), Sample
patent: 2006/0015516 (2006-01-01), Benakot et al.
patent: 2007/0162473 (2007-07-01), Hadzikadic et al.
patent: 2253744 (2000-05-01), None
patent: 0 586 086 (1994-03-01), None
patent: WO 98/04980 (1998-02-01), None
patent: WO 99/38094 (1999-07-01), None
Kanemoto et al., “An efficiently updatable index scheme for structured documents”, Database and Expert Systems Applications, 1998. Proceedings. Ninth International Workshop on, Aug 1998, p. 991-996. Download: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=707525&isnumber=15304.
Milo et al., “Index Structures for Path Expressions”, 1997,CiteSeerx, Download: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.275.
Dao, Tuong, “An indexing model for structured documents to support queries on content, structure and attributes”, IEEE, Apr. 1998, pp. 88-97. Download: http://ieeexplore.ieee.org/xpls/abs—all.jsp?arnumber=670383&tag=1.
Merrett et al., “Trie Methods for Representing Text,” School of Computer Science, McGill University, pp. 130145.
Morrison, “Patricia-Practical Algorithm to Retrieve Information Coded in Alphanumeric,” Journal of the Association for Computing Machinery, vol. 15, No. 4, pp. 514-534, Oct. 1968.
Shang et al., “Tries for Approximate String Matching,” School of Computer Science, McGill University, pp. 100-145.
Hubalek et al., “A multivariate View of Random Bucket Digital Search Trees,” Journal of Algorithms, vol. 44, pp. 121158, 2002.
Atalay et al., “Pointerless Implementation of Hierarchical Simplical Meshes and Efficient Neighbor Finding in Arbitrary Dimensions,” Department of Computer Science, University of Maryland.
Mar. 27, 2008 Office Action issued in U.S. Appl. No. 10/931,035.
Sep. 15, 2008 Office Action issued in U.S. Appl. No. 10/931,035.
Jul. 7, 2009 Office Action issued in U.S. Appl. No. 10/931,035.
Dec. 28, 2009 Office Action issued in U.S. Appl. No. 10/931,035.
Apr. 8, 2010 Office Action issued in U.S. Appl. No. 11/183,752.
Aug. 17, 2009 Office Action issued in U.S. Appl. No. 11/183,752.
Jan. 5, 2009 Office Action issued in U.S. Appl. No. 11/183,752.
Apr. 25, 2008 Office Action issued in U.S. Appl. No. 11/183,752.
D. Knuth, “Sorting and Search”, The Art of Computing Programming,Addison-Wesley, vol. 3, pp. 473-479, 490-499 and 501-504, 1973.
Oracle 9i Index-Organized Tables, Technical Whitepaper, Sep. 2001.
P. Blumulis et al. “A compact B-tree,” SIGMOD Conference, Jun. 3-6, 2002, 9 pages.
Horowitz and Sahni, “Fundamentals of Data Structures ”Computer Science Press, 1976.
J. Rumbaugh et al., “Object Oriented Modeling and Design,” Chapter 3, pp. 21-56.
H.F. Korth et al. “Database System Concepts,”McGraw-Hill International Editions, Chapters 3-5 and 7-8, pp. 45-172 and 229-299, 1986.
G. Wiederhold, “File Organization for Database Design,”McGraw-Hill, pp. 272-273, 1987.
J.D. Ullman, “Physical Data Organization Principles of Database Systems”, pp. 30-51, Jan. 1980.
T. Harden, “Implementierung von Operationalen Schnittstellen,”Lockemann, P.C.. Schmidt. J.W.: Daten bank—Handbuch, Chapter 3, pp. 238-243, Berlin, Germany, 1987.
Database Systems Concepts, Chapter 7.
A. Andersson et al., “Efficient Implementation of Suffix Trees,”Software-Practice and Experience, vol. 25, No. 2, pp. 129-141, Feb. 1995.
W.A. Litwin et al., “Trie Hasing with Controlled Load,” 678-691, Jul. 1991.IEEE Transactions on Software Engineering, vol. 17, No. 7, pp. 678-691, Jul. 1991.
“The Art of Computer Programming”Addison-Wesley, XP002 135679 120440, vol. 3, pp. 471-479, 1988.
D. Knuth, “The Art of Computer Programming, Sorting and Searching,”Addison-Wesley, vol. 3, pp. 481-505, 681-687.
FOLDOC Free On-line Dictionary of Cmputing—markup p. 1.
H.R. Lewis et al., “Data Structures & Their Algorithms,”Addison-Wesley Pub. Co., pp. 96-129, Jan. 1997.
P. Buneman et al., “Query Optimization for Semistructured Data using Path Constraints in a Deterministic Data Model,”Computer Science, pp. 1-12, 1999.
A. Deutsch et al., “Storing Semistructured Data with STORED,” pp. 1-25, 1999.
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.

Affiliated with

Also associated with

Rating

Encoding semi-structured data for efficient search and browsing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Encoding semi-structured data for efficient search and browsing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding semi-structured data for efficient search and browsing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4298006