多盘广播的偏斜索引算法

在移动环境中,多盘广播是被广泛使用的数据广播调度算法之一。为广播数据建立索引可以使移动客户机选择性地监听信道,以减少电源消耗,但过多地插入索引会增加数据访问时间。针对该问题,为多盘广播建立偏斜索引,设计索引树构造算法和广播数据的索引树算法。与可变扇出算法相比,多盘广播的偏斜索引算法需要的平均访问时间和平均调谐时间较短。     

移动环境下多信道广播的有效数据访问

在移动计算环境中,数据广播是数据发布和数据获取得的重要手段.为提高数据广播的性能,在服务器端采用了近似最优的多信道广播数据调度策略(TOSA),同时在移动客户端提出了高效的Huffman树索引策略.从服务器端和客户端同时提高数据广播性能.最后通过仿真试验以及推理,在访问时间、谐调时间等方面证明了该模式的高效性.     

空间数据的混合树索引结构与访问引擎的研究

通过对空间数据库系统关键技术的研究,改进了空间数据索引结构,设计实现了基于2K叉树与R-树的混合树索引结构,提高了空间数据的访问效率,并通过实验验证了该结构的正确性与有效性;同时,在混合树空间索引结构的基础上,设计实现了一个符合OpenGIS规范的空间数据库访问引擎,它能有效地支持空间数据的存储与管理,并为数据共享和系统互操作打下了基础.该数据访问引擎在应用实践中也取得了较好的效果.     

改进的移动对象索引机制

针对R树结构在索引移动对象时存在的内部节点重叠问题,结合四叉树结构,提出一种R+树与四叉树(Quad树)混合的改进索引结构,采用懒惰更新算法以及扩充与收缩MBR方法,可同时索引移动对象历史及当前位置信息。仿真实验结果表明,该索引结构在查询数量较大时能够获得较高的查询效率。     

移动环境中基于Huffman索引树的广播数据组织

移动计算环境中无线网络通信的非对称性和伸缩性要求 ,使得数据广播成为移动环境中数据发布和获取的重要手段 .为使移动客户有效地从广播中获取数据 ,该文提出了一种基于 Huffm an树的索引模型 ,给出 Huffman索引树的构造方法和基于 Huffman索引树的广播数据组织方式 .同时 ,该文还对比 B 树 ,对基于 Huffman索引树的数据组织方式从空间开销、调谐时间、存取时间等方面进行了性能分析与比较 ,表明该广播组织方式能提高移动数据广播的性能     

移动对象索引方法研究

传统空间索引结构因无法适应大量的更新操作而不能应用于移动对象的存储和检索。本文介绍了三种主要移动时象索引方法的基本思想，即R树及其变形树、四叉树及其变形树以及网格文件及其变形算法，并进行了分析时比，在此基础上提出了混合索引结构，比已知的索引结构效率更高。     

支持频繁更新的移动对象混合索引方法

TPR-tree是目前广泛使用的移动对象当前及未来位置索引技术,但是其频繁更新性能低下.通过在TPR-tree上增加一个指向索引树中间节点的直接访问表（direct-access table）内存结构和建于叶节点之上的Hash辅助索引结构,提出了一种支持频繁更新的移动对象混合索引HTPR-tree,并提出了基于HTPR-tree的扩展自底向上（EBUU）更新算法.性能分析和实验表明,采用EBUU算法的HTPRtree动态更新性能大大高于TPR^＊-tree等索引,而查询性能仅仅稍逊.     

基于数据访问概率的广播索引技术

在移动计算中,如何节约移动设备的电源是一个重要的研究方向。采用索引广播的方式可以使移动设备选择性地监听信道,从而减少了电源的消耗。该文提出了为广播数据建立基于访问概率的索引技术,并分固定扇出的非平衡索引树和可变扇出的索引树两种情况讨论如何降低平均访问代价。针对这两种情况,分别设计了构造索引树的算法。     

基于速度分布的移动对象混合索引方法

TPR*树是目前广泛使用的移动对象当前及未来位置预测索引技术,但是其频繁更新及查询性能随着时间变化而急遽下降.文中提出了一种基于速度分布的移动对象混合索引HVTPR树,综合考虑移动对象在速度域和空间域中的分布,首先在速度域中对移动对象集进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶,每个速度桶中移动对象具有相近的速度矢量;对每个速度桶中的移动对象,则利用TPR树进行索引.HVTPR树索引增加了一个建于移动对象标识上的Hash辅助索引结构,并采用增强的自底向上更新(EBUU)算法以提高其频繁更新性能,具有很好的动态更新性能和并发性.实验表明,采用EBUU算法的HVTPR树索引动态更新及查询性能优于TPR*树等通用索引技术.     

一种基于受限网络的移动对象索引结构

为了提高受限网络中移动对象索引效率和满足近邻查询需求,基于FNR-Tree索引结构和Geohash编码算法,提出一种能够满足近邻查询的移动对象索引结构RNR(restricted network R-Tree).通过添加哈希表、链表等辅助索引结构来提升索引结构操作效率,融合Geohash编码和相关算法来使得索引结构能高效满足近邻查询的需求.通过将指定区域按一定规则划分,可使得索引结构具备在不规则范围查询的能力.使用旧金山市地理数据和移动对象数据对索引结构性能进行了测试,结果表明RNR具有较高索引结构操作效率,并且能够高效地提供窗口查询和近邻查询的功能.     

一种支持历史航迹和预查询的动目标索引方法

随着目标检测技术和传感器网络技术的发展,高效的目标信息索引方法可以提高系统性能和稳定性.因此,提出了一种动目标索引方法SSTR-tree,能将历史索引和预测索引结合,实现全时态查询,具有较高的更新、查询效率;通过设置有效时间段索引,对无效时间段内信息只记录目标突变信息,提高了动目标航迹管理的效率.通过实验证明,与传统的哈希存储和3 DR-tree索引方法相比较,SSTR-tree动目标索引方法更新和查询效率更优.     

多核处理器中支持频繁访问的B+-Tree

针对传统B+-Tree自顶向下访问模式的缺点,提出了支持频繁访问的FAB+-Tree（Frequent Access B+-Tree）。在B+-Tree的基础上增加了Hash辅助索引,使得访问B+-Tree时直接定位到叶结点,并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器,提出了基于流水线的FAB+-Tree多线程访问模块,并优化了该模块的共享Cache访问性能。在实验中,基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块,实验结果表明B+-Tree的访问性能得到显著提高。     

An indexing scheme for energy-efficient processing of content-based retrieval queries on a wireless data stream

Wireless data broadcasting is a popular data delivery approach in mobile computing environments, where the broadcasting servers usually adopt indexing schemes for mobile clients to energy-efficiently access data on a wireless broadcast stream. However, conventional indexing schemes use primary key attribute values to construct tree structures. Therefore, these schemes do not support content-based retrieval queries such as partial-match queries and range-queries. This paper proposes an indexing method that supports content-based retrieval queries on a wireless data stream. The method uses a tree-structured index, called B2V-Tree, which is composed of bit-vectors that are generated from data records through multi-attribute hashing. Through analysis and experiments, the effectiveness of the proposed method is shown.     

一种新型索引结构

传统Hash算法中溢出桶与主桶、溢出桶与溢出桶之间一般通过指针实现链接,对海量数据的等值查询采用指针方式效率很低。该文提出一种动态哈希索引算法,用B+树结构表示桶地址表,在桶地址表与记录键值之间建立一个B+树结构,通过二分查找可直接找到相应桶元素。实验结果表明,该算法的综合性能优于其他索引,其等值查询效率提高了15%。     

An energy-efficient and access latency optimized indexing scheme for wireless data broadcast

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.     

A Hybrid Index Technique for Power Efficient Data Broadcast

The intention of power conservative indexing techniques for wireless data broadcast is to reduce mobile client tune-in time while maintaining an acceptable data access time. In this paper, we investigate indexing techniques based on index trees and signatures for data disseminated on a broadcast channel. Moreover, a hybrid indexing method combining strengths of the signature and the index tree techniques is proposed. Different from previous studies, our research takes into consideration of two important data organization factors, namely, clustering and scheduling. Cost models for the three indexing methods are derived for various data organization accommodating these two factors. Based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conservative indexing of various data organization on wireless broadcast channels.     

Efficient query execution on broadcasted index tree structures

The continuous broadcast of data together with an index structure is an effective way of disseminating data in a wireless mobile environment. The index allows a mobile client to tune in only when relevant data is available on the channel and leads to reduced power consumption for the clients. This paper investigates the execution of queries on broadcasted index trees when query execution corresponds to a partial traversal of the tree. Queries exhibiting this behavior include range queries and nearest neighbor queries. We present two broadcast schedules for index trees and two query algorithms executed by mobile clients. Our solutions simultaneously minimize tuning time and latency and adapt to the client’s available memory. Experimental results using real and synthetic data compare results for a broadcast with node repetition to one without node repetition and they show how a priority-based data management can help reduce tuning time and latency.     

Energy- and Latency-Efficient Processing of Full-Text Searches on a Wireless Broadcast Stream

In wireless mobile computing environments, broadcasting is an effective and scalable technique to disseminate information to a massive number of clients, wherein the energy usage and latency are considered major concerns. This paper presents an indexing scheme for the energy- and latency-efficient processing of full-text searches over the wireless broadcast data stream. Although a lot of access methods and index structures have been proposed in the past for full-text searches, all of them are targeted for data in disk storage, not wireless broadcast channels. For full-text searches on a wireless broadcast stream, we firstly introduce a naive, inverted list-style indexing method, where inverted lists are placed in front of the data on the wireless channel. In order to reduce the latency overhead, we propose a two-level indexing method which adds another level of index structure to the basic inverted list-style index. In addition, we propose a replication strategy of the index list and index tree to further improve the latency performance. We analyze the performance of the proposed indexing scheme with respect to the latency and energy usage measures, and show the optimality of index replication. The correctness of the analysis is demonstrated through simulation experiments, and the effectiveness of the proposed scheme is shown by implementing a real wireless information delivery system.     

Evaluation and comparison of various indexing schemes in single-channel broadcast communication environment

Wireless Data Broadcasting is a newly developed data dissemination method for spreading public information to a tremendous number of mobile subscribers. Access Latency and Tuning Time are two main criteria to evaluate the performance of such system. With the help of indexing technology, clients can reduce tuning time significantly by searching indices first and turning to doze mode during waiting period. Different indexing schemes perform differently, so we can hardly compare the efficiency of different indexing schemes. In this paper, we redesigned several most popular indexing schemes for data broadcasting systems, i.e., distributed index, exponential index, hash table, and Huffman tree index. We created a unified communication model and constructed a novel evaluation strategy by using the probability theory to formulate the performance of each scheme theoretically and then conducted simulations to compare their performance by numerical experiments. This is the first work to provide scalable communication environment and accurate evaluation strategies. Our communication model can easily be modified to meet specific requirements. Our comparison model can be used by the service providers to evaluate other indexing schemes to choose the best one for their systems.