News Column

Patent Issued for B-Tree Ordinal Approximation

August 26, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- A patent by the inventors Deschler, Kurt (Marborough, MA); Kirk, Steven A. (Chelmsford, MA), filed on March 29, 2010, was published online on August 12, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8805891 is assigned to Sybase, Inc. (Dublin, CA).

The following quote was obtained by the news editors from the background information supplied by the inventors: "The present invention relates generally to databases and, more specifically, to parallel processing of data from databases.

"In many database systems, key-value lookups are performed through the use of B-Tree data structures. A B-Tree is an ordered data structure, with groupings of data at leaf nodes typically corresponding to a memory page in the database context. Under typical usage in a database, a B-Tree will serve as a tool for sorting the key-values in groupings corresponding to memory page size limits.

"When performing database operations on data corresponding to a set of key-values, it is beneficial to allow multiple processors to resolve the operations in parallel when possible. This typically involves splitting the data in the B-Tree into two or more sets of data, for each processor or processor core to operate on. However, the techniques for splitting this data remain rudimentary at best, and do not realize the significant advantages that can be obtained through proper partitioning.

"Accordingly, what is desired are techniques to improve parallelization of data sets represented by a B-Tree data structure."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventors' summary information for this patent: "Embodiments of the invention include a method comprising generating a range of ordinals corresponding to key values represented in a B-Tree data structure, specifying a boundary point using an ordinal value of the range of ordinals, and performing an ordinal-to-key transformation to identify a key value corresponding to the boundary point.

"Embodiments of the invention additionally include a computer-readable medium having computer-executable instructions stored thereon that, if executed by a computing device, cause the computing device to perform a method comprising generating a range of ordinals corresponding to key values represented in a B-Tree data structure, specifying a boundary point using an ordinal value of the range of ordinals, and performing an ordinal-to-key transformation to identify a key value corresponding to the boundary point.

"Embodiments of the invention further include a system comprising a memory configured to store modules comprising a generating module configured to generate a range of ordinals corresponding to key values represented in a B-Tree data structure, a specifying module configured to specify a boundary point using an ordinal value of the range of ordinals, and a performing module configured to perform an ordinal-to-key transformation to identify a key value corresponding to the boundary point, and one or more processors configured to process the modules.

"Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. It is noted that the invention is not limited to the specific embodiments described herein. Such embodiments are presented herein for illustrative purposes only. Additional embodiments will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein."

URL and more information on this patent, see: Deschler, Kurt; Kirk, Steven A.. B-Tree Ordinal Approximation. U.S. Patent Number 8805891, filed March 29, 2010, and published online on August 12, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8805891.PN.&OS=PN/8805891RS=PN/8805891

Keywords for this news article include: Sybase Inc, Information Technology, Information and Data Architecture.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters