Algorithms for BD trees

Database applications often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most are generalizations of the storage structures used for managing one-dimensional data. Recently, a new storage structure, called the BD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. This paper presents algorithms for the BD tree to perform insertion, deletion, and to answer exact match, partial match and range queries. In addition, some experimental evidence is presented that suggests that BD trees have good dynamic characteristics.     

Dividedk-d trees

A variant ofk-d trees, thedivided k-d tree, is described that has some important advantages over ordinaryk-d trees. The dividedk-d tree is fully dynamic and allows for the insertion and deletion of points inO(logn) worst-case time. Moreover, dividedk-d trees allow for split and concatenate operations. Different types of queries can be performed with equal or almost equal efficiency as on ordinaryk-d trees. Both two- and multidimensional dividedk-d trees are studied.     

An efficient peer-to-peer indexing tree structure for multidimensional data

As one of the most important technologies for implementing large-scale distributed systems, peer-to-peer (P2P) computing has attracted much attention in both research and industrial communities, for its advantages such as high availability, high performance, and high flexibility to the dynamics of networks. However, multidimensional data indexing remains as a big challenge to P2P computing, because of the inefficiency in search and network maintenance caused by the complicated existing index structures, which greatly limits the scalability of applications and dimensionality of the data to be indexed.We propose SDI (Swift tree structure for multidimensional Data Indexing), a swift index scheme with a simple tree structure for multidimensional data indexing in large-scale distributed systems. While keeping the query efficiency in O(logN) in terms of routing hops, SDI has extremely low maintenance costs which is proved through theoretical analysis. Furthermore, SDI overcomes the root-bottleneck problem existing in most other tree-based distributed indexing systems. Extensive empirical study verifies the superiority of SDI in both query and maintenance performance.     

External segment trees

The segment tree is a well-known internal data structure with numerous applications in computational geometry. It allows the dynamical maintenance of a set of intervals such that the intervals enclosing a query point can be found efficiently (point enclosure search).In this paper we transfer the underlying principle of the segment tree in a nontrivial way to secondary storage and arrive at the EST-an external file structure with the same functionality and the following properties: (1) Point enclosure searches are very efficient—only very few pages are accessed that are not filled to more than 50% with result intervals. (2) A page filling of 50% is guaranteed—on the average it will be around 70%. Although the segment tree represents, in the worst case, each interval by a logarithmic number offragments, in practical cases fragmentation remains low and the storage requirements about linear. (3) The EST is balanced and the update algorithms are efficient. (4) Unlike many other file structures for spatial objects the EST has no problems with an arbitrarydensity, that is, an arbitrarily large number of intervals covering any point of the line.Furthermore, the EST can be used as a file structureconstructor in the following sense: Let there be a file structureX supporting searches for objects with propertyx and suppose it is necessary to maintain a collection of objects with associated (e.g., time) intervals. Then an EST-X structure that supports searches for objects with propertyx present at timet can be built. This suggests using the EST as a building block in the implementation of temporal database systems. Other applications include the one-dimensional indexing of collections of spatial objects in two or more dimensions.More generally, this paper shows techniques for mapping internal tree structures with node lists (other examples: range tree, interval tree) to secondary memory. In this context an intriguing theoretical problem, thecover-balancing problem, is solved: Given a tree whose nodes have associatedweights partitioned into subtrees whose weights must lie in a certain range, maintain this partition under weight changes at arbitrary nodes. This is in contrast to classical balancing problems where updates occur only at the leaves.This work was supported by the DFG (Deutsche Forschungsgemeinschaft) under Grant Cr 65/2-5.     

Dividedk-d trees

A variant ofk-d trees, thedivided k-d tree, is described that has some important advantages over ordinaryk-d trees. The dividedk-d tree is fully dynamic and allows for the insertion and deletion of points inO(logn) worst-case time. Moreover, dividedk-d trees allow for split and concatenate operations. Different types of queries can be performed with equal or almost equal efficiency as on ordinaryk-d trees. Both two- and multidimensional dividedk-d trees are studied.     

SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees

Emerging database applications require the use of new indexing structures beyond B-trees and R-trees. Examples are the k-D tree, the trie, the quadtree, and their variants. They are often proposed as supporting structures in data mining, GIS, and CAD/CAM applications. A common feature of all these indexes is that they recursively divide the space into partitions. A new extensible index structure, termed SP-GiST is presented that supports this class of data structures, mainly the class of space partitioning unbalanced trees. Simple method implementations are provided that demonstrate how SP-GiST can behave as a k-D tree, a trie, a quadtree, or any of their variants. Issues related to clustering tree nodes into pages as well as concurrency control for SP-GiST are addressed. A dynamic minimum-height clustering technique is applied to minimize disk accesses and to make using such trees in database systems possible and efficient. A prototype implementation of SP-GiST is presented as well as performance studies of the various SP-GiST's tuning parameters.     

面向海量交通数据的HBase时空索引

针对HBase无法直接建立时空索引所带来的交通数据查询性能问题,基于HBase行键设计了面向海量交通数据的HBase时空索引。首先利用Geohash降维方法将二维空间位置数据转化为一维编码,再与时间维度进行组合;然后根据组合顺序的不同,提出了四种结构模型,分别讨论了模型的具体构成以及交通数据查询中的适应面;最后提出了相应的时空索引管理算法及基于Hbase时空索引的交通数据查询方法。通过实验验证了提出的HBase时空索引结构能有效提升海量交通数据的区域查询性能,并比较了四种时空索引结构在不同数据规模、不同查询半径以及不同时间范围的查询性能,量化验证了不同索引结构在交通数据查询中的适应场景。     

自适应近似树

在大规模多媒体数据库中进行基于内容的检索，高维数据牵引结构的研究是重要问题，提出了一种有效的高维索引结构－自适应近似树，阐述了它的结构，给出了构建和检索算法，它结合了树结构和顺序检索的共同优点，针对不同的数据分布情况可以自适应地调整结构，维数较低或数据分布偏斜较大时它呈现树的结构，高维或数据分布密集时呈现顺序扫描的结构，以达到更优的检索效率，在结构上，对MBR使用了压缩存储的方法以节省存储空间，在算法中充分利用了空间划分是MBS和MBR共存的特点，减少了大量复杂的计算，从而大大提高检索效率。     

Bounding Volume Hierarchies of Slab Cut Balls

We introduce a bounding volume hierarchy based on the Slab Cut Ball. This novel type of enclosing shape provides an attractive balance between tightness of fit, cost of overlap testing, and memory requirement. The hierarchy construction algorithm includes a new method for the construction of tight bounding volumes in worst case O(n) time, which means our tree data structure is constructed in O(n log n) time using traditional top‐down building methods. A fast overlap test method between two slab cut balls is also proposed, requiring as few as 28–99 arithmetic operations, including the transformation cost. Practical collision detection experiments confirm that our tree data structure is amenable for high performance collision queries. In all the tested benchmarks, our bounding volume hierarchy consistently gives performance improvements over the sphere tree, and it is also faster than the OBB tree in five out of six scenes. In particular, our method is asymptotically faster than the sphere tree, and it also outperforms the OBB tree, in close proximity situations.     

XFlat: Query-friendly encrypted XML view publishing

The security of published XML data receives exceptional attention due to its sensitive nature in many applications. This paper proposes an XML view publishing method called XFlat. Compared with other methods, XFlat focuses on query performance over the published XML view while simultaneously protecting the sensitive data via encryption techniques. XFlat decomposes an XML tree into a set of sub-trees, in each of which multiple users have the same accessibility to all nodes, and may encrypt and store each sub-tree in a flat, sequential manner. This storage strategy can avoid the nested encryption cost in view construction and the nested decryption cost in query evaluation. In addition, we discuss how to generate a user-specific schema and how to minimize the total space cost of the published XML view when considering the overhead of the relationships among the sub-trees. We also propose an XML schema index to enhance query performance over the final XML view. The experimental results demonstrate the effectiveness and efficiency of the proposed XFlat method.     

Extended Branch Decomposition Graphs: Structural Comparison of Scalar Data

We present a method to find repeating topological structures in scalar data sets. More precisely, we compare all subtrees of two merge trees against each other – in an efficient manner exploiting redundancy. This provides pair‐wise distances between the topological structures defined by sub/superlevel sets, which can be exploited in several applications such as finding similar structures in the same data set, assessing periodic behavior in time‐dependent data, and comparing the topology of two different data sets. To do so, we introduce a novel data structure called the extended branch decomposition graph, which is composed of the branch decompositions of all subtrees of the merge tree. Based on dynamic programming, we provide two highly efficient algorithms for computing and comparing extended branch decomposition graphs. Several applications attest to the utility of our method and its robustness against noise.     

The TV-tree: An index structure for high-dimensional data

We propose a file structure to index high-dimensionality data, which are typically points in some feature space. The idea is to use only a few of the features, using additional features only when the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such varying length feature vectors. Finally, we report simulation results, comparing the proposed structure with theR ^*-tree, which is one of the most successful methods for low-dimensionality spaces.The results illustrate the superiority of our method, which saves up to 80% in disk accesses.     

An efficient nonuniform index in the wireless broadcast environments

Data broadcast is an efficient dissemination method to deliver information to mobile clients through the wireless channel. It allows a huge number of the mobile clients simultaneously access data in the wireless environments. In real-life applications, more popular data may be frequently accessed by clients than less popular ones. Under such scenarios, Acharya et al.’s Broadcast Disks algorithm (BD) allocates more popular data appeared more times in a broadcast period than less popular ones, i.e., the nonuniform broadcast, and provides a good performance on reducing client waiting time. However, mobile devices should constantly tune in to the wireless broadcast channel to examine data, consuming a lot of energy. Using index technologies on the broadcast file can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. In this paper, we propose an efficient nonuniform index called the skewed index, SI, over BD. The proposed algorithm builds an index tree according to skewed access patterns of clients, and allocates index nodes for the popular data more times than those for the less popular ones in a broadcast cycle. From our experimental study, we have shown that our proposed algorithm outperforms the flexible index and the flexible distributed index.     

Performance analysis of partial-match search algorithms for BD trees

Database systems are becoming increasingly popular for answering queries. Partial-match search queries are an important class of queries in such a system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A previous study indicated that the k-d tree performance is better than that of the BD tree for partial-match search queries. A recent paper reported some improved algorithms. However, it is unclear whether the improved algorithms show the BD tree in a favourable light for partial-match search queries. This paper explores the performance of these algorithms and compares their performance to that of the k-d tree. Since the BD tree construction process uses some heuristics to make it a better balanced tree, this paper also evaluates the effect of these heuristics on the partial-match search algorithms. The major conclusions of this study are that the BD tree performance for partial-match search is better than that of the k-d tree when an improved algorithm is used for partial-match search, and only the DZ expression rearrangement heuristic has substantial effect on partial-match search performance.     

A MapReduce‐supported network structure for data centers

Several novel data center network structures have been proposed to improve the topological properties of data centers. A common characteristic of these structures is that they are designed for supporting general applications and services. Consequently, these structures do not match well with the specific requirements of some dedicated applications. In this paper, we propose a hyper‐fat‐tree network (HFN): a novel data center structure for MapReduce, a well‐known distributed data processing application. HFN possesses the advanced characteristics of BCube as well as fat‐tree structures and naturally supports MapReduce. We then address several challenging issues that face HFN in supporting MapReduce. Mathematical analysis and comprehensive evaluation show that HFN possesses excellent properties and is indeed a viable structure for MapReduce in practice. Copyright © 2011 John Wiley & Sons, Ltd.     

Generic and efficient framework for search trees on flash memory storage systems

Tree index structures are crucial components in data management systems. Existing tree index structure are designed with the implicit assumption that the underlying external memory storage is the conventional magnetic hard disk drives. This assumption is going to be invalid soon, as flash memory storage is increasingly adopted as the main storage media in mobile devices, digital cameras, embedded sensors, and notebooks. Though it is direct and simple to port existing tree index structures on the flash memory storage, that direct approach does not consider the unique characteristics of flash memory, i.e., slow write operations, and erase-before-update property, which would result in a sub optimal performance. In this paper, we introduce FAST (i.e., Flash-Aware Search Trees) as a generic framework for flash-aware tree index structures. FAST distinguishes itself from all previous attempts of flash memory indexing in two aspects: (1) FAST is a generic framework that can be applied to a wide class of data partitioning tree structures including R-tree and its variants, and (2) FAST achieves both efficiency and durability of read and write flash operations through memory flushing and crash recovery techniques. Extensive experimental results, based on an actual implementation of FAST inside the GiST index structure in PostgreSQL, show that FAST achieves better performance than its competitors.     

Pattern discovery and change detection of online music query streams

Mining of music data is one of the most important problems in multimedia data mining. In this paper, two research issues of mining music data, i.e., online mining of music query streams and change detection of music query streams, are discussed. First, we proposed an efficient online algorithm, FTP-stream (Frequent Temporal Pattern mining of streams), to mine all frequent melody structures over sliding windows of music melody sequence streams. An effective bit-sequence representation is used in the proposed algorithm to reduce the time and memory needed to slide the windows. An effective list structure is developed in the FTP-stream algorithm to overcome the performance bottleneck of 2-candidate generation. Experiments show that the proposed algorithm FTP-stream only needs a half of memory requirement of original melody sequence data, and just scans the music query stream once. After mining frequent melody structures, we developed a simple online algorithm, MQS-change (changes of Music Query Streams), to detect the changes of frequent melody structures in current user-centered music query streams. Two music melody structures (set of chord-sets and string of chord-sets) are maintained and four melody structure changes (positive burst, negative burst, increasing change and decreasing change) are monitored in a new summary data structure, MSC-list (a list of Music Structure Changes). Experiments show that the MQS-change algorithm is an effective online method to detect the changes of music melody structures over continuous music query streams.

基于环结构的传感器网络多分辨率数据存储机制

提出了一套基于环结构的传感器网络多分辨率数据存储机制,结合层次结构的存储查询方案,有效地利用了环结构的特性高效、节能地支持事件信息的不同分辨率的存储和查询操作,并采用优化的环结构参数,在基于环的层次结构数据存储架构中能够最小化网络节点的总体通信能耗.同时,对环结构多分辨率数据存储机制的相关性能从节能性、负载均衡性等多个角度进行了具体理论分析.模拟实验结果表明,基于环的层次结构存储机制能够高效、节能地支持传感器网络事件数据的多分辨率存储和查询操作.     

Efficient range query processing over DHTs based on the balanced Kautz tree

Distributed Hash Tables (DHTs) are scalable, self‐organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for hosting large‐scale distributed applications. The ever‐wider use of DHT infrastructures has found more and more applications that require support for range queries. Recently, a number of DHT‐based range query schemes have been proposed. However, most of them suffer from high query delay or imbalanced load distribution. To address these problems, in this paper we first present an efficient indexing structure called Balanced Kautz (BK) tree that uniformly maps the m‐dimensional data space onto DHT nodes, and then propose a BK tree‐based range query scheme called ERQ that processes range queries in a parallel fashion and guarantees to return the results in a bounded delay. In a DHT with N nodes, ERQ can answer any range of query in less than rmlog N(2loglog N + 1) hops in a load‐balanced manner, irrespective of the queried range, the whole space size, or the number of queried attributes. The effectiveness of our proposals is demonstrated through experiments. Copyright © 2010 John Wiley & Sons, Ltd.     

空间数据库中的一种混合索引结构的研究

空间索引是实现空间查询的关键技术,其性能的好坏直接决定着空间数据的存储效率及空间查询的性能。为了提高空间查询效率,提出一种混合空间索引结构松散QR-树：LQR-tree。针对已有的QR-树索引结构在节点分配中,可能存在较小的对象落入较大的节点中的问题,将松散四叉树和R-树相结合,能够实现节点下移,优化处理移动空间对象的查询,给出LQR-tree的结构和插入删除算法,并提出对应算法的相关定理和证明。