Wednesday, February 27, 2008

KD-Tree: McObject Edge in Database Indexing

McObject has added support for the KD-Tree, a database index with uses in spatial and pattern-matching applications, to its Perst™ open source, object-oriented embedded database system. For developers working with Perst, the KD-Tree expands coding efficiency and helps make Java and .NET data objects easier to use in certain types of application.

For McObject, Perst’s new feature marks a widening of its lead in providing application developers with the best data management tools for building highly efficient software – an edge that is evident in the company’s growing list of supported indexes, many of them specialized and customizable.

The new k-dimensional tree or KD-Tree index adds a structure in Perst that stores and manipulates point objects in a k-dimensional space by partitioning that space. Practical uses include computer graphics, geographical information systems and biometric applications such as fingerprint matching. In addition to their efficiency in handling multi-dimensional data, KD-trees are useful in "normal" applications in which query predicates contain various combinations of object fields. For example, KD-Trees are used to construct Query-By-Example (QBE) features in which the user selects fields and values, and the application builds database queries based on these selections.

Most database systems don’t venture beyond general purpose b-tree indexes and, for Java and .NET databases, the standard JDK/.NET collection classes. In contrast, McObject’s Perst and eXtremeDB embedded databases offer a rich assortment of index types, including:

• B-trees for common sorting and searches, insertions, and deletions

• R-trees for geospatial indexing (common in GPS/navigation systems)

• T-trees for all-in-memory data storage and access

• Hash tables for quickly locating a single unique index entry

• Patricia trie index, which speeds searches in networking and telephony applications

• “Custom indexes” for b-trees that allow the application to define the collating sequence of entries; this is useful in implementing soundex algorithm searches, for example

• Bit or bitmap indexes that are optimized for columns in which values repeat frequently (for example, fields to which only three values could apply)

• TimeSeries class to efficiently deal with small fixed-size objects

• Specialized versions of collections for thick indices (indexes with many duplicates), and bit indexes

“Support for diverse index types is especially valuable in embedded and device-based applications, where code efficiency takes full advantage of scarce memory and CPU resources and enables developers to ‘do more with less.’ McObject shows the way in providing data management that is designed with intelligent devices in mind, so it makes sense that we focus on widening our index toolset,” CTO and Co-Founder Andrei Gorine said.

Source : http://www.mcobject.com/

0 comments:

Post a Comment